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