coinselection: Optimize BnB exploration #32150

murchandamus · 2025-03-27T02:33:51Z

This PR rewrites the implementation of the BnB coinselection algorithm
to skip the duplicate evaluation of previously visited input selections.

In the original implementation of BnB, the state of the search is
backtracked by explicitly walking back to the omission branch and then
testing again. This retests an equivalent candidate set as before, e.g.,
after backtracking from {ABC}, it would evaluate {AB_}, before trying
{AB_D}, but {AB_} is equivalent to {AB} which was tested before.

CoinGrinder tracks the state of the search instead by remembering which
UTXO was last added and explicitly shifting from that UTXO directly to
the next, so after {ABC}, it will immediately move on to {AB_D}. We
replicate this approach here.

As fewer nodes are visited, this approach will enumerate more possible
combinations than the original implementation given the same limit for
iterations.

DrahtBot · 2025-03-27T02:33:54Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32150.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	yancyribbens
Stale ACK	achow101

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

No conflicts as of last run.

LLM Linter (✨ experimental)

Possible typos and grammar issues:

"als well as" -> "as well as" [typo in “as well as”]
"matches the the effective value" -> "matches the effective value" [duplicate “the”]

^{drahtbot_id_4_m}

yancyribbens · 2025-03-27T16:05:49Z

Concept ACK

yancyribbens · 2025-03-27T16:12:30Z

I ran benchmarking on master and benchmarking on this branch since it's fairly large change.

master:

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|       43,633,696.00 |               22.92 |    0.1% |      0.48 | `CoinSelection`

e2a4d86:


|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|       40,433,894.00 |               24.73 |    0.1% |      0.44 | `CoinSelection`

looks like a marginal improvement in bechmarked performance.

murchandamus · 2025-04-01T00:05:57Z

Rebased on #29532

yancyribbens · 2025-04-01T19:12:26Z

src/wallet/test/coinselection_tests.cpp

-    TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/5 * CENT, /*expected_input_amounts=*/{5 * CENT}, /*expected_attempts=*/2);
-    TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/6);
-    TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/9 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT, 5 * CENT}, /*expected_attempts=*/6);
+    TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/3);


Nice, it looks like the backtrack iterations are no longer recorded which effectively makes this probably more of an optimization than a refactor. Now it's possible more solutions can be found since the number of times the loop will run is effectively more improving search resolution. May be worth adding a note of that to the commit message.

Thanks, I renamed the PR and added more explanation to the opening comment.

murchandamus · 2025-04-02T16:14:13Z

I ran benchmarking on master and benchmarking on this branch since it's fairly large change.

If I remember right the Coin Selection benchmark is rather non-representative. I have a todo to update it somewhere in my backlog.

yancyribbens · 2025-04-03T16:04:18Z

If I remember right the Coin Selection benchmark is rather non-representative. I have a todo to update it somewhere in my backlog.

Good point. I took a quick look, and the current benchmark runs BnB for only 4 iterations. there are 1,000 clones and one non clone so most of the work is done by skipping clones which isn't very representative as you say.

Instead of keeping this in your backlog, shouldn't there be an issue opened so it doesn't get overlooked? Maybe someone else has the bandwidth to pick it up. Possibly I could but I also have a large backlog of I'd like to work on.

Also, I note there is also BnBExhaustion(benchmark::Bench& bench) which is probably more "representative" although it also looks like you have a TODO to re-write that as well:

Worth noting that src/bench/coin_selection.cpp makes a copy of the make_hard_case function (commenting as such), so removal here may lead to confusion unless that benchmark is also updated.

murchandamus · 2025-05-08T21:57:54Z

The preceding PR #29532 got merged, so this is now ready for review.

src/wallet/test/coinselector_tests.cpp

achow101

I think the last 2 commits "opt: Skip evaluation of equivalent input sets" and "opt: Skip evaluation of equivalent input sets" could be combined. The change the last commit makes is to the comment introduced in the commit before it, and removing a line introduced in the commit before it. We generally don't want to add code just to immediately remove it, so I think these can be squashed together.

