test: wallet: BnB incomplete result on attempt-limit success
What the developer wrote
Authored by Bruno Garcia
test: wallet: BnB incomplete result on attempt-limit success
BnB can return a valid selection before exhausting
the search tree, then hit TOTAL_TRIES while continuing
to look for a better one. Add a unit test for that path
using a known exhaustion fixture plus an exact-match
coin, and assert the result is marked incomplete via
GetAlgoCompleted() == false.
Co-authored-by: Murch <murch@murch.one>
What changed, and why it matters
This commit adds a new unit test for Bitcoin Core's coin selection algorithm. It checks that when the Branch-and-Bound (BnB) search finds a usable coin selection early but then keeps searching for a better one until it hits the attempt limit, the result is correctly marked as 'incomplete' (the algorithm did not fully finish exploring all possibilities). There is no code change to the actual wallet behavior—only a new test.
No security action needed. This is a test-only addition verifying existing behavior. Reviewers may optionally confirm the fixture values match the intended exhaustion path and that GetAlgoCompleted() semantics are as documented.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The diff adds BOOST_AUTO_TEST_CASE(bnb_exhaustion_with_solution_test) in src/wallet/test/coinselection_tests.cpp. It constructs a UTXO pool of 19 outputs with values 100,000 satoshis increasing by 1 sat each, sets a selection target of 800,000 sat, and calls SelectCoinsBnB. The test asserts that a result exists, its selected effective value exceeds target + 28, the input set size is 8, exactly 100,000 selection evaluations occurred, and GetAlgoCompleted() returns false. This exercises the path where BnB discovers a solution within cost_of_change but later exhausts TOTAL_TRIES before fully exploring the tree.
Changed components
src/wallet/test/coinselection_tests.cppInspect captured patch +20 / −0
diff --git a/src/wallet/test/coinselection_tests.cpp b/src/wallet/test/coinselection_tests.cpp
index b4b865d6..f470fd1f 100644
--- a/src/wallet/test/coinselection_tests.cpp
+++ b/src/wallet/test/coinselection_tests.cpp
@@ -220,6 +220,26 @@ BOOST_AUTO_TEST_CASE(bnb_test)
}
}
+BOOST_AUTO_TEST_CASE(bnb_exhaustion_with_solution_test)
+{
+ std::vector<OutputGroup> utxo_pool;
+ utxo_pool.reserve(19);
+
+ CAmount selection_target{800'000};
+ // A hard case with no exact-match solution: BnB must still report that the algorithm did not complete once the
+ // search is pushed into the attempt limit, even though it finds a solution within cost_of_change of the target.
+ for (size_t i = 0; i < 19; ++i) {
+ utxo_pool.push_back(MakeCoin(100'000 + i, /*is_eff_value=*/true, default_cs_params));
+ }
+
+ const auto result{SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT)};
+ BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: Exhaust with early solution");
+ BOOST_CHECK(result->GetSelectedEffectiveValue() > selection_target + 28);
+ BOOST_CHECK_EQUAL(result->GetInputSet().size(), 8U);
+ BOOST_CHECK_EQUAL(result->GetSelectionsEvaluated(), 100'000U);
+ BOOST_CHECK(!result->GetAlgoCompleted());
+}
+
BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
{
// Create sets of UTXOs with the same effective amounts at different feerates (but different absolute amounts)
Why this scored 15/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.