test: wallet: BnB incomplete result on attempt-limit success #35590

brunoerg commented at 12:14 PM on June 23, 2026: contributor

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.

It kills the following mutant:

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 8d69957c30..e4d07415f3 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -212,7 +212,7 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
 
         if (curr_try >= TOTAL_TRIES) {
             // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
-            result.SetAlgoCompleted(false);
+            result.SetAlgoCompleted(true);
             break;
         }

DrahtBot added the label Tests on Jun 23, 2026

DrahtBot commented at 12:14 PM on June 23, 2026: 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/35590.

Reviews

See the guideline and AI policy for information on the review process.

Type	Reviewers
ACK	yashbhutwala, murchandamus, achow101
Concept ACK	yancyribbens

If your review is incorrectly listed, please copy-paste <code></code> into the comment that the bot should ignore.

Conflicts

No conflicts as of last run.

brunoerg commented at 6:11 PM on June 30, 2026: contributor

cc @murchandamus

in src/wallet/test/coinselection_tests.cpp:238 in 8132644275

 233 | +        utxo_pool.push_back(MakeCoin(base + (CAmount{1} << (pairs - 1 - i)), /*is_eff_value=*/true, default_cs_params));
 234 | +    }
 235 | +
 236 | +    // Add an exact-match solution that is found immediately. BnB must still report that the algorithm did not
 237 | +    // complete once the remaining hard case pushes the search into the attempt limit.
 238 | +    AddCoins(utxo_pool, {selection_target}, default_cs_params);

murchandamus commented at 8:30 PM on July 14, 2026:

The way the amounts are found makes it harder than necessary to understand what values are available and what the selection target is. The second bitshift-based amount could be simplified to + 1 and it should still interleave the values in the same order and thus behave the same way:

    CAmount selection_target{0};
    const size_t pairs{17};
    for (size_t i = 0; i < pairs; ++i) {
        const CAmount base{CAmount{1} << (pairs + i)};
        selection_target += base;
        utxo_pool.push_back(MakeCoin(base, /*is_eff_value=*/true, default_cs_params));
        utxo_pool.push_back(MakeCoin(base + 1), /*is_eff_value=*/true, default_cs_params));
    }

    // Add an exact-match solution that is found immediately. BnB must still report that the algorithm did not
    // complete once the remaining hard case pushes the search into the attempt limit.
    AddCoins(utxo_pool, {selection_target}, default_cs_params);

