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