src/wallet/coinselection.cpp

achow101 · 2025-06-11T20:03:42Z

src/wallet/coinselection.cpp

-    result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
-    assert(best_waste == result.GetWaste());


In 9580c0e "coinselection: rewrite BnB in CoinGrinder-style"

Why is the waste calculation being dropped? result will be returned with an incorrect waste value.

The waste calculation here is semantically incorrect and it is unnecessary, because the waste of all coin selection results is recalculated after they are collected, before they are compared to correctly assess bump fees.

I don’t think we want to pull the bump fee calculation into each coin selection algorithm, but maybe we can pass the entire coin selection parameters object, so that we can calculate a semantically correct waste score for coin selection results, although it may still need to be amended for bump fees afterwards.

Let’s fix this in a follow-up properly. And also add some tests for the waste results of coin selection algorithms.

src/wallet/coinselection.cpp

murchandamus

I think I addressed everything, except the issue for the follow-up.

src/wallet/test/coinselector_tests.cpp

src/wallet/coinselection.cpp

murchandamus · 2025-06-12T00:35:18Z

src/wallet/coinselection.cpp

-    result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
-    assert(best_waste == result.GetWaste());


The waste calculation here is semantically incorrect and it is unnecessary, because the waste of all coin selection results is recalculated after they are collected, before they are compared to correctly assess bump fees.

I don’t think we want to pull the bump fee calculation into each coin selection algorithm, but maybe we can pass the entire coin selection parameters object, so that we can calculate a semantically correct waste score for coin selection results, although it may still need to be amended for bump fees afterwards.

Let’s fix this in a follow-up properly. And also add some tests for the waste results of coin selection algorithms.

murchandamus · 2025-06-12T19:12:54Z

Ready for Review

murchandamus · 2025-06-14T02:58:14Z

Sorry, I forgot to reply to this comment:

I think the last 2 commits "opt: Skip evaluation of equivalent input sets" and "opt: Skip evaluation of equivalent input sets" could be combined. The change the last commit makes is to the comment introduced in the commit before it, and removing a line introduced in the commit before it. We generally don't want to add code just to immediately remove it, so I think these can be squashed together.

I think of the last two commits as two separate optimizations. The idea that you only have to explore all combinations with the first of several clones in itself can use explaining. The separate step to present the realization that we can skip any UTXO that ties the predecessor on effective value due to the way the UTXO sorting is tie-broken by minimal waste seemed easier to review. The second commit also adds six more lines of documentation and shows per the test that the iteration count is further reduced. I prefer to keep them as two commits.

achow101 · 2025-06-14T02:59:56Z

ACK cf36d1a

The expected iteration count demonstrates how the following improvements reduce iterations will help catch any regressions in the future.

murchandamus · 2025-08-05T00:09:09Z

Fixed the merge conflict with #33060.

DrahtBot · 2025-08-05T01:01:03Z

