1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
// Copyright (c) 2017 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include "wallet/wallet.h"
#include "wallet/coinselection.h"
#include "amount.h"
#include "primitives/transaction.h"
#include "random.h"
#include "test/test_bitcoin.h"
#include "wallet/test/wallet_test_fixture.h"
#include <boost/test/unit_test.hpp>
#include <random>
BOOST_FIXTURE_TEST_SUITE(coin_selection_tests, WalletTestingSetup)
typedef std::set<CInputCoin> CoinSet;
static std::vector<COutput> vCoins;
static const CWallet testWallet("dummy", CWalletDBWrapper::CreateDummy());
static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>& set)
{
CMutableTransaction tx;
tx.vout.resize(nInput + 1);
tx.vout[nInput].nValue = nValue;
set.emplace_back(MakeTransactionRef(tx), nInput);
}
static void add_coin(const CAmount& nValue, int nInput, CoinSet& set)
{
CMutableTransaction tx;
tx.vout.resize(nInput + 1);
tx.vout[nInput].nValue = nValue;
set.emplace(MakeTransactionRef(tx), nInput);
}
static bool equal_sets(CoinSet a, CoinSet b)
{
std::pair<CoinSet::iterator, CoinSet::iterator> ret = mismatch(a.begin(), a.end(), b.begin());
return ret.first == a.end() && ret.second == b.end();
}
static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool)
{
utxo_pool.clear();
CAmount target = 0;
for (int i = 0; i < utxos; ++i) {
target += (CAmount)1 << (utxos+i);
add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool);
add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool);
}
return target;
}
// Branch and bound coin selection tests
BOOST_AUTO_TEST_CASE(bnb_search_test)
{
LOCK(testWallet.cs_wallet);
// Setup
std::vector<CInputCoin> utxo_pool;
CoinSet selection;
CoinSet actual_selection;
CAmount value_ret = 0;
CAmount not_input_fees = 0;
/////////////////////////
// Known Outcome tests //
/////////////////////////
BOOST_TEST_MESSAGE("Testing known outcomes");
// Empty utxo pool
BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
selection.clear();
// Add utxos
add_coin(1 * CENT, 1, utxo_pool);
add_coin(2 * CENT, 2, utxo_pool);
add_coin(3 * CENT, 3, utxo_pool);
add_coin(4 * CENT, 4, utxo_pool);
// Select 1 Cent
add_coin(1 * CENT, 1, actual_selection);
BOOST_CHECK(SelectCoinsBnB(utxo_pool, 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
BOOST_CHECK(equal_sets(selection, actual_selection));
actual_selection.clear();
selection.clear();
// Select 2 Cent
add_coin(2 * CENT, 2, actual_selection);
BOOST_CHECK(SelectCoinsBnB(utxo_pool, 2 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
BOOST_CHECK(equal_sets(selection, actual_selection));
actual_selection.clear();
selection.clear();
// Select 5 Cent
add_coin(3 * CENT, 3, actual_selection);
add_coin(2 * CENT, 2, actual_selection);
BOOST_CHECK(SelectCoinsBnB(utxo_pool, 5 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
BOOST_CHECK(equal_sets(selection, actual_selection));
actual_selection.clear();
selection.clear();
// Select 11 Cent, not possible
BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 11 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
actual_selection.clear();
selection.clear();
// Select 10 Cent
add_coin(5 * CENT, 5, utxo_pool);
add_coin(4 * CENT, 4, actual_selection);
add_coin(3 * CENT, 3, actual_selection);
add_coin(2 * CENT, 2, actual_selection);
add_coin(1 * CENT, 1, actual_selection);
BOOST_CHECK(SelectCoinsBnB(utxo_pool, 10 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
BOOST_CHECK(equal_sets(selection, actual_selection));
actual_selection.clear();
selection.clear();
// Negative effective value
// Select 10 Cent but have 1 Cent not be possible because too small
add_coin(5 * CENT, 5, actual_selection);
add_coin(3 * CENT, 3, actual_selection);
add_coin(2 * CENT, 2, actual_selection);
BOOST_CHECK(SelectCoinsBnB(utxo_pool, 10 * CENT, 5000, selection, value_ret, not_input_fees));
// Select 0.25 Cent, not possible
BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 0.25 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
actual_selection.clear();
selection.clear();
// Iteration exhaustion test
CAmount target = make_hard_case(17, utxo_pool);
BOOST_CHECK(!SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret, not_input_fees)); // Should exhaust
target = make_hard_case(14, utxo_pool);
BOOST_CHECK(SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret, not_input_fees)); // Should not exhaust
// Test same value early bailout optimization
add_coin(7 * CENT, 7, actual_selection);
add_coin(7 * CENT, 7, actual_selection);
add_coin(7 * CENT, 7, actual_selection);
add_coin(7 * CENT, 7, actual_selection);
add_coin(2 * CENT, 7, actual_selection);
add_coin(7 * CENT, 7, utxo_pool);
add_coin(7 * CENT, 7, utxo_pool);
add_coin(7 * CENT, 7, utxo_pool);
add_coin(7 * CENT, 7, utxo_pool);
add_coin(2 * CENT, 7, utxo_pool);
for (int i = 0; i < 50000; ++i) {
add_coin(5 * CENT, 7, utxo_pool);
}
BOOST_CHECK(SelectCoinsBnB(utxo_pool, 30 * CENT, 5000, selection, value_ret, not_input_fees));
////////////////////
// Behavior tests //
////////////////////
// Select 1 Cent with pool of only greater than 5 Cent
utxo_pool.clear();
for (int i = 5; i <= 20; ++i) {
add_coin(i * CENT, i, utxo_pool);
}
// Run 100 times, to make sure it is never finding a solution
for (int i = 0; i < 100; ++i) {
BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 1 * CENT, 2 * CENT, selection, value_ret, not_input_fees));
}
}
BOOST_AUTO_TEST_SUITE_END()
|
