Branch data Line data Source code
# 1 : : // Copyright (c) 2017-2021 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 <primitives/transaction.h>
# 8 : : #include <random.h>
# 9 : : #include <test/util/setup_common.h>
# 10 : : #include <util/translation.h>
# 11 : : #include <wallet/coincontrol.h>
# 12 : : #include <wallet/coinselection.h>
# 13 : : #include <wallet/spend.h>
# 14 : : #include <wallet/test/wallet_test_fixture.h>
# 15 : : #include <wallet/wallet.h>
# 16 : :
# 17 : : #include <algorithm>
# 18 : : #include <boost/test/unit_test.hpp>
# 19 : : #include <random>
# 20 : :
# 21 : : namespace wallet {
# 22 : : BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup)
# 23 : :
# 24 : : // how many times to run all the tests to have a chance to catch errors that only show up with particular random shuffles
# 25 : 808 : #define RUN_TESTS 100
# 26 : :
# 27 : : // some tests fail 1% of the time due to bad luck.
# 28 : : // we repeat those tests this many times and only complain if all iterations of the test fail
# 29 : 1200 : #define RANDOM_REPEATS 5
# 30 : :
# 31 : : typedef std::set<COutput> CoinSet;
# 32 : :
# 33 : : static const CoinEligibilityFilter filter_standard(1, 6, 0);
# 34 : : static const CoinEligibilityFilter filter_confirmed(1, 1, 0);
# 35 : : static const CoinEligibilityFilter filter_standard_extra(6, 6, 0);
# 36 : : static int nextLockTime = 0;
# 37 : :
# 38 : : static void add_coin(const CAmount& nValue, int nInput, std::vector<COutput>& set)
# 39 : 50088 : {
# 40 : 50088 : CMutableTransaction tx;
# 41 : 50088 : tx.vout.resize(nInput + 1);
# 42 : 50088 : tx.vout[nInput].nValue = nValue;
# 43 : 50088 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
# 44 : 50088 : 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);
# 45 : 50088 : }
# 46 : :
# 47 : : static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result)
# 48 : 16 : {
# 49 : 16 : CMutableTransaction tx;
# 50 : 16 : tx.vout.resize(nInput + 1);
# 51 : 16 : tx.vout[nInput].nValue = nValue;
# 52 : 16 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
# 53 : 16 : 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);
# 54 : 16 : OutputGroup group;
# 55 : 16 : group.Insert(output, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ true);
# 56 : 16 : result.AddInput(group);
# 57 : 16 : }
# 58 : :
# 59 : : static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fee = 0, CAmount long_term_fee = 0)
# 60 : 20 : {
# 61 : 20 : CMutableTransaction tx;
# 62 : 20 : tx.vout.resize(nInput + 1);
# 63 : 20 : tx.vout[nInput].nValue = nValue;
# 64 : 20 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
# 65 : 20 : COutput coin(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false);
# 66 : 20 : coin.effective_value = nValue - fee;
# 67 : 20 : coin.fee = fee;
# 68 : 20 : coin.long_term_fee = long_term_fee;
# 69 : 20 : set.insert(coin);
# 70 : 20 : }
# 71 : :
# 72 : : static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount& nValue, int nAge = 6*24, bool fIsFromMe = false, int nInput=0, bool spendable = false)
# 73 : 109991 : {
# 74 : 109991 : CMutableTransaction tx;
# 75 : 109991 : tx.nLockTime = nextLockTime++; // so all transactions get different hashes
# 76 : 109991 : tx.vout.resize(nInput + 1);
# 77 : 109991 : tx.vout[nInput].nValue = nValue;
# 78 [ + + ]: 109991 : if (spendable) {
# 79 : 3 : CTxDestination dest;
# 80 : 3 : bilingual_str error;
# 81 : 3 : const bool destination_ok = wallet.GetNewDestination(OutputType::BECH32, "", dest, error);
# 82 : 3 : assert(destination_ok);
# 83 : 0 : tx.vout[nInput].scriptPubKey = GetScriptForDestination(dest);
# 84 : 3 : }
# 85 : 0 : uint256 txid = tx.GetHash();
# 86 : :
# 87 : 109991 : LOCK(wallet.cs_wallet);
# 88 : 109991 : auto ret = wallet.mapWallet.emplace(std::piecewise_construct, std::forward_as_tuple(txid), std::forward_as_tuple(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
# 89 : 109991 : assert(ret.second);
# 90 : 0 : CWalletTx& wtx = (*ret.first).second;
# 91 : 109991 : coins.emplace_back(COutPoint(wtx.GetHash(), nInput), wtx.tx->vout.at(nInput), nAge, GetTxSpendSize(wallet, wtx, nInput), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe);
# 92 : 109991 : }
# 93 : :
# 94 : : /** Check if SelectionResult a is equivalent to SelectionResult b.
# 95 : : * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */
# 96 : : static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
# 97 : 6 : {
# 98 : 6 : std::vector<CAmount> a_amts;
# 99 : 6 : std::vector<CAmount> b_amts;
# 100 [ + + ]: 13 : for (const auto& coin : a.GetInputSet()) {
# 101 : 13 : a_amts.push_back(coin.txout.nValue);
# 102 : 13 : }
# 103 [ + + ]: 13 : for (const auto& coin : b.GetInputSet()) {
# 104 : 13 : b_amts.push_back(coin.txout.nValue);
# 105 : 13 : }
# 106 : 6 : std::sort(a_amts.begin(), a_amts.end());
# 107 : 6 : std::sort(b_amts.begin(), b_amts.end());
# 108 : :
# 109 : 6 : std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator> ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
# 110 [ + - ][ + - ]: 6 : return ret.first == a_amts.end() && ret.second == b_amts.end();
# 111 : 6 : }
# 112 : :
# 113 : : /** Check if this selection is equal to another one. Equal means same inputs (i.e same value and prevout) */
# 114 : : static bool EqualResult(const SelectionResult& a, const SelectionResult& b)
# 115 : 1100 : {
# 116 : 1100 : std::pair<CoinSet::iterator, CoinSet::iterator> ret = std::mismatch(a.GetInputSet().begin(), a.GetInputSet().end(), b.GetInputSet().begin(),
# 117 : 1154 : [](const COutput& a, const COutput& b) {
# 118 : 1154 : return a.outpoint == b.outpoint;
# 119 : 1154 : });
# 120 [ + + ][ + - ]: 1100 : return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end();
# 121 : 1100 : }
# 122 : :
# 123 : : static CAmount make_hard_case(int utxos, std::vector<COutput>& utxo_pool)
# 124 : 2 : {
# 125 : 2 : utxo_pool.clear();
# 126 : 2 : CAmount target = 0;
# 127 [ + + ]: 33 : for (int i = 0; i < utxos; ++i) {
# 128 : 31 : target += (CAmount)1 << (utxos+i);
# 129 : 31 : add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool);
# 130 : 31 : add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool);
# 131 : 31 : }
# 132 : 2 : return target;
# 133 : 2 : }
# 134 : :
# 135 : : inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
# 136 : 2315 : {
# 137 : 2315 : static std::vector<OutputGroup> static_groups;
# 138 : 2315 : static_groups.clear();
# 139 [ + + ]: 276708 : for (auto& coin : coins) {
# 140 : 276708 : static_groups.emplace_back();
# 141 : 276708 : static_groups.back().Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false);
# 142 : 276708 : }
# 143 : 2315 : return static_groups;
# 144 : 2315 : }
# 145 : :
# 146 : : inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>& coins, CWallet& wallet, const CoinEligibilityFilter& filter)
# 147 : 3401 : {
# 148 : 3401 : FastRandomContext rand{};
# 149 : 3401 : CoinSelectionParams coin_selection_params{
# 150 : 3401 : rand,
# 151 : 3401 : /*change_output_size=*/ 0,
# 152 : 3401 : /*change_spend_size=*/ 0,
# 153 : 3401 : /*min_change_target=*/ CENT,
# 154 : 3401 : /*effective_feerate=*/ CFeeRate(0),
# 155 : 3401 : /*long_term_feerate=*/ CFeeRate(0),
# 156 : 3401 : /*discard_feerate=*/ CFeeRate(0),
# 157 : 3401 : /*tx_noinputs_size=*/ 0,
# 158 : 3401 : /*avoid_partial=*/ false,
# 159 : 3401 : };
# 160 : 3401 : static std::vector<OutputGroup> static_groups;
# 161 : 3401 : static_groups = GroupOutputs(wallet, coins, coin_selection_params, filter, /*positive_only=*/false);
# 162 : 3401 : return static_groups;
# 163 : 3401 : }
# 164 : :
# 165 : : // Branch and bound coin selection tests
# 166 : : BOOST_AUTO_TEST_CASE(bnb_search_test)
# 167 : 1 : {
# 168 : 1 : FastRandomContext rand{};
# 169 : : // Setup
# 170 : 1 : std::vector<COutput> utxo_pool;
# 171 : 1 : SelectionResult expected_result(CAmount(0));
# 172 : :
# 173 : : /////////////////////////
# 174 : : // Known Outcome tests //
# 175 : : /////////////////////////
# 176 : :
# 177 : : // Empty utxo pool
# 178 : 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT));
# 179 : :
# 180 : : // Add utxos
# 181 : 1 : add_coin(1 * CENT, 1, utxo_pool);
# 182 : 1 : add_coin(2 * CENT, 2, utxo_pool);
# 183 : 1 : add_coin(3 * CENT, 3, utxo_pool);
# 184 : 1 : add_coin(4 * CENT, 4, utxo_pool);
# 185 : :
# 186 : : // Select 1 Cent
# 187 : 1 : add_coin(1 * CENT, 1, expected_result);
# 188 : 1 : const auto result1 = SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT);
# 189 : 1 : BOOST_CHECK(result1);
# 190 : 1 : BOOST_CHECK(EquivalentResult(expected_result, *result1));
# 191 : 1 : BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);
# 192 : 1 : expected_result.Clear();
# 193 : :
# 194 : : // Select 2 Cent
# 195 : 1 : add_coin(2 * CENT, 2, expected_result);
# 196 : 1 : const auto result2 = SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT);
# 197 : 1 : BOOST_CHECK(result2);
# 198 : 1 : BOOST_CHECK(EquivalentResult(expected_result, *result2));
# 199 : 1 : BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 2 * CENT);
# 200 : 1 : expected_result.Clear();
# 201 : :
# 202 : : // Select 5 Cent
# 203 : 1 : add_coin(4 * CENT, 4, expected_result);
# 204 : 1 : add_coin(1 * CENT, 1, expected_result);
# 205 : 1 : const auto result3 = SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT);
# 206 : 1 : BOOST_CHECK(result3);
# 207 : 1 : BOOST_CHECK(EquivalentResult(expected_result, *result3));
# 208 : 1 : BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 5 * CENT);
# 209 : 1 : expected_result.Clear();
# 210 : :
# 211 : : // Select 11 Cent, not possible
# 212 : 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT));
# 213 : 1 : expected_result.Clear();
# 214 : :
# 215 : : // Cost of change is greater than the difference between target value and utxo sum
# 216 : 1 : add_coin(1 * CENT, 1, expected_result);
# 217 : 1 : const auto result4 = SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT);
# 218 : 1 : BOOST_CHECK(result4);
# 219 : 1 : BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 1 * CENT);
# 220 : 1 : BOOST_CHECK(EquivalentResult(expected_result, *result4));
# 221 : 1 : expected_result.Clear();
# 222 : :
# 223 : : // Cost of change is less than the difference between target value and utxo sum
# 224 : 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0));
# 225 : 1 : expected_result.Clear();
# 226 : :
# 227 : : // Select 10 Cent
# 228 : 1 : add_coin(5 * CENT, 5, utxo_pool);
# 229 : 1 : add_coin(5 * CENT, 5, expected_result);
# 230 : 1 : add_coin(4 * CENT, 4, expected_result);
# 231 : 1 : add_coin(1 * CENT, 1, expected_result);
# 232 : 1 : const auto result5 = SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT);
# 233 : 1 : BOOST_CHECK(result5);
# 234 : 1 : BOOST_CHECK(EquivalentResult(expected_result, *result5));
# 235 : 1 : BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 10 * CENT);
# 236 : 1 : expected_result.Clear();
# 237 : :
# 238 : : // Negative effective value
# 239 : : // Select 10 Cent but have 1 Cent not be possible because too small
# 240 : 1 : add_coin(5 * CENT, 5, expected_result);
# 241 : 1 : add_coin(3 * CENT, 3, expected_result);
# 242 : 1 : add_coin(2 * CENT, 2, expected_result);
# 243 : 1 : const auto result6 = SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000);
# 244 : 1 : BOOST_CHECK(result6);
# 245 : 1 : BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 10 * CENT);
# 246 : : // FIXME: this test is redundant with the above, because 1 Cent is selected, not "too small"
# 247 : : // BOOST_CHECK(EquivalentResult(expected_result, *result));
# 248 : :
# 249 : : // Select 0.25 Cent, not possible
# 250 : 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT));
# 251 : 1 : expected_result.Clear();
# 252 : :
# 253 : : // Iteration exhaustion test
# 254 : 1 : CAmount target = make_hard_case(17, utxo_pool);
# 255 : 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0)); // Should exhaust
# 256 : 1 : target = make_hard_case(14, utxo_pool);
# 257 : 1 : const auto result7 = SelectCoinsBnB(GroupCoins(utxo_pool), target, 0); // Should not exhaust
# 258 : 1 : BOOST_CHECK(result7);
# 259 : :
# 260 : : // Test same value early bailout optimization
# 261 : 1 : utxo_pool.clear();
# 262 : 1 : add_coin(7 * CENT, 7, expected_result);
# 263 : 1 : add_coin(7 * CENT, 7, expected_result);
# 264 : 1 : add_coin(7 * CENT, 7, expected_result);
# 265 : 1 : add_coin(7 * CENT, 7, expected_result);
# 266 : 1 : add_coin(2 * CENT, 7, expected_result);
# 267 : 1 : add_coin(7 * CENT, 7, utxo_pool);
# 268 : 1 : add_coin(7 * CENT, 7, utxo_pool);
# 269 : 1 : add_coin(7 * CENT, 7, utxo_pool);
# 270 : 1 : add_coin(7 * CENT, 7, utxo_pool);
# 271 : 1 : add_coin(2 * CENT, 7, utxo_pool);
# 272 [ + + ]: 50001 : for (int i = 0; i < 50000; ++i) {
# 273 : 50000 : add_coin(5 * CENT, 7, utxo_pool);
# 274 : 50000 : }
# 275 : 1 : const auto result8 = SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000);
# 276 : 1 : BOOST_CHECK(result8);
# 277 : 1 : BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 30 * CENT);
# 278 : 1 : BOOST_CHECK(EquivalentResult(expected_result, *result8));
# 279 : :
# 280 : : ////////////////////
# 281 : : // Behavior tests //
# 282 : : ////////////////////
# 283 : : // Select 1 Cent with pool of only greater than 5 Cent
# 284 : 1 : utxo_pool.clear();
# 285 [ + + ]: 17 : for (int i = 5; i <= 20; ++i) {
# 286 : 16 : add_coin(i * CENT, i, utxo_pool);
# 287 : 16 : }
# 288 : : // Run 100 times, to make sure it is never finding a solution
# 289 [ + + ]: 101 : for (int i = 0; i < 100; ++i) {
# 290 : 100 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT));
# 291 : 100 : }
# 292 : :
# 293 : : // Make sure that effective value is working in AttemptSelection when BnB is used
# 294 : 1 : CoinSelectionParams coin_selection_params_bnb{
# 295 : 1 : rand,
# 296 : 1 : /*change_output_size=*/ 0,
# 297 : 1 : /*change_spend_size=*/ 0,
# 298 : 1 : /*min_change_target=*/ 0,
# 299 : 1 : /*effective_feerate=*/ CFeeRate(3000),
# 300 : 1 : /*long_term_feerate=*/ CFeeRate(1000),
# 301 : 1 : /*discard_feerate=*/ CFeeRate(1000),
# 302 : 1 : /*tx_noinputs_size=*/ 0,
# 303 : 1 : /*avoid_partial=*/ false,
# 304 : 1 : };
# 305 : 1 : {
# 306 : 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
# 307 : 1 : wallet->LoadWallet();
# 308 : 1 : LOCK(wallet->cs_wallet);
# 309 : 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
# 310 : 1 : wallet->SetupDescriptorScriptPubKeyMans();
# 311 : :
# 312 : 1 : std::vector<COutput> coins;
# 313 : :
# 314 : 1 : add_coin(coins, *wallet, 1);
# 315 : 1 : coins.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
# 316 : 1 : BOOST_CHECK(!SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change));
# 317 : :
# 318 : : // Test fees subtracted from output:
# 319 : 1 : coins.clear();
# 320 : 1 : add_coin(coins, *wallet, 1 * CENT);
# 321 : 1 : coins.at(0).input_bytes = 40;
# 322 : 1 : coin_selection_params_bnb.m_subtract_fee_outputs = true;
# 323 : 1 : const auto result9 = SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change);
# 324 : 1 : BOOST_CHECK(result9);
# 325 : 1 : BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT);
# 326 : 1 : }
# 327 : :
# 328 : 1 : {
# 329 : 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
# 330 : 1 : wallet->LoadWallet();
# 331 : 1 : LOCK(wallet->cs_wallet);
# 332 : 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
# 333 : 1 : wallet->SetupDescriptorScriptPubKeyMans();
# 334 : :
# 335 : 1 : std::vector<COutput> coins;
# 336 : :
# 337 : 1 : add_coin(coins, *wallet, 5 * CENT, 6 * 24, false, 0, true);
# 338 : 1 : add_coin(coins, *wallet, 3 * CENT, 6 * 24, false, 0, true);
# 339 : 1 : add_coin(coins, *wallet, 2 * CENT, 6 * 24, false, 0, true);
# 340 : 1 : CCoinControl coin_control;
# 341 : 1 : coin_control.fAllowOtherInputs = true;
# 342 : 1 : coin_control.Select(coins.at(0).outpoint);
# 343 : 1 : coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
# 344 : 1 : const auto result10 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb);
# 345 : 1 : BOOST_CHECK(result10);
# 346 : 1 : }
# 347 : 1 : }
# 348 : :
# 349 : : BOOST_AUTO_TEST_CASE(knapsack_solver_test)
# 350 : 1 : {
# 351 : 1 : FastRandomContext rand{};
# 352 : 5600 : const auto temp1{[&rand](std::vector<OutputGroup>& g, const CAmount& v, CAmount c) { return KnapsackSolver(g, v, c, rand); }};
# 353 : 1 : const auto KnapsackSolver{temp1};
# 354 : 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
# 355 : 1 : wallet->LoadWallet();
# 356 : 1 : LOCK(wallet->cs_wallet);
# 357 : 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
# 358 : 1 : wallet->SetupDescriptorScriptPubKeyMans();
# 359 : :
# 360 : 1 : std::vector<COutput> coins;
# 361 : :
# 362 : : // test multiple times to allow for differences in the shuffle order
# 363 [ + + ]: 101 : for (int i = 0; i < RUN_TESTS; i++)
# 364 : 100 : {
# 365 : 100 : coins.clear();
# 366 : :
# 367 : : // with an empty wallet we can't even pay one cent
# 368 : 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT, CENT));
# 369 : :
# 370 : 100 : add_coin(coins, *wallet, 1*CENT, 4); // add a new 1 cent coin
# 371 : :
# 372 : : // with a new 1 cent coin, we still can't find a mature 1 cent
# 373 : 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT, CENT));
# 374 : :
# 375 : : // but we can find a new 1 cent
# 376 : 100 : const auto result1 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
# 377 : 100 : BOOST_CHECK(result1);
# 378 : 100 : BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);
# 379 : :
# 380 : 100 : add_coin(coins, *wallet, 2*CENT); // add a mature 2 cent coin
# 381 : :
# 382 : : // we can't make 3 cents of mature coins
# 383 : 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 3 * CENT, CENT));
# 384 : :
# 385 : : // we can make 3 cents of new coins
# 386 : 100 : const auto result2 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 3 * CENT, CENT);
# 387 : 100 : BOOST_CHECK(result2);
# 388 : 100 : BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 3 * CENT);
# 389 : :
# 390 : 100 : add_coin(coins, *wallet, 5*CENT); // add a mature 5 cent coin,
# 391 : 100 : add_coin(coins, *wallet, 10*CENT, 3, true); // a new 10 cent coin sent from one of our own addresses
# 392 : 100 : add_coin(coins, *wallet, 20*CENT); // and a mature 20 cent coin
# 393 : :
# 394 : : // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38
# 395 : :
# 396 : : // we can't make 38 cents only if we disallow new coins:
# 397 : 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 38 * CENT, CENT));
# 398 : : // we can't even make 37 cents if we don't allow new coins even if they're from us
# 399 : 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard_extra), 38 * CENT, CENT));
# 400 : : // but we can make 37 cents if we accept new coins from ourself
# 401 : 100 : const auto result3 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 37 * CENT, CENT);
# 402 : 100 : BOOST_CHECK(result3);
# 403 : 100 : BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 37 * CENT);
# 404 : : // and we can make 38 cents if we accept all new coins
# 405 : 100 : const auto result4 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 38 * CENT, CENT);
# 406 : 100 : BOOST_CHECK(result4);
# 407 : 100 : BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 38 * CENT);
# 408 : :
# 409 : : // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
# 410 : 100 : const auto result5 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 34 * CENT, CENT);
# 411 : 100 : BOOST_CHECK(result5);
# 412 : 100 : BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 35 * CENT); // but 35 cents is closest
# 413 : 100 : 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)
# 414 : :
# 415 : : // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5
# 416 : 100 : const auto result6 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 7 * CENT, CENT);
# 417 : 100 : BOOST_CHECK(result6);
# 418 : 100 : BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 7 * CENT);
# 419 : 100 : BOOST_CHECK_EQUAL(result6->GetInputSet().size(), 2U);
# 420 : :
# 421 : : // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.
# 422 : 100 : const auto result7 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 8 * CENT, CENT);
# 423 : 100 : BOOST_CHECK(result7);
# 424 : 100 : BOOST_CHECK(result7->GetSelectedValue() == 8 * CENT);
# 425 : 100 : BOOST_CHECK_EQUAL(result7->GetInputSet().size(), 3U);
# 426 : :
# 427 : : // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)
# 428 : 100 : const auto result8 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 9 * CENT, CENT);
# 429 : 100 : BOOST_CHECK(result8);
# 430 : 100 : BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 10 * CENT);
# 431 : 100 : BOOST_CHECK_EQUAL(result8->GetInputSet().size(), 1U);
# 432 : :
# 433 : : // now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin
# 434 : 100 : coins.clear();
# 435 : :
# 436 : 100 : add_coin(coins, *wallet, 6*CENT);
# 437 : 100 : add_coin(coins, *wallet, 7*CENT);
# 438 : 100 : add_coin(coins, *wallet, 8*CENT);
# 439 : 100 : add_coin(coins, *wallet, 20*CENT);
# 440 : 100 : add_coin(coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total
# 441 : :
# 442 : : // check that we have 71 and not 72
# 443 : 100 : const auto result9 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 71 * CENT, CENT);
# 444 : 100 : BOOST_CHECK(result9);
# 445 : 100 : BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 72 * CENT, CENT));
# 446 : :
# 447 : : // 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
# 448 : 100 : const auto result10 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT);
# 449 : 100 : BOOST_CHECK(result10);
# 450 : 100 : BOOST_CHECK_EQUAL(result10->GetSelectedValue(), 20 * CENT); // we should get 20 in one coin
# 451 : 100 : BOOST_CHECK_EQUAL(result10->GetInputSet().size(), 1U);
# 452 : :
# 453 : 100 : add_coin(coins, *wallet, 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total
# 454 : :
# 455 : : // 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
# 456 : 100 : const auto result11 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT);
# 457 : 100 : BOOST_CHECK(result11);
# 458 : 100 : BOOST_CHECK_EQUAL(result11->GetSelectedValue(), 18 * CENT); // we should get 18 in 3 coins
# 459 : 100 : BOOST_CHECK_EQUAL(result11->GetInputSet().size(), 3U);
# 460 : :
# 461 : 100 : add_coin(coins, *wallet, 18*CENT); // now we have 5+6+7+8+18+20+30
# 462 : :
# 463 : : // 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
# 464 : 100 : const auto result12 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT);
# 465 : 100 : BOOST_CHECK(result12);
# 466 : 100 : BOOST_CHECK_EQUAL(result12->GetSelectedValue(), 18 * CENT); // we should get 18 in 1 coin
# 467 : 100 : BOOST_CHECK_EQUAL(result12->GetInputSet().size(), 1U); // because in the event of a tie, the biggest coin wins
# 468 : :
# 469 : : // now try making 11 cents. we should get 5+6
# 470 : 100 : const auto result13 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 11 * CENT, CENT);
# 471 : 100 : BOOST_CHECK(result13);
# 472 : 100 : BOOST_CHECK_EQUAL(result13->GetSelectedValue(), 11 * CENT);
# 473 : 100 : BOOST_CHECK_EQUAL(result13->GetInputSet().size(), 2U);
# 474 : :
# 475 : : // check that the smallest bigger coin is used
# 476 : 100 : add_coin(coins, *wallet, 1*COIN);
# 477 : 100 : add_coin(coins, *wallet, 2*COIN);
# 478 : 100 : add_coin(coins, *wallet, 3*COIN);
# 479 : 100 : add_coin(coins, *wallet, 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
# 480 : 100 : const auto result14 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 95 * CENT, CENT);
# 481 : 100 : BOOST_CHECK(result14);
# 482 : 100 : BOOST_CHECK_EQUAL(result14->GetSelectedValue(), 1 * COIN); // we should get 1 BTC in 1 coin
# 483 : 100 : BOOST_CHECK_EQUAL(result14->GetInputSet().size(), 1U);
# 484 : :
# 485 : 100 : const auto result15 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 195 * CENT, CENT);
# 486 : 100 : BOOST_CHECK(result15);
# 487 : 100 : BOOST_CHECK_EQUAL(result15->GetSelectedValue(), 2 * COIN); // we should get 2 BTC in 1 coin
# 488 : 100 : BOOST_CHECK_EQUAL(result15->GetInputSet().size(), 1U);
# 489 : :
# 490 : : // empty the wallet and start again, now with fractions of a cent, to test small change avoidance
# 491 : :
# 492 : 100 : coins.clear();
# 493 : 100 : add_coin(coins, *wallet, CENT * 1 / 10);
# 494 : 100 : add_coin(coins, *wallet, CENT * 2 / 10);
# 495 : 100 : add_coin(coins, *wallet, CENT * 3 / 10);
# 496 : 100 : add_coin(coins, *wallet, CENT * 4 / 10);
# 497 : 100 : add_coin(coins, *wallet, CENT * 5 / 10);
# 498 : :
# 499 : : // try making 1 * CENT from the 1.5 * CENT
# 500 : : // we'll get change smaller than CENT whatever happens, so can expect CENT exactly
# 501 : 100 : const auto result16 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT, CENT);
# 502 : 100 : BOOST_CHECK(result16);
# 503 : 100 : BOOST_CHECK_EQUAL(result16->GetSelectedValue(), CENT);
# 504 : :
# 505 : : // but if we add a bigger coin, small change is avoided
# 506 : 100 : add_coin(coins, *wallet, 1111*CENT);
# 507 : :
# 508 : : // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5
# 509 : 100 : const auto result17 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
# 510 : 100 : BOOST_CHECK(result17);
# 511 : 100 : BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * CENT); // we should get the exact amount
# 512 : :
# 513 : : // if we add more small coins:
# 514 : 100 : add_coin(coins, *wallet, CENT * 6 / 10);
# 515 : 100 : add_coin(coins, *wallet, CENT * 7 / 10);
# 516 : :
# 517 : : // and try again to make 1.0 * CENT
# 518 : 100 : const auto result18 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
# 519 : 100 : BOOST_CHECK(result18);
# 520 : 100 : BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * CENT); // we should get the exact amount
# 521 : :
# 522 : : // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
# 523 : : // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change
# 524 : 100 : coins.clear();
# 525 [ + + ]: 2100 : for (int j = 0; j < 20; j++)
# 526 : 2000 : add_coin(coins, *wallet, 50000 * COIN);
# 527 : :
# 528 : 100 : const auto result19 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 500000 * COIN, CENT);
# 529 : 100 : BOOST_CHECK(result19);
# 530 : 100 : BOOST_CHECK_EQUAL(result19->GetSelectedValue(), 500000 * COIN); // we should get the exact amount
# 531 : 100 : BOOST_CHECK_EQUAL(result19->GetInputSet().size(), 10U); // in ten coins
# 532 : :
# 533 : : // 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),
# 534 : : // we need to try finding an exact subset anyway
# 535 : :
# 536 : : // sometimes it will fail, and so we use the next biggest coin:
# 537 : 100 : coins.clear();
# 538 : 100 : add_coin(coins, *wallet, CENT * 5 / 10);
# 539 : 100 : add_coin(coins, *wallet, CENT * 6 / 10);
# 540 : 100 : add_coin(coins, *wallet, CENT * 7 / 10);
# 541 : 100 : add_coin(coins, *wallet, 1111 * CENT);
# 542 : 100 : const auto result20 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
# 543 : 100 : BOOST_CHECK(result20);
# 544 : 100 : BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * CENT); // we get the bigger coin
# 545 : 100 : BOOST_CHECK_EQUAL(result20->GetInputSet().size(), 1U);
# 546 : :
# 547 : : // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0)
# 548 : 100 : coins.clear();
# 549 : 100 : add_coin(coins, *wallet, CENT * 4 / 10);
# 550 : 100 : add_coin(coins, *wallet, CENT * 6 / 10);
# 551 : 100 : add_coin(coins, *wallet, CENT * 8 / 10);
# 552 : 100 : add_coin(coins, *wallet, 1111 * CENT);
# 553 : 100 : const auto result21 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT, CENT);
# 554 : 100 : BOOST_CHECK(result21);
# 555 : 100 : BOOST_CHECK_EQUAL(result21->GetSelectedValue(), CENT); // we should get the exact amount
# 556 : 100 : BOOST_CHECK_EQUAL(result21->GetInputSet().size(), 2U); // in two coins 0.4+0.6
# 557 : :
# 558 : : // test avoiding small change
# 559 : 100 : coins.clear();
# 560 : 100 : add_coin(coins, *wallet, CENT * 5 / 100);
# 561 : 100 : add_coin(coins, *wallet, CENT * 1);
# 562 : 100 : add_coin(coins, *wallet, CENT * 100);
# 563 : :
# 564 : : // trying to make 100.01 from these three coins
# 565 : 100 : const auto result22 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT * 10001 / 100, CENT);
# 566 : 100 : BOOST_CHECK(result22);
# 567 : 100 : BOOST_CHECK_EQUAL(result22->GetSelectedValue(), CENT * 10105 / 100); // we should get all coins
# 568 : 100 : BOOST_CHECK_EQUAL(result22->GetInputSet().size(), 3U);
# 569 : :
# 570 : : // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change
# 571 : 100 : const auto result23 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT * 9990 / 100, CENT);
# 572 : 100 : BOOST_CHECK(result23);
# 573 : 100 : BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * CENT);
# 574 : 100 : BOOST_CHECK_EQUAL(result23->GetInputSet().size(), 2U);
# 575 : 100 : }
# 576 : :
# 577 : : // test with many inputs
# 578 [ + + ]: 6 : for (CAmount amt=1500; amt < COIN; amt*=10) {
# 579 : 5 : coins.clear();
# 580 : : // Create 676 inputs (= (old MAX_STANDARD_TX_SIZE == 100000) / 148 bytes per input)
# 581 [ + + ]: 3385 : for (uint16_t j = 0; j < 676; j++)
# 582 : 3380 : add_coin(coins, *wallet, amt);
# 583 : :
# 584 : : // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
# 585 [ + + ]: 505 : for (int i = 0; i < RUN_TESTS; i++) {
# 586 : 500 : const auto result24 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 2000, CENT);
# 587 : 500 : BOOST_CHECK(result24);
# 588 : :
# 589 [ + + ]: 500 : if (amt - 2000 < CENT) {
# 590 : : // needs more than one input:
# 591 : 300 : uint16_t returnSize = std::ceil((2000.0 + CENT)/amt);
# 592 : 300 : CAmount returnValue = amt * returnSize;
# 593 : 300 : BOOST_CHECK_EQUAL(result24->GetSelectedValue(), returnValue);
# 594 : 300 : BOOST_CHECK_EQUAL(result24->GetInputSet().size(), returnSize);
# 595 : 300 : } else {
# 596 : : // one input is sufficient:
# 597 : 200 : BOOST_CHECK_EQUAL(result24->GetSelectedValue(), amt);
# 598 : 200 : BOOST_CHECK_EQUAL(result24->GetInputSet().size(), 1U);
# 599 : 200 : }
# 600 : 500 : }
# 601 : 5 : }
# 602 : :
# 603 : : // test randomness
# 604 : 1 : {
# 605 : 1 : coins.clear();
# 606 [ + + ]: 101 : for (int i2 = 0; i2 < 100; i2++)
# 607 : 100 : add_coin(coins, *wallet, COIN);
# 608 : :
# 609 : : // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
# 610 [ + + ]: 101 : for (int i = 0; i < RUN_TESTS; i++) {
# 611 : : // picking 50 from 100 coins doesn't depend on the shuffle,
# 612 : : // but does depend on randomness in the stochastic approximation code
# 613 : 100 : const auto result25 = KnapsackSolver(GroupCoins(coins), 50 * COIN, CENT);
# 614 : 100 : BOOST_CHECK(result25);
# 615 : 100 : const auto result26 = KnapsackSolver(GroupCoins(coins), 50 * COIN, CENT);
# 616 : 100 : BOOST_CHECK(result26);
# 617 : 100 : BOOST_CHECK(!EqualResult(*result25, *result26));
# 618 : :
# 619 : 100 : int fails = 0;
# 620 [ + + ]: 600 : for (int j = 0; j < RANDOM_REPEATS; j++)
# 621 : 500 : {
# 622 : : // Test that the KnapsackSolver selects randomly from equivalent coins (same value and same input size).
# 623 : : // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice
# 624 : : // which will cause it to fail.
# 625 : : // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail
# 626 : 500 : const auto result27 = KnapsackSolver(GroupCoins(coins), COIN, CENT);
# 627 : 500 : BOOST_CHECK(result27);
# 628 : 500 : const auto result28 = KnapsackSolver(GroupCoins(coins), COIN, CENT);
# 629 : 500 : BOOST_CHECK(result28);
# 630 [ + + ]: 500 : if (EqualResult(*result27, *result28))
# 631 : 7 : fails++;
# 632 : 500 : }
# 633 : 100 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
# 634 : 100 : }
# 635 : :
# 636 : : // add 75 cents in small change. not enough to make 90 cents,
# 637 : : // then try making 90 cents. there are multiple competing "smallest bigger" coins,
# 638 : : // one of which should be picked at random
# 639 : 1 : add_coin(coins, *wallet, 5 * CENT);
# 640 : 1 : add_coin(coins, *wallet, 10 * CENT);
# 641 : 1 : add_coin(coins, *wallet, 15 * CENT);
# 642 : 1 : add_coin(coins, *wallet, 20 * CENT);
# 643 : 1 : add_coin(coins, *wallet, 25 * CENT);
# 644 : :
# 645 [ + + ]: 101 : for (int i = 0; i < RUN_TESTS; i++) {
# 646 : 100 : int fails = 0;
# 647 [ + + ]: 600 : for (int j = 0; j < RANDOM_REPEATS; j++)
# 648 : 500 : {
# 649 : 500 : const auto result29 = KnapsackSolver(GroupCoins(coins), 90 * CENT, CENT);
# 650 : 500 : BOOST_CHECK(result29);
# 651 : 500 : const auto result30 = KnapsackSolver(GroupCoins(coins), 90 * CENT, CENT);
# 652 : 500 : BOOST_CHECK(result30);
# 653 [ + + ]: 500 : if (EqualResult(*result29, *result30))
# 654 : 3 : fails++;
# 655 : 500 : }
# 656 : 100 : BOOST_CHECK_NE(fails, RANDOM_REPEATS);
# 657 : 100 : }
# 658 : 1 : }
# 659 : 1 : }
# 660 : :
# 661 : : BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
# 662 : 1 : {
# 663 : 1 : FastRandomContext rand{};
# 664 : 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
# 665 : 1 : wallet->LoadWallet();
# 666 : 1 : LOCK(wallet->cs_wallet);
# 667 : 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
# 668 : 1 : wallet->SetupDescriptorScriptPubKeyMans();
# 669 : :
# 670 : 1 : std::vector<COutput> coins;
# 671 : :
# 672 : : // Test vValue sort order
# 673 [ + + ]: 1001 : for (int i = 0; i < 1000; i++)
# 674 : 1000 : add_coin(coins, *wallet, 1000 * COIN);
# 675 : 1 : add_coin(coins, *wallet, 3 * COIN);
# 676 : :
# 677 : 1 : const auto result = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1003 * COIN, CENT, rand);
# 678 : 1 : BOOST_CHECK(result);
# 679 : 1 : BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN);
# 680 : 1 : BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U);
# 681 : 1 : }
# 682 : :
# 683 : : // Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value
# 684 : : BOOST_AUTO_TEST_CASE(SelectCoins_test)
# 685 : 1 : {
# 686 : 1 : std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
# 687 : 1 : wallet->LoadWallet();
# 688 : 1 : LOCK(wallet->cs_wallet);
# 689 : 1 : wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
# 690 : 1 : wallet->SetupDescriptorScriptPubKeyMans();
# 691 : :
# 692 : : // Random generator stuff
# 693 : 1 : std::default_random_engine generator;
# 694 : 1 : std::exponential_distribution<double> distribution (100);
# 695 : 1 : FastRandomContext rand;
# 696 : :
# 697 : : // Run this test 100 times
# 698 [ + + ]: 101 : for (int i = 0; i < 100; ++i)
# 699 : 100 : {
# 700 : 100 : std::vector<COutput> coins;
# 701 : 100 : CAmount balance{0};
# 702 : :
# 703 : : // Make a wallet with 1000 exponentially distributed random inputs
# 704 [ + + ]: 100100 : for (int j = 0; j < 1000; ++j)
# 705 : 100000 : {
# 706 : 100000 : CAmount val = distribution(generator)*10000000;
# 707 : 100000 : add_coin(coins, *wallet, val);
# 708 : 100000 : balance += val;
# 709 : 100000 : }
# 710 : :
# 711 : : // Generate a random fee rate in the range of 100 - 400
# 712 : 100 : CFeeRate rate(rand.randrange(300) + 100);
# 713 : :
# 714 : : // Generate a random target value between 1000 and wallet balance
# 715 : 100 : CAmount target = rand.randrange(balance - 1000) + 1000;
# 716 : :
# 717 : : // Perform selection
# 718 : 100 : CoinSelectionParams cs_params{
# 719 : 100 : rand,
# 720 : 100 : /*change_output_size=*/ 34,
# 721 : 100 : /*change_spend_size=*/ 148,
# 722 : 100 : /*min_change_target=*/ CENT,
# 723 : 100 : /*effective_feerate=*/ CFeeRate(0),
# 724 : 100 : /*long_term_feerate=*/ CFeeRate(0),
# 725 : 100 : /*discard_feerate=*/ CFeeRate(0),
# 726 : 100 : /*tx_noinputs_size=*/ 0,
# 727 : 100 : /*avoid_partial=*/ false,
# 728 : 100 : };
# 729 : 100 : CCoinControl cc;
# 730 : 100 : const auto result = SelectCoins(*wallet, coins, target, cc, cs_params);
# 731 : 100 : BOOST_CHECK(result);
# 732 : 100 : BOOST_CHECK_GE(result->GetSelectedValue(), target);
# 733 : 100 : }
# 734 : 1 : }
# 735 : :
# 736 : : BOOST_AUTO_TEST_CASE(waste_test)
# 737 : 1 : {
# 738 : 1 : CoinSet selection;
# 739 : 1 : const CAmount fee{100};
# 740 : 1 : const CAmount change_cost{125};
# 741 : 1 : const CAmount fee_diff{40};
# 742 : 1 : const CAmount in_amt{3 * COIN};
# 743 : 1 : const CAmount target{2 * COIN};
# 744 : 1 : const CAmount excess{in_amt - fee * 2 - target};
# 745 : :
# 746 : : // Waste with change is the change cost and difference between fee and long term fee
# 747 : 1 : add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
# 748 : 1 : add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
# 749 : 1 : const CAmount waste1 = GetSelectionWaste(selection, change_cost, target);
# 750 : 1 : BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, waste1);
# 751 : 1 : selection.clear();
# 752 : :
# 753 : : // Waste without change is the excess and difference between fee and long term fee
# 754 : 1 : add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
# 755 : 1 : add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
# 756 : 1 : const CAmount waste_nochange1 = GetSelectionWaste(selection, 0, target);
# 757 : 1 : BOOST_CHECK_EQUAL(fee_diff * 2 + excess, waste_nochange1);
# 758 : 1 : selection.clear();
# 759 : :
# 760 : : // Waste with change and fee == long term fee is just cost of change
# 761 : 1 : add_coin(1 * COIN, 1, selection, fee, fee);
# 762 : 1 : add_coin(2 * COIN, 2, selection, fee, fee);
# 763 : 1 : BOOST_CHECK_EQUAL(change_cost, GetSelectionWaste(selection, change_cost, target));
# 764 : 1 : selection.clear();
# 765 : :
# 766 : : // Waste without change and fee == long term fee is just the excess
# 767 : 1 : add_coin(1 * COIN, 1, selection, fee, fee);
# 768 : 1 : add_coin(2 * COIN, 2, selection, fee, fee);
# 769 : 1 : BOOST_CHECK_EQUAL(excess, GetSelectionWaste(selection, 0, target));
# 770 : 1 : selection.clear();
# 771 : :
# 772 : : // Waste will be greater when fee is greater, but long term fee is the same
# 773 : 1 : add_coin(1 * COIN, 1, selection, fee * 2, fee - fee_diff);
# 774 : 1 : add_coin(2 * COIN, 2, selection, fee * 2, fee - fee_diff);
# 775 : 1 : const CAmount waste2 = GetSelectionWaste(selection, change_cost, target);
# 776 : 1 : BOOST_CHECK_GT(waste2, waste1);
# 777 : 1 : selection.clear();
# 778 : :
# 779 : : // Waste with change is the change cost and difference between fee and long term fee
# 780 : : // With long term fee greater than fee, waste should be less than when long term fee is less than fee
# 781 : 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
# 782 : 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
# 783 : 1 : const CAmount waste3 = GetSelectionWaste(selection, change_cost, target);
# 784 : 1 : BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, waste3);
# 785 : 1 : BOOST_CHECK_LT(waste3, waste1);
# 786 : 1 : selection.clear();
# 787 : :
# 788 : : // Waste without change is the excess and difference between fee and long term fee
# 789 : : // With long term fee greater than fee, waste should be less than when long term fee is less than fee
# 790 : 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
# 791 : 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
# 792 : 1 : const CAmount waste_nochange2 = GetSelectionWaste(selection, 0, target);
# 793 : 1 : BOOST_CHECK_EQUAL(fee_diff * -2 + excess, waste_nochange2);
# 794 : 1 : BOOST_CHECK_LT(waste_nochange2, waste_nochange1);
# 795 : 1 : selection.clear();
# 796 : :
# 797 : : // No Waste when fee == long_term_fee, no change, and no excess
# 798 : 1 : add_coin(1 * COIN, 1, selection, fee, fee);
# 799 : 1 : add_coin(2 * COIN, 2, selection, fee, fee);
# 800 : 1 : const CAmount exact_target{in_amt - fee * 2};
# 801 : 1 : BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/0, exact_target));
# 802 : 1 : selection.clear();
# 803 : :
# 804 : : // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess
# 805 : 1 : const CAmount new_change_cost{fee_diff * 2};
# 806 : 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
# 807 : 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
# 808 : 1 : BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, new_change_cost, target));
# 809 : 1 : selection.clear();
# 810 : :
# 811 : : // No Waste when (fee - long_term_fee) == (-excess), no change cost
# 812 : 1 : const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
# 813 : 1 : add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
# 814 : 1 : add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
# 815 : 1 : BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /* change cost */ 0, new_target));
# 816 : 1 : }
# 817 : :
# 818 : : BOOST_AUTO_TEST_SUITE_END()
# 819 : : } // namespace wallet
|
