Line data Source code
1 : // Copyright (c) 2017-2021 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 <test/util/setup_common.h>
6 :
7 : #include <consensus/amount.h>
8 : #include <node/context.h>
9 : #include <primitives/transaction.h>
10 : #include <random.h>
11 : #include <util/translation.h>
12 : #include <validation.h>
13 : #include <wallet/coincontrol.h>
14 : #include <wallet/coinselection.h>
15 : #include <wallet/spend.h>
16 : #include <wallet/test/wallet_test_fixture.h>
17 : #include <wallet/wallet.h>
18 :
19 : #include <algorithm>
20 : #include <boost/test/unit_test.hpp>
21 : #include <random>
22 :
23 : namespace wallet {
24 146 : BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup)
25 :
26 : // how many times to run all the tests to have a chance to catch errors that only show up with particular random shuffles
27 : #define RUN_TESTS 100
28 :
29 : // some tests fail 1% of the time due to bad luck.
30 : // we repeat those tests this many times and only complain if all iterations of the test fail
31 : #define RANDOM_REPEATS 5
32 :
33 : typedef std::set<COutput> CoinSet;
34 :
35 146 : static const CoinEligibilityFilter filter_standard(1, 6, 0);
36 146 : static const CoinEligibilityFilter filter_confirmed(1, 1, 0);
37 146 : static const CoinEligibilityFilter filter_standard_extra(6, 6, 0);
38 : static int nextLockTime = 0;
39 :
40 50088 : static void add_coin(const CAmount& nValue, int nInput, std::vector<COutput>& set)
41 : {
42 50088 : CMutableTransaction tx;
43 50088 : tx.vout.resize(nInput + 1);
44 50088 : tx.vout[nInput].nValue = nValue;
45 50088 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
46 50088 : set.emplace_back(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, /*fees=*/ 0);
47 50088 : }
48 :
49 19 : static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result)
50 : {
51 19 : CMutableTransaction tx;
52 19 : tx.vout.resize(nInput + 1);
53 19 : tx.vout[nInput].nValue = nValue;
54 19 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
55 19 : COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, /*fees=*/ 0);
56 19 : OutputGroup group;
57 19 : group.Insert(output, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ true);
58 19 : result.AddInput(group);
59 19 : }
60 :
61 24 : static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fee = 0, CAmount long_term_fee = 0)
62 : {
63 24 : CMutableTransaction tx;
64 24 : tx.vout.resize(nInput + 1);
65 24 : tx.vout[nInput].nValue = nValue;
66 24 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
67 24 : COutput coin(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ 148, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fee);
68 24 : coin.long_term_fee = long_term_fee;
69 24 : set.insert(coin);
70 24 : }
71 :
72 115544 : static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmount& nValue, CFeeRate feerate = CFeeRate(0), int nAge = 6*24, bool fIsFromMe = false, int nInput =0, bool spendable = false, int custom_size = 0)
73 : {
74 115544 : CMutableTransaction tx;
75 115544 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
76 115544 : tx.vout.resize(nInput + 1);
77 115544 : tx.vout[nInput].nValue = nValue;
78 115544 : if (spendable) {
79 5536 : tx.vout[nInput].scriptPubKey = GetScriptForDestination(*Assert(wallet.GetNewDestination("")));
80 5536 : }
81 115544 : uint256 txid = tx.GetHash();
82 :
83 115544 : LOCK(wallet.cs_wallet);
84 115544 : auto ret = wallet.mapWallet.emplace(std::piecewise_construct, std::forward_as_tuple(txid), std::forward_as_tuple(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
85 115544 : assert(ret.second);
86 115544 : CWalletTx& wtx = (*ret.first).second;
87 115544 : const auto& txout = wtx.tx->vout.at(nInput);
88 115544 : available_coins.legacy.emplace_back(COutPoint(wtx.GetHash(), nInput), txout, nAge, custom_size == 0 ? CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr) : custom_size, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate);
89 115544 : }
90 :
91 114 : inline std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
92 : {
93 114 : auto res{wallet::SelectCoinsBnB(utxo_pool, selection_target, cost_of_change, MAX_STANDARD_TX_SIZE)};
94 114 : return res ? std::optional<SelectionResult>(*res) : std::nullopt;
95 114 : }
96 :
97 : /** Check if SelectionResult a is equivalent to SelectionResult b.
98 : * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */
99 8 : static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
100 : {
101 8 : std::vector<CAmount> a_amts;
102 8 : std::vector<CAmount> b_amts;
103 25 : for (const auto& coin : a.GetInputSet()) {
104 17 : a_amts.push_back(coin.txout.nValue);
105 : }
106 25 : for (const auto& coin : b.GetInputSet()) {
107 17 : b_amts.push_back(coin.txout.nValue);
108 : }
109 8 : std::sort(a_amts.begin(), a_amts.end());
110 8 : std::sort(b_amts.begin(), b_amts.end());
111 :
112 8 : std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator> ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
113 8 : return ret.first == a_amts.end() && ret.second == b_amts.end();
114 8 : }
115 :
116 : /** Check if this selection is equal to another one. Equal means same inputs (i.e same value and prevout) */
117 1100 : static bool EqualResult(const SelectionResult& a, const SelectionResult& b)
118 : {
119 1100 : std::pair<CoinSet::iterator, CoinSet::iterator> ret = std::mismatch(a.GetInputSet().begin(), a.GetInputSet().end(), b.GetInputSet().begin(),
120 1143 : [](const COutput& a, const COutput& b) {
121 1143 : return a.outpoint == b.outpoint;
122 : });
123 1100 : return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end();
124 : }
125 :
126 2 : static int GetSelectionWeight(const SelectionResult& result)
127 : {
128 1383 : return std::accumulate(result.GetInputSet().cbegin(), result.GetInputSet().cend(), 0, [](int sum, const COutput& coin) {
129 1381 : return sum + std::max(coin.input_bytes, 0);
130 : });
131 : }
132 :
133 2 : static CAmount make_hard_case(int utxos, std::vector<COutput>& utxo_pool)
134 : {
135 2 : utxo_pool.clear();
136 2 : CAmount target = 0;
137 33 : for (int i = 0; i < utxos; ++i) {
138 31 : target += CAmount{1} << (utxos+i);
139 31 : add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool);
140 31 : add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool);
141 31 : }
142 2 : return target;
143 : }
144 :
145 2314 : inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins)
146 : {
147 2314 : static std::vector<OutputGroup> static_groups;
148 2314 : static_groups.clear();
149 279017 : for (auto& coin : available_coins) {
150 276703 : static_groups.emplace_back();
151 276703 : static_groups.back().Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false);
152 : }
153 2314 : return static_groups;
154 : }
155 :
156 5601 : inline std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, CAmount change_target, FastRandomContext& rng)
157 : {
158 5601 : auto res{wallet::KnapsackSolver(groups, nTargetValue, change_target, rng, MAX_STANDARD_TX_SIZE, /*fFullyMixedOnly=*/false, /*maxTxFee=*/DEFAULT_TRANSACTION_MAXFEE)};
159 5601 : return res ? std::optional<SelectionResult>(*res) : std::nullopt;
160 5601 : }
161 :
162 3401 : inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>& available_coins, CWallet& wallet, const CoinEligibilityFilter& filter)
163 : {
164 3401 : FastRandomContext rand{};
165 3401 : CoinSelectionParams coin_selection_params{
166 : rand,
167 : /*change_output_size=*/ 0,
168 : /*change_spend_size=*/ 0,
169 : /*min_change_target=*/ CENT,
170 3401 : /*effective_feerate=*/ CFeeRate(0),
171 3401 : /*long_term_feerate=*/ CFeeRate(0),
172 3401 : /*discard_feerate=*/ CFeeRate(0),
173 : /*tx_noinputs_size=*/ 0,
174 : /*avoid_partial=*/ false,
175 : };
176 3401 : static std::vector<OutputGroup> static_groups;
177 3401 : static_groups = GroupOutputs(wallet, available_coins, coin_selection_params, filter, /*positive_only=*/false);
178 : return static_groups;
179 3401 : }
180 :
181 : // Branch and bound coin selection tests
182 148 : BOOST_AUTO_TEST_CASE(bnb_search_test)
183 : {
184 1 : FastRandomContext rand{};
185 : // Setup
186 1 : std::vector<COutput> utxo_pool;
187 1 : SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB);
188 :
189 : /////////////////////////
190 : // Known Outcome tests //
191 : /////////////////////////
192 :
193 : // Empty utxo pool
194 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT));
195 :
196 : // Add utxos
197 1 : add_coin(1 * CENT, 1, utxo_pool);
198 1 : add_coin(2 * CENT, 2, utxo_pool);
199 1 : add_coin(3 * CENT, 3, utxo_pool);
200 1 : add_coin(4 * CENT, 4, utxo_pool);
201 :
202 : // Select 1 Cent
203 1 : add_coin(1 * CENT, 1, expected_result);
204 1 : const auto result1 = SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT);
205 1 : BOOST_CHECK(result1);
206 1 : BOOST_CHECK(EquivalentResult(expected_result, *result1));
207 1 : BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);
208 1 : expected_result.Clear();
209 :
210 : // Select 2 Cent
211 1 : add_coin(2 * CENT, 2, expected_result);
212 1 : const auto result2 = SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT);
213 1 : BOOST_CHECK(result2);
214 1 : BOOST_CHECK(EquivalentResult(expected_result, *result2));
215 1 : BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 2 * CENT);
216 1 : expected_result.Clear();
217 :
218 : // Select 5 Cent
219 1 : add_coin(3 * CENT, 3, expected_result);
220 1 : add_coin(2 * CENT, 2, expected_result);
221 1 : const auto result3 = SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT);
222 1 : BOOST_CHECK(result3);
223 1 : BOOST_CHECK(EquivalentResult(expected_result, *result3));
224 1 : BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 5 * CENT);
225 1 : expected_result.Clear();
226 :
227 : // Select 11 Cent, not possible
228 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT));
229 1 : expected_result.Clear();
230 :
231 : // Cost of change is greater than the difference between target value and utxo sum
232 1 : add_coin(1 * CENT, 1, expected_result);
233 1 : const auto result4 = SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT);
234 1 : BOOST_CHECK(result4);
235 1 : BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 1 * CENT);
236 1 : BOOST_CHECK(EquivalentResult(expected_result, *result4));
237 1 : expected_result.Clear();
238 :
239 : // Cost of change is less than the difference between target value and utxo sum
240 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0));
241 1 : expected_result.Clear();
242 :
243 : // Select 10 Cent
244 1 : add_coin(5 * CENT, 5, utxo_pool);
245 1 : add_coin(4 * CENT, 4, expected_result);
246 1 : add_coin(3 * CENT, 3, expected_result);
247 1 : add_coin(2 * CENT, 2, expected_result);
248 1 : add_coin(1 * CENT, 1, expected_result);
249 1 : const auto result5 = SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT);
250 1 : BOOST_CHECK(result5);
251 1 : BOOST_CHECK(EquivalentResult(expected_result, *result5));
252 1 : BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 10 * CENT);
253 1 : expected_result.Clear();
254 :
255 : // Select 0.25 Cent, not possible
256 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT));
257 1 : expected_result.Clear();
258 :
259 : // Iteration exhaustion test
260 1 : CAmount target = make_hard_case(17, utxo_pool);
261 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0)); // Should exhaust
262 1 : target = make_hard_case(14, utxo_pool);
263 1 : const auto result7 = SelectCoinsBnB(GroupCoins(utxo_pool), target, 0); // Should not exhaust
264 1 : BOOST_CHECK(result7);
265 :
266 : // Test same value early bailout optimization
267 1 : utxo_pool.clear();
268 1 : add_coin(7 * CENT, 7, expected_result);
269 1 : add_coin(7 * CENT, 7, expected_result);
270 1 : add_coin(7 * CENT, 7, expected_result);
271 1 : add_coin(7 * CENT, 7, expected_result);
272 1 : add_coin(2 * CENT, 7, expected_result);
273 1 : add_coin(7 * CENT, 7, utxo_pool);
274 1 : add_coin(7 * CENT, 7, utxo_pool);
275 1 : add_coin(7 * CENT, 7, utxo_pool);
276 1 : add_coin(7 * CENT, 7, utxo_pool);
277 1 : add_coin(2 * CENT, 7, utxo_pool);
278 50001 : for (int i = 0; i < 50000; ++i) {
279 50000 : add_coin(5 * CENT, 7, utxo_pool);
280 50000 : }
281 1 : const auto result8 = SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000);
282 1 : BOOST_CHECK(result8);
283 1 : BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 30 * CENT);
284 1 : BOOST_CHECK(EquivalentResult(expected_result, *result8));
285 :
286 : ////////////////////
287 : // Behavior tests //
288 : ////////////////////
289 : // Select 1 Cent with pool of only greater than 5 Cent
290 1 : utxo_pool.clear();
291 17 : for (int i = 5; i <= 20; ++i) {
292 16 : add_coin(i * CENT, i, utxo_pool);
293 16 : }
294 : // Run 100 times, to make sure it is never finding a solution
295 101 : for (int i = 0; i < 100; ++i) {
296 100 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT));
297 100 : }
298 :
299 : // Make sure that effective value is working in AttemptSelection when BnB is used
300 1 : CoinSelectionParams coin_selection_params_bnb{
301 : rand,
302 : /*change_output_size=*/ 0,
303 : /*change_spend_size=*/ 0,
304 : /*min_change_target=*/ 0,
305 1 : /*effective_feerate=*/ CFeeRate(3000),
306 1 : /*long_term_feerate=*/ CFeeRate(1000),
307 1 : /*discard_feerate=*/ CFeeRate(1000),
308 : /*tx_noinputs_size=*/ 0,
309 : /*avoid_partial=*/ false,
310 : };
311 1 : coin_selection_params_bnb.m_subtract_fee_outputs = true;
312 :
313 : {
314 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", m_args, CreateMockWalletDatabase());
315 1 : wallet->LoadWallet();
316 1 : LOCK(wallet->cs_wallet);
317 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
318 1 : wallet->SetupDescriptorScriptPubKeyMans("", "");
319 :
320 1 : CoinsResult available_coins;
321 :
322 1 : add_coin(available_coins, *wallet, 1, coin_selection_params_bnb.m_effective_feerate);
323 1 : available_coins.all().at(0).input_bytes = 40; // Make sure that it has a negative effective value. The next check should assert if this somehow got through. Otherwise it will fail
324 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(available_coins.all()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change));
325 :
326 : // Test fees subtracted from output:
327 1 : available_coins.clear();
328 1 : add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate);
329 1 : available_coins.all().at(0).input_bytes = 40;
330 1 : const auto result9 = SelectCoinsBnB(GroupCoins(available_coins.all()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change);
331 1 : BOOST_CHECK(result9);
332 1 : BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT);
333 1 : }
334 :
335 : {
336 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", m_args, CreateMockWalletDatabase());
337 1 : wallet->LoadWallet();
338 1 : LOCK(wallet->cs_wallet);
339 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
340 1 : wallet->SetupDescriptorScriptPubKeyMans("", "");
341 :
342 1 : CoinsResult available_coins;
343 :
344 1 : add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
345 1 : add_coin(available_coins, *wallet, 3 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
346 1 : add_coin(available_coins, *wallet, 2 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
347 1 : CCoinControl coin_control;
348 1 : coin_control.m_allow_other_inputs = true;
349 1 : coin_control.Select(available_coins.all().at(0).outpoint);
350 1 : coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
351 1 : const auto result10 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
352 1 : BOOST_CHECK(result10);
353 1 : }
354 : {
355 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", m_args, CreateMockWalletDatabase());
356 1 : wallet->LoadWallet();
357 1 : LOCK(wallet->cs_wallet);
358 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
359 1 : wallet->SetupDescriptorScriptPubKeyMans("", "");
360 :
361 1 : CoinsResult available_coins;
362 :
363 : // single coin should be selected when effective fee > long term fee
364 1 : coin_selection_params_bnb.m_effective_feerate = CFeeRate(5000);
365 1 : coin_selection_params_bnb.m_long_term_feerate = CFeeRate(3000);
366 :
367 1 : add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
368 1 : add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
369 1 : add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
370 :
371 1 : expected_result.Clear();
372 1 : add_coin(10 * CENT, 2, expected_result);
373 1 : CCoinControl coin_control;
374 1 : const auto result11 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
375 1 : BOOST_CHECK(EquivalentResult(expected_result, *result11));
376 1 : available_coins.clear();
377 :
378 : // more coins should be selected when effective fee < long term fee
379 1 : coin_selection_params_bnb.m_effective_feerate = CFeeRate(3000);
380 1 : coin_selection_params_bnb.m_long_term_feerate = CFeeRate(5000);
381 :
382 1 : add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
383 1 : add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
384 1 : add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
385 :
386 1 : expected_result.Clear();
387 1 : add_coin(9 * CENT, 2, expected_result);
388 1 : add_coin(1 * CENT, 2, expected_result);
389 1 : const auto result12 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
390 : // NOTE: Dash does not use BnB and therefore, this check will fail
391 : // BOOST_CHECK(EquivalentResult(expected_result, *result12));
392 1 : available_coins.clear();
393 :
394 : // pre selected coin should be selected even if disadvantageous
395 1 : coin_selection_params_bnb.m_effective_feerate = CFeeRate(5000);
396 1 : coin_selection_params_bnb.m_long_term_feerate = CFeeRate(3000);
397 :
398 1 : add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
399 1 : add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
400 1 : add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
401 :
402 1 : expected_result.Clear();
403 1 : add_coin(9 * CENT, 2, expected_result);
404 1 : add_coin(1 * CENT, 2, expected_result);
405 1 : coin_control.m_allow_other_inputs = true;
406 1 : coin_control.Select(available_coins.all().at(1).outpoint); // pre select 9 coin
407 1 : const auto result13 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb);
408 1 : BOOST_CHECK(EquivalentResult(expected_result, *result13));
409 1 : }
410 1 : }
411 :
412 148 : BOOST_AUTO_TEST_CASE(knapsack_solver_test)
413 : {
414 1 : FastRandomContext rand{};
415 5601 : const auto temp1{[&rand](std::vector<OutputGroup>& g, const CAmount& v, CAmount c) { return KnapsackSolver(g, v, c, rand); }};
416 1 : const auto KnapsackSolver{temp1};
417 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", m_args, CreateMockWalletDatabase());
418 1 : wallet->LoadWallet();
419 1 : LOCK(wallet->cs_wallet);
420 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
421 1 : wallet->SetupDescriptorScriptPubKeyMans("", "");
422 :
423 1 : CoinsResult available_coins;
424 :
425 : // test multiple times to allow for differences in the shuffle order
426 101 : for (int i = 0; i < RUN_TESTS; i++)
427 : {
428 100 : available_coins.clear();
429 :
430 : // with an empty wallet we can't even pay one cent
431 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 1 * CENT, CENT));
432 :
433 100 : add_coin(available_coins, *wallet, 1*CENT, CFeeRate(0), 4); // add a new 1 cent coin
434 :
435 : // with a new 1 cent coin, we still can't find a mature 1 cent
436 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 1 * CENT, CENT));
437 :
438 : // but we can find a new 1 cent
439 100 : const auto result1 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT);
440 100 : BOOST_CHECK(result1);
441 100 : BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);
442 :
443 100 : add_coin(available_coins, *wallet, 2*CENT); // add a mature 2 cent coin
444 :
445 : // we can't make 3 cents of mature coins
446 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 3 * CENT, CENT));
447 :
448 : // we can make 3 cents of new coins
449 100 : const auto result2 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 3 * CENT, CENT);
450 100 : BOOST_CHECK(result2);
451 100 : BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 3 * CENT);
452 :
453 100 : add_coin(available_coins, *wallet, 5*CENT); // add a mature 5 cent coin,
454 100 : add_coin(available_coins, *wallet, 10*CENT, CFeeRate(0), 3, true); // a new 10 cent coin sent from one of our own addresses
455 100 : add_coin(available_coins, *wallet, 20*CENT); // and a mature 20 cent coin
456 :
457 : // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38
458 :
459 : // we can't make 38 cents only if we disallow new coins:
460 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 38 * CENT, CENT));
461 : // we can't even make 37 cents if we don't allow new coins even if they're from us
462 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard_extra), 38 * CENT, CENT));
463 : // but we can make 37 cents if we accept new coins from ourself
464 100 : const auto result3 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 37 * CENT, CENT);
465 100 : BOOST_CHECK(result3);
466 100 : BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 37 * CENT);
467 : // and we can make 38 cents if we accept all new coins
468 100 : const auto result4 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 38 * CENT, CENT);
469 100 : BOOST_CHECK(result4);
470 100 : BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 38 * CENT);
471 :
472 : // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
473 100 : const auto result5 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 34 * CENT, CENT);
474 100 : BOOST_CHECK(result5);
475 100 : BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 35 * CENT); // but 35 cents is closest
476 100 : BOOST_CHECK_EQUAL(result5->GetInputSet().size(), 3U); // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got included (but possible)
477 :
478 : // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5
479 100 : const auto result6 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 7 * CENT, CENT);
480 100 : BOOST_CHECK(result6);
481 100 : BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 7 * CENT);
482 100 : BOOST_CHECK_EQUAL(result6->GetInputSet().size(), 2U);
483 :
484 : // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.
485 100 : const auto result7 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 8 * CENT, CENT);
486 100 : BOOST_CHECK(result7);
487 100 : BOOST_CHECK(result7->GetSelectedValue() == 8 * CENT);
488 100 : BOOST_CHECK_EQUAL(result7->GetInputSet().size(), 3U);
489 :
490 : // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)
491 100 : const auto result8 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 9 * CENT, CENT);
492 100 : BOOST_CHECK(result8);
493 100 : BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 10 * CENT);
494 100 : BOOST_CHECK_EQUAL(result8->GetInputSet().size(), 1U);
495 :
496 : // now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin
497 100 : available_coins.clear();
498 :
499 100 : add_coin(available_coins, *wallet, 6*CENT);
500 100 : add_coin(available_coins, *wallet, 7*CENT);
501 100 : add_coin(available_coins, *wallet, 8*CENT);
502 100 : add_coin(available_coins, *wallet, 20*CENT);
503 100 : add_coin(available_coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total
504 :
505 : // check that we have 71 and not 72
506 100 : const auto result9 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 71 * CENT, CENT);
507 100 : BOOST_CHECK(result9);
508 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 72 * CENT, CENT));
509 :
510 : // now try making 16 cents. the best smaller coins can do is 6+7+8 = 21; not as good at the next biggest coin, 20
511 100 : const auto result10 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 16 * CENT, CENT);
512 100 : BOOST_CHECK(result10);
513 100 : BOOST_CHECK_EQUAL(result10->GetSelectedValue(), 20 * CENT); // we should get 20 in one coin
514 100 : BOOST_CHECK_EQUAL(result10->GetInputSet().size(), 1U);
515 :
516 100 : add_coin(available_coins, *wallet, 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total
517 :
518 : // now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, better than the next biggest coin, 20
519 100 : const auto result11 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 16 * CENT, CENT);
520 100 : BOOST_CHECK(result11);
521 100 : BOOST_CHECK_EQUAL(result11->GetSelectedValue(), 18 * CENT); // we should get 18 in 3 coins
522 100 : BOOST_CHECK_EQUAL(result11->GetInputSet().size(), 3U);
523 :
524 100 : add_coin(available_coins, *wallet, 18*CENT); // now we have 5+6+7+8+18+20+30
525 :
526 : // and now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, the same as the next biggest coin, 18
527 100 : const auto result12 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 16 * CENT, CENT);
528 100 : BOOST_CHECK(result12);
529 100 : BOOST_CHECK_EQUAL(result12->GetSelectedValue(), 18 * CENT); // we should get 18 in 1 coin
530 100 : BOOST_CHECK_EQUAL(result12->GetInputSet().size(), 1U); // because in the event of a tie, the biggest coin wins
531 :
532 : // now try making 11 cents. we should get 5+6
533 100 : const auto result13 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 11 * CENT, CENT);
534 100 : BOOST_CHECK(result13);
535 100 : BOOST_CHECK_EQUAL(result13->GetSelectedValue(), 11 * CENT);
536 100 : BOOST_CHECK_EQUAL(result13->GetInputSet().size(), 2U);
537 :
538 : // check that the smallest bigger coin is used
539 100 : add_coin(available_coins, *wallet, 1*COIN);
540 100 : add_coin(available_coins, *wallet, 2*COIN);
541 100 : add_coin(available_coins, *wallet, 3*COIN);
542 100 : add_coin(available_coins, *wallet, 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
543 100 : const auto result14 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 95 * CENT, CENT);
544 100 : BOOST_CHECK(result14);
545 100 : BOOST_CHECK_EQUAL(result14->GetSelectedValue(), 1 * COIN); // we should get 1 BTC in 1 coin
546 100 : BOOST_CHECK_EQUAL(result14->GetInputSet().size(), 1U);
547 :
548 100 : const auto result15 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 195 * CENT, CENT);
549 100 : BOOST_CHECK(result15);
550 100 : BOOST_CHECK_EQUAL(result15->GetSelectedValue(), 2 * COIN); // we should get 2 BTC in 1 coin
551 100 : BOOST_CHECK_EQUAL(result15->GetInputSet().size(), 1U);
552 :
553 : // empty the wallet and start again, now with fractions of a cent, to test small change avoidance
554 :
555 100 : available_coins.clear();
556 100 : add_coin(available_coins, *wallet, CENT * 1 / 10);
557 100 : add_coin(available_coins, *wallet, CENT * 2 / 10);
558 100 : add_coin(available_coins, *wallet, CENT * 3 / 10);
559 100 : add_coin(available_coins, *wallet, CENT * 4 / 10);
560 100 : add_coin(available_coins, *wallet, CENT * 5 / 10);
561 :
562 : // try making 1 * CENT from the 1.5 * CENT
563 : // we'll get change smaller than CENT whatever happens, so can expect CENT exactly
564 100 : const auto result16 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT, CENT);
565 100 : BOOST_CHECK(result16);
566 100 : BOOST_CHECK_EQUAL(result16->GetSelectedValue(), CENT);
567 :
568 : // but if we add a bigger coin, small change is avoided
569 100 : add_coin(available_coins, *wallet, 1111*CENT);
570 :
571 : // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5
572 100 : const auto result17 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT);
573 100 : BOOST_CHECK(result17);
574 100 : BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * CENT); // we should get the exact amount
575 :
576 : // if we add more small coins:
577 100 : add_coin(available_coins, *wallet, CENT * 6 / 10);
578 100 : add_coin(available_coins, *wallet, CENT * 7 / 10);
579 :
580 : // and try again to make 1.0 * CENT
581 100 : const auto result18 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT);
582 100 : BOOST_CHECK(result18);
583 100 : BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * CENT); // we should get the exact amount
584 :
585 : // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
586 : // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change
587 100 : available_coins.clear();
588 2100 : for (int j = 0; j < 20; j++)
589 2000 : add_coin(available_coins, *wallet, 50000 * COIN);
590 :
591 100 : const auto result19 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 500000 * COIN, CENT);
592 100 : BOOST_CHECK(result19);
593 100 : BOOST_CHECK_EQUAL(result19->GetSelectedValue(), 500000 * COIN); // we should get the exact amount
594 100 : BOOST_CHECK_EQUAL(result19->GetInputSet().size(), 10U); // in ten coins
595 :
596 : // if there's not enough in the smaller coins to make at least 1 * CENT change (0.5+0.6+0.7 < 1.0+1.0),
597 : // we need to try finding an exact subset anyway
598 :
599 : // sometimes it will fail, and so we use the next biggest coin:
600 100 : available_coins.clear();
601 100 : add_coin(available_coins, *wallet, CENT * 5 / 10);
602 100 : add_coin(available_coins, *wallet, CENT * 6 / 10);
603 100 : add_coin(available_coins, *wallet, CENT * 7 / 10);
604 100 : add_coin(available_coins, *wallet, 1111 * CENT);
605 100 : const auto result20 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT);
606 100 : BOOST_CHECK(result20);
607 100 : BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * CENT); // we get the bigger coin
608 100 : BOOST_CHECK_EQUAL(result20->GetInputSet().size(), 1U);
609 :
610 : // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0)
611 100 : available_coins.clear();
612 100 : add_coin(available_coins, *wallet, CENT * 4 / 10);
613 100 : add_coin(available_coins, *wallet, CENT * 6 / 10);
614 100 : add_coin(available_coins, *wallet, CENT * 8 / 10);
615 100 : add_coin(available_coins, *wallet, 1111 * CENT);
616 100 : const auto result21 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT, CENT);
617 100 : BOOST_CHECK(result21);
618 100 : BOOST_CHECK_EQUAL(result21->GetSelectedValue(), CENT); // we should get the exact amount
619 100 : BOOST_CHECK_EQUAL(result21->GetInputSet().size(), 2U); // in two coins 0.4+0.6
620 :
621 : // test avoiding small change
622 100 : available_coins.clear();
623 100 : add_coin(available_coins, *wallet, CENT * 5 / 100);
624 100 : add_coin(available_coins, *wallet, CENT * 1);
625 100 : add_coin(available_coins, *wallet, CENT * 100);
626 :
627 : // trying to make 100.01 from these three coins
628 100 : const auto result22 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT * 10001 / 100, CENT);
629 100 : BOOST_CHECK(result22);
630 100 : BOOST_CHECK_EQUAL(result22->GetSelectedValue(), CENT * 10105 / 100); // we should get all coins
631 100 : BOOST_CHECK_EQUAL(result22->GetInputSet().size(), 3U);
632 :
633 : // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change
634 100 : const auto result23 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT * 9990 / 100, CENT);
635 100 : BOOST_CHECK(result23);
636 100 : BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * CENT);
637 100 : BOOST_CHECK_EQUAL(result23->GetInputSet().size(), 2U);
638 100 : }
639 :
640 : // test with many inputs
641 6 : for (CAmount amt=1500; amt < COIN; amt*=10) {
642 5 : available_coins.clear();
643 : // Create 676 inputs (= (old MAX_STANDARD_TX_SIZE == 100000) / 148 bytes per input)
644 3385 : for (uint16_t j = 0; j < 676; j++)
645 3380 : add_coin(available_coins, *wallet, amt);
646 :
647 : // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
648 505 : for (int i = 0; i < RUN_TESTS; i++) {
649 500 : const auto result24 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 2000, CENT);
650 500 : BOOST_CHECK(result24);
651 :
652 500 : if (amt - 2000 < CENT) {
653 : // needs more than one input:
654 300 : uint16_t returnSize = std::ceil((2000.0 + CENT)/amt);
655 300 : CAmount returnValue = amt * returnSize;
656 300 : BOOST_CHECK_EQUAL(result24->GetSelectedValue(), returnValue);
657 300 : BOOST_CHECK_EQUAL(result24->GetInputSet().size(), returnSize);
658 300 : } else {
659 : // one input is sufficient:
660 200 : BOOST_CHECK_EQUAL(result24->GetSelectedValue(), amt);
661 200 : BOOST_CHECK_EQUAL(result24->GetInputSet().size(), 1U);
662 : }
663 500 : }
664 5 : }
665 :
666 : // test randomness
667 : {
668 1 : available_coins.clear();
669 101 : for (int i2 = 0; i2 < 100; i2++)
670 100 : add_coin(available_coins, *wallet, COIN);
671 :
672 : // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
673 101 : for (int i = 0; i < RUN_TESTS; i++) {
674 : // picking 50 from 100 coins doesn't depend on the shuffle,
675 : // but does depend on randomness in the stochastic approximation code
676 100 : const auto result25 = KnapsackSolver(GroupCoins(available_coins.all()), 50 * COIN, CENT);
677 100 : BOOST_CHECK(result25);
678 100 : const auto result26 = KnapsackSolver(GroupCoins(available_coins.all()), 50 * COIN, CENT);
679 100 : BOOST_CHECK(result26);
680 100 : BOOST_CHECK(!EqualResult(*result25, *result26));
681 :
682 100 : int fails = 0;
683 600 : for (int j = 0; j < RANDOM_REPEATS; j++)
684 : {
685 : // Test that the KnapsackSolver selects randomly from equivalent coins (same value and same input size).
686 : // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice
687 : // which will cause it to fail.
688 : // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail
689 500 : const auto result27 = KnapsackSolver(GroupCoins(available_coins.all()), COIN, CENT);
690 500 : BOOST_CHECK(result27);
691 500 : const auto result28 = KnapsackSolver(GroupCoins(available_coins.all()), COIN, CENT);
692 500 : BOOST_CHECK(result28);
693 500 : if (EqualResult(*result27, *result28))
694 9 : fails++;
695 500 : }
696 100 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
697 100 : }
698 :
699 : // add 75 cents in small change. not enough to make 90 cents,
700 : // then try making 90 cents. there are multiple competing "smallest bigger" coins,
701 : // one of which should be picked at random
702 1 : add_coin(available_coins, *wallet, 5 * CENT);
703 1 : add_coin(available_coins, *wallet, 10 * CENT);
704 1 : add_coin(available_coins, *wallet, 15 * CENT);
705 1 : add_coin(available_coins, *wallet, 20 * CENT);
706 1 : add_coin(available_coins, *wallet, 25 * CENT);
707 :
708 101 : for (int i = 0; i < RUN_TESTS; i++) {
709 100 : int fails = 0;
710 600 : for (int j = 0; j < RANDOM_REPEATS; j++)
711 : {
712 500 : const auto result29 = KnapsackSolver(GroupCoins(available_coins.all()), 90 * CENT, CENT);
713 500 : BOOST_CHECK(result29);
714 500 : const auto result30 = KnapsackSolver(GroupCoins(available_coins.all()), 90 * CENT, CENT);
715 500 : BOOST_CHECK(result30);
716 500 : if (EqualResult(*result29, *result30))
717 5 : fails++;
718 500 : }
719 100 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
720 100 : }
721 : }
722 1 : }
723 :
724 148 : BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
725 : {
726 1 : FastRandomContext rand{};
727 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", m_args, CreateMockWalletDatabase());
728 1 : wallet->LoadWallet();
729 1 : LOCK(wallet->cs_wallet);
730 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
731 1 : wallet->SetupDescriptorScriptPubKeyMans("", "");
732 :
733 1 : CoinsResult available_coins;
734 :
735 : // Test vValue sort order
736 1001 : for (int i = 0; i < 1000; i++)
737 1000 : add_coin(available_coins, *wallet, 1000 * COIN);
738 1 : add_coin(available_coins, *wallet, 3 * COIN);
739 :
740 1 : const auto result = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 1003 * COIN, CENT, rand);
741 1 : BOOST_CHECK(result);
742 1 : BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN);
743 1 : BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U);
744 1 : }
745 :
746 : // Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value
747 148 : BOOST_AUTO_TEST_CASE(SelectCoins_test)
748 : {
749 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", m_args, CreateMockWalletDatabase());
750 1 : wallet->LoadWallet();
751 1 : LOCK(wallet->cs_wallet);
752 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
753 1 : wallet->SetupDescriptorScriptPubKeyMans("", "");
754 :
755 : // Random generator stuff
756 1 : std::default_random_engine generator;
757 1 : std::exponential_distribution<double> distribution (100);
758 1 : FastRandomContext rand;
759 :
760 : // Run this test 100 times
761 101 : for (int i = 0; i < 100; ++i)
762 : {
763 100 : CoinsResult available_coins;
764 100 : CAmount balance{0};
765 :
766 : // Make a wallet with 1000 exponentially distributed random inputs
767 100100 : for (int j = 0; j < 1000; ++j)
768 : {
769 100000 : CAmount val = distribution(generator)*10000000;
770 100000 : add_coin(available_coins, *wallet, val);
771 100000 : balance += val;
772 100000 : }
773 :
774 : // Generate a random fee rate in the range of 100 - 400
775 100 : CFeeRate rate(rand.randrange(300) + 100);
776 :
777 : // Generate a random target value between 1000 and wallet balance
778 100 : CAmount target = rand.randrange(balance - 1000) + 1000;
779 :
780 : // Perform selection
781 100 : CoinSelectionParams cs_params{
782 : rand,
783 : /*change_output_size=*/ 34,
784 : /*change_spend_size=*/ 148,
785 : /*min_change_target=*/ CENT,
786 100 : /*effective_feerate=*/ CFeeRate(0),
787 100 : /*long_term_feerate=*/ CFeeRate(0),
788 100 : /*discard_feerate=*/ CFeeRate(0),
789 : /*tx_noinputs_size=*/ 0,
790 : /*avoid_partial=*/ false,
791 : };
792 100 : CCoinControl cc;
793 100 : const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
794 100 : BOOST_CHECK(result);
795 100 : BOOST_CHECK_GE(result->GetSelectedValue(), target);
796 100 : }
797 1 : }
798 :
799 148 : BOOST_AUTO_TEST_CASE(waste_test)
800 : {
801 1 : CoinSet selection;
802 1 : const CAmount fee{100};
803 1 : const CAmount change_cost{125};
804 1 : const CAmount fee_diff{40};
805 1 : const CAmount in_amt{3 * COIN};
806 1 : const CAmount target{2 * COIN};
807 1 : const CAmount excess{in_amt - fee * 2 - target};
808 :
809 : // Waste with change is the change cost and difference between fee and long term fee
810 1 : add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
811 1 : add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
812 1 : const CAmount waste1 = GetSelectionWaste(selection, change_cost, target);
813 1 : BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, waste1);
814 1 : selection.clear();
815 :
816 : // Waste without change is the excess and difference between fee and long term fee
817 1 : add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
818 1 : add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
819 1 : const CAmount waste_nochange1 = GetSelectionWaste(selection, 0, target);
820 1 : BOOST_CHECK_EQUAL(fee_diff * 2 + excess, waste_nochange1);
821 1 : selection.clear();
822 :
823 : // Waste with change and fee == long term fee is just cost of change
824 1 : add_coin(1 * COIN, 1, selection, fee, fee);
825 1 : add_coin(2 * COIN, 2, selection, fee, fee);
826 1 : BOOST_CHECK_EQUAL(change_cost, GetSelectionWaste(selection, change_cost, target));
827 1 : selection.clear();
828 :
829 : // Waste without change and fee == long term fee is just the excess
830 1 : add_coin(1 * COIN, 1, selection, fee, fee);
831 1 : add_coin(2 * COIN, 2, selection, fee, fee);
832 1 : BOOST_CHECK_EQUAL(excess, GetSelectionWaste(selection, 0, target));
833 1 : selection.clear();
834 :
835 : // Waste will be greater when fee is greater, but long term fee is the same
836 1 : add_coin(1 * COIN, 1, selection, fee * 2, fee - fee_diff);
837 1 : add_coin(2 * COIN, 2, selection, fee * 2, fee - fee_diff);
838 1 : const CAmount waste2 = GetSelectionWaste(selection, change_cost, target);
839 1 : BOOST_CHECK_GT(waste2, waste1);
840 1 : selection.clear();
841 :
842 : // Waste with change is the change cost and difference between fee and long term fee
843 : // With long term fee greater than fee, waste should be less than when long term fee is less than fee
844 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
845 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
846 1 : const CAmount waste3 = GetSelectionWaste(selection, change_cost, target);
847 1 : BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, waste3);
848 1 : BOOST_CHECK_LT(waste3, waste1);
849 1 : selection.clear();
850 :
851 : // Waste without change is the excess and difference between fee and long term fee
852 : // With long term fee greater than fee, waste should be less than when long term fee is less than fee
853 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
854 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
855 1 : const CAmount waste_nochange2 = GetSelectionWaste(selection, 0, target);
856 1 : BOOST_CHECK_EQUAL(fee_diff * -2 + excess, waste_nochange2);
857 1 : BOOST_CHECK_LT(waste_nochange2, waste_nochange1);
858 1 : selection.clear();
859 :
860 : // No Waste when fee == long_term_fee, no change, and no excess
861 1 : add_coin(1 * COIN, 1, selection, fee, fee);
862 1 : add_coin(2 * COIN, 2, selection, fee, fee);
863 1 : const CAmount exact_target{in_amt - fee * 2};
864 1 : BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/0, exact_target));
865 1 : selection.clear();
866 :
867 : // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess
868 1 : const CAmount new_change_cost{fee_diff * 2};
869 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
870 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
871 1 : BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, new_change_cost, target));
872 1 : selection.clear();
873 :
874 : // No Waste when (fee - long_term_fee) == (-excess), no change cost
875 1 : const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
876 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
877 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
878 1 : BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/ 0, new_target));
879 1 : selection.clear();
880 :
881 : // Negative waste when the long term fee is greater than the current fee and the selected value == target
882 1 : const CAmount exact_target1{3 * COIN - 2 * fee};
883 1 : const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff))
884 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
885 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
886 1 : BOOST_CHECK_EQUAL(target_waste1, GetSelectionWaste(selection, /*change_cost=*/ 0, exact_target1));
887 1 : selection.clear();
888 :
889 : // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee))
890 1 : const CAmount large_fee_diff{90};
891 1 : const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
892 1 : add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff);
893 1 : add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff);
894 1 : BOOST_CHECK_EQUAL(target_waste2, GetSelectionWaste(selection, change_cost, target));
895 1 : }
896 :
897 148 : BOOST_AUTO_TEST_CASE(effective_value_test)
898 : {
899 1 : const int input_bytes = 148;
900 1 : const CFeeRate feerate(1000);
901 1 : const CAmount nValue = 10000;
902 1 : const int nInput = 0;
903 :
904 1 : CMutableTransaction tx;
905 1 : tx.vout.resize(1);
906 1 : tx.vout[nInput].nValue = nValue;
907 :
908 : // standard case, pass feerate in constructor
909 1 : COutput output1(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, input_bytes, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, feerate);
910 1 : const CAmount expected_ev1 = 9852; // 10000 - 148
911 1 : BOOST_CHECK_EQUAL(output1.GetEffectiveValue(), expected_ev1);
912 :
913 : // input bytes unknown (input_bytes = -1), pass feerate in constructor
914 1 : COutput output2(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, feerate);
915 1 : BOOST_CHECK_EQUAL(output2.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1
916 :
917 : // negative effective value, pass feerate in constructor
918 1 : COutput output3(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, input_bytes, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, CFeeRate(100000));
919 1 : const CAmount expected_ev3 = -4800; // 10000 - 14800
920 1 : BOOST_CHECK_EQUAL(output3.GetEffectiveValue(), expected_ev3);
921 :
922 : // standard case, pass fees in constructor
923 1 : const CAmount fees = 148;
924 1 : COutput output4(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, input_bytes, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fees);
925 1 : BOOST_CHECK_EQUAL(output4.GetEffectiveValue(), expected_ev1);
926 :
927 : // input bytes unknown (input_bytes = -1), pass fees in constructor
928 1 : COutput output5(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, /*fees=*/ 0);
929 1 : BOOST_CHECK_EQUAL(output5.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1
930 1 : }
931 :
932 3 : static util::Result<SelectionResult> SelectCoinsSRDResult(const CAmount& target,
933 : const CoinSelectionParams& cs_params,
934 : const node::NodeContext& m_node,
935 : int max_weight,
936 : std::function<CoinsResult(CWallet&)> coin_setup)
937 : {
938 3 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", gArgs, CreateMockWalletDatabase());
939 3 : wallet->LoadWallet();
940 3 : LOCK(wallet->cs_wallet);
941 3 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
942 3 : wallet->SetupDescriptorScriptPubKeyMans("", "");
943 :
944 3 : CoinEligibilityFilter filter(0, 0, 0);
945 3 : auto available_coins = coin_setup(*wallet);
946 3 : auto groups = GroupOutputs(*wallet, available_coins.all(), cs_params, filter, /*positive_only=*/true);
947 3 : return wallet::SelectCoinsSRD(groups, target, cs_params.rng_fast, max_weight);
948 3 : }
949 :
950 148 : BOOST_AUTO_TEST_CASE(srd_tests)
951 : {
952 1 : FastRandomContext rand;
953 1 : CoinSelectionParams dummy_params{
954 : rand,
955 : /*change_output_size=*/34,
956 : /*change_spend_size=*/68,
957 : /*min_change_target=*/CENT,
958 1 : /*effective_feerate=*/CFeeRate(0),
959 1 : /*long_term_feerate=*/CFeeRate(0),
960 1 : /*discard_feerate=*/CFeeRate(0),
961 : /*tx_noinputs_size=*/10 + 34,
962 : /*avoid_partial=*/false,
963 : };
964 :
965 : {
966 2 : const auto& res = SelectCoinsSRDResult(49.5L * COIN, dummy_params, m_node, /*max_weight=*/10000, [&](CWallet& wallet) {
967 1 : CoinsResult available_coins;
968 11 : for (int j = 0; j < 10; ++j) {
969 10 : add_coin(available_coins, wallet, CAmount(1 * COIN));
970 10 : add_coin(available_coins, wallet, CAmount(2 * COIN));
971 10 : }
972 1 : return available_coins;
973 1 : });
974 1 : BOOST_CHECK(!res);
975 1 : BOOST_CHECK(util::ErrorString(res).empty());
976 1 : }
977 :
978 : {
979 2 : const auto& res = SelectCoinsSRDResult(49.5L * COIN, dummy_params, m_node, /*max_weight=*/1000, [&](CWallet& wallet) {
980 1 : CoinsResult available_coins;
981 11 : for (int j = 0; j < 10; ++j) {
982 10 : add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(0), 144, false, 0, true, 68);
983 10 : add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(0), 144, false, 0, true, 68);
984 10 : }
985 1 : return available_coins;
986 1 : });
987 1 : BOOST_CHECK(!res);
988 1 : BOOST_CHECK(util::ErrorString(res).original.find("The inputs size exceeds the maximum weight") != std::string::npos);
989 1 : }
990 :
991 : {
992 2 : const auto& res = SelectCoinsSRDResult(25.33L * COIN, dummy_params, m_node, /*max_weight=*/10000, [&](CWallet& wallet) {
993 1 : CoinsResult available_coins;
994 61 : for (int j = 0; j < 60; ++j) {
995 60 : add_coin(available_coins, wallet, CAmount(0.33 * COIN), CFeeRate(0), 144, false, 0, true, 68);
996 60 : }
997 11 : for (int i = 0; i < 10; ++i) {
998 10 : add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(0), 144, false, 0, true, 68);
999 10 : }
1000 1 : return available_coins;
1001 1 : });
1002 1 : BOOST_CHECK(res);
1003 1 : }
1004 1 : }
1005 :
1006 3 : static std::optional<SelectionResult> select_coins(const CAmount& target, const CoinSelectionParams& cs_params, const CCoinControl& cc, std::function<CoinsResult(CWallet&)> coin_setup, const node::NodeContext& m_node)
1007 : {
1008 3 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", gArgs, CreateMockWalletDatabase());
1009 3 : wallet->LoadWallet();
1010 3 : LOCK(wallet->cs_wallet);
1011 3 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
1012 3 : wallet->SetupDescriptorScriptPubKeyMans("", "");
1013 :
1014 3 : auto available_coins = coin_setup(*wallet);
1015 3 : auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
1016 3 : if (result) {
1017 2 : BOOST_CHECK_LE(static_cast<int>(cs_params.tx_noinputs_size) + GetSelectionWeight(*result), MAX_STANDARD_TX_SIZE);
1018 2 : BOOST_CHECK_GE(result->GetSelectedValue(), target);
1019 2 : }
1020 3 : return result;
1021 3 : }
1022 :
1023 2 : static bool has_coin(const CoinSet& set, CAmount amount)
1024 : {
1025 9 : return std::any_of(set.begin(), set.end(), [&](const auto& coin) { return coin.GetEffectiveValue() == amount; });
1026 : }
1027 :
1028 148 : BOOST_AUTO_TEST_CASE(check_max_weight)
1029 : {
1030 1 : const CAmount target = 49.5L * COIN;
1031 1 : CCoinControl cc;
1032 :
1033 1 : FastRandomContext rand;
1034 1 : CoinSelectionParams cs_params{
1035 : rand,
1036 : /*change_output_size=*/34,
1037 : /*change_spend_size=*/68,
1038 : /*min_change_target=*/CENT,
1039 1 : /*effective_feerate=*/CFeeRate(0),
1040 1 : /*long_term_feerate=*/CFeeRate(0),
1041 1 : /*discard_feerate=*/CFeeRate(0),
1042 : /*tx_noinputs_size=*/10 + 34,
1043 : /*avoid_partial=*/false,
1044 : };
1045 :
1046 : {
1047 2 : const auto result = select_coins(target, cs_params, cc, [&](CWallet& wallet) {
1048 1 : CoinsResult available_coins;
1049 1516 : for (int j = 0; j < 1515; ++j) {
1050 1515 : add_coin(available_coins, wallet, CAmount(0.033 * COIN), CFeeRate(0), 144, false, 0, true, 68);
1051 1515 : }
1052 1 : add_coin(available_coins, wallet, CAmount(50 * COIN), CFeeRate(0), 144, false, 0, true, 68);
1053 1 : return available_coins;
1054 2 : }, m_node);
1055 :
1056 1 : BOOST_CHECK(result);
1057 1 : BOOST_CHECK_EQUAL(result->GetInputSet().size(), 1U);
1058 1 : BOOST_CHECK_EQUAL(result->GetInputSet().begin()->GetEffectiveValue(), 50 * COIN);
1059 1 : }
1060 :
1061 : {
1062 2 : const auto result = select_coins(target, cs_params, cc, [&](CWallet& wallet) {
1063 1 : CoinsResult available_coins;
1064 401 : for (int j = 0; j < 400; ++j) {
1065 400 : add_coin(available_coins, wallet, CAmount(0.0625 * COIN), CFeeRate(0), 144, false, 0, true, 68);
1066 400 : }
1067 2001 : for (int j = 0; j < 2000; ++j) {
1068 2000 : add_coin(available_coins, wallet, CAmount(0.025 * COIN), CFeeRate(0), 144, false, 0, true, 68);
1069 2000 : }
1070 1 : return available_coins;
1071 2 : }, m_node);
1072 :
1073 1 : BOOST_REQUIRE(result);
1074 1 : BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.0625 * COIN)));
1075 1 : BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.025 * COIN)));
1076 1 : }
1077 :
1078 : {
1079 2 : const auto result = select_coins(target, cs_params, cc, [&](CWallet& wallet) {
1080 1 : CoinsResult available_coins;
1081 1516 : for (int j = 0; j < 1515; ++j) {
1082 1515 : add_coin(available_coins, wallet, CAmount(0.033 * COIN), CFeeRate(0), 144, false, 0, true, 68);
1083 1515 : }
1084 1 : return available_coins;
1085 2 : }, m_node);
1086 :
1087 1 : BOOST_CHECK(!result);
1088 1 : }
1089 1 : }
1090 :
1091 : /* --------------------------- Dash-specific tests start here --------------------------- */
1092 148 : BOOST_AUTO_TEST_CASE(minimum_inputs_test)
1093 : {
1094 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), /*coinjoin_loader=*/nullptr, "", m_args, CreateMockWalletDatabase());
1095 1 : wallet->LoadWallet();
1096 1 : LOCK(wallet->cs_wallet);
1097 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
1098 1 : wallet->SetupDescriptorScriptPubKeyMans("", "");
1099 :
1100 : // Create coins (denominations) for a target that can be met without consuming all the coins
1101 1 : CoinsResult available_coins{};
1102 : CAmount target{25 * COIN};
1103 : add_coin(available_coins, *wallet, 9 * COIN, CFeeRate(0), /*nAge=*/6*24, /*fIsFromMe=*/false, /*nInput=*/0, /*spendable=*/true);
1104 : add_coin(available_coins, *wallet, 16 * COIN, CFeeRate(0), /*nAge=*/6*24, /*fIsFromMe=*/false, /*nInput=*/0, /*spendable=*/true);
1105 : add_coin(available_coins, *wallet, 24 * COIN, CFeeRate(0), /*nAge=*/6*24, /*fIsFromMe=*/false, /*nInput=*/0, /*spendable=*/true);
1106 :
1107 : // Setup coin control to select from the given coins (!m_allow_other_inputs) *but* consume as little
1108 : // as possible (!fRequireAllInputs) and select our coins.
1109 : CCoinControl coin_control{};
1110 : coin_control.m_allow_other_inputs = false;
1111 : coin_control.fRequireAllInputs = false;
1112 : for (const auto& coin : available_coins.all()) {
1113 : coin_control.Select(coin.outpoint);
1114 : }
1115 :
1116 : // Select coins
1117 : FastRandomContext rand{};
1118 : CoinSelectionParams coin_selection_params{
1119 : rand,
1120 : /*change_output_size=*/0,
1121 : /*change_spend_size=*/0,
1122 : /*min_change_target=*/CENT,
1123 : /*effective_feerate=*/CFeeRate(0),
1124 : /*long_term_feerate=*/CFeeRate(0),
1125 : /*discard_feerate=*/CFeeRate(0),
1126 : /*tx_noinputs_size=*/0,
1127 : /*avoid_partial=*/false,
1128 : };
1129 : auto result = SelectCoins(*wallet, available_coins, target, coin_control, coin_selection_params);
1130 : BOOST_REQUIRE(result);
1131 :
1132 : // Should consume only the first two coins (9 + 16) >= 25 and account correctly
1133 : BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2);
1134 : BOOST_CHECK_EQUAL(result->GetSelectedValue(), 25 * COIN);
1135 0 : }
1136 :
1137 146 : BOOST_AUTO_TEST_SUITE_END()
1138 : } // namespace wallet
|
