wallet: Branch and Bound producing change

brunoerg commented at 9:47 pm on February 9, 2025: contributor

My fuzz server crashed due to Branch and Bound producing change. I could reproduce the issue with the following test:

 0BOOST_AUTO_TEST_CASE(bnb_change)
 1{
 2    FastRandomContext fast_random_context{};
 3    CoinSelectionParams coin_params{
 4        /*rng_fast*/fast_random_context,
 5        /*change_output_size=*/31,
 6        /*change_spend_size=*/68,
 7        /*min_change_target=*/50'000,
 8        /*effective_feerate=*/CFeeRate(5000),
 9        /*long_term_feerate=*/CFeeRate(10'000),
10        /*discard_feerate=*/CFeeRate(3000),
11        /*tx_noinputs_size=*/11 + 31, //static header size + output size
12        /*avoid_partial=*/false,
13    };
14    coin_params.m_change_fee = /*155 sats=*/coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
15    coin_params.min_viable_change = /*204 sats=*/coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);
16    coin_params.m_cost_of_change = /*204 + 155 sats=*/coin_params.min_viable_change + coin_params.m_change_fee;
17    coin_params.m_subtract_fee_outputs = false;
18
19    std::vector<COutput> utxo_pool;
20    CMutableTransaction tx;
21    tx.vout.resize(8);
22    tx.vout[7].nValue = 1395186823946715;
23    tx.nLockTime = 1; // all transactions get different hashes
24    utxo_pool.emplace_back(COutPoint(tx.GetHash(), 7), tx.vout.at(7), /*depth=*/1, /*input_bytes=*/1578, /*spendable=*/true, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, coin_params.m_effective_feerate.GetFee(1578));
25
26    std::vector<OutputGroup> output_groups;
27    auto output_group = OutputGroup(coin_params);
28    output_group.Insert(std::make_shared<COutput>(utxo_pool[0]), /*ancestors=*/0, /*descendants=*/0);
29    output_groups.push_back(output_group);
30
31    const auto target{1395186823938466};
32    auto result_bnb = SelectCoinsBnB(output_groups, target, coin_params.m_cost_of_change, 400000);
33    if (result_bnb) {
34        assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
35    }
36}

I noted that change and min_viable_change have the same values. For reference: https://bitcoincore.space/src/wallet/coinselection.cpp#987

maflcko added the label Wallet on Feb 10, 2025

brunoerg renamed this:
~~Branch and Bound producing change~~
wallet: Branch and Bound producing change
on Feb 10, 2025

brunoerg commented at 8:37 pm on February 10, 2025: contributor

friendly ping: @murchandamus

yancyribbens commented at 9:25 pm on February 10, 2025: contributor

Change is computed as:

0effective_values - target - change_fee
11395186823938825 - 1395186823938466 - 155
2204

Why does the test assert this should be zero instead of 204?

yancyribbens commented at 9:29 pm on February 10, 2025: contributor

In otherwords, I think setting the change_fee to 359 would produce zero change, although I’m not sure what you are testing.

brunoerg commented at 9:30 pm on February 10, 2025: contributor

This is a failing test to show BnB is producing change.

yancyribbens commented at 9:34 pm on February 10, 2025: contributor

This is a failing test to show BnB is producing change.

With those parameters though, BnB should be producing change.

yancyribbens commented at 9:59 pm on February 10, 2025: contributor

Also, the cost_of_change is computed as 359, so any solution between target and target + cost_of_change is valid (inclusive).

brunoerg commented at 4:06 pm on February 11, 2025: contributor

With those parameters though, BnB should be producing change.

Take a look at coinselection fuzz target. See that regardless the parameters/coins/etc we assert that BnB does not produce change (this is the expected for this algorithm).

0// Run coinselection algorithms
1auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
2                  SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, max_selection_weight);
3if (result_bnb) {
4    assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
5    assert(result_bnb->GetSelectedValue() >= target);
6    assert(result_bnb->GetWeight() <= max_selection_weight);
7    (void)result_bnb->GetShuffledInputVector();
8    (void)result_bnb->GetInputSet();
9}

