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