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