coinselection: Optimize BnB exploration

murchandamus commented at 2:33 am on March 27, 2025: contributor

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 commented at 2:33 am on March 27, 2025: contributor

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	achow101
Concept ACK	yancyribbens

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 “als”]
“matches the the effective value” → “matches the effective value” [duplicated “the”]
“solution is chosen by minimal waste score” → “The solution is chosen by minimal waste score” [missing article “The”]

drahtbot_id_4_m

DrahtBot added the label Refactoring on Mar 27, 2025

murchandamus marked this as a draft on Mar 27, 2025

murchandamus force-pushed on Mar 27, 2025

yancyribbens commented at 4:05 pm on March 27, 2025: contributor

Concept ACK

yancyribbens commented at 4:12 pm on March 27, 2025: contributor

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

master:

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

https://github.com/bitcoin/bitcoin/pull/32150/commits/e2a4d86131e8f1661eb450c50b8072147965b111:

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

looks like a marginal improvement in bechmarked performance.

murchandamus force-pushed on Apr 1, 2025

murchandamus commented at 0:05 am on April 1, 2025: contributor

Rebased on #29532

murchandamus force-pushed on Apr 1, 2025

in src/wallet/test/coinselection_tests.cpp:133 in d765ba9ae5 outdated

129@@ -130,14 +130,14 @@ BOOST_AUTO_TEST_CASE(bnb_test)
130     AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT});
131 
132     // Simple success cases
133-    TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/6);
134-    TestBnBSuccess("Select middle UTXO", utxo_pool, /*selection_target=*/3 * CENT, /*expected_input_amounts=*/{3 * CENT}, /*expected_attempts=*/4);
135-    TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/5 * CENT, /*expected_input_amounts=*/{5 * CENT}, /*expected_attempts=*/2);
136-    TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/6);
137-    TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/9 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT, 5 * CENT}, /*expected_attempts=*/6);
138+    TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/3);

yancyribbens commented at 7:12 pm on April 1, 2025:

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.

murchandamus commented at 9:35 pm on April 1, 2025:

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

murchandamus renamed this:
~~refactor: Optimize BnB exploration~~
coinselection: Optimize BnB exploration
on Apr 1, 2025

murchandamus commented at 4:14 pm on April 2, 2025: contributor

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 commented at 4:04 pm on April 3, 2025: contributor

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.

DrahtBot added the label CI failed on Apr 29, 2025

DrahtBot removed the label CI failed on May 2, 2025

murchandamus force-pushed on May 2, 2025

murchandamus force-pushed on May 3, 2025

murchandamus marked this as ready for review on May 6, 2025

murchandamus force-pushed on May 8, 2025

murchandamus commented at 9:57 pm on May 8, 2025: contributor

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

in src/wallet/test/coinselector_tests.cpp:214 in df20dd4f90 outdated

210@@ -210,6 +211,9 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
211         const auto result9 = SelectCoinsBnB(GroupCoins(available_coins.All()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change);
212         BOOST_CHECK(result9);
213         BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT);
214+        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.

achow101 commented at 6:48 pm on June 11, 2025:

In df20dd4f905a0d04e48bfe20919cccaff11b9b30 “coinselection: Track BnB iteration count in result”

This kind of comment belongs in the commit message, not the code.

murchandamus commented at 9:06 pm on June 11, 2025:

Thanks, I removed the repeated comment and added an explanation to the commit message instead.

in src/wallet/coinselection.cpp:118 in 9580c0e490 outdated

127     std::vector<size_t> best_selection;
128+
129+    // The currently selected effective amount
130+    CAmount curr_amount = 0;
131+
132+    // The waste score of the current section, and the best waste score so far

achow101 commented at 6:52 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

s/section/selection

in src/wallet/coinselection.cpp:187 in 9580c0e490 outdated

251-                curr_selection_weight += utxo.m_weight;
252+        if (should_cut) {
253+            // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can
254+            // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e.
255+            // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs)
256+            should_cut = false;

achow101 commented at 7:54 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

should_cut is not used after this, there is no need to reset it.

murchandamus commented at 9:43 pm on June 11, 2025:

Removed

in src/wallet/coinselection.cpp:241 in 9580c0e490 outdated

264+                // Exhausted search space before running into attempt limit
265+                break;
266             }
267+            next_utxo = curr_selection.back() + 1;
268+            deselect_last();
269+            should_shift  = false;

achow101 commented at 7:54 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

should_shift is not used after this, there is no need to reset it.

murchandamus commented at 9:43 pm on June 11, 2025:

Removed

in src/wallet/coinselection.cpp:193 in 9580c0e490 outdated

