Bitcoin Core 29.99.0
P2P Digital Currency
coinselection_tests.cpp
Go to the documentation of this file.
1// Copyright (c) 2024 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>
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;
17
22{
24 /*rng_fast*/default_rand,
25 /*change_output_size=*/31,
26 /*change_spend_size=*/68,
27 /*min_change_target=*/50'000,
28 /*effective_feerate=*/CFeeRate(5000),
29 /*long_term_feerate=*/CFeeRate(10'000),
30 /*discard_feerate=*/CFeeRate(3000),
31 /*tx_noinputs_size=*/11 + 31, //static header size + output size
32 /*avoid_partial=*/false,
33 };
34 dcsp.m_change_fee = /*155 sats=*/dcsp.m_effective_feerate.GetFee(dcsp.change_output_size);
35 dcsp.min_viable_change = /*204 sats=*/dcsp.m_discard_feerate.GetFee(dcsp.change_spend_size);
36 dcsp.m_cost_of_change = /*204 + 155 sats=*/dcsp.min_viable_change + dcsp.m_change_fee;
37 dcsp.m_subtract_fee_outputs = false;
38 return dcsp;
39}
40
42
44static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, CoinSelectionParams cs_params = default_cs_params, int custom_spending_vsize = 68)
45{
46 // Always assume that we only have one input
48 tx.vout.resize(1);
49 CAmount fees = cs_params.m_effective_feerate.GetFee(custom_spending_vsize);
50 tx.vout[0].nValue = amount + int(is_eff_value) * fees;
51 tx.nLockTime = next_lock_time++; // so all transactions get different hashes
52 OutputGroup group(cs_params);
53 group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /*depth=*/1, /*input_bytes=*/custom_spending_vsize, /*spendable=*/true, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/fees), /*ancestors=*/0, /*descendants=*/0);
54 return group;
55}
56
58static void AddCoins(std::vector<OutputGroup>& utxo_pool, std::vector<CAmount> coins, CoinSelectionParams cs_params = default_cs_params)
59{
60 for (CAmount c : coins) {
61 utxo_pool.push_back(MakeCoin(c, true, cs_params));
62 }
63}
64
66static void AddDuplicateCoins(std::vector<OutputGroup>& utxo_pool, int count, int amount, CoinSelectionParams cs_params = default_cs_params) {
67 for (int i = 0 ; i < count; ++i) {
68 utxo_pool.push_back(MakeCoin(amount, true, cs_params));
69 }
70}
71
75{
76 std::vector<CAmount> a_amts;
77 std::vector<CAmount> b_amts;
78 for (const auto& coin : a.GetInputSet()) {
79 a_amts.push_back(coin->txout.nValue);
80 }
81 for (const auto& coin : b.GetInputSet()) {
82 b_amts.push_back(coin->txout.nValue);
83 }
84 std::sort(a_amts.begin(), a_amts.end());
85 std::sort(b_amts.begin(), b_amts.end());
86
87 auto ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
88 return ret.first == a_amts.end() && ret.second == b_amts.end();
89}
90
91static std::string InputAmountsToString(const SelectionResult& selection)
92{
93 return "[" + util::Join(selection.GetInputSet(), " ", [](const auto& input){ return util::ToString(input->txout.nValue);}) + "]";
94}
95
96static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CoinSelectionParams& cs_params = default_cs_params, int custom_spending_vsize = 68)
97{
99 CAmount expected_amount = 0;
100 for (CAmount input_amount : expected_input_amounts) {
101 OutputGroup group = MakeCoin(input_amount, true, cs_params, custom_spending_vsize);
102 expected_amount += group.m_value;
103 expected_result.AddInput(group);
104 }
105
106 const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT);
107 BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title);
108 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)));
109 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()));
110}
111
112static void TestBnBFail(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target)
113{
114 BOOST_CHECK_MESSAGE(!SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT), "BnB-Fail: " + test_title);
115}
116
118{
119 std::vector<int> feerates = {0, 1, 5'000, 10'000, 25'000, 59'764, 500'000, 999'000, 1'500'000};
120
121 for (int feerate : feerates) {
122 std::vector<OutputGroup> utxo_pool;
123
125 cs_params.m_effective_feerate = CFeeRate{feerate};
126
127 // Fail for empty UTXO pool
128 TestBnBFail("Empty UTXO pool", utxo_pool, /*selection_target=*/1 * CENT);
129
130 AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT}, cs_params);
131
132 // Simple success cases
133 TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/1 * CENT, /*expected_input_amounts=*/{1 * CENT}, cs_params);
134 TestBnBSuccess("Select middle UTXO", utxo_pool, /*selection_target=*/3 * CENT, /*expected_input_amounts=*/{3 * CENT}, cs_params);
135 TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/5 * CENT, /*expected_input_amounts=*/{5 * CENT}, cs_params);
136 TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/4 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, cs_params);
137 TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/9 * CENT, /*expected_input_amounts=*/{1 * CENT, 3 * CENT, 5 * CENT}, cs_params);
138
139 // BnB finds changeless solution while overshooting by up to cost_of_change
140 TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/4 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/{1 * CENT, 3 * CENT}, cs_params);
141
142 // BnB fails to find changeless solution when overshooting by cost_of_change + 1 sat
143 TestBnBFail("Overshoot upper bound", utxo_pool, /*selection_target=*/4 * CENT - default_cs_params.m_cost_of_change - 1);
144
145 // Simple cases without BnB solution
146 TestBnBFail("Smallest combination too big", utxo_pool, /*selection_target=*/0.5 * CENT);
147 TestBnBFail("No UTXO combination in target window", utxo_pool, /*selection_target=*/7 * CENT);
148 TestBnBFail("Select more than available", utxo_pool, /*selection_target=*/10 * CENT);
149
150 // Test skipping of equivalent input sets
151 std::vector<OutputGroup> clone_pool;
152 AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT}, cs_params);
153 AddDuplicateCoins(clone_pool, 50'000, 5 * CENT, cs_params);
154 TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT}, cs_params);
155
156 /* Test BnB attempt limit (`TOTAL_TRIES`)
157 *
158 * Generally, on a diverse UTXO pool BnB will quickly pass over UTXOs bigger than the target and then start
159 * combining small counts of UTXOs that in sum remain under the selection_target+cost_of_change. When there are
160 * multiple UTXOs that have matching amount and cost, combinations with equivalent input sets are skipped. The
161 * UTXO pool for this test is specifically crafted to create as much branching as possible. The selection target
162 * is 8 CENT while all UTXOs are slightly bigger than 1 CENT. The smallest eight are 100,000…100,007 sats, while
163 * the larger nine are 100,368…100,375 (i.e., 100,008…100,016 sats plus cost_of_change (359 sats)).
164 *
165 * Because BnB will only select input sets that fall between selection_target and selection_target +
166 * cost_of_change, and the search traverses the UTXO pool from large to small amounts, the search will visit
167 * every single combination of eight inputs. All except the last combination will overshoot by more than
168 * cost_of_change on the eighth input, because the larger nine inputs each exceed 1 CENT by more than
169 * cost_of_change. Only the last combination consisting of the eight smallest UTXOs falls into the target
170 * window.
171 */
172 std::vector<OutputGroup> doppelganger_pool;
173 std::vector<CAmount> doppelgangers;
174 std::vector<CAmount> expected_inputs;
175 for (int i = 0; i < 17; ++i) {
176 if (i < 8) {
177 // The eight smallest UTXOs can be combined to create expected_result
178 doppelgangers.push_back(1 * CENT + i);
179 expected_inputs.push_back(doppelgangers[i]);
180 } else {
181 // Any eight UTXOs including at least one UTXO with the added cost_of_change will exceed target window
182 doppelgangers.push_back(1 * CENT + default_cs_params.m_cost_of_change + i);
183 }
184 }
185 AddCoins(doppelganger_pool, doppelgangers, cs_params);
186 // Among up to 17 unique UTXOs of similar effective value we will find a solution composed of the eight smallest UTXOs
187 TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs, cs_params);
188
189 // Starting with 18 unique UTXOs of similar effective value we will not find the solution due to exceeding the attempt limit
190 AddCoins(doppelganger_pool, {1 * CENT + default_cs_params.m_cost_of_change + 17}, cs_params);
191 TestBnBFail("Exhaust looking for smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT);
192 }
193}
194
195BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
196{
197 // Create sets of UTXOs with the same effective amounts at different feerates (but different absolute amounts)
198 std::vector<OutputGroup> low_feerate_pool; // 5 sat/vB (default, and lower than long_term_feerate of 10 sat/vB)
199 AddCoins(low_feerate_pool, {2 * CENT, 3 * CENT, 5 * CENT, 10 * CENT});
200 TestBnBSuccess("Select many inputs at low feerates", low_feerate_pool, /*selection_target=*/10 * CENT, /*expected_input_amounts=*/{2 * CENT, 3 * CENT, 5 * CENT});
201
202 CoinSelectionParams high_feerate_params = init_default_params();
203 high_feerate_params.m_effective_feerate = CFeeRate{25'000};
204 std::vector<OutputGroup> high_feerate_pool; // 25 sat/vB (greater than long_term_feerate of 10 sat/vB)
205 AddCoins(high_feerate_pool, {2 * CENT, 3 * CENT, 5 * CENT, 10 * CENT}, high_feerate_params);
206 TestBnBSuccess("Select one input at high feerates", high_feerate_pool, /*selection_target=*/10 * CENT, /*expected_input_amounts=*/{10 * CENT}, high_feerate_params);
207
208 // Add heavy inputs {6, 7} to existing {2, 3, 5, 10}
209 low_feerate_pool.push_back(MakeCoin(6 * CENT, true, default_cs_params, /*custom_spending_vsize=*/500));
210 low_feerate_pool.push_back(MakeCoin(7 * CENT, true, default_cs_params, /*custom_spending_vsize=*/500));
211 TestBnBSuccess("Prefer two heavy inputs over two light inputs at low feerates", low_feerate_pool, /*selection_target=*/13 * CENT, /*expected_input_amounts=*/{6 * CENT, 7 * CENT}, default_cs_params, /*custom_spending_vsize=*/500);
212
213 high_feerate_pool.push_back(MakeCoin(6 * CENT, true, high_feerate_params, /*custom_spending_vsize=*/500));
214 high_feerate_pool.push_back(MakeCoin(7 * CENT, true, high_feerate_params, /*custom_spending_vsize=*/500));
215 TestBnBSuccess("Prefer two light inputs over two heavy inputs at high feerates", high_feerate_pool, /*selection_target=*/13 * CENT, /*expected_input_amounts=*/{3 * CENT, 10 * CENT}, high_feerate_params);
216}
217
219} // namespace wallet
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
int ret
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
CAmount GetFee(uint32_t num_bytes) const
Return the fee in satoshis for the given vsize in vbytes.
Definition: feerate.cpp:23
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:29
Fast randomness source.
Definition: random.h:377
BOOST_FIXTURE_TEST_SUITE(cuckoocache_tests, BasicTestingSetup)
Test Suite for CuckooCache.
BOOST_AUTO_TEST_SUITE_END()
auto Join(const C &container, const S &separator, UnaryOp unary_op)
Join all container items.
Definition: string.h:192
static OutputGroup MakeCoin(const CAmount &amount, bool is_eff_value=true, CoinSelectionParams cs_params=default_cs_params, int custom_spending_vsize=68)
Make one OutputGroup with a single UTXO that either has a given effective value (default) or a given ...
util::Result< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, int max_selection_weight)
static bool HaveEquivalentValues(const SelectionResult &a, const SelectionResult &b)
Check if SelectionResult a is equivalent to SelectionResult b.
static void TestBnBFail(std::string test_title, std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target)
static void AddDuplicateCoins(std::vector< OutputGroup > &utxo_pool, int count, int amount, CoinSelectionParams cs_params=default_cs_params)
Make multiple coins that share the same effective value.
BOOST_AUTO_TEST_CASE(bnb_test)
static int next_lock_time
static const CoinSelectionParams default_cs_params
static void AddCoins(std::vector< OutputGroup > &utxo_pool, std::vector< CAmount > coins, CoinSelectionParams cs_params=default_cs_params)
Make multiple OutputGroups with the given values as their effective value.
static CoinSelectionParams init_default_params()
Default coin selection parameters (dcsp) allow us to only explicitly set parameters when a diverging ...
static void TestBnBSuccess(std::string test_title, std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const std::vector< CAmount > &expected_input_amounts, const CoinSelectionParams &cs_params=default_cs_params, int custom_spending_vsize=68)
static FastRandomContext default_rand
static std::string InputAmountsToString(const SelectionResult &selection)
static constexpr int32_t MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
Definition: policy.h:34
static constexpr CAmount CENT
Definition: setup_common.h:47
A mutable version of CTransaction.
Definition: transaction.h:378
std::vector< CTxOut > vout
Definition: transaction.h:380
Txid GetHash() const
Compute the hash of this CMutableTransaction.
Definition: transaction.cpp:69
Testing setup that configures a complete environment.
Definition: setup_common.h:121
Parameters for one iteration of Coin Selection.
CFeeRate m_effective_feerate
The targeted feerate of the transaction being built.
CAmount m_cost_of_change
Cost of creating the change output + cost of spending the change output in the future.
A group of UTXOs paid to the same output script.
const std::set< std::shared_ptr< COutput > > & GetInputSet() const
Get m_selected_inputs.
void AddInput(const OutputGroup &group)
static int count
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1172