Line data Source code
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>
7 : #include <primitives/transaction.h>
8 : #include <random.h>
9 : #include <test/util/setup_common.h>
10 : #include <wallet/coincontrol.h>
11 : #include <wallet/coinselection.h>
12 : #include <wallet/test/wallet_test_fixture.h>
13 : #include <wallet/wallet.h>
14 :
15 : #include <boost/test/unit_test.hpp>
16 : #include <random>
17 :
18 89 : BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup)
19 :
20 : // how many times to run all the tests to have a chance to catch errors that only show up with particular random shuffles
21 : #define RUN_TESTS 100
22 :
23 : // some tests fail 1% of the time due to bad luck.
24 : // we repeat those tests this many times and only complain if all iterations of the test fail
25 : #define RANDOM_REPEATS 5
26 :
27 : typedef std::set<CInputCoin> CoinSet;
28 :
29 89 : static std::vector<COutput> vCoins;
30 89 : static NodeContext testNode;
31 89 : static auto testChain = interfaces::MakeChain(testNode);
32 89 : static CWallet testWallet(testChain.get(), "", CreateDummyWalletDatabase());
33 : static CAmount balance = 0;
34 :
35 89 : CoinEligibilityFilter filter_standard(1, 6, 0);
36 89 : CoinEligibilityFilter filter_confirmed(1, 1, 0);
37 89 : CoinEligibilityFilter filter_standard_extra(6, 6, 0);
38 89 : CoinSelectionParams coin_selection_params(false, 0, 0, CFeeRate(0), 0);
39 :
40 50088 : static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>& set)
41 : {
42 50088 : CMutableTransaction tx;
43 50088 : tx.vout.resize(nInput + 1);
44 50088 : tx.vout[nInput].nValue = nValue;
45 50088 : set.emplace_back(MakeTransactionRef(tx), nInput);
46 50088 : }
47 :
48 16 : static void add_coin(const CAmount& nValue, int nInput, CoinSet& set)
49 : {
50 16 : CMutableTransaction tx;
51 16 : tx.vout.resize(nInput + 1);
52 16 : tx.vout[nInput].nValue = nValue;
53 16 : set.emplace(MakeTransactionRef(tx), nInput);
54 16 : }
55 :
56 109991 : static void add_coin(CWallet& wallet, const CAmount& nValue, int nAge = 6*24, bool fIsFromMe = false, int nInput=0, bool spendable = false)
57 : {
58 109991 : balance += nValue;
59 : static int nextLockTime = 0;
60 109991 : CMutableTransaction tx;
61 109991 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
62 109991 : tx.vout.resize(nInput + 1);
63 109991 : tx.vout[nInput].nValue = nValue;
64 109991 : if (spendable) {
65 3 : CTxDestination dest;
66 3 : std::string error;
67 3 : assert(wallet.GetNewDestination(OutputType::BECH32, "", dest, error));
68 3 : tx.vout[nInput].scriptPubKey = GetScriptForDestination(dest);
69 3 : }
70 109991 : if (fIsFromMe) {
71 : // IsFromMe() returns (GetDebit() > 0), and GetDebit() is 0 if vin.empty(),
72 : // so stop vin being empty, and cache a non-zero Debit to fake out IsFromMe()
73 100 : tx.vin.resize(1);
74 : }
75 109991 : CWalletTx* wtx = wallet.AddToWallet(MakeTransactionRef(std::move(tx)), /* confirm= */ {});
76 109991 : if (fIsFromMe)
77 : {
78 100 : wtx->m_amounts[CWalletTx::DEBIT].Set(ISMINE_SPENDABLE, 1);
79 100 : wtx->m_is_cache_empty = false;
80 100 : }
81 109991 : COutput output(wtx, nInput, nAge, true /* spendable */, true /* solvable */, true /* safe */);
82 109991 : vCoins.push_back(output);
83 109991 : }
84 109988 : static void add_coin(const CAmount& nValue, int nAge = 6*24, bool fIsFromMe = false, int nInput=0, bool spendable = false)
85 : {
86 109988 : add_coin(testWallet, nValue, nAge, fIsFromMe, nInput, spendable);
87 109988 : }
88 :
89 812 : static void empty_wallet(void)
90 : {
91 812 : vCoins.clear();
92 812 : balance = 0;
93 812 : }
94 :
95 1106 : static bool equal_sets(CoinSet a, CoinSet b)
96 : {
97 1106 : std::pair<CoinSet::iterator, CoinSet::iterator> ret = mismatch(a.begin(), a.end(), b.begin());
98 1106 : return ret.first == a.end() && ret.second == b.end();
99 1106 : }
100 :
101 2 : static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool)
102 : {
103 2 : utxo_pool.clear();
104 : CAmount target = 0;
105 33 : for (int i = 0; i < utxos; ++i) {
106 31 : target += (CAmount)1 << (utxos+i);
107 31 : add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool);
108 31 : add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool);
109 : }
110 2 : return target;
111 : }
112 :
113 113 : inline std::vector<OutputGroup>& GroupCoins(const std::vector<CInputCoin>& coins)
114 : {
115 113 : static std::vector<OutputGroup> static_groups;
116 113 : static_groups.clear();
117 51819 : for (auto& coin : coins) static_groups.emplace_back(coin, 0, true, 0, 0);
118 113 : return static_groups;
119 : }
120 :
121 5704 : inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
122 : {
123 5704 : static std::vector<OutputGroup> static_groups;
124 5704 : static_groups.clear();
125 685308 : for (auto& coin : coins) static_groups.emplace_back(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);
126 5704 : return static_groups;
127 0 : }
128 :
129 : // Branch and bound coin selection tests
130 95 : BOOST_AUTO_TEST_CASE(bnb_search_test)
131 : {
132 :
133 1 : LOCK(testWallet.cs_wallet);
134 1 : testWallet.SetupLegacyScriptPubKeyMan();
135 :
136 : // Setup
137 1 : std::vector<CInputCoin> utxo_pool;
138 1 : CoinSet selection;
139 1 : CoinSet actual_selection;
140 1 : CAmount value_ret = 0;
141 : CAmount not_input_fees = 0;
142 :
143 : /////////////////////////
144 : // Known Outcome tests //
145 : /////////////////////////
146 :
147 : // Empty utxo pool
148 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
149 1 : selection.clear();
150 :
151 : // Add utxos
152 1 : add_coin(1 * CENT, 1, utxo_pool);
153 1 : add_coin(2 * CENT, 2, utxo_pool);
154 1 : add_coin(3 * CENT, 3, utxo_pool);
155 1 : add_coin(4 * CENT, 4, utxo_pool);
156 :
157 : // Select 1 Cent
158 1 : add_coin(1 * CENT, 1, actual_selection);
159 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
160 1 : BOOST_CHECK(equal_sets(selection, actual_selection));
161 1 : BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
162 1 : actual_selection.clear();
163 1 : selection.clear();
164 :
165 : // Select 2 Cent
166 1 : add_coin(2 * CENT, 2, actual_selection);
167 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
168 1 : BOOST_CHECK(equal_sets(selection, actual_selection));
169 1 : BOOST_CHECK_EQUAL(value_ret, 2 * CENT);
170 1 : actual_selection.clear();
171 1 : selection.clear();
172 :
173 : // Select 5 Cent
174 1 : add_coin(4 * CENT, 4, actual_selection);
175 1 : add_coin(1 * CENT, 1, actual_selection);
176 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
177 1 : BOOST_CHECK(equal_sets(selection, actual_selection));
178 1 : BOOST_CHECK_EQUAL(value_ret, 5 * CENT);
179 1 : actual_selection.clear();
180 1 : selection.clear();
181 :
182 : // Select 11 Cent, not possible
183 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
184 1 : actual_selection.clear();
185 1 : selection.clear();
186 :
187 : // Cost of change is greater than the difference between target value and utxo sum
188 1 : add_coin(1 * CENT, 1, actual_selection);
189 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
190 1 : BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
191 1 : BOOST_CHECK(equal_sets(selection, actual_selection));
192 1 : actual_selection.clear();
193 1 : selection.clear();
194 :
195 : // Cost of change is less than the difference between target value and utxo sum
196 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0, selection, value_ret, not_input_fees));
197 1 : actual_selection.clear();
198 1 : selection.clear();
199 :
200 : // Select 10 Cent
201 1 : add_coin(5 * CENT, 5, utxo_pool);
202 1 : add_coin(5 * CENT, 5, actual_selection);
203 1 : add_coin(4 * CENT, 4, actual_selection);
204 1 : add_coin(1 * CENT, 1, actual_selection);
205 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
206 1 : BOOST_CHECK(equal_sets(selection, actual_selection));
207 1 : BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
208 1 : actual_selection.clear();
209 1 : selection.clear();
210 :
211 : // Negative effective value
212 : // Select 10 Cent but have 1 Cent not be possible because too small
213 1 : add_coin(5 * CENT, 5, actual_selection);
214 1 : add_coin(3 * CENT, 3, actual_selection);
215 1 : add_coin(2 * CENT, 2, actual_selection);
216 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000, selection, value_ret, not_input_fees));
217 1 : BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
218 : // FIXME: this test is redundant with the above, because 1 Cent is selected, not "too small"
219 : // BOOST_CHECK(equal_sets(selection, actual_selection));
220 :
221 : // Select 0.25 Cent, not possible
222 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
223 1 : actual_selection.clear();
224 1 : selection.clear();
225 :
226 : // Iteration exhaustion test
227 1 : CAmount target = make_hard_case(17, utxo_pool);
228 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret, not_input_fees)); // Should exhaust
229 1 : target = make_hard_case(14, utxo_pool);
230 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret, not_input_fees)); // Should not exhaust
231 :
232 : // Test same value early bailout optimization
233 1 : utxo_pool.clear();
234 1 : add_coin(7 * CENT, 7, actual_selection);
235 1 : add_coin(7 * CENT, 7, actual_selection);
236 1 : add_coin(7 * CENT, 7, actual_selection);
237 1 : add_coin(7 * CENT, 7, actual_selection);
238 1 : add_coin(2 * CENT, 7, actual_selection);
239 1 : add_coin(7 * CENT, 7, utxo_pool);
240 1 : add_coin(7 * CENT, 7, utxo_pool);
241 1 : add_coin(7 * CENT, 7, utxo_pool);
242 1 : add_coin(7 * CENT, 7, utxo_pool);
243 1 : add_coin(2 * CENT, 7, utxo_pool);
244 50001 : for (int i = 0; i < 50000; ++i) {
245 50000 : add_coin(5 * CENT, 7, utxo_pool);
246 : }
247 1 : BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000, selection, value_ret, not_input_fees));
248 1 : BOOST_CHECK_EQUAL(value_ret, 30 * CENT);
249 1 : BOOST_CHECK(equal_sets(selection, actual_selection));
250 :
251 : ////////////////////
252 : // Behavior tests //
253 : ////////////////////
254 : // Select 1 Cent with pool of only greater than 5 Cent
255 1 : utxo_pool.clear();
256 17 : for (int i = 5; i <= 20; ++i) {
257 16 : add_coin(i * CENT, i, utxo_pool);
258 : }
259 : // Run 100 times, to make sure it is never finding a solution
260 101 : for (int i = 0; i < 100; ++i) {
261 100 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT, selection, value_ret, not_input_fees));
262 : }
263 :
264 : // Make sure that effective value is working in SelectCoinsMinConf when BnB is used
265 1 : CoinSelectionParams coin_selection_params_bnb(true, 0, 0, CFeeRate(3000), 0);
266 1 : CoinSet setCoinsRet;
267 1 : CAmount nValueRet;
268 1 : bool bnb_used;
269 1 : empty_wallet();
270 1 : add_coin(1);
271 1 : 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
272 1 : BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used));
273 :
274 : // Test fees subtracted from output:
275 1 : empty_wallet();
276 1 : add_coin(1 * CENT);
277 1 : vCoins.at(0).nInputBytes = 40;
278 1 : BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used));
279 1 : coin_selection_params_bnb.m_subtract_fee_outputs = true;
280 1 : BOOST_CHECK(testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used));
281 1 : BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
282 :
283 : // Make sure that can use BnB when there are preset inputs
284 1 : empty_wallet();
285 : {
286 1 : std::unique_ptr<CWallet> wallet = MakeUnique<CWallet>(m_chain.get(), "", CreateMockWalletDatabase());
287 1 : bool firstRun;
288 1 : wallet->LoadWallet(firstRun);
289 1 : wallet->SetupLegacyScriptPubKeyMan();
290 1 : LOCK(wallet->cs_wallet);
291 1 : add_coin(*wallet, 5 * CENT, 6 * 24, false, 0, true);
292 1 : add_coin(*wallet, 3 * CENT, 6 * 24, false, 0, true);
293 1 : add_coin(*wallet, 2 * CENT, 6 * 24, false, 0, true);
294 1 : CCoinControl coin_control;
295 1 : coin_control.fAllowOtherInputs = true;
296 1 : coin_control.Select(COutPoint(vCoins.at(0).tx->GetHash(), vCoins.at(0).i));
297 1 : coin_selection_params_bnb.effective_fee = CFeeRate(0);
298 1 : BOOST_CHECK(wallet->SelectCoins(vCoins, 10 * CENT, setCoinsRet, nValueRet, coin_control, coin_selection_params_bnb, bnb_used));
299 1 : BOOST_CHECK(bnb_used);
300 1 : BOOST_CHECK(coin_selection_params_bnb.use_bnb);
301 1 : }
302 1 : }
303 :
304 95 : BOOST_AUTO_TEST_CASE(knapsack_solver_test)
305 : {
306 1 : CoinSet setCoinsRet, setCoinsRet2;
307 1 : CAmount nValueRet;
308 1 : bool bnb_used;
309 :
310 1 : LOCK(testWallet.cs_wallet);
311 1 : testWallet.SetupLegacyScriptPubKeyMan();
312 :
313 : // test multiple times to allow for differences in the shuffle order
314 101 : for (int i = 0; i < RUN_TESTS; i++)
315 : {
316 100 : empty_wallet();
317 :
318 : // with an empty wallet we can't even pay one cent
319 100 : BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
320 :
321 100 : add_coin(1*CENT, 4); // add a new 1 cent coin
322 :
323 : // with a new 1 cent coin, we still can't find a mature 1 cent
324 100 : BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
325 :
326 : // but we can find a new 1 cent
327 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf( 1 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
328 100 : BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
329 :
330 100 : add_coin(2*CENT); // add a mature 2 cent coin
331 :
332 : // we can't make 3 cents of mature coins
333 100 : BOOST_CHECK(!testWallet.SelectCoinsMinConf( 3 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
334 :
335 : // we can make 3 cents of new coins
336 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf( 3 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
337 100 : BOOST_CHECK_EQUAL(nValueRet, 3 * CENT);
338 :
339 100 : add_coin(5*CENT); // add a mature 5 cent coin,
340 100 : add_coin(10*CENT, 3, true); // a new 10 cent coin sent from one of our own addresses
341 100 : add_coin(20*CENT); // and a mature 20 cent coin
342 :
343 : // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38
344 :
345 : // we can't make 38 cents only if we disallow new coins:
346 100 : BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
347 : // we can't even make 37 cents if we don't allow new coins even if they're from us
348 100 : BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard_extra, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
349 : // but we can make 37 cents if we accept new coins from ourself
350 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(37 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
351 100 : BOOST_CHECK_EQUAL(nValueRet, 37 * CENT);
352 : // and we can make 38 cents if we accept all new coins
353 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(38 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
354 100 : BOOST_CHECK_EQUAL(nValueRet, 38 * CENT);
355 :
356 : // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
357 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(34 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
358 100 : BOOST_CHECK_EQUAL(nValueRet, 35 * CENT); // but 35 cents is closest
359 100 : 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)
360 :
361 : // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5
362 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf( 7 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
363 100 : BOOST_CHECK_EQUAL(nValueRet, 7 * CENT);
364 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
365 :
366 : // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.
367 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf( 8 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
368 100 : BOOST_CHECK(nValueRet == 8 * CENT);
369 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
370 :
371 : // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)
372 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf( 9 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
373 100 : BOOST_CHECK_EQUAL(nValueRet, 10 * CENT);
374 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
375 :
376 : // now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin
377 100 : empty_wallet();
378 :
379 100 : add_coin( 6*CENT);
380 100 : add_coin( 7*CENT);
381 100 : add_coin( 8*CENT);
382 100 : add_coin(20*CENT);
383 100 : add_coin(30*CENT); // now we have 6+7+8+20+30 = 71 cents total
384 :
385 : // check that we have 71 and not 72
386 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(71 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
387 100 : BOOST_CHECK(!testWallet.SelectCoinsMinConf(72 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
388 :
389 : // 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
390 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
391 100 : BOOST_CHECK_EQUAL(nValueRet, 20 * CENT); // we should get 20 in one coin
392 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
393 :
394 100 : add_coin( 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total
395 :
396 : // 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
397 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
398 100 : BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 3 coins
399 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
400 :
401 100 : add_coin( 18*CENT); // now we have 5+6+7+8+18+20+30
402 :
403 : // 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
404 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
405 100 : BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 1 coin
406 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); // because in the event of a tie, the biggest coin wins
407 :
408 : // now try making 11 cents. we should get 5+6
409 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(11 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
410 100 : BOOST_CHECK_EQUAL(nValueRet, 11 * CENT);
411 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
412 :
413 : // check that the smallest bigger coin is used
414 100 : add_coin( 1*COIN);
415 100 : add_coin( 2*COIN);
416 100 : add_coin( 3*COIN);
417 100 : add_coin( 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
418 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(95 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
419 100 : BOOST_CHECK_EQUAL(nValueRet, 1 * COIN); // we should get 1 BTC in 1 coin
420 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
421 :
422 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(195 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
423 100 : BOOST_CHECK_EQUAL(nValueRet, 2 * COIN); // we should get 2 BTC in 1 coin
424 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
425 :
426 : // empty the wallet and start again, now with fractions of a cent, to test small change avoidance
427 :
428 100 : empty_wallet();
429 100 : add_coin(MIN_CHANGE * 1 / 10);
430 100 : add_coin(MIN_CHANGE * 2 / 10);
431 100 : add_coin(MIN_CHANGE * 3 / 10);
432 100 : add_coin(MIN_CHANGE * 4 / 10);
433 100 : add_coin(MIN_CHANGE * 5 / 10);
434 :
435 : // try making 1 * MIN_CHANGE from the 1.5 * MIN_CHANGE
436 : // we'll get change smaller than MIN_CHANGE whatever happens, so can expect MIN_CHANGE exactly
437 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
438 100 : BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE);
439 :
440 : // but if we add a bigger coin, small change is avoided
441 100 : add_coin(1111*MIN_CHANGE);
442 :
443 : // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5
444 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
445 100 : BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
446 :
447 : // if we add more small coins:
448 100 : add_coin(MIN_CHANGE * 6 / 10);
449 100 : add_coin(MIN_CHANGE * 7 / 10);
450 :
451 : // and try again to make 1.0 * MIN_CHANGE
452 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
453 100 : BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
454 :
455 : // run the 'mtgox' test (see http://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
456 : // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change
457 100 : empty_wallet();
458 2100 : for (int j = 0; j < 20; j++)
459 2000 : add_coin(50000 * COIN);
460 :
461 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(500000 * COIN, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
462 100 : BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN); // we should get the exact amount
463 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U); // in ten coins
464 :
465 : // 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),
466 : // we need to try finding an exact subset anyway
467 :
468 : // sometimes it will fail, and so we use the next biggest coin:
469 100 : empty_wallet();
470 100 : add_coin(MIN_CHANGE * 5 / 10);
471 100 : add_coin(MIN_CHANGE * 6 / 10);
472 100 : add_coin(MIN_CHANGE * 7 / 10);
473 100 : add_coin(1111 * MIN_CHANGE);
474 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
475 100 : BOOST_CHECK_EQUAL(nValueRet, 1111 * MIN_CHANGE); // we get the bigger coin
476 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
477 :
478 : // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0)
479 100 : empty_wallet();
480 100 : add_coin(MIN_CHANGE * 4 / 10);
481 100 : add_coin(MIN_CHANGE * 6 / 10);
482 100 : add_coin(MIN_CHANGE * 8 / 10);
483 100 : add_coin(1111 * MIN_CHANGE);
484 100 : BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
485 100 : BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE); // we should get the exact amount
486 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // in two coins 0.4+0.6
487 :
488 : // test avoiding small change
489 100 : empty_wallet();
490 100 : add_coin(MIN_CHANGE * 5 / 100);
491 100 : add_coin(MIN_CHANGE * 1);
492 100 : add_coin(MIN_CHANGE * 100);
493 :
494 : // trying to make 100.01 from these three coins
495 100 : BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 10001 / 100, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
496 100 : BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE * 10105 / 100); // we should get all coins
497 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
498 :
499 : // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change
500 100 : BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 9990 / 100, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
501 100 : BOOST_CHECK_EQUAL(nValueRet, 101 * MIN_CHANGE);
502 100 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
503 : }
504 :
505 : // test with many inputs
506 6 : for (CAmount amt=1500; amt < COIN; amt*=10) {
507 5 : empty_wallet();
508 : // Create 676 inputs (= (old MAX_STANDARD_TX_SIZE == 100000) / 148 bytes per input)
509 3385 : for (uint16_t j = 0; j < 676; j++)
510 3380 : add_coin(amt);
511 :
512 : // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
513 505 : for (int i = 0; i < RUN_TESTS; i++) {
514 500 : BOOST_CHECK(testWallet.SelectCoinsMinConf(2000, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
515 :
516 500 : if (amt - 2000 < MIN_CHANGE) {
517 : // needs more than one input:
518 300 : uint16_t returnSize = std::ceil((2000.0 + MIN_CHANGE)/amt);
519 300 : CAmount returnValue = amt * returnSize;
520 300 : BOOST_CHECK_EQUAL(nValueRet, returnValue);
521 300 : BOOST_CHECK_EQUAL(setCoinsRet.size(), returnSize);
522 300 : } else {
523 : // one input is sufficient:
524 200 : BOOST_CHECK_EQUAL(nValueRet, amt);
525 200 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
526 : }
527 : }
528 : }
529 :
530 : // test randomness
531 : {
532 1 : empty_wallet();
533 101 : for (int i2 = 0; i2 < 100; i2++)
534 100 : add_coin(COIN);
535 :
536 : // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
537 101 : for (int i = 0; i < RUN_TESTS; i++) {
538 : // picking 50 from 100 coins doesn't depend on the shuffle,
539 : // but does depend on randomness in the stochastic approximation code
540 100 : BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, GroupCoins(vCoins), setCoinsRet , nValueRet, coin_selection_params, bnb_used));
541 100 : BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, GroupCoins(vCoins), setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
542 100 : BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2));
543 :
544 100 : int fails = 0;
545 600 : for (int j = 0; j < RANDOM_REPEATS; j++)
546 : {
547 : // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
548 : // run the test RANDOM_REPEATS times and only complain if all of them fail
549 500 : BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, GroupCoins(vCoins), setCoinsRet , nValueRet, coin_selection_params, bnb_used));
550 500 : BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, GroupCoins(vCoins), setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
551 500 : if (equal_sets(setCoinsRet, setCoinsRet2))
552 5 : fails++;
553 : }
554 100 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
555 100 : }
556 :
557 : // add 75 cents in small change. not enough to make 90 cents,
558 : // then try making 90 cents. there are multiple competing "smallest bigger" coins,
559 : // one of which should be picked at random
560 1 : add_coin(5 * CENT);
561 1 : add_coin(10 * CENT);
562 1 : add_coin(15 * CENT);
563 1 : add_coin(20 * CENT);
564 1 : add_coin(25 * CENT);
565 :
566 101 : for (int i = 0; i < RUN_TESTS; i++) {
567 100 : int fails = 0;
568 600 : for (int j = 0; j < RANDOM_REPEATS; j++)
569 : {
570 : // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
571 : // run the test RANDOM_REPEATS times and only complain if all of them fail
572 500 : BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, GroupCoins(vCoins), setCoinsRet , nValueRet, coin_selection_params, bnb_used));
573 500 : BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, GroupCoins(vCoins), setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
574 500 : if (equal_sets(setCoinsRet, setCoinsRet2))
575 7 : fails++;
576 : }
577 100 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
578 100 : }
579 : }
580 :
581 1 : empty_wallet();
582 1 : }
583 :
584 95 : BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
585 : {
586 1 : CoinSet setCoinsRet;
587 1 : CAmount nValueRet;
588 1 : bool bnb_used;
589 :
590 1 : LOCK(testWallet.cs_wallet);
591 1 : testWallet.SetupLegacyScriptPubKeyMan();
592 :
593 1 : empty_wallet();
594 :
595 : // Test vValue sort order
596 1001 : for (int i = 0; i < 1000; i++)
597 1000 : add_coin(1000 * COIN);
598 1 : add_coin(3 * COIN);
599 :
600 1 : BOOST_CHECK(testWallet.SelectCoinsMinConf(1003 * COIN, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used));
601 1 : BOOST_CHECK_EQUAL(nValueRet, 1003 * COIN);
602 1 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
603 :
604 1 : empty_wallet();
605 1 : }
606 :
607 : // Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value
608 95 : BOOST_AUTO_TEST_CASE(SelectCoins_test)
609 : {
610 1 : testWallet.SetupLegacyScriptPubKeyMan();
611 :
612 : // Random generator stuff
613 1 : std::default_random_engine generator;
614 1 : std::exponential_distribution<double> distribution (100);
615 1 : FastRandomContext rand;
616 :
617 : // Run this test 100 times
618 101 : for (int i = 0; i < 100; ++i)
619 : {
620 100 : empty_wallet();
621 :
622 : // Make a wallet with 1000 exponentially distributed random inputs
623 100100 : for (int j = 0; j < 1000; ++j)
624 : {
625 100000 : add_coin((CAmount)(distribution(generator)*10000000));
626 : }
627 :
628 : // Generate a random fee rate in the range of 100 - 400
629 100 : CFeeRate rate(rand.randrange(300) + 100);
630 :
631 : // Generate a random target value between 1000 and wallet balance
632 100 : CAmount target = rand.randrange(balance - 1000) + 1000;
633 :
634 : // Perform selection
635 100 : CoinSelectionParams coin_selection_params_knapsack(false, 34, 148, CFeeRate(0), 0);
636 100 : CoinSelectionParams coin_selection_params_bnb(true, 34, 148, CFeeRate(0), 0);
637 100 : CoinSet out_set;
638 100 : CAmount out_value = 0;
639 100 : bool bnb_used = false;
640 100 : BOOST_CHECK(testWallet.SelectCoinsMinConf(target, filter_standard, GroupCoins(vCoins), out_set, out_value, coin_selection_params_bnb, bnb_used) ||
641 : testWallet.SelectCoinsMinConf(target, filter_standard, GroupCoins(vCoins), out_set, out_value, coin_selection_params_knapsack, bnb_used));
642 100 : BOOST_CHECK_GE(out_value, target);
643 100 : }
644 1 : }
645 :
646 89 : BOOST_AUTO_TEST_SUITE_END()
|