257+            deselect_last();
258+            should_shift  = true;
259+        }
260+
261+        if (should_shift) {
262+            // Set `next_utxo` to one after last selected, then deselect last selected UTXO

achow101 commented at 7:58 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

This comment should be after the if

in src/wallet/coinselection.cpp:198 in 9580c0e490 outdated

281-    // Set output set
282     for (const size_t& i : best_selection) {
283         result.AddInput(utxo_pool.at(i));
284     }
285-    result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
286-    assert(best_waste == result.GetWaste());

achow101 commented at 8:03 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

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

murchandamus commented at 0:35 am on June 12, 2025:

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.

in src/wallet/coinselection.cpp:191 in 813ac54726 outdated

157@@ -157,6 +158,9 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
158         } else if (curr_amount > selection_target + cost_of_change) {
159             // Overshot target range: SHIFT
160             should_shift = true;
161+        } else if (is_feerate_high && curr_selection_waste > best_waste) {

achow101 commented at 8:06 pm on June 11, 2025:

In 813ac54726866b1051c502fe8bfef3b279af890f “coinselection: BnB skip exploring high waste”

Why does this optimization only work at high feerates?

murchandamus commented at 11:38 pm on June 11, 2025:

At high feerates adding more inputs will increase the waste score. If the current waste is already worse than the best selection’s while we have insufficient funds, we cannot beat the best selection by adding more inputs: SHIFT

At low feerates, adding more inputs decreases waste, so we would exit prematurely.

in src/wallet/coinselection.cpp:103 in 6ff6e98000 outdated

103-    for (const OutputGroup& utxo : utxo_pool) {
104-        // Assert UTXOs with non-positive effective value have been filtered
105-        Assume(utxo.GetSelectionAmount() > 0);
106-        total_available += utxo.GetSelectionAmount();
107+    for (size_t i = 0; i < utxo_pool.size(); ++i) {
108+        size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order

achow101 commented at 8:10 pm on June 11, 2025:

In 6ff6e98000792f715324c513fd9eb83440929d0e “coinselection: Track effective_value lookahead”

Do the reversing in the for

0    for (size_t i = utxo_pool.size() - 1; i >= 0; --i) {

murchandamus commented at 11:55 pm on June 11, 2025:

Taken with minor adjustments.

in src/wallet/coinselection.cpp:71 in 9580c0e490 outdated

67@@ -68,9 +68,9 @@ struct {
68  *
69  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
70  *
71- * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
72+ * The algorithm uses two additional optimizations. A lookahead (tk) keeps track of the total value of

achow101 commented at 8:13 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

What is (tk) mean?

murchandamus commented at 9:20 pm on June 11, 2025:

“tk” is a symbol for “to come” in drafting articles. My idea was to express that these two optimizations are not in this first commit, but will be implemented in the coming PRs. On second thought, I removed these sentences and will reintroduce with the commits that introduce the described optimizations.

in src/wallet/coinselection.cpp:73 in 9580c0e490 outdated

67@@ -68,9 +68,9 @@ struct {
68  *
69  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
70  *
71- * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
72+ * The algorithm uses two additional optimizations. A lookahead (tk) keeps track of the total value of
73  * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
74- * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
75+ * cannot be reached. Further, it is unnecessary to test equivalent combinations (tk). This allows us

achow101 commented at 8:13 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

What is (tk) mean?

murchandamus commented at 9:40 pm on June 11, 2025:

Responded above.

in src/wallet/coinselection.cpp:71 in 6ff6e98000 outdated

67@@ -68,7 +68,7 @@ struct {
68  *
69  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
70  *
71- * The algorithm uses two additional optimizations. A lookahead (tk) keeps track of the total value of

achow101 commented at 8:14 pm on June 11, 2025:

In 6ff6e98000792f715324c513fd9eb83440929d0e “coinselection: Track effective_value lookahead”

This should be squashed into 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

in src/wallet/coinselection.cpp:73 in ee103e5df9 outdated

69@@ -70,7 +70,7 @@ struct {
70  *
71  * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
72  * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
73- * cannot be reached. Further, it is unnecessary to test equivalent combinations (tk). This allows us

achow101 commented at 8:14 pm on June 11, 2025:

In 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

This should be squashed into 9580c0e49030f13fe57603521b59b96e6e50cf82 “coinselection: rewrite BnB in CoinGrinder-style”

achow101 commented at 8:22 pm on June 11, 2025: member

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.

coinselection: Track BnB iteration count in result

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

60cb6a078d

coinselection: rewrite BnB in CoinGrinder-style

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.

4be47e58bd

coinselection: Track whether BnB completed

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.

d704d97ed2

coinselection: BnB skip exploring high waste

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.

fb1fa954f6

coinselection: Track effective_value lookahead

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.

de8bcb043d

opt: Skip evaluation of equivalent input sets

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.

602bc16506

murchandamus commented at 0:36 am on June 12, 2025: contributor

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

murchandamus force-pushed on Jun 12, 2025

opt: Skip UTXOs with worse waste, same eff_value

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.

cf36d1af18

murchandamus force-pushed on Jun 12, 2025

murchandamus commented at 7:12 pm on June 12, 2025: contributor

Ready for Review

murchandamus commented at 2:58 am on June 14, 2025: contributor

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 commented at 2:59 am on June 14, 2025: member

ACK cf36d1af18f1fdb2f9846634032f468d00d7ddfb

DrahtBot requested review from yancyribbens on Jun 14, 2025

in src/wallet/coinselection.cpp:91 in 4be47e58bd outdated

93-    int curr_selection_weight = 0; // sum of selected utxo weight
94-
95-    // Calculate curr_available_value
96-    CAmount curr_available_value = 0;
97+    // Check that there are sufficient funds
98+    CAmount total_available = 0;

yancyribbens commented at 7:12 pm on June 19, 2025:

Is there some rhyme or reason behind the refactor of the variable name here? I probably would have put that into a different commit personally. I prefer also just dropping curr_ although I notice this is done seemingly at random since there are other variables such as curr_selection_waste where the original name was maintained?

yancyribbens commented at 7:14 pm on June 19, 2025:

To be clear, I’m commenting on the apparent rename from curr_available_value to total_available.

yancyribbens commented at 7:16 pm on June 19, 2025:

I also think available_value is perfectly fine as well.

murchandamus commented at 6:48 pm on June 20, 2025:

curr_available_value was used to track the available funds in the remaining undecided UTXOs during our search. While we were exploring the search tree, we would reduce it each time we descended further in the tree, and then we had to increment it again when we ascended back to earlier UTXOs.

total_available on the other hand is only summed up once and then refers to the total sum of available funds in our UTXO pool. While we are summing it up, we store the available funds for each depth in the lookahead vector. This allows us to look up the remaining funds at each depth directly and we no longer have to traverse every UTXO when we backtrack to increment the curr_available_value but allows us to skip back up multiple steps at once.

DrahtBot requested review from yancyribbens on Jun 19, 2025

in src/wallet/coinselection.cpp:117 in 4be47e58bd outdated

127+    CAmount curr_selection_waste = 0;
128     CAmount best_waste = MAX_MONEY;
129 
130-    bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
131+    // The weight of the currently selected input set
132+    int curr_weight = 0;

yancyribbens commented at 7:27 pm on June 19, 2025:

This isn’t mentioned in the comit message, so I’ll ask since It’s not apparent on first glance. Why is curr_weight being added here? I though bnb was agnostic to the weight, only selecting by effective_value().

yancyribbens commented at 7:30 pm on June 19, 2025:

Sorry, my understanding of this is stale. It looks like max_tx_weight_exceeded was added sometime recently which I missed.

murchandamus commented at 6:54 pm on June 20, 2025:

As you mention, curr_weight is necessary to test whether we have exceeded the max_selection_weight. While we could previously bump into unhandled failure cases where we exceeded the maximum weight for standard transactions, being able to handle smaller transaction weight limits has become even more relevant especially, because we want to be able to reliably create TRUC transactions that are limited to 1000 vB if they have a parent.

yancyribbens commented at 7:11 pm on June 20, 2025:

Thanks, I have been doing some more research into this.

..limited to 1000 vB if they have a parent.

And what if they don’t have a parent? I was under the impression that the upper bound is always 4,000 WU (MAX_STANDARD_TX_WEIGHT). Apologies btw, I could move this question to the forum or elsewhere since it’s getting off topic.

murchandamus commented at 7:31 pm on June 20, 2025:

Unconfirmed TRUC transactions may not have more than one unconfirmed ancestor transaction (not counting itself) and no more than one unconfirmed descendant transaction. Unconfirmed parent or child transactions of TRUC transactions must be TRUC themselves. TRUC transactions are limited to 40,000 WU, TRUC transactions with an unconfirmed parent transaction are limited to 4,000 WU. The full specification is found in BIP 431 and a short summary can be found in the corresponding release notes.

DrahtBot requested review from yancyribbens on Jun 19, 2025

yancyribbens commented at 7:37 pm on June 19, 2025: contributor

I think DrahtBot has had too much caffine, he keeps pinging me to review.

murchandamus commented at 6:56 pm on June 20, 2025: contributor

Thanks for your review, @yancyribbens. I think @DrahtBot treats “Concept ACK” as a signal that the reviewer intends to later do a full review and will automatically ping reviewers when PRs are updated. I have no idea why it pinged you multiple times, though.

yancyribbens commented at 9:52 pm on June 21, 2025: contributor

Thanks for your review, @yancyribbens.

Sure, of course It’s on my TODO list to go over it again in more detail since I’ve really only done a surface level inspection so far.

coinselection: Optimize BnB exploration #32150

Code Coverage & Benchmarks

Reviews

Conflicts

LLM Linter (✨ experimental)