Bitcoin ABC 0.34.3
P2P Digital Currency
Loading...
Searching...
No Matches
coinselector_tests.cpp
Go to the documentation of this file.
1// Copyright (c) 2017 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 <chainparams.h> // For Params
6#include <consensus/amount.h>
7#include <node/context.h>
8#include <primitives/transaction.h>
9#include <random.h>
10#include <wallet/coincontrol.h>
11#include <wallet/coinselection.h>
12#include <wallet/spend.h>
13#include <wallet/wallet.h>
14
15#include <test/util/setup_common.h>
16#include <wallet/test/wallet_test_fixture.h>
17
18#include <boost/test/unit_test.hpp>
19
20#include <memory>
21#include <random>
22
23BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup)
24
25// how many times to run all the tests to have a chance to catch errors that
26// 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
31// the test fail
32#define RANDOM_REPEATS 5
33
34typedef std::set<CInputCoin> CoinSet;
35
36static std::vector<COutput> vCoins;
37static node::NodeContext testNode;
38static Amount balance = Amount::zero();
39
40CoinEligibilityFilter filter_standard(1, 6);
41CoinEligibilityFilter filter_confirmed(1, 1);
42CoinEligibilityFilter filter_standard_extra(6, 6);
43CoinSelectionParams coin_selection_params(false, 0, 0, CFeeRate(Amount::zero()),
44 0, false);
45
46static void add_coin(const Amount nValue, int nInput,
47 std::vector<CInputCoin> &set) {
48 CMutableTransaction tx;
49 tx.vout.resize(nInput + 1);
50 tx.vout[nInput].nValue = nValue;
51 set.emplace_back(MakeTransactionRef(tx), nInput);
52}
53
54static void add_coin(const Amount nValue, int nInput, CoinSet &set) {
55 CMutableTransaction tx;
56 tx.vout.resize(nInput + 1);
57 tx.vout[nInput].nValue = nValue;
58 set.emplace(MakeTransactionRef(tx), nInput);
59}
60
61static void add_coin(CWallet &wallet, const Amount nValue, int nAge = 6 * 24,
62 bool fIsFromMe = false, int nInput = 0,
63 bool spendable = false) {
64 balance += nValue;
65 static int nextLockTime = 0;
66 CMutableTransaction tx;
67 // so all transactions get different hashes
68 tx.nLockTime = nextLockTime++;
69 tx.vout.resize(nInput + 1);
70 tx.vout[nInput].nValue = nValue;
71 if (spendable) {
72 auto op_dest = wallet.GetNewDestination(OutputType::LEGACY, "");
73 assert(op_dest);
74 tx.vout[nInput].scriptPubKey = GetScriptForDestination(*op_dest);
75 }
76 if (fIsFromMe) {
77 // IsFromMe() returns (GetDebit() > 0), and GetDebit() is 0 if
78 // vin.empty(), so stop vin being empty, and cache a non-zero Debit to
79 // fake out IsFromMe()
80 tx.vin.resize(1);
81 }
82 CWalletTx *wtx = wallet.AddToWallet(MakeTransactionRef(std::move(tx)),
83 /* confirm= */ {});
84 if (fIsFromMe) {
85 wtx->m_amounts[CWalletTx::DEBIT].Set(ISMINE_SPENDABLE, SATOSHI);
86 wtx->m_is_cache_empty = false;
87 }
88 COutput output(wallet, *wtx, nInput, nAge, true /* spendable */,
89 true /* solvable */, true /* safe */);
90 vCoins.push_back(output);
91}
92
93static void empty_wallet() {
94 vCoins.clear();
95 balance = Amount::zero();
96}
97
98static bool equal_sets(CoinSet a, CoinSet b) {
99 std::pair<CoinSet::iterator, CoinSet::iterator> ret =
100 mismatch(a.begin(), a.end(), b.begin());
101 return ret.first == a.end() && ret.second == b.end();
102}
103
104static Amount make_hard_case(int utxos, std::vector<CInputCoin> &utxo_pool) {
105 utxo_pool.clear();
106 Amount target = Amount::zero();
107 for (int i = 0; i < utxos; ++i) {
108 const Amount base = (int64_t(1) << (utxos + i)) * SATOSHI;
109 target += base;
110 add_coin(base, 2 * i, utxo_pool);
111 add_coin(base + (int64_t(1) << (utxos - 1 - i)) * SATOSHI, 2 * i + 1,
112 utxo_pool);
113 }
114 return target;
115}
116
117inline std::vector<OutputGroup> &
118GroupCoins(const std::vector<CInputCoin> &coins) {
119 static std::vector<OutputGroup> static_groups;
120 static_groups.clear();
121 for (auto &coin : coins) {
122 static_groups.emplace_back();
123 static_groups.back().Insert(coin, 0, true, false);
124 }
125 return static_groups;
126}
127
128inline std::vector<OutputGroup> &GroupCoins(const std::vector<COutput> &coins) {
129 static std::vector<OutputGroup> static_groups;
130 static_groups.clear();
131 for (auto &coin : coins) {
132 // HACK: we can't figure out the is_me flag so we use the conditions
133 // defined below; perhaps set safe to false for !fIsFromMe in add_coin()
134 const bool is_me =
135 coin.tx->m_amounts[CWalletTx::DEBIT].m_cached[ISMINE_SPENDABLE] &&
136 coin.tx->m_amounts[CWalletTx::DEBIT].m_value[ISMINE_SPENDABLE] ==
137 SATOSHI;
138 static_groups.emplace_back();
139 static_groups.back().Insert(coin.GetInputCoin(), coin.nDepth, is_me,
140 false);
141 }
142 return static_groups;
143}
144
145// Branch and bound coin selection tests
146BOOST_AUTO_TEST_CASE(bnb_search_test) {
147 LOCK(m_wallet.cs_wallet);
148 m_wallet.SetupLegacyScriptPubKeyMan();
149
150 // Setup
151 std::vector<CInputCoin> utxo_pool;
152 CoinSet selection;
153 CoinSet actual_selection;
154 Amount value_ret = Amount::zero();
155 Amount not_input_fees = Amount::zero();
156
158 // Known Outcome tests //
160
161 // Empty utxo pool
162 BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, CENT / 2,
163 selection, value_ret, not_input_fees));
164 selection.clear();
165
166 // Add utxos
167 add_coin(1 * CENT, 1, utxo_pool);
168 add_coin(2 * CENT, 2, utxo_pool);
169 add_coin(3 * CENT, 3, utxo_pool);
170 add_coin(4 * CENT, 4, utxo_pool);
171
172 // Select 1 Cent
173 add_coin(1 * CENT, 1, actual_selection);
174 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, CENT / 2,
175 selection, value_ret, not_input_fees));
176 BOOST_CHECK(equal_sets(selection, actual_selection));
177 BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
178 actual_selection.clear();
179 selection.clear();
180
181 // Select 2 Cent
182 add_coin(2 * CENT, 2, actual_selection);
183 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, CENT / 2,
184 selection, value_ret, not_input_fees));
185 BOOST_CHECK(equal_sets(selection, actual_selection));
186 BOOST_CHECK_EQUAL(value_ret, 2 * CENT);
187 actual_selection.clear();
188 selection.clear();
189
190 // Select 5 Cent
191 add_coin(4 * CENT, 4, actual_selection);
192 add_coin(1 * CENT, 1, actual_selection);
193 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, CENT / 2,
194 selection, value_ret, not_input_fees));
195 BOOST_CHECK(equal_sets(selection, actual_selection));
196 BOOST_CHECK_EQUAL(value_ret, 5 * CENT);
197 actual_selection.clear();
198 selection.clear();
199
200 // Select 11 Cent, not possible
201 BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, CENT / 2,
202 selection, value_ret, not_input_fees));
203 actual_selection.clear();
204 selection.clear();
205
206 // Cost of change is greater than the difference between target value and
207 // utxo sum
208 add_coin(1 * CENT, 1, actual_selection);
209 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 9 * CENT / 10,
210 5 * CENT / 10, selection, value_ret,
211 not_input_fees));
212 BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
213 BOOST_CHECK(equal_sets(selection, actual_selection));
214 actual_selection.clear();
215 selection.clear();
216
217 // Cost of change is less than the difference between target value and utxo
218 // sum
219 BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 9 * CENT / 10,
220 Amount::zero(), selection, value_ret,
221 not_input_fees));
222 actual_selection.clear();
223 selection.clear();
224
225 // Select 10 Cent
226 add_coin(5 * CENT, 5, utxo_pool);
227 add_coin(5 * CENT, 5, actual_selection);
228 add_coin(4 * CENT, 4, actual_selection);
229 add_coin(1 * CENT, 1, actual_selection);
230 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, CENT / 2,
231 selection, value_ret, not_input_fees));
232 BOOST_CHECK(equal_sets(selection, actual_selection));
233 BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
234 actual_selection.clear();
235 selection.clear();
236
237 // Negative effective value
238 // Select 10 Cent but have 1 Cent not be possible because too small
239 add_coin(5 * CENT, 5, actual_selection);
240 add_coin(3 * CENT, 3, actual_selection);
241 add_coin(2 * CENT, 2, actual_selection);
242 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000 * SATOSHI,
243 selection, value_ret, not_input_fees));
244 BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
245 // FIXME: this test is redundant with the above, because 1 Cent is selected,
246 // not "too small" BOOST_CHECK(equal_sets(selection, actual_selection));
247
248 // Select 0.25 Cent, not possible
249 BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), CENT / 4, CENT / 2,
250 selection, value_ret, not_input_fees));
251 actual_selection.clear();
252 selection.clear();
253
254 // Iteration exhaustion test
255 Amount target = make_hard_case(17, utxo_pool);
256 // Should exhaust
257 BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, Amount::zero(),
258 selection, value_ret, not_input_fees));
259 target = make_hard_case(14, utxo_pool);
260 // Should not exhaust
261 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), target, Amount::zero(),
262 selection, value_ret, not_input_fees));
263
264 // Test same value early bailout optimization
265 utxo_pool.clear();
266 add_coin(7 * CENT, 7, actual_selection);
267 add_coin(7 * CENT, 7, actual_selection);
268 add_coin(7 * CENT, 7, actual_selection);
269 add_coin(7 * CENT, 7, actual_selection);
270 add_coin(2 * CENT, 7, actual_selection);
271 add_coin(7 * CENT, 7, utxo_pool);
272 add_coin(7 * CENT, 7, utxo_pool);
273 add_coin(7 * CENT, 7, utxo_pool);
274 add_coin(7 * CENT, 7, utxo_pool);
275 add_coin(2 * CENT, 7, utxo_pool);
276 for (int i = 0; i < 50000; ++i) {
277 add_coin(5 * CENT, 7, utxo_pool);
278 }
279 BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000 * SATOSHI,
280 selection, value_ret, not_input_fees));
281 BOOST_CHECK_EQUAL(value_ret, 30 * CENT);
282 BOOST_CHECK(equal_sets(selection, actual_selection));
283
285 // Behavior tests //
287 // Select 1 Cent with pool of only greater than 5 Cent
288 utxo_pool.clear();
289 for (int i = 5; i <= 20; ++i) {
290 add_coin(i * CENT, i, utxo_pool);
291 }
292 // Run 100 times, to make sure it is never finding a solution
293 for (int i = 0; i < 100; ++i) {
294 BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT,
295 selection, value_ret, not_input_fees));
296 }
297
298 // Make sure that effective value is working in SelectCoinsMinConf when BnB
299 // is used
300 CoinSelectionParams coin_selection_params_bnb(
301 true, 0, 0, CFeeRate(3000 * SATOSHI), 0, false);
302 CoinSet setCoinsRet;
303 Amount nValueRet;
304 bool bnb_used;
305 empty_wallet();
306 add_coin(m_wallet, SATOSHI);
307 // Make sure that it has a negative effective value. The next check should
308 // assert if this somehow got through. Otherwise it will fail
309 vCoins.at(0).nInputBytes = 40;
310 BOOST_CHECK(!SelectCoinsMinConf(m_wallet, 1 * CENT, filter_standard, vCoins,
311 setCoinsRet, nValueRet,
312 coin_selection_params_bnb, bnb_used));
313
314 // Test fees subtracted from output:
315 empty_wallet();
316 add_coin(m_wallet, 1 * CENT);
317 vCoins.at(0).nInputBytes = 40;
318 BOOST_CHECK(!SelectCoinsMinConf(m_wallet, 1 * CENT, filter_standard, vCoins,
319 setCoinsRet, nValueRet,
320 coin_selection_params_bnb, bnb_used));
321 coin_selection_params_bnb.m_subtract_fee_outputs = true;
322 BOOST_CHECK(SelectCoinsMinConf(m_wallet, 1 * CENT, filter_standard, vCoins,
323 setCoinsRet, nValueRet,
324 coin_selection_params_bnb, bnb_used));
325 BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
326
327 // Make sure that can use BnB when there are preset inputs
328 empty_wallet();
329 {
330 auto wallet = std::make_unique<CWallet>(m_node.chain.get(), "",
331 CreateMockWalletDatabase());
332 wallet->LoadWallet();
333 LOCK(wallet->cs_wallet);
334 wallet->SetupLegacyScriptPubKeyMan();
335 add_coin(*wallet, 5 * CENT, 6 * 24, false, 0, true);
336 add_coin(*wallet, 3 * CENT, 6 * 24, false, 0, true);
337 add_coin(*wallet, 2 * CENT, 6 * 24, false, 0, true);
338 CCoinControl coin_control;
339 coin_control.fAllowOtherInputs = true;
340 coin_control.Select(
341 COutPoint(vCoins.at(0).tx->GetId(), vCoins.at(0).i));
342 coin_selection_params_bnb.effective_fee = CFeeRate(Amount::zero());
343 BOOST_CHECK(SelectCoins(*wallet, vCoins, 10 * CENT, setCoinsRet,
344 nValueRet, coin_control,
345 coin_selection_params_bnb, bnb_used));
346 BOOST_CHECK(bnb_used);
347 BOOST_CHECK(coin_selection_params_bnb.use_bnb);
348 }
349}
350
351BOOST_AUTO_TEST_CASE(knapsack_solver_test) {
352 auto testChain = interfaces::MakeChain(testNode, Params());
353 CWallet testWallet(testChain.get(), "", CreateDummyWalletDatabase());
354
355 CoinSet setCoinsRet, setCoinsRet2;
356 Amount nValueRet;
357 bool bnb_used;
358
359 LOCK(testWallet.cs_wallet);
360 testWallet.SetupLegacyScriptPubKeyMan();
361
362 // test multiple times to allow for differences in the shuffle order
363 for (int i = 0; i < RUN_TESTS; i++) {
364 empty_wallet();
365
366 // with an empty wallet we can't even pay one cent
367 BOOST_CHECK(!SelectCoinsMinConf(testWallet, 1 * CENT, filter_standard,
368 vCoins, setCoinsRet, nValueRet,
369 coin_selection_params, bnb_used));
370
371 // add a new 1 cent coin
372 add_coin(testWallet, 1 * CENT, 4);
373
374 // with a new 1 cent coin, we still can't find a mature 1 cent
375 BOOST_CHECK(!SelectCoinsMinConf(testWallet, 1 * CENT, filter_standard,
376 vCoins, setCoinsRet, nValueRet,
377 coin_selection_params, bnb_used));
378
379 // but we can find a new 1 cent
380 BOOST_CHECK(SelectCoinsMinConf(testWallet, 1 * CENT, filter_confirmed,
381 vCoins, setCoinsRet, nValueRet,
382 coin_selection_params, bnb_used));
383 BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
384 // add a mature 2 cent coin
385 add_coin(testWallet, 2 * CENT);
386
387 // we can't make 3 cents of mature coins
388 BOOST_CHECK(!SelectCoinsMinConf(testWallet, 3 * CENT, filter_standard,
389 vCoins, setCoinsRet, nValueRet,
390 coin_selection_params, bnb_used));
391
392 // we can make 3 cents of new coins
393 BOOST_CHECK(SelectCoinsMinConf(testWallet, 3 * CENT, filter_confirmed,
394 vCoins, setCoinsRet, nValueRet,
395 coin_selection_params, bnb_used));
396 BOOST_CHECK_EQUAL(nValueRet, 3 * CENT);
397
398 // add a mature 5 cent coin,
399 add_coin(testWallet, 5 * CENT);
400 // a new 10 cent coin sent from one of our own addresses
401 add_coin(testWallet, 10 * CENT, 3, true);
402 // and a mature 20 cent coin
403 add_coin(testWallet, 20 * CENT);
404
405 // now we have new: 1+10=11 (of which 10 was self-sent), and mature:
406 // 2+5+20=27. total = 38
407
408 // we can't make 38 cents only if we disallow new coins:
409 BOOST_CHECK(!SelectCoinsMinConf(testWallet, 38 * CENT, filter_standard,
410 vCoins, setCoinsRet, nValueRet,
411 coin_selection_params, bnb_used));
412 // we can't even make 37 cents if we don't allow new coins even if
413 // they're from us
414 BOOST_CHECK(!SelectCoinsMinConf(
415 testWallet, 38 * CENT, filter_standard_extra, vCoins, setCoinsRet,
416 nValueRet, coin_selection_params, bnb_used));
417 // but we can make 37 cents if we accept new coins from ourself
418 BOOST_CHECK(SelectCoinsMinConf(testWallet, 37 * CENT, filter_standard,
419 vCoins, setCoinsRet, nValueRet,
420 coin_selection_params, bnb_used));
421 BOOST_CHECK_EQUAL(nValueRet, 37 * CENT);
422 // and we can make 38 cents if we accept all new coins
423 BOOST_CHECK(SelectCoinsMinConf(testWallet, 38 * CENT, filter_confirmed,
424 vCoins, setCoinsRet, nValueRet,
425 coin_selection_params, bnb_used));
426 BOOST_CHECK_EQUAL(nValueRet, 38 * CENT);
427
428 // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
429 BOOST_CHECK(SelectCoinsMinConf(testWallet, 34 * CENT, filter_confirmed,
430 vCoins, setCoinsRet, nValueRet,
431 coin_selection_params, bnb_used));
432 // but 35 cents is closest
433 BOOST_CHECK_EQUAL(nValueRet, 35 * CENT);
434 // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got
435 // included (but possible)
436 BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
437
438 // when we try making 7 cents, the smaller coins (1,2,5) are enough. We
439 // should see just 2+5
440 BOOST_CHECK(SelectCoinsMinConf(testWallet, 7 * CENT, filter_confirmed,
441 vCoins, setCoinsRet, nValueRet,
442 coin_selection_params, bnb_used));
443 BOOST_CHECK_EQUAL(nValueRet, 7 * CENT);
444 BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
445
446 // when we try making 8 cents, the smaller coins (1,2,5) are exactly
447 // enough.
448 BOOST_CHECK(SelectCoinsMinConf(testWallet, 8 * CENT, filter_confirmed,
449 vCoins, setCoinsRet, nValueRet,
450 coin_selection_params, bnb_used));
451 BOOST_CHECK(nValueRet == 8 * CENT);
452 BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
453
454 // when we try making 9 cents, no subset of smaller coins is enough, and
455 // we get the next bigger coin (10)
456 BOOST_CHECK(SelectCoinsMinConf(testWallet, 9 * CENT, filter_confirmed,
457 vCoins, setCoinsRet, nValueRet,
458 coin_selection_params, bnb_used));
459 BOOST_CHECK_EQUAL(nValueRet, 10 * CENT);
460 BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
461
462 // now clear out the wallet and start again to test choosing between
463 // subsets of smaller coins and the next biggest coin
464 empty_wallet();
465
466 add_coin(testWallet, 6 * CENT);
467 add_coin(testWallet, 7 * CENT);
468 add_coin(testWallet, 8 * CENT);
469 add_coin(testWallet, 20 * CENT);
470 // now we have 6+7+8+20+30 = 71 cents total
471 add_coin(testWallet, 30 * CENT);
472
473 // check that we have 71 and not 72
474 BOOST_CHECK(SelectCoinsMinConf(testWallet, 71 * CENT, filter_confirmed,
475 vCoins, setCoinsRet, nValueRet,
476 coin_selection_params, bnb_used));
477 BOOST_CHECK(!SelectCoinsMinConf(testWallet, 72 * CENT, filter_confirmed,
478 vCoins, setCoinsRet, nValueRet,
479 coin_selection_params, bnb_used));
480
481 // now try making 16 cents. the best smaller coins can do is 6+7+8 =
482 // 21; not as good at the next biggest coin, 20
483 BOOST_CHECK(SelectCoinsMinConf(testWallet, 16 * CENT, filter_confirmed,
484 vCoins, setCoinsRet, nValueRet,
485 coin_selection_params, bnb_used));
486 // we should get 20 in one coin
487 BOOST_CHECK_EQUAL(nValueRet, 20 * CENT);
488 BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
489
490 // now we have 5+6+7+8+20+30 = 75 cents total
491 add_coin(testWallet, 5 * CENT);
492
493 // now if we try making 16 cents again, the smaller coins can make 5+6+7
494 // = 18 cents, better than the next biggest coin, 20
495 BOOST_CHECK(SelectCoinsMinConf(testWallet, 16 * CENT, filter_confirmed,
496 vCoins, setCoinsRet, nValueRet,
497 coin_selection_params, bnb_used));
498 // we should get 18 in 3 coins
499 BOOST_CHECK_EQUAL(nValueRet, 18 * CENT);
500 BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
501
502 // now we have 5+6+7+8+18+20+30
503 add_coin(testWallet, 18 * CENT);
504
505 // and now if we try making 16 cents again, the smaller coins can make
506 // 5+6+7 = 18 cents, the same as the next biggest coin, 18
507 BOOST_CHECK(SelectCoinsMinConf(testWallet, 16 * CENT, filter_confirmed,
508 vCoins, setCoinsRet, nValueRet,
509 coin_selection_params, bnb_used));
510 // we should get 18 in 1 coin
511 BOOST_CHECK_EQUAL(nValueRet, 18 * CENT);
512 // because in the event of a tie, the biggest coin wins
513 BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
514
515 // now try making 11 cents. we should get 5+6
516 BOOST_CHECK(SelectCoinsMinConf(testWallet, 11 * CENT, filter_confirmed,
517 vCoins, setCoinsRet, nValueRet,
518 coin_selection_params, bnb_used));
519 BOOST_CHECK_EQUAL(nValueRet, 11 * CENT);
520 BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
521
522 // check that the smallest bigger coin is used
523 add_coin(testWallet, 1 * COIN);
524 add_coin(testWallet, 2 * COIN);
525 add_coin(testWallet, 3 * COIN);
526 // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
527 add_coin(testWallet, 4 * COIN);
528 BOOST_CHECK(SelectCoinsMinConf(testWallet, 95 * CENT, filter_confirmed,
529 vCoins, setCoinsRet, nValueRet,
530 coin_selection_params, bnb_used));
531 // we should get 1,000,000 XEC in 1 coin
532 BOOST_CHECK_EQUAL(nValueRet, 1 * COIN);
533 BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
534
535 BOOST_CHECK(SelectCoinsMinConf(testWallet, 195 * CENT, filter_confirmed,
536 vCoins, setCoinsRet, nValueRet,
537 coin_selection_params, bnb_used));
538 // we should get 2,000,000 XEC in 1 coin
539 BOOST_CHECK_EQUAL(nValueRet, 2 * COIN);
540 BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
541
542 // empty the wallet and start again, now with fractions of a cent, to
543 // test small change avoidance
544
545 empty_wallet();
546 add_coin(testWallet, 1 * MIN_CHANGE / 10);
547 add_coin(testWallet, 2 * MIN_CHANGE / 10);
548 add_coin(testWallet, 3 * MIN_CHANGE / 10);
549 add_coin(testWallet, 4 * MIN_CHANGE / 10);
550 add_coin(testWallet, 5 * MIN_CHANGE / 10);
551
552 // try making 1 * MIN_CHANGE from the 1.5 * MIN_CHANGE
553 // we'll get change smaller than MIN_CHANGE whatever happens, so can
554 // expect MIN_CHANGE exactly
555 BOOST_CHECK(SelectCoinsMinConf(testWallet, MIN_CHANGE, filter_confirmed,
556 vCoins, setCoinsRet, nValueRet,
557 coin_selection_params, bnb_used));
558 BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE);
559
560 // but if we add a bigger coin, small change is avoided
561 add_coin(testWallet, 1111 * MIN_CHANGE);
562
563 // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5
564 BOOST_CHECK(SelectCoinsMinConf(
565 testWallet, 1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet,
566 nValueRet, coin_selection_params, bnb_used));
567 // we should get the exact amount
568 BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE);
569
570 // if we add more small coins:
571 add_coin(testWallet, 6 * MIN_CHANGE / 10);
572 add_coin(testWallet, 7 * MIN_CHANGE / 10);
573
574 // and try again to make 1.0 * MIN_CHANGE
575 BOOST_CHECK(SelectCoinsMinConf(
576 testWallet, 1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet,
577 nValueRet, coin_selection_params, bnb_used));
578 // we should get the exact amount
579 BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE);
580
581 // run the 'mtgox' test (see
582 // http://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
583 // they tried to consolidate 10 50k coins into one 500k coin, and ended
584 // up with 50k in change
585 empty_wallet();
586 for (int j = 0; j < 20; j++) {
587 add_coin(testWallet, 50000 * COIN);
588 }
589
590 BOOST_CHECK(SelectCoinsMinConf(
591 testWallet, 500000 * COIN, filter_confirmed, vCoins, setCoinsRet,
592 nValueRet, coin_selection_params, bnb_used));
593 // we should get the exact amount
594 BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN);
595 // in ten coins
596 BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U);
597
598 // if there's not enough in the smaller coins to make at least 1 *
599 // MIN_CHANGE change (0.5+0.6+0.7 < 1.0+1.0), we need to try finding an
600 // exact subset anyway
601
602 // sometimes it will fail, and so we use the next biggest coin:
603 empty_wallet();
604 add_coin(testWallet, 5 * MIN_CHANGE / 10);
605 add_coin(testWallet, 6 * MIN_CHANGE / 10);
606 add_coin(testWallet, 7 * MIN_CHANGE / 10);
607 add_coin(testWallet, 1111 * MIN_CHANGE);
608 BOOST_CHECK(SelectCoinsMinConf(
609 testWallet, 1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet,
610 nValueRet, coin_selection_params, bnb_used));
611 // we get the bigger coin
612 BOOST_CHECK_EQUAL(nValueRet, 1111 * MIN_CHANGE);
613 BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
614
615 // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 =
616 // 1.0)
617 empty_wallet();
618 add_coin(testWallet, 4 * MIN_CHANGE / 10);
619 add_coin(testWallet, 6 * MIN_CHANGE / 10);
620 add_coin(testWallet, 8 * MIN_CHANGE / 10);
621 add_coin(testWallet, 1111 * MIN_CHANGE);
622 BOOST_CHECK(SelectCoinsMinConf(testWallet, MIN_CHANGE, filter_confirmed,
623 vCoins, setCoinsRet, nValueRet,
624 coin_selection_params, bnb_used));
625 // we should get the exact amount
626 BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE);
627 // in two coins 0.4+0.6
628 BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
629
630 // test avoiding small change
631 empty_wallet();
632 add_coin(testWallet, 5 * MIN_CHANGE / 100);
633 add_coin(testWallet, 1 * MIN_CHANGE);
634 add_coin(testWallet, 100 * MIN_CHANGE);
635
636 // trying to make 100.01 from these three coins
637 BOOST_CHECK(SelectCoinsMinConf(
638 testWallet, 10001 * MIN_CHANGE / 100, filter_confirmed, vCoins,
639 setCoinsRet, nValueRet, coin_selection_params, bnb_used));
640 // we should get all coins
641 BOOST_CHECK_EQUAL(nValueRet, 10105 * MIN_CHANGE / 100);
642 BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
643
644 // but if we try to make 99.9, we should take the bigger of the two
645 // small coins to avoid small change
646 BOOST_CHECK(SelectCoinsMinConf(
647 testWallet, 9990 * MIN_CHANGE / 100, filter_confirmed, vCoins,
648 setCoinsRet, nValueRet, coin_selection_params, bnb_used));
649 BOOST_CHECK_EQUAL(nValueRet, 101 * MIN_CHANGE);
650 BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
651 }
652
653 // test with many inputs
654 for (Amount amt = 1500 * SATOSHI; amt < COIN; amt = 10 * amt) {
655 empty_wallet();
656 // Create 676 inputs (= (old MAX_STANDARD_TX_SIZE == 100000) / 148
657 // bytes per input)
658 for (uint16_t j = 0; j < 676; j++) {
659 add_coin(testWallet, amt);
660 }
661
662 // We only create the wallet once to save time, but we still run the
663 // coin selection RUN_TESTS times.
664 for (int i = 0; i < RUN_TESTS; i++) {
665 BOOST_CHECK(SelectCoinsMinConf(
666 testWallet, 2000 * SATOSHI, filter_confirmed, vCoins,
667 setCoinsRet, nValueRet, coin_selection_params, bnb_used));
668
669 if (amt - 2000 * SATOSHI < MIN_CHANGE) {
670 // needs more than one input:
671 uint16_t returnSize = std::ceil(
672 (2000.0 + (MIN_CHANGE / SATOSHI)) / (amt / SATOSHI));
673 Amount returnValue = returnSize * amt;
674 BOOST_CHECK_EQUAL(nValueRet, returnValue);
675 BOOST_CHECK_EQUAL(setCoinsRet.size(), returnSize);
676 } else {
677 // one input is sufficient:
678 BOOST_CHECK_EQUAL(nValueRet, amt);
679 BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
680 }
681 }
682 }
683
684 // test randomness
685 {
686 empty_wallet();
687 for (int i2 = 0; i2 < 100; i2++) {
688 add_coin(testWallet, COIN);
689 }
690
691 // Again, we only create the wallet once to save time, but we still run
692 // the coin selection RUN_TESTS times.
693 for (int i = 0; i < RUN_TESTS; i++) {
694 // picking 50 from 100 coins doesn't depend on the shuffle, but does
695 // depend on randomness in the stochastic approximation code
696 BOOST_CHECK(SelectCoinsMinConf(
697 testWallet, 50 * COIN, filter_standard, vCoins, setCoinsRet,
698 nValueRet, coin_selection_params, bnb_used));
699 BOOST_CHECK(SelectCoinsMinConf(
700 testWallet, 50 * COIN, filter_standard, vCoins, setCoinsRet2,
701 nValueRet, coin_selection_params, bnb_used));
702 BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2));
703
704 int fails = 0;
705 for (int j = 0; j < RANDOM_REPEATS; j++) {
706 // selecting 1 from 100 identical coins depends on the shuffle;
707 // this test will fail 1% of the time run the test
708 // RANDOM_REPEATS times and only complain if all of them fail
709 BOOST_CHECK(SelectCoinsMinConf(
710 testWallet, COIN, filter_standard, vCoins, setCoinsRet,
711 nValueRet, coin_selection_params, bnb_used));
712 BOOST_CHECK(SelectCoinsMinConf(
713 testWallet, COIN, filter_standard, vCoins, setCoinsRet2,
714 nValueRet, coin_selection_params, bnb_used));
715 if (equal_sets(setCoinsRet, setCoinsRet2)) {
716 fails++;
717 }
718 }
719 BOOST_CHECK_NE(fails, RANDOM_REPEATS);
720 }
721
722 // add 75 cents in small change. not enough to make 90 cents, then
723 // try making 90 cents. there are multiple competing "smallest
724 // bigger" coins, one of which should be picked at random
725 add_coin(testWallet, 5 * CENT);
726 add_coin(testWallet, 10 * CENT);
727 add_coin(testWallet, 15 * CENT);
728 add_coin(testWallet, 20 * CENT);
729 add_coin(testWallet, 25 * CENT);
730
731 for (int i = 0; i < RUN_TESTS; i++) {
732 int fails = 0;
733 for (int j = 0; j < RANDOM_REPEATS; j++) {
734 // selecting 1 from 100 identical coins depends on the shuffle;
735 // this test will fail 1% of the time run the test
736 // RANDOM_REPEATS times and only complain if all of them fail
737 BOOST_CHECK(SelectCoinsMinConf(
738 testWallet, 90 * CENT, filter_standard, vCoins, setCoinsRet,
739 nValueRet, coin_selection_params, bnb_used));
740 BOOST_CHECK(SelectCoinsMinConf(
741 testWallet, 90 * CENT, filter_standard, vCoins,
742 setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
743 if (equal_sets(setCoinsRet, setCoinsRet2)) {
744 fails++;
745 }
746 }
747 BOOST_CHECK_NE(fails, RANDOM_REPEATS);
748 }
749 }
750
751 empty_wallet();
752}
753
754BOOST_AUTO_TEST_CASE(ApproximateBestSubset) {
755 CoinSet setCoinsRet;
756 Amount nValueRet;
757 bool bnb_used;
758
759 LOCK(m_wallet.cs_wallet);
760 m_wallet.SetupLegacyScriptPubKeyMan();
761
762 empty_wallet();
763
764 // Test vValue sort order
765 for (int i = 0; i < 1000; i++) {
766 add_coin(m_wallet, 1000 * COIN);
767 }
768 add_coin(m_wallet, 3 * COIN);
769
770 BOOST_CHECK(SelectCoinsMinConf(m_wallet, 1003 * COIN, filter_standard,
771 vCoins, setCoinsRet, nValueRet,
772 coin_selection_params, bnb_used));
773 BOOST_CHECK_EQUAL(nValueRet, 1003 * COIN);
774 BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
775
776 empty_wallet();
777}
778
779// Tests that with the ideal conditions, the coin selector will always be able
780// to find a solution that can pay the target value
781BOOST_AUTO_TEST_CASE(SelectCoins_test) {
782 auto testChain = interfaces::MakeChain(testNode, Params());
783 CWallet testWallet(testChain.get(), "", CreateDummyWalletDatabase());
784 testWallet.SetupLegacyScriptPubKeyMan();
785
786 // Random generator stuff
787 std::default_random_engine generator;
788 std::exponential_distribution<double> distribution(100);
789 FastRandomContext rand;
790
791 // Run this test 100 times
792 for (int i = 0; i < 100; ++i) {
793 empty_wallet();
794
795 // Make a wallet with 1000 exponentially distributed random inputs
796 for (int j = 0; j < 1000; ++j) {
797 add_coin(testWallet,
798 int64_t(10000000 * distribution(generator)) * SATOSHI);
799 }
800
801 // Generate a random fee rate in the range of 100 - 400
802 CFeeRate rate(int64_t(rand.randrange(300) + 100) * SATOSHI);
803
804 // Generate a random target value between 1000 and wallet balance
805 Amount target =
806 int64_t(rand.randrange(balance / SATOSHI - 1000) + 1000) * SATOSHI;
807
808 // Perform selection
809 CoinSelectionParams coin_selection_params_knapsack(
810 false, 34, 148, CFeeRate(Amount::zero()), 0, false);
811 CoinSelectionParams coin_selection_params_bnb(
812 true, 34, 148, CFeeRate(Amount::zero()), 0, false);
813 CoinSet out_set;
814 Amount out_value = Amount::zero();
815 bool bnb_used = false;
816 BOOST_CHECK(SelectCoinsMinConf(testWallet, target, filter_standard,
817 vCoins, out_set, out_value,
818 coin_selection_params_bnb, bnb_used) ||
819 SelectCoinsMinConf(
820 testWallet, target, filter_standard, vCoins, out_set,
821 out_value, coin_selection_params_knapsack, bnb_used));
822 BOOST_CHECK_GE(out_value, target);
823 }
824}
825
826BOOST_AUTO_TEST_SUITE_END()
GetScriptForDestination
CScript GetScriptForDestination(const CTxDestination &dest)
Generate a Bitcoin scriptPubKey for the given CTxDestination.
Definition addresstype.cpp:115
SATOSHI
static constexpr Amount SATOSHI
Definition amount.h:153
COIN
static constexpr Amount COIN
Definition amount.h:154
Params
const CChainParams & Params()
Return the currently selected parameters.
Definition chainparams.cpp:21
CCoinControl
Coin Control Features.
Definition coincontrol.h:20
CCoinControl::Select
void Select(const COutPoint &output)
Definition coincontrol.h:59
CCoinControl::fAllowOtherInputs
bool fAllowOtherInputs
If false, allows unselected inputs, but requires all selected inputs be used.
Definition coincontrol.h:31
CFeeRate
Fee rate in satoshis per virtualbyte: Amount / vB the feerate is represented internally as FeeFrac.
Definition feerate.h:24
CMutableTransaction
A mutable version of CTransaction.
Definition transaction.h:274
CMutableTransaction::vout
std::vector< CTxOut > vout
Definition transaction.h:277
CMutableTransaction::vin
std::vector< CTxIn > vin
Definition transaction.h:276
COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition transaction.h:20
CWallet
A CWallet maintains a set of transactions and balances, and provides the ability to create new transa...
Definition wallet.h:270
CWallet::SetupLegacyScriptPubKeyMan
void SetupLegacyScriptPubKeyMan()
Make a LegacyScriptPubKeyMan and set it for all types, internal, and external.
Definition wallet.cpp:3427
CWallet::cs_wallet
RecursiveMutex cs_wallet
Definition wallet.h:416
CWalletTx
A transaction with a bunch of additional info that only the owner cares about.
Definition transaction.h:65
CWalletTx::m_amounts
CachableAmount m_amounts[AMOUNTTYPE_ENUM_ELEMENTS]
Definition transaction.h:132
CWalletTx::m_is_cache_empty
bool m_is_cache_empty
This flag is true if all m_amounts caches are empty.
Definition transaction.h:139
FastRandomContext
Fast randomness source.
Definition random.h:411
RandomMixin::randrange
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
Definition random.h:266
CoinSet
std::set< CInputCoin > CoinSet
Definition coin_selection.cpp:80
ApproximateBestSubset
static void ApproximateBestSubset(const std::vector< OutputGroup > &groups, const Amount &nTotalLower, const Amount &nTargetValue, std::vector< char > &vfBest, Amount &nBest, int iterations=1000)
Definition coinselection.cpp:214
SelectCoinsBnB
bool SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const Amount &target_value, const Amount &cost_of_change, std::set< CInputCoin > &out_set, Amount &value_ret, const Amount not_input_fees)
This is the Branch and Bound Coin Selection algorithm designed by Murch.
Definition coinselection.cpp:73
MIN_CHANGE
static constexpr Amount MIN_CHANGE
target minimum change amount
Definition coinselection.h:13
filter_standard_extra
CoinEligibilityFilter filter_standard_extra(6, 6)
vCoins
static std::vector< COutput > vCoins
Definition coinselector_tests.cpp:36
empty_wallet
static void empty_wallet()
Definition coinselector_tests.cpp:93
testNode
static node::NodeContext testNode
Definition coinselector_tests.cpp:37
BOOST_AUTO_TEST_CASE
BOOST_AUTO_TEST_CASE(bnb_search_test)
Definition coinselector_tests.cpp:146
coin_selection_params
CoinSelectionParams coin_selection_params(false, 0, 0, CFeeRate(Amount::zero()), 0, false)
equal_sets
static bool equal_sets(CoinSet a, CoinSet b)
Definition coinselector_tests.cpp:98
CoinSet
std::set< CInputCoin > CoinSet
Definition coinselector_tests.cpp:34
GroupCoins
std::vector< OutputGroup > & GroupCoins(const std::vector< CInputCoin > &coins)
Definition coinselector_tests.cpp:118
filter_standard
CoinEligibilityFilter filter_standard(1, 6)
filter_confirmed
CoinEligibilityFilter filter_confirmed(1, 1)
RANDOM_REPEATS
#define RANDOM_REPEATS
Definition coinselector_tests.cpp:32
make_hard_case
static Amount make_hard_case(int utxos, std::vector< CInputCoin > &utxo_pool)
Definition coinselector_tests.cpp:104
balance
static Amount balance
Definition coinselector_tests.cpp:38
RUN_TESTS
#define RUN_TESTS
Definition coinselector_tests.cpp:27
add_coin
static void add_coin(const Amount nValue, int nInput, std::vector< CInputCoin > &set)
Definition coinselector_tests.cpp:46
ISMINE_SPENDABLE
@ ISMINE_SPENDABLE
Definition ismine.h:21
interfaces::MakeChain
std::unique_ptr< Chain > MakeChain(node::NodeContext &node, const CChainParams &params)
Return implementation of Chain interface.
Definition interfaces.cpp:837
m_node
NodeContext & m_node
Definition interfaces.cpp:827
BOOST_CHECK_EQUAL
#define BOOST_CHECK_EQUAL(v1, v2)
Definition object.cpp:18
BOOST_CHECK
#define BOOST_CHECK(expr)
Definition object.cpp:17
MakeTransactionRef
static CTransactionRef MakeTransactionRef()
Definition transaction.h:316
SelectCoinsMinConf
bool SelectCoinsMinConf(const CWallet &wallet, const Amount nTargetValue, const CoinEligibilityFilter &eligibility_filter, std::vector< COutput > coins, std::set< CInputCoin > &setCoinsRet, Amount &nValueRet, const CoinSelectionParams &coin_selection_params, bool &bnb_used)
Shuffle and select coins until nTargetValue is reached while avoiding small change; This method is st...
Definition spend.cpp:426
SelectCoins
bool SelectCoins(const CWallet &wallet, const std::vector< COutput > &vAvailableCoins, const Amount nTargetValue, std::set< CInputCoin > &setCoinsRet, Amount &nValueRet, const CCoinControl &coin_control, CoinSelectionParams &coin_selection_params, bool &bnb_used)
Select a set of coins such that nValueRet >= nTargetValue and at least all coins from coin_control ar...
Definition spend.cpp:478
Amount::zero
static constexpr Amount zero() noexcept
Definition amount.h:36
CachableAmount::Set
void Set(isminefilter filter, Amount value)
Definition ismine.h:39
CoinSelectionParams::m_subtract_fee_outputs
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
Definition wallet.h:249
CoinSelectionParams::effective_fee
CFeeRate effective_fee
Definition wallet.h:246
WalletTestingSetup
Testing setup and teardown for wallet.
Definition wallet_test_fixture.h:22
node::NodeContext
NodeContext struct containing references to chain state and connection state.
Definition context.h:50
LOCK
#define LOCK(cs)
Definition sync.h:295
assert
assert(!tx.IsCoinBase())
m_wallet
std::shared_ptr< CWallet > m_wallet
Definition interfaces.cpp:480
wallet_test_fixture.h
CreateDummyWalletDatabase
std::unique_ptr< WalletDatabase > CreateDummyWalletDatabase()
Return object for accessing dummy database with no read/write capabilities.
Definition walletdb.cpp:1169
CreateMockWalletDatabase
std::unique_ptr< WalletDatabase > CreateMockWalletDatabase()
Return object for accessing temporary in-memory database.
Definition walletdb.cpp:1174
Generated on Thu Nov 5 2026 21:14:06 for Bitcoin ABC by doxygen 1.9.8