coinselector_tests.cpp
1 // Copyright (c) 2017-2022 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 <policy/policy.h> 8 #include <primitives/transaction.h> 9 #include <random.h> 10 #include <test/util/setup_common.h> 11 #include <util/translation.h> 12 #include <wallet/coincontrol.h> 13 #include <wallet/coinselection.h> 14 #include <wallet/spend.h> 15 #include <wallet/test/util.h> 16 #include <wallet/test/wallet_test_fixture.h> 17 #include <wallet/wallet.h> 18 19 #include <algorithm> 20 #include <boost/test/unit_test.hpp> 21 #include <random> 22 23 namespace wallet { 24 BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup) 25 26 // how many times to run all the tests to have a chance to catch errors that only show up with particular random shuffles 27 #define RUN_TESTS 100 28 29 // some tests fail 1% of the time due to bad luck. 30 // we repeat those tests this many times and only complain if all iterations of the test fail 31 #define RANDOM_REPEATS 5 32 33 typedef std::set<std::shared_ptr<COutput>> CoinSet; 34 35 static const CoinEligibilityFilter filter_standard(1, 6, 0); 36 static const CoinEligibilityFilter filter_confirmed(1, 1, 0); 37 static const CoinEligibilityFilter filter_standard_extra(6, 6, 0); 38 static int nextLockTime = 0; 39 40 static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result) 41 { 42 CMutableTransaction tx; 43 tx.vout.resize(nInput + 1); 44 tx.vout[nInput].nValue = nValue; 45 tx.nLockTime = nextLockTime++; // so all transactions get different hashes 46 COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/ 0); 47 OutputGroup group; 48 group.Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*descendants=*/ 0); 49 result.AddInput(group); 50 } 51 52 static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result, CAmount fee, CAmount long_term_fee) 53 { 54 CMutableTransaction tx; 55 tx.vout.resize(nInput + 1); 56 tx.vout[nInput].nValue = nValue; 57 tx.nLockTime = nextLockTime++; // so all transactions get different hashes 58 std::shared_ptr<COutput> coin = std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/148, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, fee); 59 OutputGroup group; 60 group.Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0); 61 coin->long_term_fee = long_term_fee; // group.Insert() will modify long_term_fee, so we need to set it afterwards 62 result.AddInput(group); 63 } 64 65 static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmount& nValue, CFeeRate feerate = CFeeRate(0), int nAge = 6*24, bool fIsFromMe = false, int nInput =0, bool spendable = false, int custom_size = 0) 66 { 67 CMutableTransaction tx; 68 tx.nLockTime = nextLockTime++; // so all transactions get different hashes 69 tx.vout.resize(nInput + 1); 70 tx.vout[nInput].nValue = nValue; 71 if (spendable) { 72 tx.vout[nInput].scriptPubKey = GetScriptForDestination(*Assert(wallet.GetNewDestination(OutputType::BECH32, ""))); 73 } 74 Txid txid = tx.GetHash(); 75 76 LOCK(wallet.cs_wallet); 77 auto ret = wallet.mapWallet.emplace(std::piecewise_construct, std::forward_as_tuple(txid), std::forward_as_tuple(MakeTransactionRef(std::move(tx)), TxStateInactive{})); 78 assert(ret.second); 79 CWalletTx& wtx = (*ret.first).second; 80 const auto& txout = wtx.tx->vout.at(nInput); 81 available_coins.Add(OutputType::BECH32, {COutPoint(wtx.GetHash(), nInput), txout, nAge, custom_size == 0 ? CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr) : custom_size, /*solvable=*/true, /*safe=*/true, wtx.GetTxTime(), fIsFromMe, feerate}); 82 } 83 84 // Helpers 85 std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, 86 CAmount change_target, FastRandomContext& rng) 87 { 88 auto res{KnapsackSolver(groups, nTargetValue, change_target, rng, MAX_STANDARD_TX_WEIGHT)}; 89 return res ? std::optional<SelectionResult>(*res) : std::nullopt; 90 } 91 92 std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change) 93 { 94 auto res{SelectCoinsBnB(utxo_pool, selection_target, cost_of_change, MAX_STANDARD_TX_WEIGHT)}; 95 return res ? std::optional<SelectionResult>(*res) : std::nullopt; 96 } 97 98 /** Check if SelectionResult a is equivalent to SelectionResult b. 99 * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */ 100 static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b) 101 { 102 std::vector<CAmount> a_amts; 103 std::vector<CAmount> b_amts; 104 for (const auto& coin : a.GetInputSet()) { 105 a_amts.push_back(coin->txout.nValue); 106 } 107 for (const auto& coin : b.GetInputSet()) { 108 b_amts.push_back(coin->txout.nValue); 109 } 110 std::sort(a_amts.begin(), a_amts.end()); 111 std::sort(b_amts.begin(), b_amts.end()); 112 113 std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator> ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin()); 114 return ret.first == a_amts.end() && ret.second == b_amts.end(); 115 } 116 117 /** Check if this selection is equal to another one. Equal means same inputs (i.e same value and prevout) */ 118 static bool EqualResult(const SelectionResult& a, const SelectionResult& b) 119 { 120 std::pair<CoinSet::iterator, CoinSet::iterator> ret = std::mismatch(a.GetInputSet().begin(), a.GetInputSet().end(), b.GetInputSet().begin(), 121 [](const std::shared_ptr<COutput>& a, const std::shared_ptr<COutput>& b) { 122 return a->outpoint == b->outpoint; 123 }); 124 return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end(); 125 } 126 127 inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins, bool subtract_fee_outputs = false) 128 { 129 static std::vector<OutputGroup> static_groups; 130 static_groups.clear(); 131 for (auto& coin : available_coins) { 132 static_groups.emplace_back(); 133 OutputGroup& group = static_groups.back(); 134 group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/ 0, /*descendants=*/ 0); 135 group.m_subtract_fee_outputs = subtract_fee_outputs; 136 } 137 return static_groups; 138 } 139 140 inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinsResult& available_coins, CWallet& wallet, const CoinEligibilityFilter& filter) 141 { 142 FastRandomContext rand{}; 143 CoinSelectionParams coin_selection_params{ 144 rand, 145 /*change_output_size=*/ 0, 146 /*change_spend_size=*/ 0, 147 /*min_change_target=*/ CENT, 148 /*effective_feerate=*/ CFeeRate(0), 149 /*long_term_feerate=*/ CFeeRate(0), 150 /*discard_feerate=*/ CFeeRate(0), 151 /*tx_noinputs_size=*/ 0, 152 /*avoid_partial=*/ false, 153 }; 154 static OutputGroupTypeMap static_groups; 155 static_groups = GroupOutputs(wallet, available_coins, coin_selection_params, {{filter}})[filter]; 156 return static_groups.all_groups.mixed_group; 157 } 158 159 static std::unique_ptr<CWallet> NewWallet(const node::NodeContext& m_node, const std::string& wallet_name = "") 160 { 161 std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), wallet_name, CreateMockableWalletDatabase()); 162 LOCK(wallet->cs_wallet); 163 wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS); 164 wallet->SetupDescriptorScriptPubKeyMans(); 165 return wallet; 166 } 167 168 // Branch and bound coin selection tests 169 BOOST_AUTO_TEST_CASE(bnb_search_test) 170 { 171 FastRandomContext rand{}; 172 // Setup 173 std::vector<COutput> utxo_pool; 174 SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB); 175 176 //////////////////// 177 // Behavior tests // 178 //////////////////// 179 180 // Make sure that effective value is working in AttemptSelection when BnB is used 181 CoinSelectionParams coin_selection_params_bnb{ 182 rand, 183 /*change_output_size=*/ 31, 184 /*change_spend_size=*/ 68, 185 /*min_change_target=*/ 0, 186 /*effective_feerate=*/ CFeeRate(3000), 187 /*long_term_feerate=*/ CFeeRate(1000), 188 /*discard_feerate=*/ CFeeRate(1000), 189 /*tx_noinputs_size=*/ 0, 190 /*avoid_partial=*/ false, 191 }; 192 coin_selection_params_bnb.m_change_fee = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_output_size); 193 coin_selection_params_bnb.m_cost_of_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size) + coin_selection_params_bnb.m_change_fee; 194 coin_selection_params_bnb.min_viable_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size); 195 196 { 197 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 198 199 CoinsResult available_coins; 200 201 add_coin(available_coins, *wallet, 1, coin_selection_params_bnb.m_effective_feerate); 202 available_coins.All().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 203 BOOST_CHECK(!SelectCoinsBnB(GroupCoins(available_coins.All()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change)); 204 205 // Test fees subtracted from output: 206 available_coins.Clear(); 207 add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate); 208 available_coins.All().at(0).input_bytes = 40; 209 const auto result9 = SelectCoinsBnB(GroupCoins(available_coins.All()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change); 210 BOOST_CHECK(result9); 211 BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT); 212 } 213 214 { 215 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 216 217 CoinsResult available_coins; 218 219 coin_selection_params_bnb.m_effective_feerate = CFeeRate(0); 220 add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 221 add_coin(available_coins, *wallet, 3 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 222 add_coin(available_coins, *wallet, 2 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 223 CCoinControl coin_control; 224 coin_control.m_allow_other_inputs = true; 225 COutput select_coin = available_coins.All().at(0); 226 coin_control.Select(select_coin.outpoint); 227 PreSelectedInputs selected_input; 228 selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs); 229 available_coins.Erase({available_coins.coins[OutputType::BECH32].begin()->outpoint}); 230 231 LOCK(wallet->cs_wallet); 232 const auto result10 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb); 233 BOOST_CHECK(result10); 234 } 235 { 236 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 237 LOCK(wallet->cs_wallet); // Every 'SelectCoins' call requires it 238 239 CoinsResult available_coins; 240 241 // pre selected coin should be selected even if disadvantageous 242 coin_selection_params_bnb.m_effective_feerate = CFeeRate(5000); 243 coin_selection_params_bnb.m_long_term_feerate = CFeeRate(3000); 244 245 // Add selectable outputs, increasing their raw amounts by their input fee to make the effective value equal to the raw amount 246 CAmount input_fee = coin_selection_params_bnb.m_effective_feerate.GetFee(/*virtual_bytes=*/68); // bech32 input size (default test output type) 247 add_coin(available_coins, *wallet, 10 * CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 248 add_coin(available_coins, *wallet, 9 * CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 249 add_coin(available_coins, *wallet, 1 * CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 250 251 expected_result.Clear(); 252 add_coin(9 * CENT + input_fee, 2, expected_result); 253 add_coin(1 * CENT + input_fee, 2, expected_result); 254 CCoinControl coin_control; 255 coin_control.m_allow_other_inputs = true; 256 COutput select_coin = available_coins.All().at(1); // pre select 9 coin 257 coin_control.Select(select_coin.outpoint); 258 PreSelectedInputs selected_input; 259 selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs); 260 available_coins.Erase({(++available_coins.coins[OutputType::BECH32].begin())->outpoint}); 261 const auto result13 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb); 262 BOOST_CHECK(EquivalentResult(expected_result, *result13)); 263 } 264 265 { 266 // Test bnb max weight exceeded 267 // Inputs set [10, 9, 8, 5, 3, 1], Selection Target = 16 and coin 5 exceeding the max weight. 268 269 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 270 271 CoinsResult available_coins; 272 add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 273 add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 274 add_coin(available_coins, *wallet, 8 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 275 add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true, /*custom_size=*/MAX_STANDARD_TX_WEIGHT); 276 add_coin(available_coins, *wallet, 3 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 277 add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 278 279 CAmount selection_target = 16 * CENT; 280 const auto& no_res = SelectCoinsBnB(GroupCoins(available_coins.All(), /*subtract_fee_outputs*/true), 281 selection_target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT); 282 BOOST_REQUIRE(!no_res); 283 BOOST_CHECK(util::ErrorString(no_res).original.find("The inputs size exceeds the maximum weight") != std::string::npos); 284 285 // Now add same coin value with a good size and check that it gets selected 286 add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); 287 const auto& res = SelectCoinsBnB(GroupCoins(available_coins.All(), /*subtract_fee_outputs*/true), selection_target, /*cost_of_change=*/0); 288 289 expected_result.Clear(); 290 add_coin(8 * CENT, 2, expected_result); 291 add_coin(5 * CENT, 2, expected_result); 292 add_coin(3 * CENT, 2, expected_result); 293 BOOST_CHECK(EquivalentResult(expected_result, *res)); 294 } 295 } 296 297 BOOST_AUTO_TEST_CASE(bnb_sffo_restriction) 298 { 299 // Verify the coin selection process does not produce a BnB solution when SFFO is enabled. 300 // This is currently problematic because it could require a change output. And BnB is specialized on changeless solutions. 301 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 302 WITH_LOCK(wallet->cs_wallet, wallet->SetLastBlockProcessed(300, uint256{})); // set a high block so internal UTXOs are selectable 303 304 FastRandomContext rand{}; 305 CoinSelectionParams params{ 306 rand, 307 /*change_output_size=*/ 31, // unused value, p2wpkh output size (wallet default change type) 308 /*change_spend_size=*/ 68, // unused value, p2wpkh input size (high-r signature) 309 /*min_change_target=*/ 0, // dummy, set later 310 /*effective_feerate=*/ CFeeRate(3000), 311 /*long_term_feerate=*/ CFeeRate(1000), 312 /*discard_feerate=*/ CFeeRate(1000), 313 /*tx_noinputs_size=*/ 0, 314 /*avoid_partial=*/ false, 315 }; 316 params.m_subtract_fee_outputs = true; 317 params.m_change_fee = params.m_effective_feerate.GetFee(params.change_output_size); 318 params.m_cost_of_change = params.m_discard_feerate.GetFee(params.change_spend_size) + params.m_change_fee; 319 params.m_min_change_target = params.m_cost_of_change + 1; 320 // Add spendable coin at the BnB selection upper bound 321 CoinsResult available_coins; 322 add_coin(available_coins, *wallet, COIN + params.m_cost_of_change, /*feerate=*/params.m_effective_feerate, /*nAge=*/6, /*fIsFromMe=*/true, /*nInput=*/0, /*spendable=*/true); 323 add_coin(available_coins, *wallet, 0.5 * COIN + params.m_cost_of_change, /*feerate=*/params.m_effective_feerate, /*nAge=*/6, /*fIsFromMe=*/true, /*nInput=*/0, /*spendable=*/true); 324 add_coin(available_coins, *wallet, 0.5 * COIN, /*feerate=*/params.m_effective_feerate, /*nAge=*/6, /*fIsFromMe=*/true, /*nInput=*/0, /*spendable=*/true); 325 // Knapsack will only find a changeless solution on an exact match to the satoshi, SRD doesn’t look for changeless 326 // If BnB were run, it would produce a single input solution with the best waste score 327 auto result = WITH_LOCK(wallet->cs_wallet, return SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/{}, COIN, /*coin_control=*/{}, params)); 328 BOOST_CHECK(result.has_value()); 329 BOOST_CHECK_NE(result->GetAlgo(), SelectionAlgorithm::BNB); 330 BOOST_CHECK(result->GetInputSet().size() == 2); 331 // We have only considered BnB, SRD, and Knapsack. Test needs to be reevaluated if new algo is added 332 BOOST_CHECK(result->GetAlgo() == SelectionAlgorithm::SRD || result->GetAlgo() == SelectionAlgorithm::KNAPSACK); 333 } 334 335 BOOST_AUTO_TEST_CASE(knapsack_solver_test) 336 { 337 FastRandomContext rand{}; 338 const auto temp1{[&rand](std::vector<OutputGroup>& g, const CAmount& v, CAmount c) { return KnapsackSolver(g, v, c, rand); }}; 339 const auto KnapsackSolver{temp1}; 340 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 341 342 CoinsResult available_coins; 343 344 // test multiple times to allow for differences in the shuffle order 345 for (int i = 0; i < RUN_TESTS; i++) 346 { 347 available_coins.Clear(); 348 349 // with an empty wallet we can't even pay one cent 350 BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 1 * CENT, CENT)); 351 352 add_coin(available_coins, *wallet, 1*CENT, CFeeRate(0), 4); // add a new 1 cent coin 353 354 // with a new 1 cent coin, we still can't find a mature 1 cent 355 BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 1 * CENT, CENT)); 356 357 // but we can find a new 1 cent 358 const auto result1 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT); 359 BOOST_CHECK(result1); 360 BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT); 361 362 add_coin(available_coins, *wallet, 2*CENT); // add a mature 2 cent coin 363 364 // we can't make 3 cents of mature coins 365 BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 3 * CENT, CENT)); 366 367 // we can make 3 cents of new coins 368 const auto result2 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 3 * CENT, CENT); 369 BOOST_CHECK(result2); 370 BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 3 * CENT); 371 372 add_coin(available_coins, *wallet, 5*CENT); // add a mature 5 cent coin, 373 add_coin(available_coins, *wallet, 10*CENT, CFeeRate(0), 3, true); // a new 10 cent coin sent from one of our own addresses 374 add_coin(available_coins, *wallet, 20*CENT); // and a mature 20 cent coin 375 376 // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38 377 378 // we can't make 38 cents only if we disallow new coins: 379 BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 38 * CENT, CENT)); 380 // we can't even make 37 cents if we don't allow new coins even if they're from us 381 BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard_extra), 38 * CENT, CENT)); 382 // but we can make 37 cents if we accept new coins from ourself 383 const auto result3 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 37 * CENT, CENT); 384 BOOST_CHECK(result3); 385 BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 37 * CENT); 386 // and we can make 38 cents if we accept all new coins 387 const auto result4 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 38 * CENT, CENT); 388 BOOST_CHECK(result4); 389 BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 38 * CENT); 390 391 // try making 34 cents from 1,2,5,10,20 - we can't do it exactly 392 const auto result5 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 34 * CENT, CENT); 393 BOOST_CHECK(result5); 394 BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 35 * CENT); // but 35 cents is closest 395 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) 396 397 // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5 398 const auto result6 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 7 * CENT, CENT); 399 BOOST_CHECK(result6); 400 BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 7 * CENT); 401 BOOST_CHECK_EQUAL(result6->GetInputSet().size(), 2U); 402 403 // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough. 404 const auto result7 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 8 * CENT, CENT); 405 BOOST_CHECK(result7); 406 BOOST_CHECK(result7->GetSelectedValue() == 8 * CENT); 407 BOOST_CHECK_EQUAL(result7->GetInputSet().size(), 3U); 408 409 // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10) 410 const auto result8 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 9 * CENT, CENT); 411 BOOST_CHECK(result8); 412 BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 10 * CENT); 413 BOOST_CHECK_EQUAL(result8->GetInputSet().size(), 1U); 414 415 // now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin 416 available_coins.Clear(); 417 418 add_coin(available_coins, *wallet, 6*CENT); 419 add_coin(available_coins, *wallet, 7*CENT); 420 add_coin(available_coins, *wallet, 8*CENT); 421 add_coin(available_coins, *wallet, 20*CENT); 422 add_coin(available_coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total 423 424 // check that we have 71 and not 72 425 const auto result9 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 71 * CENT, CENT); 426 BOOST_CHECK(result9); 427 BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 72 * CENT, CENT)); 428 429 // 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 430 const auto result10 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 16 * CENT, CENT); 431 BOOST_CHECK(result10); 432 BOOST_CHECK_EQUAL(result10->GetSelectedValue(), 20 * CENT); // we should get 20 in one coin 433 BOOST_CHECK_EQUAL(result10->GetInputSet().size(), 1U); 434 435 add_coin(available_coins, *wallet, 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total 436 437 // 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 438 const auto result11 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 16 * CENT, CENT); 439 BOOST_CHECK(result11); 440 BOOST_CHECK_EQUAL(result11->GetSelectedValue(), 18 * CENT); // we should get 18 in 3 coins 441 BOOST_CHECK_EQUAL(result11->GetInputSet().size(), 3U); 442 443 add_coin(available_coins, *wallet, 18*CENT); // now we have 5+6+7+8+18+20+30 444 445 // 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 446 const auto result12 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 16 * CENT, CENT); 447 BOOST_CHECK(result12); 448 BOOST_CHECK_EQUAL(result12->GetSelectedValue(), 18 * CENT); // we should get 18 in 1 coin 449 BOOST_CHECK_EQUAL(result12->GetInputSet().size(), 1U); // because in the event of a tie, the biggest coin wins 450 451 // now try making 11 cents. we should get 5+6 452 const auto result13 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 11 * CENT, CENT); 453 BOOST_CHECK(result13); 454 BOOST_CHECK_EQUAL(result13->GetSelectedValue(), 11 * CENT); 455 BOOST_CHECK_EQUAL(result13->GetInputSet().size(), 2U); 456 457 // check that the smallest bigger coin is used 458 add_coin(available_coins, *wallet, 1*COIN); 459 add_coin(available_coins, *wallet, 2*COIN); 460 add_coin(available_coins, *wallet, 3*COIN); 461 add_coin(available_coins, *wallet, 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents 462 const auto result14 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 95 * CENT, CENT); 463 BOOST_CHECK(result14); 464 BOOST_CHECK_EQUAL(result14->GetSelectedValue(), 1 * COIN); // we should get 1 BTC in 1 coin 465 BOOST_CHECK_EQUAL(result14->GetInputSet().size(), 1U); 466 467 const auto result15 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 195 * CENT, CENT); 468 BOOST_CHECK(result15); 469 BOOST_CHECK_EQUAL(result15->GetSelectedValue(), 2 * COIN); // we should get 2 BTC in 1 coin 470 BOOST_CHECK_EQUAL(result15->GetInputSet().size(), 1U); 471 472 // empty the wallet and start again, now with fractions of a cent, to test small change avoidance 473 474 available_coins.Clear(); 475 add_coin(available_coins, *wallet, CENT * 1 / 10); 476 add_coin(available_coins, *wallet, CENT * 2 / 10); 477 add_coin(available_coins, *wallet, CENT * 3 / 10); 478 add_coin(available_coins, *wallet, CENT * 4 / 10); 479 add_coin(available_coins, *wallet, CENT * 5 / 10); 480 481 // try making 1 * CENT from the 1.5 * CENT 482 // we'll get change smaller than CENT whatever happens, so can expect CENT exactly 483 const auto result16 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT, CENT); 484 BOOST_CHECK(result16); 485 BOOST_CHECK_EQUAL(result16->GetSelectedValue(), CENT); 486 487 // but if we add a bigger coin, small change is avoided 488 add_coin(available_coins, *wallet, 1111*CENT); 489 490 // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5 491 const auto result17 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT); 492 BOOST_CHECK(result17); 493 BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * CENT); // we should get the exact amount 494 495 // if we add more small coins: 496 add_coin(available_coins, *wallet, CENT * 6 / 10); 497 add_coin(available_coins, *wallet, CENT * 7 / 10); 498 499 // and try again to make 1.0 * CENT 500 const auto result18 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT); 501 BOOST_CHECK(result18); 502 BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * CENT); // we should get the exact amount 503 504 // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf) 505 // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change 506 available_coins.Clear(); 507 for (int j = 0; j < 20; j++) 508 add_coin(available_coins, *wallet, 50000 * COIN); 509 510 const auto result19 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 500000 * COIN, CENT); 511 BOOST_CHECK(result19); 512 BOOST_CHECK_EQUAL(result19->GetSelectedValue(), 500000 * COIN); // we should get the exact amount 513 BOOST_CHECK_EQUAL(result19->GetInputSet().size(), 10U); // in ten coins 514 515 // 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), 516 // we need to try finding an exact subset anyway 517 518 // sometimes it will fail, and so we use the next biggest coin: 519 available_coins.Clear(); 520 add_coin(available_coins, *wallet, CENT * 5 / 10); 521 add_coin(available_coins, *wallet, CENT * 6 / 10); 522 add_coin(available_coins, *wallet, CENT * 7 / 10); 523 add_coin(available_coins, *wallet, 1111 * CENT); 524 const auto result20 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT); 525 BOOST_CHECK(result20); 526 BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * CENT); // we get the bigger coin 527 BOOST_CHECK_EQUAL(result20->GetInputSet().size(), 1U); 528 529 // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0) 530 available_coins.Clear(); 531 add_coin(available_coins, *wallet, CENT * 4 / 10); 532 add_coin(available_coins, *wallet, CENT * 6 / 10); 533 add_coin(available_coins, *wallet, CENT * 8 / 10); 534 add_coin(available_coins, *wallet, 1111 * CENT); 535 const auto result21 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT, CENT); 536 BOOST_CHECK(result21); 537 BOOST_CHECK_EQUAL(result21->GetSelectedValue(), CENT); // we should get the exact amount 538 BOOST_CHECK_EQUAL(result21->GetInputSet().size(), 2U); // in two coins 0.4+0.6 539 540 // test avoiding small change 541 available_coins.Clear(); 542 add_coin(available_coins, *wallet, CENT * 5 / 100); 543 add_coin(available_coins, *wallet, CENT * 1); 544 add_coin(available_coins, *wallet, CENT * 100); 545 546 // trying to make 100.01 from these three coins 547 const auto result22 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT * 10001 / 100, CENT); 548 BOOST_CHECK(result22); 549 BOOST_CHECK_EQUAL(result22->GetSelectedValue(), CENT * 10105 / 100); // we should get all coins 550 BOOST_CHECK_EQUAL(result22->GetInputSet().size(), 3U); 551 552 // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change 553 const auto result23 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT * 9990 / 100, CENT); 554 BOOST_CHECK(result23); 555 BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * CENT); 556 BOOST_CHECK_EQUAL(result23->GetInputSet().size(), 2U); 557 } 558 559 // test with many inputs 560 for (CAmount amt=1500; amt < COIN; amt*=10) { 561 available_coins.Clear(); 562 // Create 676 inputs (= (old MAX_STANDARD_TX_SIZE == 100000) / 148 bytes per input) 563 for (uint16_t j = 0; j < 676; j++) 564 add_coin(available_coins, *wallet, amt); 565 566 // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times. 567 for (int i = 0; i < RUN_TESTS; i++) { 568 const auto result24 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 2000, CENT); 569 BOOST_CHECK(result24); 570 571 if (amt - 2000 < CENT) { 572 // needs more than one input: 573 uint16_t returnSize = std::ceil((2000.0 + CENT)/amt); 574 CAmount returnValue = amt * returnSize; 575 BOOST_CHECK_EQUAL(result24->GetSelectedValue(), returnValue); 576 BOOST_CHECK_EQUAL(result24->GetInputSet().size(), returnSize); 577 } else { 578 // one input is sufficient: 579 BOOST_CHECK_EQUAL(result24->GetSelectedValue(), amt); 580 BOOST_CHECK_EQUAL(result24->GetInputSet().size(), 1U); 581 } 582 } 583 } 584 585 // test randomness 586 { 587 available_coins.Clear(); 588 for (int i2 = 0; i2 < 100; i2++) 589 add_coin(available_coins, *wallet, COIN); 590 591 // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times. 592 for (int i = 0; i < RUN_TESTS; i++) { 593 // picking 50 from 100 coins doesn't depend on the shuffle, 594 // but does depend on randomness in the stochastic approximation code 595 const auto result25 = KnapsackSolver(GroupCoins(available_coins.All()), 50 * COIN, CENT); 596 BOOST_CHECK(result25); 597 const auto result26 = KnapsackSolver(GroupCoins(available_coins.All()), 50 * COIN, CENT); 598 BOOST_CHECK(result26); 599 BOOST_CHECK(!EqualResult(*result25, *result26)); 600 601 int fails = 0; 602 for (int j = 0; j < RANDOM_REPEATS; j++) 603 { 604 // Test that the KnapsackSolver selects randomly from equivalent coins (same value and same input size). 605 // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice 606 // which will cause it to fail. 607 // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail 608 const auto result27 = KnapsackSolver(GroupCoins(available_coins.All()), COIN, CENT); 609 BOOST_CHECK(result27); 610 const auto result28 = KnapsackSolver(GroupCoins(available_coins.All()), COIN, CENT); 611 BOOST_CHECK(result28); 612 if (EqualResult(*result27, *result28)) 613 fails++; 614 } 615 BOOST_CHECK_NE(fails, RANDOM_REPEATS); 616 } 617 618 // add 75 cents in small change. not enough to make 90 cents, 619 // then try making 90 cents. there are multiple competing "smallest bigger" coins, 620 // one of which should be picked at random 621 add_coin(available_coins, *wallet, 5 * CENT); 622 add_coin(available_coins, *wallet, 10 * CENT); 623 add_coin(available_coins, *wallet, 15 * CENT); 624 add_coin(available_coins, *wallet, 20 * CENT); 625 add_coin(available_coins, *wallet, 25 * CENT); 626 627 for (int i = 0; i < RUN_TESTS; i++) { 628 int fails = 0; 629 for (int j = 0; j < RANDOM_REPEATS; j++) 630 { 631 const auto result29 = KnapsackSolver(GroupCoins(available_coins.All()), 90 * CENT, CENT); 632 BOOST_CHECK(result29); 633 const auto result30 = KnapsackSolver(GroupCoins(available_coins.All()), 90 * CENT, CENT); 634 BOOST_CHECK(result30); 635 if (EqualResult(*result29, *result30)) 636 fails++; 637 } 638 BOOST_CHECK_NE(fails, RANDOM_REPEATS); 639 } 640 } 641 } 642 643 BOOST_AUTO_TEST_CASE(ApproximateBestSubset) 644 { 645 FastRandomContext rand{}; 646 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 647 648 CoinsResult available_coins; 649 650 // Test vValue sort order 651 for (int i = 0; i < 1000; i++) 652 add_coin(available_coins, *wallet, 1000 * COIN); 653 add_coin(available_coins, *wallet, 3 * COIN); 654 655 const auto result = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 1003 * COIN, CENT, rand); 656 BOOST_CHECK(result); 657 BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN); 658 BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U); 659 } 660 661 // Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value 662 BOOST_AUTO_TEST_CASE(SelectCoins_test) 663 { 664 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 665 LOCK(wallet->cs_wallet); // Every 'SelectCoins' call requires it 666 667 // Random generator stuff 668 std::default_random_engine generator; 669 std::exponential_distribution<double> distribution (100); 670 FastRandomContext rand; 671 672 // Run this test 100 times 673 for (int i = 0; i < 100; ++i) 674 { 675 CoinsResult available_coins; 676 CAmount balance{0}; 677 678 // Make a wallet with 1000 exponentially distributed random inputs 679 for (int j = 0; j < 1000; ++j) 680 { 681 CAmount val = distribution(generator)*10000000; 682 add_coin(available_coins, *wallet, val); 683 balance += val; 684 } 685 686 // Generate a random fee rate in the range of 100 - 400 687 CFeeRate rate(rand.randrange(300) + 100); 688 689 // Generate a random target value between 1000 and wallet balance 690 CAmount target = rand.randrange(balance - 1000) + 1000; 691 692 // Perform selection 693 CoinSelectionParams cs_params{ 694 rand, 695 /*change_output_size=*/ 34, 696 /*change_spend_size=*/ 148, 697 /*min_change_target=*/ CENT, 698 /*effective_feerate=*/ CFeeRate(0), 699 /*long_term_feerate=*/ CFeeRate(0), 700 /*discard_feerate=*/ CFeeRate(0), 701 /*tx_noinputs_size=*/ 0, 702 /*avoid_partial=*/ false, 703 }; 704 cs_params.m_cost_of_change = 1; 705 cs_params.min_viable_change = 1; 706 CCoinControl cc; 707 const auto result = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/{}, target, cc, cs_params); 708 BOOST_CHECK(result); 709 BOOST_CHECK_GE(result->GetSelectedValue(), target); 710 } 711 } 712 713 BOOST_AUTO_TEST_CASE(waste_test) 714 { 715 const CAmount fee{100}; 716 const CAmount min_viable_change{300}; 717 const CAmount change_cost{125}; 718 const CAmount change_fee{30}; 719 const CAmount fee_diff{40}; 720 const CAmount in_amt{3 * COIN}; 721 const CAmount target{2 * COIN}; 722 const CAmount excess{80}; 723 const CAmount exact_target{in_amt - fee * 2}; // Maximum spendable amount after fees: no change, no excess 724 725 // In the following, we test that the waste is calculated correctly in various scenarios. 726 // Usually, RecalculateWaste would compute change_fee and change_cost on basis of the 727 // change output type, current feerate, and discard_feerate, but we use fixed values 728 // across this test to make the test easier to understand. 729 { 730 // Waste with change is the change cost and difference between fee and long term fee 731 SelectionResult selection1{target, SelectionAlgorithm::MANUAL}; 732 add_coin(1 * COIN, 1, selection1, /*fee=*/fee, /*long_term_fee=*/fee - fee_diff); 733 add_coin(2 * COIN, 2, selection1, fee, fee - fee_diff); 734 selection1.RecalculateWaste(min_viable_change, change_cost, change_fee); 735 BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, selection1.GetWaste()); 736 737 // Waste will be greater when fee is greater, but long term fee is the same 738 SelectionResult selection2{target, SelectionAlgorithm::MANUAL}; 739 add_coin(1 * COIN, 1, selection2, fee * 2, fee - fee_diff); 740 add_coin(2 * COIN, 2, selection2, fee * 2, fee - fee_diff); 741 selection2.RecalculateWaste(min_viable_change, change_cost, change_fee); 742 BOOST_CHECK_GT(selection2.GetWaste(), selection1.GetWaste()); 743 744 // Waste with change is the change cost and difference between fee and long term fee 745 // With long term fee greater than fee, waste should be less than when long term fee is less than fee 746 SelectionResult selection3{target, SelectionAlgorithm::MANUAL}; 747 add_coin(1 * COIN, 1, selection3, fee, fee + fee_diff); 748 add_coin(2 * COIN, 2, selection3, fee, fee + fee_diff); 749 selection3.RecalculateWaste(min_viable_change, change_cost, change_fee); 750 BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, selection3.GetWaste()); 751 BOOST_CHECK_LT(selection3.GetWaste(), selection1.GetWaste()); 752 } 753 754 { 755 // Waste without change is the excess and difference between fee and long term fee 756 SelectionResult selection_nochange1{exact_target - excess, SelectionAlgorithm::MANUAL}; 757 add_coin(1 * COIN, 1, selection_nochange1, fee, fee - fee_diff); 758 add_coin(2 * COIN, 2, selection_nochange1, fee, fee - fee_diff); 759 selection_nochange1.RecalculateWaste(min_viable_change, change_cost, change_fee); 760 BOOST_CHECK_EQUAL(fee_diff * 2 + excess, selection_nochange1.GetWaste()); 761 762 // Waste without change is the excess and difference between fee and long term fee 763 // With long term fee greater than fee, waste should be less than when long term fee is less than fee 764 SelectionResult selection_nochange2{exact_target - excess, SelectionAlgorithm::MANUAL}; 765 add_coin(1 * COIN, 1, selection_nochange2, fee, fee + fee_diff); 766 add_coin(2 * COIN, 2, selection_nochange2, fee, fee + fee_diff); 767 selection_nochange2.RecalculateWaste(min_viable_change, change_cost, change_fee); 768 BOOST_CHECK_EQUAL(fee_diff * -2 + excess, selection_nochange2.GetWaste()); 769 BOOST_CHECK_LT(selection_nochange2.GetWaste(), selection_nochange1.GetWaste()); 770 } 771 772 { 773 // Waste with change and fee == long term fee is just cost of change 774 SelectionResult selection{target, SelectionAlgorithm::MANUAL}; 775 add_coin(1 * COIN, 1, selection, fee, fee); 776 add_coin(2 * COIN, 2, selection, fee, fee); 777 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 778 BOOST_CHECK_EQUAL(change_cost, selection.GetWaste()); 779 } 780 781 { 782 // Waste without change and fee == long term fee is just the excess 783 SelectionResult selection{exact_target - excess, SelectionAlgorithm::MANUAL}; 784 add_coin(1 * COIN, 1, selection, fee, fee); 785 add_coin(2 * COIN, 2, selection, fee, fee); 786 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 787 BOOST_CHECK_EQUAL(excess, selection.GetWaste()); 788 } 789 790 { 791 // Waste is 0 when fee == long_term_fee, no change, and no excess 792 SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL}; 793 add_coin(1 * COIN, 1, selection, fee, fee); 794 add_coin(2 * COIN, 2, selection, fee, fee); 795 selection.RecalculateWaste(min_viable_change, change_cost , change_fee); 796 BOOST_CHECK_EQUAL(0, selection.GetWaste()); 797 } 798 799 { 800 // Waste is 0 when (fee - long_term_fee) == (-cost_of_change), and no excess 801 SelectionResult selection{target, SelectionAlgorithm::MANUAL}; 802 add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); 803 add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); 804 selection.RecalculateWaste(min_viable_change, /*change_cost=*/fee_diff * 2, change_fee); 805 BOOST_CHECK_EQUAL(0, selection.GetWaste()); 806 } 807 808 { 809 // Waste is 0 when (fee - long_term_fee) == (-excess), no change cost 810 const CAmount new_target{exact_target - /*excess=*/fee_diff * 2}; 811 SelectionResult selection{new_target, SelectionAlgorithm::MANUAL}; 812 add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); 813 add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); 814 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 815 BOOST_CHECK_EQUAL(0, selection.GetWaste()); 816 } 817 818 { 819 // Negative waste when the long term fee is greater than the current fee and the selected value == target 820 SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL}; 821 const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff)) 822 add_coin(1 * COIN, 1, selection, fee, fee + fee_diff); 823 add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); 824 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 825 BOOST_CHECK_EQUAL(target_waste1, selection.GetWaste()); 826 } 827 828 { 829 // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee)) 830 SelectionResult selection{target, SelectionAlgorithm::MANUAL}; 831 const CAmount large_fee_diff{90}; 832 const CAmount target_waste2{-2 * large_fee_diff + change_cost}; 833 // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost 834 // = (2 * 100) - (2 * (100 + 90)) + 125 835 // = 200 - 380 + 125 = -55 836 assert(target_waste2 == -55); 837 add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff); 838 add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff); 839 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 840 BOOST_CHECK_EQUAL(target_waste2, selection.GetWaste()); 841 } 842 } 843 844 845 BOOST_AUTO_TEST_CASE(bump_fee_test) 846 { 847 const CAmount fee{100}; 848 const CAmount min_viable_change{200}; 849 const CAmount change_cost{125}; 850 const CAmount change_fee{35}; 851 const CAmount fee_diff{40}; 852 const CAmount target{2 * COIN}; 853 854 { 855 SelectionResult selection{target, SelectionAlgorithm::MANUAL}; 856 add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff); 857 add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); 858 const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector(); 859 860 for (size_t i = 0; i < inputs.size(); ++i) { 861 inputs[i]->ApplyBumpFee(20*(i+1)); 862 } 863 864 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 865 CAmount expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60; 866 BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); 867 868 selection.SetBumpFeeDiscount(30); 869 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 870 expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60 - /*group_discount=*/30; 871 BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); 872 } 873 874 { 875 // Test with changeless transaction 876 // 877 // Bump fees and excess both contribute fully to the waste score, 878 // therefore, a bump fee group discount will not change the waste 879 // score as long as we do not create change in both instances. 880 CAmount changeless_target = 3 * COIN - 2 * fee - 100; 881 SelectionResult selection{changeless_target, SelectionAlgorithm::MANUAL}; 882 add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff); 883 add_coin(2 * COIN, 2, selection, fee, fee + fee_diff); 884 const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector(); 885 886 for (size_t i = 0; i < inputs.size(); ++i) { 887 inputs[i]->ApplyBumpFee(20*(i+1)); 888 } 889 890 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 891 CAmount expected_waste = fee_diff * -2 + /*bump_fees=*/60 + /*excess = 100 - bump_fees*/40; 892 BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); 893 894 selection.SetBumpFeeDiscount(30); 895 selection.RecalculateWaste(min_viable_change, change_cost, change_fee); 896 expected_waste = fee_diff * -2 + /*bump_fees=*/60 - /*group_discount=*/30 + /*excess = 100 - bump_fees + group_discount*/70; 897 BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste()); 898 } 899 } 900 901 BOOST_AUTO_TEST_CASE(effective_value_test) 902 { 903 const int input_bytes = 148; 904 const CFeeRate feerate(1000); 905 const CAmount nValue = 10000; 906 const int nInput = 0; 907 908 CMutableTransaction tx; 909 tx.vout.resize(1); 910 tx.vout[nInput].nValue = nValue; 911 912 // standard case, pass feerate in constructor 913 COutput output1(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, feerate); 914 const CAmount expected_ev1 = 9852; // 10000 - 148 915 BOOST_CHECK_EQUAL(output1.GetEffectiveValue(), expected_ev1); 916 917 // input bytes unknown (input_bytes = -1), pass feerate in constructor 918 COutput output2(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/ false, feerate); 919 BOOST_CHECK_EQUAL(output2.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1 920 921 // negative effective value, pass feerate in constructor 922 COutput output3(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, CFeeRate(100000)); 923 const CAmount expected_ev3 = -4800; // 10000 - 14800 924 BOOST_CHECK_EQUAL(output3.GetEffectiveValue(), expected_ev3); 925 926 // standard case, pass fees in constructor 927 const CAmount fees = 148; 928 COutput output4(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, fees); 929 BOOST_CHECK_EQUAL(output4.GetEffectiveValue(), expected_ev1); 930 931 // input bytes unknown (input_bytes = -1), pass fees in constructor 932 COutput output5(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/0); 933 BOOST_CHECK_EQUAL(output5.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1 934 } 935 936 static util::Result<SelectionResult> CoinGrinder(const CAmount& target, 937 const CoinSelectionParams& cs_params, 938 const node::NodeContext& m_node, 939 int max_selection_weight, 940 std::function<CoinsResult(CWallet&)> coin_setup) 941 { 942 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 943 CoinEligibilityFilter filter(0, 0, 0); // accept all coins without ancestors 944 Groups group = GroupOutputs(*wallet, coin_setup(*wallet), cs_params, {{filter}})[filter].all_groups; 945 return CoinGrinder(group.positive_group, target, cs_params.m_min_change_target, max_selection_weight); 946 } 947 948 BOOST_AUTO_TEST_CASE(coin_grinder_tests) 949 { 950 // Test Coin Grinder: 951 // 1) Insufficient funds, select all provided coins and fail. 952 // 2) Exceeded max weight, coin selection always surpasses the max allowed weight. 953 // 3) Select coins without surpassing the max weight (some coins surpasses the max allowed weight, some others not) 954 // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO 955 // 5) Test finding a solution in a UTXO pool with mixed weights 956 // 6) Test that the lightest solution among many clones is found 957 // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead 958 959 FastRandomContext rand; 960 CoinSelectionParams dummy_params{ // Only used to provide the 'avoid_partial' flag. 961 rand, 962 /*change_output_size=*/34, 963 /*change_spend_size=*/68, 964 /*min_change_target=*/CENT, 965 /*effective_feerate=*/CFeeRate(5000), 966 /*long_term_feerate=*/CFeeRate(2000), 967 /*discard_feerate=*/CFeeRate(1000), 968 /*tx_noinputs_size=*/10 + 34, // static header size + output size 969 /*avoid_partial=*/false, 970 }; 971 972 { 973 // ######################################################### 974 // 1) Insufficient funds, select all provided coins and fail 975 // ######################################################### 976 CAmount target = 49.5L * COIN; 977 int max_selection_weight = 10'000; // high enough to not fail for this reason. 978 const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 979 CoinsResult available_coins; 980 for (int j = 0; j < 10; ++j) { 981 add_coin(available_coins, wallet, CAmount(1 * COIN)); 982 add_coin(available_coins, wallet, CAmount(2 * COIN)); 983 } 984 return available_coins; 985 }); 986 BOOST_CHECK(!res); 987 BOOST_CHECK(util::ErrorString(res).empty()); // empty means "insufficient funds" 988 } 989 990 { 991 // ########################### 992 // 2) Test max weight exceeded 993 // ########################### 994 CAmount target = 29.5L * COIN; 995 int max_selection_weight = 3000; 996 const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 997 CoinsResult available_coins; 998 for (int j = 0; j < 10; ++j) { 999 add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true); 1000 add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true); 1001 } 1002 return available_coins; 1003 }); 1004 BOOST_CHECK(!res); 1005 BOOST_CHECK(util::ErrorString(res).original.find("The inputs size exceeds the maximum weight") != std::string::npos); 1006 } 1007 1008 { 1009 // ############################################################################################################### 1010 // 3) Test that the lowest-weight solution is found when some combinations would exceed the allowed weight 1011 // ################################################################################################################ 1012 CAmount target = 25.33L * COIN; 1013 int max_selection_weight = 10'000; // WU 1014 const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1015 CoinsResult available_coins; 1016 for (int j = 0; j < 60; ++j) { // 60 UTXO --> 19,8 BTC total --> 60 × 272 WU = 16320 WU 1017 add_coin(available_coins, wallet, CAmount(0.33 * COIN), CFeeRate(5000), 144, false, 0, true); 1018 } 1019 for (int i = 0; i < 10; i++) { // 10 UTXO --> 20 BTC total --> 10 × 272 WU = 2720 WU 1020 add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true); 1021 } 1022 return available_coins; 1023 }); 1024 SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); 1025 for (int i = 0; i < 10; ++i) { 1026 add_coin(2 * COIN, i, expected_result); 1027 } 1028 for (int j = 0; j < 17; ++j) { 1029 add_coin(0.33 * COIN, j + 10, expected_result); 1030 } 1031 BOOST_CHECK(EquivalentResult(expected_result, *res)); 1032 // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. 1033 size_t expected_attempts = 37; 1034 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); 1035 } 1036 1037 { 1038 // ################################################################################################################# 1039 // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO 1040 // ################################################################################################################# 1041 CAmount target = 1.9L * COIN; 1042 int max_selection_weight = 400'000; // WU 1043 const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1044 CoinsResult available_coins; 1045 add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true, 148); 1046 add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68); 1047 add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68); 1048 return available_coins; 1049 }); 1050 SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); 1051 add_coin(1 * COIN, 1, expected_result); 1052 add_coin(1 * COIN, 2, expected_result); 1053 BOOST_CHECK(EquivalentResult(expected_result, *res)); 1054 // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. 1055 size_t expected_attempts = 3; 1056 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); 1057 } 1058 1059 { 1060 // ############################################################################################################### 1061 // 5) Test finding a solution in a UTXO pool with mixed weights 1062 // ################################################################################################################ 1063 CAmount target = 30L * COIN; 1064 int max_selection_weight = 400'000; // WU 1065 const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1066 CoinsResult available_coins; 1067 for (int j = 0; j < 5; ++j) { 1068 // Add heavy coins {3, 6, 9, 12, 15} 1069 add_coin(available_coins, wallet, CAmount((3 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 350); 1070 // Add medium coins {2, 5, 8, 11, 14} 1071 add_coin(available_coins, wallet, CAmount((2 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 250); 1072 // Add light coins {1, 4, 7, 10, 13} 1073 add_coin(available_coins, wallet, CAmount((1 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 150); 1074 } 1075 return available_coins; 1076 }); 1077 BOOST_CHECK(res); 1078 SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); 1079 add_coin(14 * COIN, 1, expected_result); 1080 add_coin(13 * COIN, 2, expected_result); 1081 add_coin(4 * COIN, 3, expected_result); 1082 BOOST_CHECK(EquivalentResult(expected_result, *res)); 1083 // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. 1084 size_t expected_attempts = 92; 1085 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); 1086 } 1087 1088 { 1089 // ################################################################################################################# 1090 // 6) Test that the lightest solution among many clones is found 1091 // ################################################################################################################# 1092 CAmount target = 9.9L * COIN; 1093 int max_selection_weight = 400'000; // WU 1094 const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1095 CoinsResult available_coins; 1096 // Expected Result: 4 + 3 + 2 + 1 = 10 BTC at 400 vB 1097 add_coin(available_coins, wallet, CAmount(4 * COIN), CFeeRate(5000), 144, false, 0, true, 100); 1098 add_coin(available_coins, wallet, CAmount(3 * COIN), CFeeRate(5000), 144, false, 0, true, 100); 1099 add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true, 100); 1100 add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 100); 1101 // Distracting clones: 1102 for (int j = 0; j < 100; ++j) { 1103 add_coin(available_coins, wallet, CAmount(8 * COIN), CFeeRate(5000), 144, false, 0, true, 1000); 1104 } 1105 for (int j = 0; j < 100; ++j) { 1106 add_coin(available_coins, wallet, CAmount(7 * COIN), CFeeRate(5000), 144, false, 0, true, 800); 1107 } 1108 for (int j = 0; j < 100; ++j) { 1109 add_coin(available_coins, wallet, CAmount(6 * COIN), CFeeRate(5000), 144, false, 0, true, 600); 1110 } 1111 for (int j = 0; j < 100; ++j) { 1112 add_coin(available_coins, wallet, CAmount(5 * COIN), CFeeRate(5000), 144, false, 0, true, 400); 1113 } 1114 return available_coins; 1115 }); 1116 SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); 1117 add_coin(4 * COIN, 0, expected_result); 1118 add_coin(3 * COIN, 0, expected_result); 1119 add_coin(2 * COIN, 0, expected_result); 1120 add_coin(1 * COIN, 0, expected_result); 1121 BOOST_CHECK(EquivalentResult(expected_result, *res)); 1122 // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. 1123 size_t expected_attempts = 38; 1124 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); 1125 } 1126 1127 { 1128 // ################################################################################################################# 1129 // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead 1130 // ################################################################################################################# 1131 CAmount target = 1.9L * COIN; 1132 int max_selection_weight = 40000; // WU 1133 const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1134 CoinsResult available_coins; 1135 add_coin(available_coins, wallet, CAmount(1.8 * COIN), CFeeRate(5000), 144, false, 0, true, 2500); 1136 add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000); 1137 add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000); 1138 for (int j = 0; j < 100; ++j) { 1139 // make a 100 unique coins only differing by one sat 1140 add_coin(available_coins, wallet, CAmount(0.01 * COIN + j), CFeeRate(5000), 144, false, 0, true, 110); 1141 } 1142 return available_coins; 1143 }); 1144 SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); 1145 add_coin(1 * COIN, 1, expected_result); 1146 add_coin(1 * COIN, 2, expected_result); 1147 BOOST_CHECK(EquivalentResult(expected_result, *res)); 1148 // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. 1149 size_t expected_attempts = 7; 1150 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); 1151 } 1152 } 1153 1154 static util::Result<SelectionResult> SelectCoinsSRD(const CAmount& target, 1155 const CoinSelectionParams& cs_params, 1156 const node::NodeContext& m_node, 1157 int max_selection_weight, 1158 std::function<CoinsResult(CWallet&)> coin_setup) 1159 { 1160 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 1161 CoinEligibilityFilter filter(0, 0, 0); // accept all coins without ancestors 1162 Groups group = GroupOutputs(*wallet, coin_setup(*wallet), cs_params, {{filter}})[filter].all_groups; 1163 return SelectCoinsSRD(group.positive_group, target, cs_params.m_change_fee, cs_params.rng_fast, max_selection_weight); 1164 } 1165 1166 BOOST_AUTO_TEST_CASE(srd_tests) 1167 { 1168 // Test SRD: 1169 // 1) Insufficient funds, select all provided coins and fail. 1170 // 2) Exceeded max weight, coin selection always surpasses the max allowed weight. 1171 // 3) Select coins without surpassing the max weight (some coins surpasses the max allowed weight, some others not) 1172 1173 FastRandomContext rand; 1174 CoinSelectionParams dummy_params{ // Only used to provide the 'avoid_partial' flag. 1175 rand, 1176 /*change_output_size=*/34, 1177 /*change_spend_size=*/68, 1178 /*min_change_target=*/CENT, 1179 /*effective_feerate=*/CFeeRate(0), 1180 /*long_term_feerate=*/CFeeRate(0), 1181 /*discard_feerate=*/CFeeRate(0), 1182 /*tx_noinputs_size=*/10 + 34, // static header size + output size 1183 /*avoid_partial=*/false, 1184 }; 1185 1186 { 1187 // ######################################################### 1188 // 1) Insufficient funds, select all provided coins and fail 1189 // ######################################################### 1190 CAmount target = 49.5L * COIN; 1191 int max_selection_weight = 10000; // high enough to not fail for this reason. 1192 const auto& res = SelectCoinsSRD(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1193 CoinsResult available_coins; 1194 for (int j = 0; j < 10; ++j) { 1195 add_coin(available_coins, wallet, CAmount(1 * COIN)); 1196 add_coin(available_coins, wallet, CAmount(2 * COIN)); 1197 } 1198 return available_coins; 1199 }); 1200 BOOST_CHECK(!res); 1201 BOOST_CHECK(util::ErrorString(res).empty()); // empty means "insufficient funds" 1202 } 1203 1204 { 1205 // ########################### 1206 // 2) Test max weight exceeded 1207 // ########################### 1208 CAmount target = 49.5L * COIN; 1209 int max_selection_weight = 3000; 1210 const auto& res = SelectCoinsSRD(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1211 CoinsResult available_coins; 1212 for (int j = 0; j < 10; ++j) { 1213 /* 10 × 1 BTC + 10 × 2 BTC = 30 BTC. 20 × 272 WU = 5440 WU */ 1214 add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(0), 144, false, 0, true); 1215 add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(0), 144, false, 0, true); 1216 } 1217 return available_coins; 1218 }); 1219 BOOST_CHECK(!res); 1220 BOOST_CHECK(util::ErrorString(res).original.find("The inputs size exceeds the maximum weight") != std::string::npos); 1221 } 1222 1223 { 1224 // ################################################################################################################ 1225 // 3) Test that SRD result does not exceed the max weight 1226 // ################################################################################################################ 1227 CAmount target = 25.33L * COIN; 1228 int max_selection_weight = 10000; // WU 1229 const auto& res = SelectCoinsSRD(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) { 1230 CoinsResult available_coins; 1231 for (int j = 0; j < 60; ++j) { // 60 UTXO --> 19,8 BTC total --> 60 × 272 WU = 16320 WU 1232 add_coin(available_coins, wallet, CAmount(0.33 * COIN), CFeeRate(0), 144, false, 0, true); 1233 } 1234 for (int i = 0; i < 10; i++) { // 10 UTXO --> 20 BTC total --> 10 × 272 WU = 2720 WU 1235 add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(0), 144, false, 0, true); 1236 } 1237 return available_coins; 1238 }); 1239 BOOST_CHECK(res); 1240 BOOST_CHECK(res->GetWeight() <= max_selection_weight); 1241 } 1242 } 1243 1244 static util::Result<SelectionResult> select_coins(const CAmount& target, const CoinSelectionParams& cs_params, const CCoinControl& cc, std::function<CoinsResult(CWallet&)> coin_setup, const node::NodeContext& m_node) 1245 { 1246 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 1247 auto available_coins = coin_setup(*wallet); 1248 1249 LOCK(wallet->cs_wallet); 1250 auto result = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/ {}, target, cc, cs_params); 1251 if (result) { 1252 const auto signedTxSize = 10 + 34 + 68 * result->GetInputSet().size(); // static header size + output size + inputs size (P2WPKH) 1253 BOOST_CHECK_LE(signedTxSize * WITNESS_SCALE_FACTOR, MAX_STANDARD_TX_WEIGHT); 1254 1255 BOOST_CHECK_GE(result->GetSelectedValue(), target); 1256 } 1257 return result; 1258 } 1259 1260 static bool has_coin(const CoinSet& set, CAmount amount) 1261 { 1262 return std::any_of(set.begin(), set.end(), [&](const auto& coin) { return coin->GetEffectiveValue() == amount; }); 1263 } 1264 1265 BOOST_AUTO_TEST_CASE(check_max_selection_weight) 1266 { 1267 const CAmount target = 49.5L * COIN; 1268 CCoinControl cc; 1269 1270 FastRandomContext rand; 1271 CoinSelectionParams cs_params{ 1272 rand, 1273 /*change_output_size=*/34, 1274 /*change_spend_size=*/68, 1275 /*min_change_target=*/CENT, 1276 /*effective_feerate=*/CFeeRate(0), 1277 /*long_term_feerate=*/CFeeRate(0), 1278 /*discard_feerate=*/CFeeRate(0), 1279 /*tx_noinputs_size=*/10 + 34, // static header size + output size 1280 /*avoid_partial=*/false, 1281 }; 1282 1283 int max_weight = MAX_STANDARD_TX_WEIGHT - WITNESS_SCALE_FACTOR * (cs_params.tx_noinputs_size + cs_params.change_output_size); 1284 { 1285 // Scenario 1: 1286 // The actor starts with 1x 50.0 BTC and 1515x 0.033 BTC (~100.0 BTC total) unspent outputs 1287 // Then tries to spend 49.5 BTC 1288 // The 50.0 BTC output should be selected, because the transaction would otherwise be too large 1289 1290 // Perform selection 1291 1292 const auto result = select_coins( 1293 target, cs_params, cc, [&](CWallet& wallet) { 1294 CoinsResult available_coins; 1295 for (int j = 0; j < 1515; ++j) { 1296 add_coin(available_coins, wallet, CAmount(0.033 * COIN), CFeeRate(0), 144, false, 0, true); 1297 } 1298 1299 add_coin(available_coins, wallet, CAmount(50 * COIN), CFeeRate(0), 144, false, 0, true); 1300 return available_coins; 1301 }, 1302 m_node); 1303 1304 BOOST_CHECK(result); 1305 // Verify that the 50 BTC UTXO was selected, and result is below max_weight 1306 BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(50 * COIN))); 1307 BOOST_CHECK_LE(result->GetWeight(), max_weight); 1308 } 1309 1310 { 1311 // Scenario 2: 1312 1313 // The actor starts with 400x 0.0625 BTC and 2000x 0.025 BTC (75.0 BTC total) unspent outputs 1314 // Then tries to spend 49.5 BTC 1315 // A combination of coins should be selected, such that the created transaction is not too large 1316 1317 // Perform selection 1318 const auto result = select_coins( 1319 target, cs_params, cc, [&](CWallet& wallet) { 1320 CoinsResult available_coins; 1321 for (int j = 0; j < 400; ++j) { 1322 add_coin(available_coins, wallet, CAmount(0.0625 * COIN), CFeeRate(0), 144, false, 0, true); 1323 } 1324 for (int j = 0; j < 2000; ++j) { 1325 add_coin(available_coins, wallet, CAmount(0.025 * COIN), CFeeRate(0), 144, false, 0, true); 1326 } 1327 return available_coins; 1328 }, 1329 m_node); 1330 1331 BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.0625 * COIN))); 1332 BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.025 * COIN))); 1333 BOOST_CHECK_LE(result->GetWeight(), max_weight); 1334 } 1335 1336 { 1337 // Scenario 3: 1338 1339 // The actor starts with 1515x 0.033 BTC (49.995 BTC total) unspent outputs 1340 // No results should be returned, because the transaction would be too large 1341 1342 // Perform selection 1343 const auto result = select_coins( 1344 target, cs_params, cc, [&](CWallet& wallet) { 1345 CoinsResult available_coins; 1346 for (int j = 0; j < 1515; ++j) { 1347 add_coin(available_coins, wallet, CAmount(0.033 * COIN), CFeeRate(0), 144, false, 0, true); 1348 } 1349 return available_coins; 1350 }, 1351 m_node); 1352 1353 // No results 1354 // 1515 inputs * 68 bytes = 103,020 bytes 1355 // 103,020 bytes * 4 = 412,080 weight, which is above the MAX_STANDARD_TX_WEIGHT of 400,000 1356 BOOST_CHECK(!result); 1357 } 1358 } 1359 1360 BOOST_AUTO_TEST_CASE(SelectCoins_effective_value_test) 1361 { 1362 // Test that the effective value is used to check whether preset inputs provide sufficient funds when subtract_fee_outputs is not used. 1363 // This test creates a coin whose value is higher than the target but whose effective value is lower than the target. 1364 // The coin is selected using coin control, with m_allow_other_inputs = false. SelectCoins should fail due to insufficient funds. 1365 1366 std::unique_ptr<CWallet> wallet = NewWallet(m_node); 1367 1368 CoinsResult available_coins; 1369 { 1370 std::unique_ptr<CWallet> dummyWallet = NewWallet(m_node, /*wallet_name=*/"dummy"); 1371 add_coin(available_coins, *dummyWallet, 100000); // 0.001 BTC 1372 } 1373 1374 CAmount target{99900}; // 0.000999 BTC 1375 1376 FastRandomContext rand; 1377 CoinSelectionParams cs_params{ 1378 rand, 1379 /*change_output_size=*/34, 1380 /*change_spend_size=*/148, 1381 /*min_change_target=*/1000, 1382 /*effective_feerate=*/CFeeRate(3000), 1383 /*long_term_feerate=*/CFeeRate(1000), 1384 /*discard_feerate=*/CFeeRate(1000), 1385 /*tx_noinputs_size=*/0, 1386 /*avoid_partial=*/false, 1387 }; 1388 CCoinControl cc; 1389 cc.m_allow_other_inputs = false; 1390 COutput output = available_coins.All().at(0); 1391 cc.SetInputWeight(output.outpoint, 148); 1392 cc.Select(output.outpoint).SetTxOut(output.txout); 1393 1394 LOCK(wallet->cs_wallet); 1395 const auto preset_inputs = *Assert(FetchSelectedInputs(*wallet, cc, cs_params)); 1396 available_coins.Erase({available_coins.coins[OutputType::BECH32].begin()->outpoint}); 1397 1398 const auto result = SelectCoins(*wallet, available_coins, preset_inputs, target, cc, cs_params); 1399 BOOST_CHECK(!result); 1400 } 1401 1402 BOOST_FIXTURE_TEST_CASE(wallet_coinsresult_test, BasicTestingSetup) 1403 { 1404 // Test case to verify CoinsResult object sanity. 1405 CoinsResult available_coins; 1406 { 1407 std::unique_ptr<CWallet> dummyWallet = NewWallet(m_node, /*wallet_name=*/"dummy"); 1408 1409 // Add some coins to 'available_coins' 1410 for (int i=0; i<10; i++) { 1411 add_coin(available_coins, *dummyWallet, 1 * COIN); 1412 } 1413 } 1414 1415 { 1416 // First test case, check that 'CoinsResult::Erase' function works as expected. 1417 // By trying to erase two elements from the 'available_coins' object. 1418 std::unordered_set<COutPoint, SaltedOutpointHasher> outs_to_remove; 1419 const auto& coins = available_coins.All(); 1420 for (int i = 0; i < 2; i++) { 1421 outs_to_remove.emplace(coins[i].outpoint); 1422 } 1423 available_coins.Erase(outs_to_remove); 1424 1425 // Check that the elements were actually removed. 1426 const auto& updated_coins = available_coins.All(); 1427 for (const auto& out: outs_to_remove) { 1428 auto it = std::find_if(updated_coins.begin(), updated_coins.end(), [&out](const COutput &coin) { 1429 return coin.outpoint == out; 1430 }); 1431 BOOST_CHECK(it == updated_coins.end()); 1432 } 1433 // And verify that no extra element were removed 1434 BOOST_CHECK_EQUAL(available_coins.Size(), 8); 1435 } 1436 } 1437 1438 BOOST_AUTO_TEST_SUITE_END() 1439 } // namespace wallet