test: add case where `TOTAL_TRIES` is exceeded yet solution remains
What the developer wrote
Authored by yancy
test: add case where `TOTAL_TRIES` is exceeded yet solution remains
Show that `CoinGrider` halts searching when the number of attempts exceeds
`TOTAL_TRIES`. To do so, show that a solution is found, then add one
more entry to the same set of inputs. Since the search orders by
`effective_value`, the solution is constructed such that only values
with the lowest `effective_value` have the least weight. Only the
lowest weight values will not exceed the `max_selection_weight`.
Therefore, `CoinGrinder` will not evaluate all lowest weight solutions
together before exceeding `TOTAL_TRIES` since they are last found.
This test case was inspired by a similar test for `BnB` currently
named `bnb_test`.
What changed, and why it matters
This commit only adds a new test case to Bitcoin Core's automated test suite. It demonstrates an existing behavior of the CoinGrinder coin-selection algorithm: if too many combinations must be tried, the algorithm stops before finding a valid solution. The commit does not change any production wallet code, so it cannot by itself introduce a security vulnerability or fix one in live software.
No action required. Review the test for correctness and merge as part of normal quality assurance.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The diff adds one BOOST_AUTO_TEST_CASE block to src/wallet/test/coinselector_tests.cpp. It constructs two scenarios with 18 and 19 near-identical UTXOs (doppelgangers), a target of 8 BTC, and a max_selection_weight of 3200 WU. With 18 inputs CoinGrinder finds a solution after 87,525 attempts; with 19 inputs it hits the TOTAL_TRIES limit and returns no result. No wallet, consensus, or networking code is modified.
Changed components
src/wallet/test/coinselector_tests.cppInspect captured patch +35 / −0
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index c73663de..74b94ee9 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -1149,6 +1149,41 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests)
size_t expected_attempts = 7;
BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
}
+
+ {
+ // #################################################################################################################
+ // 8) Test input set that has a solution will not find a solution before reaching the attempt limit
+ // #################################################################################################################
+ CAmount target = 8 * COIN;
+ int max_selection_weight = 3200; // WU
+ dummy_params.m_min_change_target = 0;
+ const auto& result_a = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
+ CoinsResult doppelgangers;
+ for (int i = 0; i < 18; ++i) {
+ add_coin(doppelgangers, wallet, CAmount(1 * COIN + i), CFeeRate(0), 144, false, 0, true, 96 + i);
+ }
+ return doppelgangers;
+ });
+ BOOST_CHECK(result_a);
+ SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
+ for (int i = 0; i < 8; ++i) {
+ add_coin(1 * COIN + i, 0, expected_result);
+ }
+ BOOST_CHECK(EquivalentResult(expected_result, *result_a));
+ // Demonstrate a solution is found before the attempts limit is reached.
+ size_t expected_attempts = 87'525;
+ BOOST_CHECK_MESSAGE(result_a->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result_a->GetSelectionsEvaluated()));
+
+ // Adding one more doppelganger causes the attempt limit to be reached before finding a solution.
+ const auto& result_b = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
+ CoinsResult doppelgangers;
+ for (int i = 0; i < 19; ++i) {
+ add_coin(doppelgangers, wallet, CAmount(1 * COIN + i), CFeeRate(0), 144, false, 0, true, 96 + i);
+ }
+ return doppelgangers;
+ });
+ BOOST_CHECK(!result_b);
+ }
}
static util::Result<SelectionResult> SelectCoinsSRD(const CAmount& target,
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.