yancyribbens commented at 0:20 am on February 12, 2025: contributor

I tracked down the PR that add this: #27585 and commit https://github.com/bitcoin/bitcoin/pull/27585/commits/6d9b26d56ab5295dfcfe0f80a3069046a263fb2f. I’m a little confused by this since this is counter to what I would expect. BnB seeks to find a changelss solution, however only if the change created is less than the cost of creating a new output. That is, if it’s more expansive to add the change leftover to a new output, don’t bother.

murchandamus commented at 10:02 pm on February 12, 2025: contributor

The issue appears to have been introduced by myself in #28366 in the commit https://github.com/bitcoin/bitcoin/commit/7aa7e30441fe77bf8e8092916e36b004bbbfe2a7#diff-d473ed8396f9451afb848923cfcfaa630c9811a78e07f3ae1ffd3a65da218accR197

Branch and Bound uses target + cost_of_change as the upper bound inclusive of the solution space. In the mentioned PR, it also uses cost_of_change as the value for min_viable_change in the RecalculateWaste call. However, min_viable_change denotes the smallest permitted value for creating change. This causes an overlap on the edge, where the largest permitted value for a changeless solution matches the minimum viable amount for creating change.

The short term solution would be to increase the value passed to RecalculateWaste for min_viable_change by 1 to remove the overlap.

This chart implies that a better solution would be to use target + min_viable_change - 1 as the upper bound for the Branch and Bound solution space, although I would also like to change the definition of `min_viable_change, because it doesn’t make sense to me that the input cost is tied to the current feerate if we are creating a transaction at high feerates. @brunoerg: Do you happen to have a copy of the input that crashed the fuzzer? If so, could you either share it or run the fuzz input against the following fix to line 197 in coinselection.cpp

0-    result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
1+    result.RecalculateWaste(cost_of_change + 1, cost_of_change, CAmount{0});

yancyribbens commented at 10:52 pm on February 12, 2025: contributor

I tried this change running the test @brunoerg posted above and it still results in a change amount of 204 with the given params.

brunoerg commented at 11:12 pm on February 12, 2025: contributor

@brunoerg: Do you happen to have a copy of the input that crashed the fuzzer? If so, could you either share it or run the fuzz input against the following fix to line 197 in coinselection.cpp

It’s a custom target I wrote but I changed the test that I provided here and it’s still producing change.

furszy commented at 4:14 pm on February 13, 2025: member

q: isn’t the test just wrong?. min_viable_change is initialized to the future input fee without increasing the window by one as we do in the actual code. Thats why there is an overlap here. See the wallet code: https://github.com/bitcoin/bitcoin/blob/c242fa5be358150d83c2446896b6f4c45c6365e9/src/wallet/spend.cpp#L1131-L1132

While you are manually setting it to:

0coin_params.min_viable_change = coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);

brunoerg commented at 5:23 pm on February 13, 2025: contributor

q: isn’t the test just wrong?. min_viable_change is initialized to the future input fee without increasing the window by one as we do in the actual code. Thats why there is an overlap here. See the wallet code:

bitcoin/src/wallet/spend.cpp

Lines 1131 to 1132 in c242fa5

const auto change_spend_fee = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size); coin_selection_params.min_viable_change = std::max(change_spend_fee + 1, dust); While you are manually setting it to:

coin_params.min_viable_change = coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);

Interesting, makes sense, this is how I could reproduce using a similar setup of #29532. I just tested it by increasing the window by one and it did not produce change. Will close for now since our fuzz target reproduces exactly the spend behavior (std::max(change_spend_fee + 1, dust)) so it’s fine.

brunoerg closed this on Feb 13, 2025

murchandamus commented at 8:12 pm on February 13, 2025: contributor

Nice catch, @furszy. Thanks!

wallet: Branch and Bound producing change #31830