coinselection: BnB skip exploring high waste
What the developer wrote
Authored by Murch
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.
What changed, and why it matters
This commit is a performance optimization for Bitcoin Core's coin selection algorithm. It teaches the Branch-and-Bound (BnB) coin picker to skip exploring input combinations that are guaranteed to be worse at high transaction fees. It does not fix a security vulnerability, crash, or consensus bug. The change could theoretically affect which coins are selected for a transaction, but only in a way that is intended to preserve the existing best-choice behavior while doing less work.
No security action required. Treat as a normal code-quality/performance improvement. Wallet maintainers may want to verify that the optimization does not change coin-selection outcomes in edge cases, but the included unit tests cover the intended high-fee and low-fee behavior.
Security signals we found
No security-relevant signals in commit message or diff
Change is an optimization/perf improvement to wallet coin selection
No memory safety, cryptography, consensus, or network changes
No bugfix, CVE, or advisory language present
Evidence from the diff
The patch adds an early-pruning condition to SelectCoinsBnB in src/wallet/coinselection.cpp. When the effective fee rate is higher than the long-term fee rate (is_feerate_high), and the current partial selection’s waste score already exceeds the best waste found so far, the search shifts (skips exploring deeper combinations). The reasoning is that at high fee rates, adding more inputs can only increase waste, so the branch cannot improve on the current best. At low fee rates the branch is not pruned, because extra inputs reduce waste. Tests are updated to expect fewer BnB attempts (7 instead of 8, and 15 instead of 28) for the same selected outputs.
Changed components
src/wallet/coinselection.cppsrc/wallet/test/coinselection_tests.cppInspect captured patch +11 / −2
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index e671c3d0..cce4c59c 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -132,6 +132,8 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
size_t curr_try = 0;
SelectionResult result(selection_target, SelectionAlgorithm::BNB);
+ // 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) {
bool should_shift{false}, should_cut{false};
// Select `next_utxo`
@@ -151,6 +153,13 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
} else if (curr_amount > selection_target + cost_of_change) {
// Overshot target range: SHIFT
should_shift = true;
+ } else if (is_feerate_high && curr_selection_waste > best_waste) {
+ // 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, it is impossible for this partial selection
+ // to beat the best selection by adding more inputs: SHIFT
+ // At low feerates, additional inputs lower the waste score, and using this would cause us to skip exploring
+ // combinations with more inputs of lower amounts.
+ should_shift = true;
} else if (curr_amount >= selection_target) {
// Selection is within target window: potential solution
// Adding more UTXOs only increases fees and cannot be better: SHIFT
diff --git a/src/wallet/test/coinselection_tests.cpp b/src/wallet/test/coinselection_tests.cpp
index 05e36167..6a0d5e48 100644
--- a/src/wallet/test/coinselection_tests.cpp
+++ b/src/wallet/test/coinselection_tests.cpp
@@ -226,7 +226,7 @@ BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
const CoinSelectionParams high_feerate_params = init_cs_params(/*eff_feerate=*/25'000);
std::vector<OutputGroup> high_feerate_pool; // 25 sat/vB (greater than long_term_feerate of 10 sat/vB)
AddCoins(high_feerate_pool, {2 * CENT, 3 * CENT, 5 * CENT, 10 * CENT}, high_feerate_params);
- TestBnBSuccess("Select one input at high feerates", high_feerate_pool, /*selection_target=*/10 * CENT, /*expected_input_amounts=*/{10 * CENT}, /*expected_attempts=*/8, high_feerate_params);
+ TestBnBSuccess("Select one input at high feerates", high_feerate_pool, /*selection_target=*/10 * CENT, /*expected_input_amounts=*/{10 * CENT}, /*expected_attempts=*/7, high_feerate_params);
// Add heavy inputs {6, 7} to existing {2, 3, 5, 10}
low_feerate_pool.push_back(MakeCoin(6 * CENT, true, default_cs_params, /*custom_spending_vsize=*/500));
@@ -235,7 +235,7 @@ BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
high_feerate_pool.push_back(MakeCoin(6 * CENT, true, high_feerate_params, /*custom_spending_vsize=*/500));
high_feerate_pool.push_back(MakeCoin(7 * CENT, true, high_feerate_params, /*custom_spending_vsize=*/500));
- TestBnBSuccess("Prefer two light inputs over two heavy inputs at high feerates", high_feerate_pool, /*selection_target=*/13 * CENT, /*expected_input_amounts=*/{3 * CENT, 10 * CENT}, /*expected_attempts=*/28, high_feerate_params);
+ TestBnBSuccess("Prefer two light inputs over two heavy inputs at high feerates", high_feerate_pool, /*selection_target=*/13 * CENT, /*expected_input_amounts=*/{3 * CENT, 10 * CENT}, /*expected_attempts=*/15, high_feerate_params);
}
static void TestSRDSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CoinSelectionParams& cs_params = default_cs_params, const int max_selection_weight = MAX_STANDARD_TX_WEIGHT)
Why this scored 19/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.