Inside Bitcoin

1// Copyright (c) 2024-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <consensus/amount.h>
6#include <policy/policy.h>
7#include <wallet/coinselection.h>
8#include <wallet/test/wallet_test_fixture.h>
9
10#include <boost/test/unit_test.hpp>
11
12namespace wallet {
13BOOST_FIXTURE_TEST_SUITE(coinselection_tests, TestingSetup)
14
15static int next_lock_time = 0;
16static FastRandomContext default_rand;
17
18static const int P2WPKH_INPUT_VSIZE = 68;
19static const int P2WPKH_OUTPUT_VSIZE = 31;
20
21/**
22 * This set of feerates is used in the tests to test edge cases around the
23 * default minimum feerate and other potential special cases:
24 * - zero: 0 s/kvB
25 * - minimum non-zero s/kvB: 1 s/kvB
26 * - just below the new default minimum feerate: 99 s/kvB
27 * - new default minimum feerate: 100 s/kvB
28 * - old default minimum feerate: 1000 s/kvB
29 * - a few non-round realistic feerates around default minimum feerate,
30 * dust feerate, and default LTFRE: 315 s/kvB, 2345 s/kvB, and
31 * 10'292 s/kvB
32 * - a high feerate that has been exceeded occasionally: 59'764 s/kvB
33 * - a huge feerate that is extremely uncommon: 1'500'000 s/kvB */
34static const std::vector<int> FEERATES = {0, 1, 99, 100, 315, 1'000, 2'345, 10'292, 59'764, 1'500'000};
35
36/** Default coin selection parameters allow us to only explicitly set
37 * parameters when a diverging value is relevant in the context of a test,
38 * without reiterating the defaults in every test. We use P2WPKH input and
39 * output weights for the change weights. */
40static CoinSelectionParams init_cs_params(int eff_feerate = 5000)
41{
42    CoinSelectionParams csp{
43        /*rng_fast=*/default_rand,
44        /*change_output_size=*/P2WPKH_OUTPUT_VSIZE,
45        /*change_spend_size=*/P2WPKH_INPUT_VSIZE,
46        /*min_change_target=*/50'000,
47        /*effective_feerate=*/CFeeRate(eff_feerate),
48        /*long_term_feerate=*/CFeeRate(10'000),
49        /*discard_feerate=*/CFeeRate(3000),
50        /*tx_noinputs_size=*/11 + P2WPKH_OUTPUT_VSIZE, //static header size + output size
51        /*avoid_partial=*/false,
52    };
53    csp.m_change_fee = csp.m_effective_feerate.GetFee(csp.change_output_size); // 155 sats for default feerate of 5000 s/kvB
54    csp.min_viable_change = /*204 sats=*/csp.m_discard_feerate.GetFee(csp.change_spend_size);
55    csp.m_cost_of_change = csp.min_viable_change + csp.m_change_fee; // 204 + 155 sats for default feerate of 5000 s/kvB
56    csp.m_subtract_fee_outputs = false;
57    return csp;
58}
59
60static const CoinSelectionParams default_cs_params = init_cs_params();
61
62/** Make one OutputGroup with a single UTXO that either has a given effective value (default) or a given amount (`is_eff_value = false`). */
63static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, CoinSelectionParams cs_params = default_cs_params, int custom_spending_vsize = P2WPKH_INPUT_VSIZE)
64{
65    // Always assume that we only have one input
66    CMutableTransaction tx;
67    tx.vout.resize(1);
68    CAmount fees = cs_params.m_effective_feerate.GetFee(custom_spending_vsize);
69    tx.vout[0].nValue = amount + int(is_eff_value) * fees;
70    tx.nLockTime = next_lock_time++;        // so all transactions get different hashes
71    OutputGroup group(cs_params);
72    group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /*depth=*/1, /*input_bytes=*/custom_spending_vsize, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/fees), /*ancestors=*/0, /*cluster_count=*/0);
73    return group;
74}
75
76/** Make multiple OutputGroups with the given values as their effective value */
77static void AddCoins(std::vector<OutputGroup>& utxo_pool, std::vector<CAmount> coins, CoinSelectionParams cs_params = default_cs_params)
78{
79    for (CAmount c : coins) {
80        utxo_pool.push_back(MakeCoin(c, true, cs_params));
81    }
82}
83
84/** Make multiple coins that share the same effective value */
85static void AddDuplicateCoins(std::vector<OutputGroup>& utxo_pool, int count, int amount, CoinSelectionParams cs_params = default_cs_params) {
86    for (int i = 0 ; i < count; ++i) {
87        utxo_pool.push_back(MakeCoin(amount, true, cs_params));
88    }
89}
90
91/** Check if SelectionResult a is equivalent to SelectionResult b.
92 * Two results are equivalent if they are composed of the same input values, even if they have different inputs (i.e., same value, different prevout) */
93static bool HaveEquivalentValues(const SelectionResult& a, const SelectionResult& b)
94{
95    std::vector<CAmount> a_amts;
96    std::vector<CAmount> b_amts;
97    for (const auto& coin : a.GetInputSet()) {
98        a_amts.push_back(coin->txout.nValue);
99    }
100    for (const auto& coin : b.GetInputSet()) {
101        b_amts.push_back(coin->txout.nValue);
102    }
103    std::sort(a_amts.begin(), a_amts.end());
104    std::sort(b_amts.begin(), b_amts.end());
105
106    auto ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
107    return ret.first == a_amts.end() && ret.second == b_amts.end();
108}
109
110static std::string InputAmountsToString(const SelectionResult& selection)
111{
112    return "[" + util::Join(selection.GetInputSet(), " ", [](const auto& input){ return util::ToString(input->txout.nValue);}) + "]";
113}
114
115static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, size_t expected_attempts, const CoinSelectionParams& cs_params = default_cs_params, const int custom_spending_vsize = P2WPKH_INPUT_VSIZE, const int max_selection_weight = MAX_STANDARD_TX_WEIGHT)
116{
117    SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB);
118    CAmount expected_amount = 0;
119    for (CAmount input_amount : expected_input_amounts) {
120        OutputGroup group = MakeCoin(input_amount, true, cs_params, custom_spending_vsize);
121        expected_amount += group.m_value;
122        expected_result.AddInput(group);
123    }
124
125    const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/cs_params.m_cost_of_change, max_selection_weight);
126    BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title);
127    BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s, but got %s", test_title, InputAmountsToString(expected_result), InputAmountsToString(*result)));
128    BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount mismatch in BnB-Success: %s. Expected %d, but got %d", test_title, expected_amount, result->GetSelectedValue()));
129    BOOST_CHECK_MESSAGE(result->GetWeight() <= max_selection_weight, strprintf("Selected weight is higher than permitted in BnB-Success: %s. Expected %d, but got %d", test_title, max_selection_weight, result->GetWeight()));
130    BOOST_CHECK_MESSAGE(result->GetSelectionsEvaluated() == expected_attempts, strprintf("Unexpected number of attempts in BnB-Success: %s. Expected %i attempts, but got %i", test_title, expected_attempts, result->GetSelectionsEvaluated()));
131}
132
133static void TestBnBFail(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CoinSelectionParams& cs_params = default_cs_params, int max_selection_weight = MAX_STANDARD_TX_WEIGHT, const bool expect_max_weight_exceeded = false)
134{
135    const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/cs_params.m_cost_of_change, max_selection_weight);
136    BOOST_CHECK_MESSAGE(!result, "BnB-Fail: " + test_title);
137    bool max_weight_exceeded = util::ErrorString(result).original.find("The inputs size exceeds the maximum weight") != std::string::npos;
138    BOOST_CHECK(expect_max_weight_exceeded == max_weight_exceeded);
139}
140
141BOOST_AUTO_TEST_CASE(bnb_test)
142{
143    for (int feerate : FEERATES) {
144        std::vector<OutputGroup> utxo_pool;
145
146        const CoinSelectionParams cs_params = init_cs_params(feerate);
147
148        TestBnBFail("Empty UTXO pool", utxo_pool, /*selection_target=*/1 * CENT, cs_params);
149
150        AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT}, cs_params);
151
152        // Simple success cases
153        TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, /*expected_attempts=*/3, cs_params);
154        TestBnBSuccess("Select middle UTXO", utxo_pool, /*selection_target=*/3 * CENT, /*expected_input_amounts=*/{3 * CENT}, /*expected_attempts=*/3, cs_params);
155        TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/5 * CENT, /*expected_input_amounts=*/{5 * CENT}, /*expected_attempts=*/2, cs_params);
156        TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/4, cs_params);
157        TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/9 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT, 5 * CENT}, /*expected_attempts=*/5, cs_params);
158
159        // BnB finds changeless solution while overshooting by up to cost_of_change
160        TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/4 * CENT - cs_params.m_cost_of_change, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/4, cs_params);
161
162        // BnB fails to find changeless solution when overshooting by cost_of_change + 1 sat
163        TestBnBFail("Overshoot upper bound", utxo_pool, /*selection_target=*/4 * CENT - cs_params.m_cost_of_change - 1, cs_params);
164
165        TestBnBSuccess("Select max weight", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, /*expected_attempts=*/4, cs_params, /*custom_spending_vsize=*/P2WPKH_INPUT_VSIZE, /*max_selection_weight=*/4 * 2 * P2WPKH_INPUT_VSIZE);
166
167        TestBnBFail("Exceed max weight", utxo_pool, /*selection_target=*/4 * CENT, cs_params, /*max_selection_weight=*/4 * 2 * P2WPKH_INPUT_VSIZE - 1, /*expect_max_weight_exceeded=*/true);
168
169        // Simple cases without BnB solution
170        TestBnBFail("Smallest combination too big", utxo_pool, /*selection_target=*/0.5 * CENT, cs_params);
171        TestBnBFail("No UTXO combination in target window", utxo_pool, /*selection_target=*/7 * CENT, cs_params);
172        TestBnBFail("Select more than available", utxo_pool, /*selection_target=*/10 * CENT, cs_params);
173
174        // Test skipping of equivalent input sets
175        std::vector<OutputGroup> clone_pool;
176        AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT}, cs_params);
177        AddDuplicateCoins(clone_pool, /*count=*/50'000, /*amount=*/5 * CENT, cs_params);
178        TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT}, /*expected_attempts=*/16, cs_params);
179
180        /* Test BnB attempt limit (`TOTAL_TRIES`)
181         *
182         * Generally, on a diverse UTXO pool BnB will quickly pass over UTXOs bigger than the target and then start
183         * combining small counts of UTXOs that in sum remain under the selection_target+cost_of_change. When there are
184         * multiple UTXOs that have matching amount and cost, combinations with equivalent input sets are skipped. The
185         * UTXO pool for this test is specifically crafted to create as much branching as possible. The selection target
186         * is 8 CENT while all UTXOs are slightly bigger than 1 CENT. The smallest eight are 100,000…100,007 sats, while
187         * the larger nine are 100,368…100,375 (i.e., 100,008…100,016 sats plus cost_of_change (359 sats)).
188         *
189         * Because BnB will only select input sets that fall between selection_target and selection_target +
190         * cost_of_change, and the search traverses the UTXO pool from large to small amounts, the search will visit
191         * every single combination of eight inputs. All except the last combination will overshoot by more than
192         * cost_of_change on the eighth input, because the larger nine inputs each exceed 1 CENT by more than
193         * cost_of_change. Only the last combination consisting of the eight smallest UTXOs falls into the target
194         * window.
195         */
196        std::vector<OutputGroup> doppelganger_pool;
197        std::vector<CAmount> doppelgangers;
198        std::vector<CAmount> expected_inputs;
199        for (int i = 0; i < 17; ++i) {
200            if (i < 8) {
201                // The eight smallest UTXOs can be combined to create expected_result
202                doppelgangers.push_back(1 * CENT + i);
203                expected_inputs.push_back(doppelgangers[i]);
204            } else {
205                // Any eight UTXOs including at least one UTXO with the added cost_of_change will exceed target window
206                doppelgangers.push_back(1 * CENT + cs_params.m_cost_of_change + i);
207            }
208        }
209        AddCoins(doppelganger_pool, doppelgangers, cs_params);
210        // Among 17 unique UTXOs of similar effective value we will find a solution composed of the eight smallest UTXOs
211        TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs, /*expected_attempts=*/51'765, cs_params);
212
213        // Among up to 18 unique UTXOs of similar effective value we will find a solution composed of the eight smallest UTXOs
214        AddCoins(doppelganger_pool, {1 * CENT + cs_params.m_cost_of_change + 17}, cs_params);
215        TestBnBSuccess("Combine smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs, /*expected_attempts=*/87'957, cs_params);
216
217        // Starting with 19 unique UTXOs of similar effective value we will not find the solution due to exceeding the attempt limit
218        AddCoins(doppelganger_pool, {1 * CENT + cs_params.m_cost_of_change + 18}, cs_params);
219        TestBnBFail("Exhaust looking for smallest 8 of 19 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, cs_params);
220    }
221}
222
223BOOST_AUTO_TEST_CASE(bnb_exhaustion_with_solution_test)
224{
225    std::vector<OutputGroup> utxo_pool;
226    utxo_pool.reserve(19);
227
228    CAmount selection_target{800'000};
229    // A hard case with no exact-match solution: BnB must still report that the algorithm did not complete once the
230    // search is pushed into the attempt limit, even though it finds a solution within cost_of_change of the target.
231    for (size_t i = 0; i < 19; ++i) {
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(result->GetSelectedEffectiveValue() > selection_target + 28);
238    BOOST_CHECK_EQUAL(result->GetInputSet().size(), 8U);
239    BOOST_CHECK_EQUAL(result->GetSelectionsEvaluated(), 100'000U);
240    BOOST_CHECK(!result->GetAlgoCompleted());
241}
242
243BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
244{
245    // Create sets of UTXOs with the same effective amounts at different feerates (but different absolute amounts)
246    std::vector<OutputGroup> low_feerate_pool; // 5 sat/vB (default, and lower than long_term_feerate of 10 sat/vB)
247    AddCoins(low_feerate_pool, {2 * CENT, 3 * CENT, 5 * CENT, 10 * CENT});
248    TestBnBSuccess("Select many inputs at low feerates", low_feerate_pool, /*selection_target=*/10 * CENT, /*expected_input_amounts=*/{2 * CENT, 3 * CENT, 5 * CENT}, /*expected_attempts=*/6);
249
250    const CoinSelectionParams high_feerate_params = init_cs_params(/*eff_feerate=*/25'000);