← Watch feed
opt: Skip evaluation of equivalent input sets
Public commit record
80/100 · Strong
What the developer wrote
Authored by Murch
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.
✓ Descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Explains rationale or failure mode
What changed, and why it matters
This commit is a pure performance optimization for Bitcoin Core's coin selection algorithm. It avoids re-evaluating equivalent combinations of coins when choosing which inputs to include in a transaction. There is no security vulnerability being fixed here.
Recommended action
No security action required. Treat as a normal performance optimization.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The change modifies the Branch-and-Bound (BnB) coin selection logic in src/wallet/coinselection.cpp to skip evaluating UTXO combinations that would be equivalent to already-evaluated ones. When a UTXO is omitted and the next UTXO has the same effective value and weight, selecting the next one would produce an identical input set to a previously considered branch, so it is skipped. The test is updated to reflect the dramatically reduced number of attempts (from 100,000 to 16) due to this pruning optimization. No security boundary is crossed, no input validation is changed, and no bug is corrected.
Changed components
src/wallet/coinselection.cppsrc/wallet/test/coinselection_tests.cppInspect captured patch +26 / −5
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index febac429..8a4919a5 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -68,9 +68,11 @@ struct {
*
* waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
*
- * The algorithm uses one additional optimization: a lookahead keeps track of the total value of
+ * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
* the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
- * cannot be reached.
+ * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
+ * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
+ * predecessor.
*
* The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
* https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
@@ -140,9 +142,10 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
size_t curr_try = 0;
SelectionResult result(selection_target, SelectionAlgorithm::BNB);
+ bool is_done = false;
// We don’t have access to the feerate here, but fee to long_term_fee is as feerate to LTFRE
bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
- while (true) {
+ while (!is_done) {
bool should_shift{false}, should_cut{false};
// Select `next_utxo`
OutputGroup& utxo = utxo_pool[next_utxo];
@@ -204,15 +207,33 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
should_shift = true;
}
- if (should_shift) {
+ while (should_shift) {
if (curr_selection.empty()) {
// Exhausted search space before running into attempt limit
+ is_done = true;
result.SetAlgoCompleted(true);
break;
}
// Set `next_utxo` to one after last selected, then deselect last selected UTXO
next_utxo = curr_selection.back() + 1;
deselect_last();
+ should_shift = false;
+
+ // After SHIFTing to an omission branch, the `next_utxo` might have the same value and same weight as the
+ // UTXO we just omitted (i.e. it is a "clone"). If so, selecting `next_utxo` would produce an equivalent
+ // selection as one we previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a
+ // differing amount or weight.
+ Assume(next_utxo < utxo_pool.size());
+ while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()
+ && utxo_pool[next_utxo - 1].m_weight == utxo_pool[next_utxo].m_weight) {
+ if (next_utxo >= utxo_pool.size() - 1) {
+ // Reached end of UTXO pool skipping clones: SHIFT instead
+ should_shift = true;
+ break;
+ }
+ // Skip clone: previous UTXO is equivalent and unselected
+ ++next_utxo;
+ }
}
}
diff --git a/src/wallet/test/coinselection_tests.cpp b/src/wallet/test/coinselection_tests.cpp
index e1b1b074..a8d2ef2c 100644
--- a/src/wallet/test/coinselection_tests.cpp
+++ b/src/wallet/test/coinselection_tests.cpp
@@ -175,7 +175,7 @@ BOOST_AUTO_TEST_CASE(bnb_test)
std::vector<OutputGroup> clone_pool;
AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT}, cs_params);
AddDuplicateCoins(clone_pool, /*count=*/50'000, /*amount=*/5 * CENT, cs_params);
- TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT}, /*expected_attempts=*/100'000, cs_params);
+ TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT}, /*expected_attempts=*/16, cs_params);
/* Test BnB attempt limit (`TOTAL_TRIES`)
*
Risk score
Our methodology →Why this scored 15/100
Human-validated context
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
No validated notes yet.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.