I believe the following simpler construction would test the behavior the same way, but would be easier to understand:

    CAmount selection_target{800'000};
    // Add a single UTXO that will produce an immediate exact match solution. BnB must still report that the algorithm did not
    // complete once the remaining hard case pushes the search into the attempt limit.
    AddCoins(utxo_pool, {selection_target}, default_cs_params);
    for (size_t i = 0; i < 19; ++i) {
        utxo_pool.push_back(MakeCoin(100'000 + i, /*is_eff_value=*/true, default_cs_params));
    }

murchandamus commented at 8:40 PM on July 14, 2026:

This uses two different methods to add one UTXO to the UTXO pool, once AddCoins and twice MakeCoin. It would be preferable if the same method were used to add single UTXOs throughout, e.g., the two MakeCoin instances could be a single AddCoins call, or all three should be MakeCoin.

brunoerg commented at 12:32 AM on July 15, 2026:

Nice suggestion, better to read and understand. I'm going to address it, use default_cs_params.m_cost_of_change for the cost_of_change (avoiding using the 0 value) and then we can get rid of the UTXO with the selection_target as mentioned in #35590 (review).

in src/wallet/test/coinselection_tests.cpp:240 in 8132644275

 235 | +
 236 | +    // Add an exact-match solution that is found immediately. BnB must still report that the algorithm did not
 237 | +    // complete once the remaining hard case pushes the search into the attempt limit.
 238 | +    AddCoins(utxo_pool, {selection_target}, default_cs_params);
 239 | +
 240 | +    const auto result{SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT)};

murchandamus commented at 8:34 PM on July 14, 2026:

One of the main goals of this new coinselection test suite was to get away from setting unnatural values to force some specific expected outcomes. I would prefer if we didn’t set cost_of_change to zero here.

    const auto result{SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT)};

The simplified test case I propose above would find a solution with an excess of 38 sats (i.e., selection_target + 38), if cost_of_change were not artificially zeroed here. You could also drop the UTXO with the selection_target as effective value in that case.

murchandamus commented at 8:52 PM on July 14, 2026: member

Concept ACK! Thank you for proposing this test.

The two contra-moving bitshifts had me print debug the values to make sure I wasn’t misunderstanding what was happening and the cost_of_change being set to zero made some of my first experimentation error out unexpectedly. Please see the inline comments for some suggestions.

brunoerg force-pushed on Jul 15, 2026

brunoerg commented at 12:35 AM on July 15, 2026: contributor

Force-pushed addressing #35590 (review). Thanks, @murchandamus.

DrahtBot added the label CI failed on Jul 15, 2026

yancyribbens commented at 1:14 AM on July 15, 2026: contributor

Concept ACK

Instead of a new test case, why not just re-use an existing one for TOTAL_TRIES here: https://github.com/brunoerg/bitcoin/blob/ad014cc0cfe3330460b6d692afc31b0b394333d6/src/wallet/test/coinselection_tests.cpp#L180?

Perhaps add an optional argument for the number attempts to TestBnBSuccess and TestBnBFail.

yancyribbens commented at 1:40 AM on July 15, 2026: contributor

Correction, adding an assertion to the existing BnB exhaustion tests that asserts result->GetAlgoCompleted() should kill the mutant IIUC.

yancyribbens commented at 2:02 AM on July 15, 2026: contributor

Also, CoinGrinder has this same code path: https://github.com/brunoerg/bitcoin/blob/ad014cc0cfe3330460b6d692afc31b0b394333d6/src/wallet/coinselection.cpp#L542. It would be worth checking if the mutation exists there as well.

mohamadshahmaleki8-png commented at 2:13 AM on July 15, 2026: none

Hi, ok I did not find the problem you mentioned, and I don't think there is anything wrong with it.

shahmaleki$ lion

در تاریخ چهارشنبه ۱۵ ژوئیه ۲۰۲۶، ۰۵:۳۳ yancy @.***> نوشت:

yancyribbens left a comment (bitcoin/bitcoin#35590) https://github.com/bitcoin/bitcoin/pull/35590#issuecomment-4976128828

Also, CoinGrinder has this same code path: https://github.com/brunoerg/bitcoin/blob/ad014cc0cfe3330460b6d692afc31b0b394333d6/src/wallet/coinselection.cpp#L542. It would be worth checking if the mutation exists there as well.

— Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/35590?email_source=notifications&email_token=BXING6WVVYV4UUCIMZLS74L5E3Q5ZA5CNFSNUABFM5UWIORPF5TWS5BNNB2WEL2JONZXKZKDN5WW2ZLOOQXTIOJXGYYTEOBYGI4KM4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSWGM33PORSXEX3DNRUWG2Y#issuecomment-4976128828, or unsubscribe https://github.com/notifications/unsubscribe-auth/BXING6QJSWBL2NY4UTD5FDT5E3Q5ZAVCNFSNUABDKJSXA33TNF2G64TZHMYTCOBRHEZDOO2JONZXKZJ3GQ3TENJXGA3TINBZUF3AE . Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS https://github.com/notifications/mobile/ios/BXING6VOJD3NIHYMGUGT3535E3Q5ZA5CNFSNUABFM5UWIORPF5TWS5BNNB2WEL2JONZXKZKDN5WW2ZLOOQXTIOJXGYYTEOBYGI4KM4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSVGM33PORSXEX3JN5ZQ and Android https://github.com/notifications/mobile/android/BXING6RL67MLTT3KUYSYLKD5E3Q5ZA5CNFSNUABFM5UWIORPF5TWS5BNNB2WEL2JONZXKZKDN5WW2ZLOOQXTIOJXGYYTEOBYGI4KM4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSXGM33PORSXEX3BNZSHE33JMQ. Download it today! You are receiving this because you are subscribed to this thread.Message ID: @.***>

mohamadshahmaleki8-png commented at 2:16 AM on July 15, 2026: none

Yes, this is also possible and I will gladly correct it

shahmaleki$sara

در تاریخ چهارشنبه ۱۵ ژوئیه ۲۰۲۶، ۰۴:۴۴ yancy @.***> نوشت:

yancyribbens left a comment (bitcoin/bitcoin#35590) https://github.com/bitcoin/bitcoin/pull/35590#issuecomment-4975791156

Concept ACK

Instead of a new test case, why not just re-use an existing one for TOTAL_TRIES here:

https://github.com/brunoerg/bitcoin/blob/ad014cc0cfe3330460b6d692afc31b0b394333d6/src/wallet/test/coinselection_tests.cpp#L180 ?

Perhaps add an optional argument for the number attempts to TestBnBSuccess and TestBnBFail.

— Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/35590?email_source=notifications&email_token=BXING6WWFUC6EHAHDLCPKQ35E3LIXA5CNFSNUABFM5UWIORPF5TWS5BNNB2WEL2JONZXKZKDN5WW2ZLOOQXTIOJXGU3TSMJRGU3KM4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSWGM33PORSXEX3DNRUWG2Y#issuecomment-4975791156, or unsubscribe https://github.com/notifications/unsubscribe-auth/BXING6TYYYHW24KMB3575PT5E3LIXAVCNFSNUABDKJSXA33TNF2G64TZHMYTCOBRHEZDOO2JONZXKZJ3GQ3TENJXGA3TINBZUF3AE . Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS https://github.com/notifications/mobile/ios/BXING6V34ONWOSRZL3UFUV35E3LIXA5CNFSNUABFM5UWIORPF5TWS5BNNB2WEL2JONZXKZKDN5WW2ZLOOQXTIOJXGU3TSMJRGU3KM4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSVGM33PORSXEX3JN5ZQ and Android https://github.com/notifications/mobile/android/BXING6RA46XVTYCCW6XEZU35E3LIXA5CNFSNUABFM5UWIORPF5TWS5BNNB2WEL2JONZXKZKDN5WW2ZLOOQXTIOJXGU3TSMJRGU3KM4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSXGM33PORSXEX3BNZSHE33JMQ. Download it today! You are receiving this because you are subscribed to this thread.Message ID: @.***>

mohamadshahmaleki8-png commented at 2:20 AM on July 15, 2026: none

Ok I'm glad you liked it, I will definitely follow your order.

shahmaleki$sara

در تاریخ چهارشنبه ۱۵ ژوئیه ۲۰۲۶، ۰۴:۰۲ Bruno Garcia < @.***> نوشت:

@.**** commented on this pull request.

In src/wallet/test/coinselection_tests.cpp https://github.com/bitcoin/bitcoin/pull/35590#discussion_r3583603506:

CAmount selection_target{0};
const size_t pairs{17};

for (size_t i = 0; i < pairs; ++i) {
   const CAmount base{CAmount{1} << (pairs + i)};
   selection_target += base;
   utxo_pool.push_back(MakeCoin(base, /*is_eff_value=*/true, default_cs_params));
   utxo_pool.push_back(MakeCoin(base + (CAmount{1} << (pairs - 1 - i)), /*is_eff_value=*/true, default_cs_params));
}

// Add an exact-match solution that is found immediately. BnB must still report that the algorithm did not

// complete once the remaining hard case pushes the search into the attempt limit.

AddCoins(utxo_pool, {selection_target}, default_cs_params);
Nice suggestion, better to read and understand. I'm going to address it, use default_cs_params.m_cost_of_change for the cost_of_change (avoiding using the 0 value) and then we can get rid of the UTXO with the selection_target as mentioned in #35590 (comment) https://github.com/bitcoin/bitcoin/pull/35590#discussion_r3582440890.

— Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/35590?email_source=notifications&email_token=BXING6XNZKE3SU6E4GGSJ7T5E3GLVA5CNFSNUABKM5UWIORPF5TWS5BNNB2WEL2QOVWGYUTFOF2WK43UKJSXM2LFO4XTINRZHE3TMNJRGE32M4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSWGM33PORSXEX3DNRUWG2Y#discussion_r3583603506, or unsubscribe https://github.com/notifications/unsubscribe-auth/BXING6TGTPEKW4TYYR6WDY35E3GLVAVCNFSNUABDKJSXA33TNF2G64TZHMYTCOBRHEZDOO2JONZXKZJ3GQ3TENJXGA3TINBZUF3AE . Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS https://github.com/notifications/mobile/ios/BXING6VMOVIL6KN63P4QXK35E3GLVA5CNFSNUABKM5UWIORPF5TWS5BNNB2WEL2QOVWGYUTFOF2WK43UKJSXM2LFO4XTINRZHE3TMNJRGE32M4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSVGM33PORSXEX3JN5ZQ and Android https://github.com/notifications/mobile/android/BXING6WUC6YFNPTYR4TZUYD5E3GLVA5CNFSNUABKM5UWIORPF5TWS5BNNB2WEL2QOVWGYUTFOF2WK43UKJSXM2LFO4XTINRZHE3TMNJRGE32M4TFMFZW63VKON2WE43DOJUWEZLEUVSXMZLOOSXGM33PORSXEX3BNZSHE33JMQ. Download it today! You are receiving this because you are subscribed to this thread.Message ID: @.***>

murchandamus commented at 8:48 PM on July 15, 2026: member

Instead of a new test case, why not just re-use an existing one for TOTAL_TRIES here: https://github.com/brunoerg/bitcoin/blob/ad014cc0cfe3330460b6d692afc31b0b394333d6/src/wallet/test/coinselection_tests.cpp#L180?

The linked test exhausts the search space in the case with 18 UTXOs and does not find any solution in the case with 19 UTXOs. The new proposed test is different in that it finds a solution without exhausting the search space. The old test does not exhibit that case.

Perhaps add an optional argument for the number attempts to TestBnBSuccess and TestBnBFail.

TestBnBSuccess(…) already has a mandatory expected_amounts parameter. The test could use TestBnBSuccess(…) and look for 100,000 tries, but it would not kill the mutant that Bruno found, because that would not distinguish between the case of the search space being exhausted on the 100,000th attempt and the algorithm running out of tries before exhausting the search space.

brunoerg force-pushed on Jul 15, 2026

brunoerg commented at 9:58 PM on July 15, 2026: contributor

Force-pushed fixing the tidy error.

yancyribbens commented at 11:10 PM on July 15, 2026: contributor

The new proposed test is different in that it finds a solution without exhausting the search space. The old test does not exhibit that case.

Ah, I see, thanks. I think this would also be the same with the exhaust coin-grinder test.

DrahtBot removed the label CI failed on Jul 15, 2026

brunoerg commented at 6:11 PM on July 16, 2026: contributor

Also, CoinGrinder has this same code path: https://github.com/brunoerg/bitcoin/blob/ad014cc0cfe3330460b6d692afc31b0b394333d6/src/wallet/coinselection.cpp#L542. It would be worth checking if the mutation exists there as well.

It exists https://bitcoincore.space/src/wallet/coinselection.cpp#2513. I intend to address it in a follow-up.

in src/wallet/test/coinselection_tests.cpp:237 in 698432d448

 232 | +        utxo_pool.push_back(MakeCoin(100'000 + i, /*is_eff_value=*/true, default_cs_params));
 233 | +    }
 234 | +
 235 | +    const auto result{SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT)};
 236 | +    BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: Exhaust with early solution");
 237 | +    BOOST_CHECK_EQUAL(result->GetSelectedEffectiveValue(), selection_target + 38);

murchandamus commented at 10:34 PM on July 16, 2026:

Looking at this again, it might be more slightly more future proof to not look for equality with a specific input set combination, but instead to only test that the selected effective amount is greater than the optimal solution we would expect if it could run indefinitely: the optimal solution would use the eight UTXOs with the smallest amounts: Σ(0, .., 7) = 28.

    BOOST_CHECK(result->GetSelectedEffectiveValue() > selection_target + 28);

brunoerg commented at 6:21 PM on July 17, 2026:

I agree. Since what we expect here is the effective value being greater than the optimal solution, it doesn't really matter the exact value itself.

murchandamus commented at 11:05 PM on July 16, 2026: member

Other than that, looks good to me. ACK 698432d4484fd2bbe82b582660d7ac95901a514f

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>

6ee05c4b18

brunoerg force-pushed on Jul 17, 2026

brunoerg commented at 6:22 PM on July 17, 2026: contributor

Force-pushed addressing #35590 (review).

yashbhutwala commented at 8:19 PM on July 17, 2026: contributor

tACK 6ee05c4b188c0da8cefb7f361c3ba6866c5710b5 Reviewed the test and the surrounding SelectCoinsBnB attempt-limit logic. Built test_bitcoin with wallet support on macOS using AppleClang 17. The targeted bnb_exhaustion_with_solution_test passed, as did the complete coinselection_tests suite. I also ran the targeted test 20 consecutive times successfully. As a mutation check, I changed SetAlgoCompleted(false) to SetAlgoCompleted(true), rebuilt, and confirmed that the new test failed specifically at the !result->GetAlgoCompleted() assertion. After restoring the original code, the test passed again. The test exercises the intended case where BnB finds a valid selection but reaches the 100,000-attempt limit before completing the search. No issues found.

DrahtBot requested review from murchandamus on Jul 17, 2026

murchandamus commented at 9:45 PM on July 17, 2026: member

ACK 6ee05c4b188c0da8cefb7f361c3ba6866c5710b5

achow101 commented at 1:05 AM on July 18, 2026: member

ACK 6ee05c4b188c0da8cefb7f361c3ba6866c5710b5

achow101 merged this on Jul 18, 2026

achow101 closed this on Jul 18, 2026

Kino1994 referenced this in commit 5300c81eb9 on Jul 19, 2026

brunoerg deleted the branch on Jul 21, 2026