Line data Source code
1 : // Copyright (c) 2012-2014 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 "wallet/wallet.h"
6 :
7 : #include <set>
8 : #include <stdint.h>
9 : #include <utility>
10 : #include <vector>
11 :
12 : #include "test/test_bitcoin.h"
13 :
14 : #include <boost/foreach.hpp>
15 : #include <boost/test/unit_test.hpp>
16 :
17 : // how many times to run all the tests to have a chance to catch errors that only show up with particular random shuffles
18 : #define RUN_TESTS 100
19 :
20 : // some tests fail 1% of the time due to bad luck.
21 : // we repeat those tests this many times and only complain if all iterations of the test fail
22 : #define RANDOM_REPEATS 5
23 :
24 : using namespace std;
25 :
26 : typedef set<pair<const CWalletTx*,unsigned int> > CoinSet;
27 :
28 1 : BOOST_FIXTURE_TEST_SUITE(wallet_tests, TestingSetup)
29 :
30 1 : static CWallet wallet;
31 1 : static vector<COutput> vCoins;
32 :
33 16000 : static void add_coin(const CAmount& nValue, int nAge = 6*24, bool fIsFromMe = false, int nInput=0)
34 : {
35 : static int nextLockTime = 0;
36 16000 : CMutableTransaction tx;
37 16000 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
38 32000 : tx.vout.resize(nInput+1);
39 32000 : tx.vout[nInput].nValue = nValue;
40 16000 : if (fIsFromMe) {
41 : // IsFromMe() returns (GetDebit() > 0), and GetDebit() is 0 if vin.empty(),
42 : // so stop vin being empty, and cache a non-zero Debit to fake out IsFromMe()
43 200 : tx.vin.resize(1);
44 : }
45 32000 : CWalletTx* wtx = new CWalletTx(&wallet, tx);
46 16000 : if (fIsFromMe)
47 : {
48 100 : wtx->fDebitCached = true;
49 100 : wtx->nDebitCached = 1;
50 : }
51 : COutput output(wtx, nInput, nAge, true);
52 16000 : vCoins.push_back(output);
53 16000 : }
54 :
55 801 : static void empty_wallet(void)
56 : {
57 100806 : BOOST_FOREACH(COutput output, vCoins)
58 16000 : delete output.tx;
59 : vCoins.clear();
60 801 : }
61 :
62 1100 : static bool equal_sets(CoinSet a, CoinSet b)
63 : {
64 1100 : pair<CoinSet::iterator, CoinSet::iterator> ret = mismatch(a.begin(), a.end(), b.begin());
65 2210 : return ret.first == a.end() && ret.second == b.end();
66 : }
67 :
68 6 : BOOST_AUTO_TEST_CASE(coin_selection_tests)
69 : {
70 : CoinSet setCoinsRet, setCoinsRet2;
71 : CAmount nValueRet;
72 :
73 1 : LOCK(wallet.cs_wallet);
74 :
75 : // test multiple times to allow for differences in the shuffle order
76 100 : for (int i = 0; i < RUN_TESTS; i++)
77 : {
78 100 : empty_wallet();
79 :
80 : // with an empty wallet we can't even pay one cent
81 900 : BOOST_CHECK(!wallet.SelectCoinsMinConf( 1 * CENT, 1, 6, vCoins, setCoinsRet, nValueRet));
82 :
83 100 : add_coin(1*CENT, 4); // add a new 1 cent coin
84 :
85 : // with a new 1 cent coin, we still can't find a mature 1 cent
86 900 : BOOST_CHECK(!wallet.SelectCoinsMinConf( 1 * CENT, 1, 6, vCoins, setCoinsRet, nValueRet));
87 :
88 : // but we can find a new 1 cent
89 900 : BOOST_CHECK( wallet.SelectCoinsMinConf( 1 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
90 500 : BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
91 :
92 100 : add_coin(2*CENT); // add a mature 2 cent coin
93 :
94 : // we can't make 3 cents of mature coins
95 900 : BOOST_CHECK(!wallet.SelectCoinsMinConf( 3 * CENT, 1, 6, vCoins, setCoinsRet, nValueRet));
96 :
97 : // we can make 3 cents of new coins
98 900 : BOOST_CHECK( wallet.SelectCoinsMinConf( 3 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
99 500 : BOOST_CHECK_EQUAL(nValueRet, 3 * CENT);
100 :
101 100 : add_coin(5*CENT); // add a mature 5 cent coin,
102 100 : add_coin(10*CENT, 3, true); // a new 10 cent coin sent from one of our own addresses
103 100 : add_coin(20*CENT); // and a mature 20 cent coin
104 :
105 : // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38
106 :
107 : // we can't make 38 cents only if we disallow new coins:
108 900 : BOOST_CHECK(!wallet.SelectCoinsMinConf(38 * CENT, 1, 6, vCoins, setCoinsRet, nValueRet));
109 : // we can't even make 37 cents if we don't allow new coins even if they're from us
110 900 : BOOST_CHECK(!wallet.SelectCoinsMinConf(38 * CENT, 6, 6, vCoins, setCoinsRet, nValueRet));
111 : // but we can make 37 cents if we accept new coins from ourself
112 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(37 * CENT, 1, 6, vCoins, setCoinsRet, nValueRet));
113 500 : BOOST_CHECK_EQUAL(nValueRet, 37 * CENT);
114 : // and we can make 38 cents if we accept all new coins
115 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(38 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
116 500 : BOOST_CHECK_EQUAL(nValueRet, 38 * CENT);
117 :
118 : // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
119 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(34 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
120 500 : BOOST_CHECK_GT(nValueRet, 34 * CENT); // but should get more than 34 cents
121 600 : 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)
122 :
123 : // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5
124 900 : BOOST_CHECK( wallet.SelectCoinsMinConf( 7 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
125 500 : BOOST_CHECK_EQUAL(nValueRet, 7 * CENT);
126 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
127 :
128 : // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.
129 900 : BOOST_CHECK( wallet.SelectCoinsMinConf( 8 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
130 800 : BOOST_CHECK(nValueRet == 8 * CENT);
131 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
132 :
133 : // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)
134 900 : BOOST_CHECK( wallet.SelectCoinsMinConf( 9 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
135 500 : BOOST_CHECK_EQUAL(nValueRet, 10 * CENT);
136 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
137 :
138 : // now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin
139 100 : empty_wallet();
140 :
141 100 : add_coin( 6*CENT);
142 100 : add_coin( 7*CENT);
143 100 : add_coin( 8*CENT);
144 100 : add_coin(20*CENT);
145 100 : add_coin(30*CENT); // now we have 6+7+8+20+30 = 71 cents total
146 :
147 : // check that we have 71 and not 72
148 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(71 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
149 900 : BOOST_CHECK(!wallet.SelectCoinsMinConf(72 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
150 :
151 : // 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
152 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(16 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
153 500 : BOOST_CHECK_EQUAL(nValueRet, 20 * CENT); // we should get 20 in one coin
154 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
155 :
156 100 : add_coin( 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total
157 :
158 : // 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
159 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(16 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
160 500 : BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 3 coins
161 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
162 :
163 100 : add_coin( 18*CENT); // now we have 5+6+7+8+18+20+30
164 :
165 : // 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
166 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(16 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
167 500 : BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 1 coin
168 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); // because in the event of a tie, the biggest coin wins
169 :
170 : // now try making 11 cents. we should get 5+6
171 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(11 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
172 500 : BOOST_CHECK_EQUAL(nValueRet, 11 * CENT);
173 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
174 :
175 : // check that the smallest bigger coin is used
176 100 : add_coin( 1*COIN);
177 100 : add_coin( 2*COIN);
178 100 : add_coin( 3*COIN);
179 100 : add_coin( 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
180 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(95 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
181 500 : BOOST_CHECK_EQUAL(nValueRet, 1 * COIN); // we should get 1 BTC in 1 coin
182 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
183 :
184 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(195 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
185 500 : BOOST_CHECK_EQUAL(nValueRet, 2 * COIN); // we should get 2 BTC in 1 coin
186 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
187 :
188 : // empty the wallet and start again, now with fractions of a cent, to test sub-cent change avoidance
189 100 : empty_wallet();
190 100 : add_coin(0.1*CENT);
191 100 : add_coin(0.2*CENT);
192 100 : add_coin(0.3*CENT);
193 100 : add_coin(0.4*CENT);
194 100 : add_coin(0.5*CENT);
195 :
196 : // try making 1 cent from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 = 1.5 cents
197 : // we'll get sub-cent change whatever happens, so can expect 1.0 exactly
198 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(1 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
199 500 : BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
200 :
201 : // but if we add a bigger coin, making it possible to avoid sub-cent change, things change:
202 100 : add_coin(1111*CENT);
203 :
204 : // try making 1 cent from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5 cents
205 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(1 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
206 500 : BOOST_CHECK_EQUAL(nValueRet, 1 * CENT); // we should get the exact amount
207 :
208 : // if we add more sub-cent coins:
209 100 : add_coin(0.6*CENT);
210 100 : add_coin(0.7*CENT);
211 :
212 : // and try again to make 1.0 cents, we can still make 1.0 cents
213 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(1 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
214 500 : BOOST_CHECK_EQUAL(nValueRet, 1 * CENT); // we should get the exact amount
215 :
216 : // run the 'mtgox' test (see http://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
217 : // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change
218 100 : empty_wallet();
219 2100 : for (int i = 0; i < 20; i++)
220 2000 : add_coin(50000 * COIN);
221 :
222 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(500000 * COIN, 1, 1, vCoins, setCoinsRet, nValueRet));
223 500 : BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN); // we should get the exact amount
224 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U); // in ten coins
225 :
226 : // 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),
227 : // we need to try finding an exact subset anyway
228 :
229 : // sometimes it will fail, and so we use the next biggest coin:
230 100 : empty_wallet();
231 100 : add_coin(0.5 * CENT);
232 100 : add_coin(0.6 * CENT);
233 100 : add_coin(0.7 * CENT);
234 100 : add_coin(1111 * CENT);
235 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(1 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
236 500 : BOOST_CHECK_EQUAL(nValueRet, 1111 * CENT); // we get the bigger coin
237 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
238 :
239 : // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0)
240 100 : empty_wallet();
241 100 : add_coin(0.4 * CENT);
242 100 : add_coin(0.6 * CENT);
243 100 : add_coin(0.8 * CENT);
244 100 : add_coin(1111 * CENT);
245 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(1 * CENT, 1, 1, vCoins, setCoinsRet, nValueRet));
246 500 : BOOST_CHECK_EQUAL(nValueRet, 1 * CENT); // we should get the exact amount
247 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // in two coins 0.4+0.6
248 :
249 : // test avoiding sub-cent change
250 100 : empty_wallet();
251 100 : add_coin(0.0005 * COIN);
252 100 : add_coin(0.01 * COIN);
253 100 : add_coin(1 * COIN);
254 :
255 : // trying to make 1.0001 from these three coins
256 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(1.0001 * COIN, 1, 1, vCoins, setCoinsRet, nValueRet));
257 500 : BOOST_CHECK_EQUAL(nValueRet, 1.0105 * COIN); // we should get all coins
258 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
259 :
260 : // but if we try to make 0.999, we should take the bigger of the two small coins to avoid sub-cent change
261 900 : BOOST_CHECK( wallet.SelectCoinsMinConf(0.999 * COIN, 1, 1, vCoins, setCoinsRet, nValueRet));
262 500 : BOOST_CHECK_EQUAL(nValueRet, 1.01 * COIN); // we should get 1 + 0.01
263 600 : BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
264 :
265 : // test randomness
266 : {
267 100 : empty_wallet();
268 10100 : for (int i2 = 0; i2 < 100; i2++)
269 10000 : add_coin(COIN);
270 :
271 : // picking 50 from 100 coins doesn't depend on the shuffle,
272 : // but does depend on randomness in the stochastic approximation code
273 900 : BOOST_CHECK(wallet.SelectCoinsMinConf(50 * COIN, 1, 6, vCoins, setCoinsRet , nValueRet));
274 900 : BOOST_CHECK(wallet.SelectCoinsMinConf(50 * COIN, 1, 6, vCoins, setCoinsRet2, nValueRet));
275 1000 : BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2));
276 :
277 100 : int fails = 0;
278 600 : for (int i = 0; i < RANDOM_REPEATS; i++)
279 : {
280 : // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
281 : // run the test RANDOM_REPEATS times and only complain if all of them fail
282 4500 : BOOST_CHECK(wallet.SelectCoinsMinConf(COIN, 1, 6, vCoins, setCoinsRet , nValueRet));
283 4500 : BOOST_CHECK(wallet.SelectCoinsMinConf(COIN, 1, 6, vCoins, setCoinsRet2, nValueRet));
284 1500 : if (equal_sets(setCoinsRet, setCoinsRet2))
285 5 : fails++;
286 : }
287 500 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
288 :
289 : // add 75 cents in small change. not enough to make 90 cents,
290 : // then try making 90 cents. there are multiple competing "smallest bigger" coins,
291 : // one of which should be picked at random
292 100 : add_coin( 5*CENT); add_coin(10*CENT); add_coin(15*CENT); add_coin(20*CENT); add_coin(25*CENT);
293 :
294 100 : fails = 0;
295 600 : for (int i = 0; i < RANDOM_REPEATS; i++)
296 : {
297 : // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
298 : // run the test RANDOM_REPEATS times and only complain if all of them fail
299 4500 : BOOST_CHECK(wallet.SelectCoinsMinConf(90*CENT, 1, 6, vCoins, setCoinsRet , nValueRet));
300 4500 : BOOST_CHECK(wallet.SelectCoinsMinConf(90*CENT, 1, 6, vCoins, setCoinsRet2, nValueRet));
301 1500 : if (equal_sets(setCoinsRet, setCoinsRet2))
302 5 : fails++;
303 : }
304 500 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
305 : }
306 : }
307 1 : empty_wallet();
308 1 : }
309 :
310 3 : BOOST_AUTO_TEST_SUITE_END()
|