🚧 At least one of the CI tasks failed.
_{Task multiprocess, i686, DEBUG: https://github.com/bitcoin/bitcoin/runs/47377999369}
_{LLM reason (✨ experimental): The CI failure is caused by the failure of the "coinselection_tests" test.}

Hints

Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

In the original implementation of BnB, the state of the search is backtracked by explicitly walking back to the omission branch and then testing again. This retests an equivalent candidate set as before, e.g., after backtracking from {ABC}, it would evaluate {AB_}, before trying {AB_D}, but {AB_} is equivalent to {AB} which was tested before. CoinGrinder tracks the state of the search instead by remembering which UTXO was last added and explicitly shifting from that UTXO directly to the next, so after {ABC}, it will immediately move on to {AB_D}. We replicate this approach here. The description of the two optimizations is removed from the documentation as they will only be implented in a later commit.

BnB may not be able to exhaustively search all potentially interesting combinations for large UTXO pools, so we keep track of whether the search was terminated by the iteration limit.

At high feerates adding more inputs will increase the waste score. If the current waste is already higher than the best selection’s we cannot improve upon the best selection. All solutions that include the current selection with more additional inputs must be worse than the best selection so far: SHIFT This optimization only works at high feerates, because at low feerates, adding more inputs decreases waste, so this condition would exit prematurely. We would never attempt input sets with higher weight than the prior best selection, even though we would prefer those at low feerates.

Introduces a dedicated data structure to track the total effective_value available in the remaining UTXOs at each index of the UTXO pool. In contrast to the original approach in BnB, this allows us to immediately jump to a lower index instead of visiting every UTXO to add back their eff_value to the lookahead.

When two successive UTXOs match in effective value and weight, we can skip the second if the prior is not selected: adding it would create an equivalent input set to a previously evaluated. E.g. if we have three UTXOs with effective values {5, 3, 3} of the same weight each, we want to evaluate {5, _, _}, {5, 3, _}, {5, 3, 3}, {_, 3, _}, {_, 3, 3}, but skip {5, _, 3}, and {_, _, 3}, because the first 3 is not selected, and we therefore do not need to evaluate the second 3 at the same position in the input set. If we reach the end of the branch, we must SHIFT the previously selected UTXO group instead.

When two successive UTXOs differ in waste but match in effective value, we can skip the second if the first is not selected, because all input sets we can generate by swapping out a less wasteful UTXOs with a more wastefull UTXO of matching effective value would be strictly worse. Also expand documentation of Branch and Bound.

yancyribbens · 2025-08-10T21:12:48Z

src/wallet/coinselection.cpp

+    size_t curr_try = 0;
+    SelectionResult result(selection_target, SelectionAlgorithm::BNB);
+    bool is_done = false;
+    bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;


nit this ought to be is_fee_high? also this could just be a function on utxo utxo_pool.at(0).is_fee_high() alternatively .is_fee_expensive()

yancyribbens · 2025-08-10T22:04:20Z

src/wallet/coinselection.cpp

+                if (next_utxo >= utxo_pool.size() - 1) {
+                    // Reached end of UTXO pool skipping clones: SHIFT instead
+                    should_shift = true;
+                    break;


hmm could this be is_done = true; instead of break? In general I think it would be better to replace all is_done = true; with break and then change the loop condition to while curr_try < TOTAL_TRIES. That way, the entire condition which checks that the curr_try > TOTAL_TRIES can be removed. In short, the combination of the usage of break with is_done could be simplified by always using break and then change the loop invariant to while .. < TOTAL_TRIES.

Ah I see, this breaks the inner while loop. Disregard my previous comment.

yancyribbens · 2025-08-10T22:11:17Z

I reviewed this and so far it looks good. I plan to give it one more pass over shortly to finish review.

yancyribbens · 2025-08-12T20:33:51Z

src/wallet/coinselection.cpp

+ *    exploration would cause redundant work: e.g., given the UTXOs A, A', and B, where A and A' are
+ *    clones, naive exploration would combine (read underscore to as omission):
+ *    [{}, {A}, {A, A'}, {A, A', B}, {A, _, B}, {_, A'}, {_, A', B}, {_, _, B}].
+ *    In this case the input set candidates {A} and {A'} als well as {A, B} and {A', B} are


in cdc25b4 s/als/as

yancyribbens · 2025-08-12T20:37:06Z

src/wallet/coinselection.cpp

+            // Adding more UTXOs only increases fees and cannot be better: SHIFT
+            should_shift  = true;
+            // The amount exceeding the selection_target (the "excess"), would be dropped to the fees: it is waste.
+            CAmount curr_excess = curr_amount - selection_target;


in 7596e49. Now that the set is sorted by waste as tie breaker, if the curr_excess is zero, there will be no future solution with a better waste score. Therefore adding a condition testing for zero would stop the search sooner.

yancyribbens · 2025-08-12T20:40:32Z

src/wallet/coinselection.cpp

+    while (true) {
+        bool should_shift{false}, should_cut{false};
+        // Select `next_utxo`
+        OutputGroup& utxo = utxo_pool[next_utxo];


in 7596e49 is there a mechanism up the stack that prevents this from being a utxo_pool length of zero? I notice in coin-grinder also that a utxo_pool of no length here would cause an exception.

yancyribbens · 2025-08-12T20:41:59Z

src/wallet/coinselection.cpp

+            // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e.
+            // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs)
+            deselect_last();
+            should_shift  = true;


in 7596e49

nit: extra space here before the =. Same issue on L156

yancyribbens · 2025-08-12T20:44:09Z

src/wallet/coinselection.cpp

@@ -55,11 +55,11 @@ struct {
 * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
 * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
 * are sorted by their effective values and the tree is explored deterministically per the inclusion
- * branch first. At each node, the algorithm checks whether the selection is within the target range.
+ * branch first. For each new input set candidate, the algorithm checks whether the selection is within the target range.


in 7596e49

nit: line length here and in L62 breaks from the rest of the paragraph.

yancyribbens · 2025-08-12T20:47:13Z

src/wallet/coinselection.cpp

 * At that point, the last included UTXO is deselected and the corresponding omission branch explored
- * instead. The search ends after the complete tree has been searched or after a limited number of tries.
+ * instead starting by adding the subsequent UTXO. The search ends after the complete tree has been searched or after a limited number of tries.
 *
 * The search continues to search for better solutions after one solution has been found. The best


nit: this is not part of the diff, but consider rewording this sentence to "The search continues for better solutions.." so that search isn't used twice redundantly in the same sentence.

yancyribbens · 2025-08-12T20:56:13Z

ACK cdc25b4

I also tested the updates on secondary group of tests I wrote and there where no unexpected failures.

I still have mild preference to using a loop condition of while tries < TOTAL_TRIES instead of while !is_done, and then break when done.

As for variable naming on cosmetic note, I made a note of some alternate suggestions where I feel like it's shorter and/or more concise. (just a suggestion):

curr_amount -> selected_amount
curr_selection_waste -> selection_waste
curr_weight -> selection_weight
next_utxo -> next_utxo_index
is_done -> search_complete
should_shift -> shift
should_cut -> cut

brunoerg · 2025-08-21T17:26:18Z

src/wallet/coinselection.cpp

+            should_shift  = true;
+            // The amount exceeding the selection_target (the "excess"), would be dropped to the fees: it is waste.
+            CAmount curr_excess = curr_amount - selection_target;
+            CAmount curr_waste = curr_selection_waste + curr_excess;


In 7596e49: FYI my mutation testing bot reported the following mutant as not killed:

@@ -201,7 +201,7 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool should_shift = true; // The amount exceeding the selection_target (the "excess"), would be dropped to the fees: it is waste. CAmount curr_excess = curr_amount - selection_target; - CAmount curr_waste = curr_selection_waste + curr_excess; + CAmount curr_waste = curr_selection_waste - curr_excess; if (curr_waste <= best_waste) { // New best solution

DrahtBot added the Refactoring label Mar 27, 2025

murchandamus mentioned this pull request Mar 27, 2025

BnB untested/unused condition in UTXO exclusion optimization #32047

Open

murchandamus marked this pull request as draft March 27, 2025 02:34

murchandamus force-pushed the 2025-03-rewrite-BnB branch from c70f1d3 to 613df18 Compare March 27, 2025 13:35

DrahtBot mentioned this pull request Mar 27, 2025

Refactor BnB tests #29532

Merged

murchandamus force-pushed the 2025-03-rewrite-BnB branch from 613df18 to 5ac0d02 Compare April 1, 2025 00:04

murchandamus force-pushed the 2025-03-rewrite-BnB branch from 5ac0d02 to 44bab80 Compare April 1, 2025 00:08

yancyribbens reviewed Apr 1, 2025

View reviewed changes

murchandamus changed the title ~~refactor: Optimize BnB exploration~~ coinselection: Optimize BnB exploration Apr 1, 2025

DrahtBot added CI failed and removed CI failed labels Apr 29, 2025

murchandamus force-pushed the 2025-03-rewrite-BnB branch 2 times, most recently from 9cfab3b to 155d6d9 Compare May 3, 2025 01:43

murchandamus marked this pull request as ready for review May 6, 2025 23:35

murchandamus force-pushed the 2025-03-rewrite-BnB branch from 155d6d9 to 4475517 Compare May 8, 2025 21:57

achow101 reviewed Jun 11, 2025

View reviewed changes

src/wallet/test/coinselector_tests.cpp Outdated Show resolved Hide resolved

achow101 reviewed Jun 11, 2025

View reviewed changes

murchandamus commented Jun 12, 2025

View reviewed changes

murchandamus force-pushed the 2025-03-rewrite-BnB branch 2 times, most recently from 51ae802 to cf36d1a Compare June 12, 2025 18:35

yancyribbens mentioned this pull request Jul 11, 2025

FUZZ: Test that BnB finds best solution #32894

Open

DrahtBot mentioned this pull request Jul 25, 2025

test: Slay BnB Mutants #33060

Merged

DrahtBot added the Needs rebase label Aug 4, 2025

coinselection: Track BnB iteration count in result

38e1490

The expected iteration count demonstrates how the following improvements reduce iterations will help catch any regressions in the future.

murchandamus force-pushed the 2025-03-rewrite-BnB branch from cf36d1a to 792ed0d Compare August 5, 2025 00:07

DrahtBot added CI failed and removed Needs rebase labels Aug 5, 2025

murchandamus added 6 commits August 4, 2025 18:39

coinselection: Track whether BnB completed

ab8aa02

BnB may not be able to exhaustively search all potentially interesting combinations for large UTXO pools, so we keep track of whether the search was terminated by the iteration limit.

murchandamus force-pushed the 2025-03-rewrite-BnB branch from 792ed0d to cdc25b4 Compare August 5, 2025 01:44

DrahtBot removed the CI failed label Aug 5, 2025

murchandamus mentioned this pull request Aug 6, 2025

Slow unit tests delay functional tests and leave CPU unused #32770

Open

yancyribbens reviewed Aug 10, 2025

View reviewed changes

yancyribbens reviewed Aug 12, 2025

View reviewed changes

DrahtBot requested a review from achow101 August 12, 2025 20:56

brunoerg reviewed Aug 21, 2025

View reviewed changes

		result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
		assert(best_waste == result.GetWaste());

coinselection: Optimize BnB exploration #32150

Are you sure you want to change the base?

coinselection: Optimize BnB exploration #32150

Uh oh!

Conversation

murchandamus commented Mar 27, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Mar 27, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage & Benchmarks

Reviews

Conflicts

LLM Linter (✨ experimental)

Uh oh!

yancyribbens commented Mar 27, 2025

Uh oh!

yancyribbens commented Mar 27, 2025

Uh oh!

murchandamus commented Apr 1, 2025

Uh oh!

yancyribbens Apr 1, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

murchandamus commented Apr 2, 2025

Uh oh!

yancyribbens commented Apr 3, 2025

Uh oh!

murchandamus commented May 8, 2025

Uh oh!

Uh oh!

achow101 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

murchandamus commented Jun 12, 2025

Uh oh!

murchandamus commented Jun 14, 2025

Uh oh!

achow101 commented Jun 14, 2025

Uh oh!

murchandamus commented Aug 5, 2025

Uh oh!

DrahtBot commented Aug 5, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

yancyribbens commented Aug 10, 2025

Uh oh!

murchandamus commented Mar 27, 2025 •

edited

Loading

DrahtBot commented Mar 27, 2025 •

edited

Loading

yancyribbens Apr 1, 2025 •

edited

Loading

yancyribbens commented Aug 12, 2025 •

edited

Loading