diff options
| -rw-r--r-- | src/Makefile.test.include | 1 | ||||
| -rw-r--r-- | src/bench/coin_selection.cpp | 6 | ||||
| -rw-r--r-- | src/wallet/rpc/coins.cpp | 2 | ||||
| -rw-r--r-- | src/wallet/rpc/spend.cpp | 2 | ||||
| -rw-r--r-- | src/wallet/spend.cpp | 164 | ||||
| -rw-r--r-- | src/wallet/spend.h | 69 | ||||
| -rw-r--r-- | src/wallet/test/availablecoins_tests.cpp | 105 | ||||
| -rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 264 | ||||
| -rw-r--r-- | src/wallet/test/wallet_tests.cpp | 4 | ||||
| -rwxr-xr-x | test/functional/test_runner.py | 1 | ||||
| -rwxr-xr-x | test/functional/wallet_avoid_mixing_output_types.py | 176 |
11 files changed, 612 insertions, 182 deletions
diff --git a/src/Makefile.test.include b/src/Makefile.test.include index d8ff64bc43..f52964b033 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -168,6 +168,7 @@ BITCOIN_TESTS += \ wallet/test/wallet_crypto_tests.cpp \ wallet/test/wallet_transaction_tests.cpp \ wallet/test/coinselector_tests.cpp \ + wallet/test/availablecoins_tests.cpp \ wallet/test/init_tests.cpp \ wallet/test/ismine_tests.cpp \ wallet/test/scriptpubkeyman_tests.cpp diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index eaefb9b63a..a80ec3703c 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -56,10 +56,10 @@ static void CoinSelection(benchmark::Bench& bench) addCoin(3 * COIN, wallet, wtxs); // Create coins - std::vector<COutput> coins; + wallet::CoinsResult available_coins; for (const auto& wtx : wtxs) { const auto txout = wtx->tx->vout.at(0); - coins.emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/true, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0); + available_coins.bech32.emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/true, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0); } const CoinEligibilityFilter filter_standard(1, 6, 0); @@ -76,7 +76,7 @@ static void CoinSelection(benchmark::Bench& bench) /*avoid_partial=*/ false, }; bench.run([&] { - auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, coin_selection_params); + auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, available_coins, coin_selection_params, /*allow_mixed_output_types=*/true); assert(result); assert(result->GetSelectedValue() == 1003 * COIN); assert(result->GetInputSet().size() == 2); diff --git a/src/wallet/rpc/coins.cpp b/src/wallet/rpc/coins.cpp index 9e992294ff..d40d800f28 100644 --- a/src/wallet/rpc/coins.cpp +++ b/src/wallet/rpc/coins.cpp @@ -638,7 +638,7 @@ RPCHelpMan listunspent() cctl.m_max_depth = nMaxDepth; cctl.m_include_unsafe_inputs = include_unsafe; LOCK(pwallet->cs_wallet); - vecOutputs = AvailableCoinsListUnspent(*pwallet, &cctl, nMinimumAmount, nMaximumAmount, nMinimumSumAmount, nMaximumCount).coins; + vecOutputs = AvailableCoinsListUnspent(*pwallet, &cctl, nMinimumAmount, nMaximumAmount, nMinimumSumAmount, nMaximumCount).all(); } LOCK(pwallet->cs_wallet); diff --git a/src/wallet/rpc/spend.cpp b/src/wallet/rpc/spend.cpp index b5472efa61..e27cb1139e 100644 --- a/src/wallet/rpc/spend.cpp +++ b/src/wallet/rpc/spend.cpp @@ -1382,7 +1382,7 @@ RPCHelpMan sendall() total_input_value += tx->tx->vout[input.prevout.n].nValue; } } else { - for (const COutput& output : AvailableCoins(*pwallet, &coin_control, fee_rate, /*nMinimumAmount=*/0).coins) { + for (const COutput& output : AvailableCoins(*pwallet, &coin_control, fee_rate, /*nMinimumAmount=*/0).all()) { CHECK_NONFATAL(output.input_bytes > 0); if (send_max && fee_rate.GetFee(output.input_bytes) > output.txout.nValue) { continue; diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 9be29c4709..c00a2cd023 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -79,6 +79,32 @@ TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *walle return CalculateMaximumSignedTxSize(tx, wallet, txouts, coin_control); } +uint64_t CoinsResult::size() const +{ + return bech32m.size() + bech32.size() + P2SH_segwit.size() + legacy.size() + other.size(); +} + +std::vector<COutput> CoinsResult::all() const +{ + std::vector<COutput> all; + all.reserve(this->size()); + all.insert(all.end(), bech32m.begin(), bech32m.end()); + all.insert(all.end(), bech32.begin(), bech32.end()); + all.insert(all.end(), P2SH_segwit.begin(), P2SH_segwit.end()); + all.insert(all.end(), legacy.begin(), legacy.end()); + all.insert(all.end(), other.begin(), other.end()); + return all; +} + +void CoinsResult::clear() +{ + bech32m.clear(); + bech32.clear(); + P2SH_segwit.clear(); + legacy.clear(); + other.clear(); +} + CoinsResult AvailableCoins(const CWallet& wallet, const CCoinControl* coinControl, std::optional<CFeeRate> feerate, @@ -193,10 +219,55 @@ CoinsResult AvailableCoins(const CWallet& wallet, // Filter by spendable outputs only if (!spendable && only_spendable) continue; + // When parsing a scriptPubKey, Solver returns the parsed pubkeys or hashes (depending on the script) + // We don't need those here, so we are leaving them in return_values_unused + std::vector<std::vector<uint8_t>> return_values_unused; + TxoutType type; + bool is_from_p2sh{false}; + + // If the Output is P2SH and spendable, we want to know if it is + // a P2SH (legacy) or one of P2SH-P2WPKH, P2SH-P2WSH (P2SH-Segwit). We can determine + // this from the redeemScript. If the Output is not spendable, it will be classified + // as a P2SH (legacy), since we have no way of knowing otherwise without the redeemScript + if (output.scriptPubKey.IsPayToScriptHash() && solvable) { + CScript redeemScript; + CTxDestination destination; + if (!ExtractDestination(output.scriptPubKey, destination)) + continue; + const CScriptID& hash = CScriptID(std::get<ScriptHash>(destination)); + if (!provider->GetCScript(hash, redeemScript)) + continue; + type = Solver(redeemScript, return_values_unused); + is_from_p2sh = true; + } else { + type = Solver(output.scriptPubKey, return_values_unused); + } + int input_bytes = CalculateMaximumSignedInputSize(output, COutPoint(), provider.get(), coinControl); - result.coins.emplace_back(outpoint, output, nDepth, input_bytes, spendable, solvable, safeTx, wtx.GetTxTime(), tx_from_me, feerate); + COutput coin(outpoint, output, nDepth, input_bytes, spendable, solvable, safeTx, wtx.GetTxTime(), tx_from_me, feerate); + switch (type) { + case TxoutType::WITNESS_UNKNOWN: + case TxoutType::WITNESS_V1_TAPROOT: + result.bech32m.push_back(coin); + break; + case TxoutType::WITNESS_V0_KEYHASH: + case TxoutType::WITNESS_V0_SCRIPTHASH: + if (is_from_p2sh) { + result.P2SH_segwit.push_back(coin); + break; + } + result.bech32.push_back(coin); + break; + case TxoutType::SCRIPTHASH: + case TxoutType::PUBKEYHASH: + result.legacy.push_back(coin); + break; + default: + result.other.push_back(coin); + }; + + // Cache total amount as we go result.total_amount += output.nValue; - // Checks the sum amount of all UTXO's. if (nMinimumSumAmount != MAX_MONEY) { if (result.total_amount >= nMinimumSumAmount) { @@ -205,7 +276,7 @@ CoinsResult AvailableCoins(const CWallet& wallet, } // Checks the maximum number of UTXO's. - if (nMaximumCount > 0 && result.coins.size() >= nMaximumCount) { + if (nMaximumCount > 0 && result.size() >= nMaximumCount) { return result; } } @@ -261,7 +332,7 @@ std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet) std::map<CTxDestination, std::vector<COutput>> result; - for (const COutput& coin : AvailableCoinsListUnspent(wallet).coins) { + for (const COutput& coin : AvailableCoinsListUnspent(wallet).all()) { CTxDestination address; if ((coin.spendable || (wallet.IsWalletFlagSet(WALLET_FLAG_DISABLE_PRIVATE_KEYS) && coin.solvable)) && ExtractDestination(FindNonChangeParentOutput(wallet, coin.outpoint).scriptPubKey, address)) { @@ -379,20 +450,51 @@ std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<C return groups_out; } -std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins, - const CoinSelectionParams& coin_selection_params) +std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const CoinsResult& available_coins, + const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types) +{ + // Run coin selection on each OutputType and compute the Waste Metric + std::vector<SelectionResult> results; + if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.legacy, coin_selection_params)}) { + results.push_back(*result); + } + if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.P2SH_segwit, coin_selection_params)}) { + results.push_back(*result); + } + if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.bech32, coin_selection_params)}) { + results.push_back(*result); + } + if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.bech32m, coin_selection_params)}) { + results.push_back(*result); + } + + // If we can't fund the transaction from any individual OutputType, run coin selection + // over all available coins, else pick the best solution from the results + if (results.size() == 0) { + if (allow_mixed_output_types) { + if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.all(), coin_selection_params)}) { + return result; + } + } + return std::optional<SelectionResult>(); + }; + std::optional<SelectionResult> result{*std::min_element(results.begin(), results.end())}; + return result; +}; + +std::optional<SelectionResult> ChooseSelectionResult(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const std::vector<COutput>& available_coins, const CoinSelectionParams& coin_selection_params) { // Vector of results. We will choose the best one based on waste. std::vector<SelectionResult> results; // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output. - std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, coins, coin_selection_params, eligibility_filter, true /* positive_only */); + std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, available_coins, coin_selection_params, eligibility_filter, true /* positive_only */); if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) { results.push_back(*bnb_result); } // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. - std::vector<OutputGroup> all_groups = GroupOutputs(wallet, coins, coin_selection_params, eligibility_filter, false /* positive_only */); + std::vector<OutputGroup> all_groups = GroupOutputs(wallet, available_coins, coin_selection_params, eligibility_filter, false /* positive_only */); CAmount target_with_change = nTargetValue; // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output. // So we need to include that for KnapsackSolver and SRD as well, as we are expecting to create a change output. @@ -425,9 +527,8 @@ std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAm return best_result; } -std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, const CCoinControl& coin_control, const CoinSelectionParams& coin_selection_params) +std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const CAmount& nTargetValue, const CCoinControl& coin_control, const CoinSelectionParams& coin_selection_params) { - std::vector<COutput> vCoins(vAvailableCoins); CAmount value_to_select = nTargetValue; OutputGroup preset_inputs(coin_selection_params); @@ -487,13 +588,13 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec return result; } - // remove preset inputs from vCoins so that Coin Selection doesn't pick them. - for (std::vector<COutput>::iterator it = vCoins.begin(); it != vCoins.end() && coin_control.HasSelected();) - { - if (preset_coins.count(it->outpoint)) - it = vCoins.erase(it); - else - ++it; + // remove preset inputs from coins so that Coin Selection doesn't pick them. + if (coin_control.HasSelected()) { + available_coins.legacy.erase(remove_if(available_coins.legacy.begin(), available_coins.legacy.end(), [&](const COutput& c) { return preset_coins.count(c.outpoint); }), available_coins.legacy.end()); + available_coins.P2SH_segwit.erase(remove_if(available_coins.P2SH_segwit.begin(), available_coins.P2SH_segwit.end(), [&](const COutput& c) { return preset_coins.count(c.outpoint); }), available_coins.P2SH_segwit.end()); + available_coins.bech32.erase(remove_if(available_coins.bech32.begin(), available_coins.bech32.end(), [&](const COutput& c) { return preset_coins.count(c.outpoint); }), available_coins.bech32.end()); + available_coins.bech32m.erase(remove_if(available_coins.bech32m.begin(), available_coins.bech32m.end(), [&](const COutput& c) { return preset_coins.count(c.outpoint); }), available_coins.bech32m.end()); + available_coins.other.erase(remove_if(available_coins.other.begin(), available_coins.other.end(), [&](const COutput& c) { return preset_coins.count(c.outpoint); }), available_coins.other.end()); } unsigned int limit_ancestor_count = 0; @@ -505,11 +606,15 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec // form groups from remaining coins; note that preset coins will not // automatically have their associated (same address) coins included - if (coin_control.m_avoid_partial_spends && vCoins.size() > OUTPUT_GROUP_MAX_ENTRIES) { + if (coin_control.m_avoid_partial_spends && available_coins.size() > OUTPUT_GROUP_MAX_ENTRIES) { // Cases where we have 101+ outputs all pointing to the same destination may result in // privacy leaks as they will potentially be deterministically sorted. We solve that by // explicitly shuffling the outputs before processing - Shuffle(vCoins.begin(), vCoins.end(), coin_selection_params.rng_fast); + Shuffle(available_coins.legacy.begin(), available_coins.legacy.end(), coin_selection_params.rng_fast); + Shuffle(available_coins.P2SH_segwit.begin(), available_coins.P2SH_segwit.end(), coin_selection_params.rng_fast); + Shuffle(available_coins.bech32.begin(), available_coins.bech32.end(), coin_selection_params.rng_fast); + Shuffle(available_coins.bech32m.begin(), available_coins.bech32m.end(), coin_selection_params.rng_fast); + Shuffle(available_coins.other.begin(), available_coins.other.end(), coin_selection_params.rng_fast); } // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the @@ -521,26 +626,27 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six // confirmations on outputs received from other wallets and only spend confirmed change. - if (auto r1{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, coin_selection_params)}) return r1; - if (auto r2{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, coin_selection_params)}) return r2; + if (auto r1{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), available_coins, coin_selection_params, /*allow_mixed_output_types=*/false)}) return r1; + // Allow mixing only if no solution from any single output type can be found + if (auto r2{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) return r2; // Fall back to using zero confirmation change (but with as few ancestors in the mempool as // possible) if we cannot fund the transaction otherwise. if (wallet.m_spend_zero_conf_change) { - if (auto r3{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, coin_selection_params)}) return r3; + if (auto r3{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) return r3; if (auto r4{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), - vCoins, coin_selection_params)}) { + available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) { return r4; } if (auto r5{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), - vCoins, coin_selection_params)}) { + available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) { return r5; } // If partial groups are allowed, relax the requirement of spending OutputGroups (groups // of UTXOs sent to the same address, which are obviously controlled by a single wallet) // in their entirety. if (auto r6{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), - vCoins, coin_selection_params)}) { + available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) { return r6; } // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs @@ -548,7 +654,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec if (coin_control.m_include_unsafe_inputs) { if (auto r7{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0 /* conf_mine */, 0 /* conf_theirs */, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), - vCoins, coin_selection_params)}) { + available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) { return r7; } } @@ -558,7 +664,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec if (!fRejectLongChains) { if (auto r8{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true /* include_partial_groups */), - vCoins, coin_selection_params)}) { + available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) { return r8; } } @@ -778,7 +884,7 @@ static BResult<CreatedTransactionResult> CreateTransactionInternal( CAmount selection_target = recipients_sum + not_input_fees; // Get available coins - auto res_available_coins = AvailableCoins(wallet, + auto available_coins = AvailableCoins(wallet, &coin_control, coin_selection_params.m_effective_feerate, 1, /*nMinimumAmount*/ @@ -787,7 +893,7 @@ static BResult<CreatedTransactionResult> CreateTransactionInternal( 0); /*nMaximumCount*/ // Choose coins to use - std::optional<SelectionResult> result = SelectCoins(wallet, res_available_coins.coins, /*nTargetValue=*/selection_target, coin_control, coin_selection_params); + std::optional<SelectionResult> result = SelectCoins(wallet, available_coins, /*nTargetValue=*/selection_target, coin_control, coin_selection_params); if (!result) { return _("Insufficient funds"); } diff --git a/src/wallet/spend.h b/src/wallet/spend.h index ab0ff1ee58..96ecd690be 100644 --- a/src/wallet/spend.h +++ b/src/wallet/spend.h @@ -29,14 +29,38 @@ struct TxSize { TxSize CalculateMaximumSignedTxSize(const CTransaction& tx, const CWallet* wallet, const std::vector<CTxOut>& txouts, const CCoinControl* coin_control = nullptr); TxSize CalculateMaximumSignedTxSize(const CTransaction& tx, const CWallet* wallet, const CCoinControl* coin_control = nullptr) EXCLUSIVE_LOCKS_REQUIRED(wallet->cs_wallet); +/** + * COutputs available for spending, stored by OutputType. + * This struct is really just a wrapper around OutputType vectors with a convenient + * method for concatenating and returning all COutputs as one vector. + * + * clear(), size() methods are implemented so that one can interact with + * the CoinsResult struct as if it was a vector + */ struct CoinsResult { - std::vector<COutput> coins; - // Sum of all the coins amounts + /** Vectors for each OutputType */ + std::vector<COutput> legacy; + std::vector<COutput> P2SH_segwit; + std::vector<COutput> bech32; + std::vector<COutput> bech32m; + + /** Other is a catch-all for anything that doesn't match the known OutputTypes */ + std::vector<COutput> other; + + /** Concatenate and return all COutputs as one vector */ + std::vector<COutput> all() const; + + /** The following methods are provided so that CoinsResult can mimic a vector, + * i.e., methods can work with individual OutputType vectors or on the entire object */ + uint64_t size() const; + void clear(); + + /** Sum of all available coins */ CAmount total_amount{0}; }; + /** - * Return vector of available COutputs. - * By default, returns only the spendable coins. + * Populate the CoinsResult struct with vectors of available COutputs, organized by OutputType. */ CoinsResult AvailableCoins(const CWallet& wallet, const CCoinControl* coinControl = nullptr, @@ -67,35 +91,52 @@ const CTxOut& FindNonChangeParentOutput(const CWallet& wallet, const COutPoint& std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet); std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<COutput>& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only); +/** + * Attempt to find a valid input set that preserves privacy by not mixing OutputTypes. + * `ChooseSelectionResult()` will be called on each OutputType individually and the best + * the solution (according to the waste metric) will be chosen. If a valid input cannot be found from any + * single OutputType, fallback to running `ChooseSelectionResult()` over all available coins. + * + * param@[in] wallet The wallet which provides solving data for the coins + * param@[in] nTargetValue The target value + * param@[in] eligilibity_filter A filter containing rules for which coins are allowed to be included in this selection + * param@[in] available_coins The struct of coins, organized by OutputType, available for selection prior to filtering + * param@[in] coin_selection_params Parameters for the coin selection + * param@[in] allow_mixed_output_types Relax restriction that SelectionResults must be of the same OutputType + * returns If successful, a SelectionResult containing the input set + * If failed, a nullopt + */ +std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const CoinsResult& available_coins, + const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types); /** * Attempt to find a valid input set that meets the provided eligibility filter and target. * Multiple coin selection algorithms will be run and the input set that produces the least waste * (according to the waste metric) will be chosen. * - * param@[in] wallet The wallet which provides solving data for the coins - * param@[in] nTargetValue The target value - * param@[in] eligilibity_filter A filter containing rules for which coins are allowed to be included in this selection - * param@[in] coins The vector of coins available for selection prior to filtering - * param@[in] coin_selection_params Parameters for the coin selection - * returns If successful, a SelectionResult containing the input set - * If failed, a nullopt + * param@[in] wallet The wallet which provides solving data for the coins + * param@[in] nTargetValue The target value + * param@[in] eligilibity_filter A filter containing rules for which coins are allowed to be included in this selection + * param@[in] available_coins The struct of coins, organized by OutputType, available for selection prior to filtering + * param@[in] coin_selection_params Parameters for the coin selection + * returns If successful, a SelectionResult containing the input set + * If failed, a nullopt */ -std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins, +std::optional<SelectionResult> ChooseSelectionResult(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const std::vector<COutput>& available_coins, const CoinSelectionParams& coin_selection_params); /** * Select a set of coins such that nTargetValue is met and at least * all coins from coin_control are selected; never select unconfirmed coins if they are not ours * param@[in] wallet The wallet which provides data necessary to spend the selected coins - * param@[in] vAvailableCoins The vector of coins available to be spent + * param@[in] available_coins The struct of coins, organized by OutputType, available for selection prior to filtering * param@[in] nTargetValue The target value * param@[in] coin_selection_params Parameters for this coin selection such as feerates, whether to avoid partial spends, * and whether to subtract the fee from the outputs. * returns If successful, a SelectionResult containing the selected coins * If failed, a nullopt. */ -std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, const CCoinControl& coin_control, +std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const CAmount& nTargetValue, const CCoinControl& coin_control, const CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet); struct CreatedTransactionResult diff --git a/src/wallet/test/availablecoins_tests.cpp b/src/wallet/test/availablecoins_tests.cpp new file mode 100644 index 0000000000..01d24da981 --- /dev/null +++ b/src/wallet/test/availablecoins_tests.cpp @@ -0,0 +1,105 @@ +// Copyright (c) 2022 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or https://www.opensource.org/licenses/mit-license.php. + +#include <validation.h> +#include <wallet/coincontrol.h> +#include <wallet/spend.h> +#include <wallet/test/util.h> +#include <wallet/test/wallet_test_fixture.h> + +#include <boost/test/unit_test.hpp> + +namespace wallet { +BOOST_FIXTURE_TEST_SUITE(availablecoins_tests, WalletTestingSetup) +class AvailableCoinsTestingSetup : public TestChain100Setup +{ +public: + AvailableCoinsTestingSetup() + { + CreateAndProcessBlock({}, {}); + wallet = CreateSyncedWallet(*m_node.chain, m_node.chainman->ActiveChain(), m_args, coinbaseKey); + } + + ~AvailableCoinsTestingSetup() + { + wallet.reset(); + } + CWalletTx& AddTx(CRecipient recipient) + { + CTransactionRef tx; + CCoinControl dummy; + { + constexpr int RANDOM_CHANGE_POSITION = -1; + auto res = CreateTransaction(*wallet, {recipient}, RANDOM_CHANGE_POSITION, dummy); + BOOST_CHECK(res); + tx = res.GetObj().tx; + } + wallet->CommitTransaction(tx, {}, {}); + CMutableTransaction blocktx; + { + LOCK(wallet->cs_wallet); + blocktx = CMutableTransaction(*wallet->mapWallet.at(tx->GetHash()).tx); + } + CreateAndProcessBlock({CMutableTransaction(blocktx)}, GetScriptForRawPubKey(coinbaseKey.GetPubKey())); + + LOCK(wallet->cs_wallet); + wallet->SetLastBlockProcessed(wallet->GetLastBlockHeight() + 1, m_node.chainman->ActiveChain().Tip()->GetBlockHash()); + auto it = wallet->mapWallet.find(tx->GetHash()); + BOOST_CHECK(it != wallet->mapWallet.end()); + it->second.m_state = TxStateConfirmed{m_node.chainman->ActiveChain().Tip()->GetBlockHash(), m_node.chainman->ActiveChain().Height(), /*index=*/1}; + return it->second; + } + + std::unique_ptr<CWallet> wallet; +}; + +BOOST_FIXTURE_TEST_CASE(BasicOutputTypesTest, AvailableCoinsTestingSetup) +{ + CoinsResult available_coins; + BResult<CTxDestination> dest; + LOCK(wallet->cs_wallet); + + // Verify our wallet has one usable coinbase UTXO before starting + // This UTXO is a P2PK, so it should show up in the Other bucket + available_coins = AvailableCoins(*wallet); + BOOST_CHECK_EQUAL(available_coins.size(), 1U); + BOOST_CHECK_EQUAL(available_coins.other.size(), 1U); + + // We will create a self transfer for each of the OutputTypes and + // verify it is put in the correct bucket after running GetAvailablecoins + // + // For each OutputType, We expect 2 UTXOs in our wallet following the self transfer: + // 1. One UTXO as the recipient + // 2. One UTXO from the change, due to payment address matching logic + + // Bech32m + dest = wallet->GetNewDestination(OutputType::BECH32M, ""); + BOOST_ASSERT(dest.HasRes()); + AddTx(CRecipient{{GetScriptForDestination(dest.GetObj())}, 1 * COIN, /*fSubtractFeeFromAmount=*/true}); + available_coins = AvailableCoins(*wallet); + BOOST_CHECK_EQUAL(available_coins.bech32m.size(), 2U); + + // Bech32 + dest = wallet->GetNewDestination(OutputType::BECH32, ""); + BOOST_ASSERT(dest.HasRes()); + AddTx(CRecipient{{GetScriptForDestination(dest.GetObj())}, 2 * COIN, /*fSubtractFeeFromAmount=*/true}); + available_coins = AvailableCoins(*wallet); + BOOST_CHECK_EQUAL(available_coins.bech32.size(), 2U); + + // P2SH-SEGWIT + dest = wallet->GetNewDestination(OutputType::P2SH_SEGWIT, ""); + AddTx(CRecipient{{GetScriptForDestination(dest.GetObj())}, 3 * COIN, /*fSubtractFeeFromAmount=*/true}); + available_coins = AvailableCoins(*wallet); + BOOST_CHECK_EQUAL(available_coins.P2SH_segwit.size(), 2U); + + // Legacy (P2PKH) + dest = wallet->GetNewDestination(OutputType::LEGACY, ""); + BOOST_ASSERT(dest.HasRes()); + AddTx(CRecipient{{GetScriptForDestination(dest.GetObj())}, 4 * COIN, /*fSubtractFeeFromAmount=*/true}); + available_coins = AvailableCoins(*wallet); + BOOST_CHECK_EQUAL(available_coins.legacy.size(), 2U); +} + +BOOST_AUTO_TEST_SUITE_END() +} // namespace wallet diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index a418105ee1..cd7fd3f4dd 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -67,7 +67,7 @@ static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fe set.insert(coin); } -static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount& nValue, CFeeRate feerate = CFeeRate(0), int nAge = 6*24, bool fIsFromMe = false, int nInput=0, bool spendable = false) +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) { CMutableTransaction tx; tx.nLockTime = nextLockTime++; // so all transactions get different hashes @@ -85,7 +85,7 @@ static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount assert(ret.second); CWalletTx& wtx = (*ret.first).second; const auto& txout = wtx.tx->vout.at(nInput); - coins.emplace_back(COutPoint(wtx.GetHash(), nInput), txout, nAge, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate); + available_coins.bech32.emplace_back(COutPoint(wtx.GetHash(), nInput), txout, nAge, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate); } /** Check if SelectionResult a is equivalent to SelectionResult b. @@ -129,18 +129,18 @@ static CAmount make_hard_case(int utxos, std::vector<COutput>& utxo_pool) return target; } -inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins) +inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins) { static std::vector<OutputGroup> static_groups; static_groups.clear(); - for (auto& coin : coins) { + for (auto& coin : available_coins) { static_groups.emplace_back(); static_groups.back().Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false); } return static_groups; } -inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>& coins, CWallet& wallet, const CoinEligibilityFilter& filter) +inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>& available_coins, CWallet& wallet, const CoinEligibilityFilter& filter) { FastRandomContext rand{}; CoinSelectionParams coin_selection_params{ @@ -155,7 +155,7 @@ inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput> /*avoid_partial=*/ false, }; static std::vector<OutputGroup> static_groups; - static_groups = GroupOutputs(wallet, coins, coin_selection_params, filter, /*positive_only=*/false); + static_groups = GroupOutputs(wallet, available_coins, coin_selection_params, filter, /*positive_only=*/false); return static_groups; } @@ -307,18 +307,18 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS); wallet->SetupDescriptorScriptPubKeyMans(); - std::vector<COutput> coins; + CoinsResult available_coins; - add_coin(coins, *wallet, 1, coin_selection_params_bnb.m_effective_feerate); - 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 - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change)); + add_coin(available_coins, *wallet, 1, coin_selection_params_bnb.m_effective_feerate); + 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 + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(available_coins.all()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change)); // Test fees subtracted from output: - coins.clear(); - add_coin(coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate); - coins.at(0).input_bytes = 40; + available_coins.clear(); + add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate); + available_coins.all().at(0).input_bytes = 40; coin_selection_params_bnb.m_subtract_fee_outputs = true; - const auto result9 = SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change); + const auto result9 = SelectCoinsBnB(GroupCoins(available_coins.all()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change); BOOST_CHECK(result9); BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT); } @@ -330,16 +330,16 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS); wallet->SetupDescriptorScriptPubKeyMans(); - std::vector<COutput> coins; + CoinsResult available_coins; - add_coin(coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 3 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 2 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 3 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 2 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); CCoinControl coin_control; coin_control.m_allow_other_inputs = true; - coin_control.Select(coins.at(0).outpoint); + coin_control.Select(available_coins.all().at(0).outpoint); coin_selection_params_bnb.m_effective_feerate = CFeeRate(0); - const auto result10 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb); + const auto result10 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb); BOOST_CHECK(result10); } { @@ -349,52 +349,52 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS); wallet->SetupDescriptorScriptPubKeyMans(); - std::vector<COutput> coins; + CoinsResult available_coins; // single coin should be selected when effective fee > long term fee coin_selection_params_bnb.m_effective_feerate = CFeeRate(5000); coin_selection_params_bnb.m_long_term_feerate = CFeeRate(3000); - add_coin(coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); expected_result.Clear(); add_coin(10 * CENT, 2, expected_result); CCoinControl coin_control; - const auto result11 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb); + const auto result11 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb); BOOST_CHECK(EquivalentResult(expected_result, *result11)); - coins.clear(); + available_coins.clear(); // more coins should be selected when effective fee < long term fee coin_selection_params_bnb.m_effective_feerate = CFeeRate(3000); coin_selection_params_bnb.m_long_term_feerate = CFeeRate(5000); - add_coin(coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); expected_result.Clear(); add_coin(9 * CENT, 2, expected_result); add_coin(1 * CENT, 2, expected_result); - const auto result12 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb); + const auto result12 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb); BOOST_CHECK(EquivalentResult(expected_result, *result12)); - coins.clear(); + available_coins.clear(); // pre selected coin should be selected even if disadvantageous coin_selection_params_bnb.m_effective_feerate = CFeeRate(5000); coin_selection_params_bnb.m_long_term_feerate = CFeeRate(3000); - add_coin(coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); - add_coin(coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); + add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true); expected_result.Clear(); add_coin(9 * CENT, 2, expected_result); add_coin(1 * CENT, 2, expected_result); coin_control.m_allow_other_inputs = true; - coin_control.Select(coins.at(1).outpoint); // pre select 9 coin - const auto result13 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb); + coin_control.Select(available_coins.all().at(1).outpoint); // pre select 9 coin + const auto result13 = SelectCoins(*wallet, available_coins, 10 * CENT, coin_control, coin_selection_params_bnb); BOOST_CHECK(EquivalentResult(expected_result, *result13)); } } @@ -410,175 +410,175 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS); wallet->SetupDescriptorScriptPubKeyMans(); - std::vector<COutput> coins; + CoinsResult available_coins; // test multiple times to allow for differences in the shuffle order for (int i = 0; i < RUN_TESTS; i++) { - coins.clear(); + available_coins.clear(); // with an empty wallet we can't even pay one cent - BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT, CENT)); + BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 1 * CENT, CENT)); - add_coin(coins, *wallet, 1*CENT, CFeeRate(0), 4); // add a new 1 cent coin + add_coin(available_coins, *wallet, 1*CENT, CFeeRate(0), 4); // add a new 1 cent coin // with a new 1 cent coin, we still can't find a mature 1 cent - BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT, CENT)); + BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 1 * CENT, CENT)); // but we can find a new 1 cent - const auto result1 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT); + const auto result1 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT); BOOST_CHECK(result1); BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT); - add_coin(coins, *wallet, 2*CENT); // add a mature 2 cent coin + add_coin(available_coins, *wallet, 2*CENT); // add a mature 2 cent coin // we can't make 3 cents of mature coins - BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 3 * CENT, CENT)); + BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 3 * CENT, CENT)); // we can make 3 cents of new coins - const auto result2 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 3 * CENT, CENT); + const auto result2 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 3 * CENT, CENT); BOOST_CHECK(result2); BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 3 * CENT); - add_coin(coins, *wallet, 5*CENT); // add a mature 5 cent coin, - add_coin(coins, *wallet, 10*CENT, CFeeRate(0), 3, true); // a new 10 cent coin sent from one of our own addresses - add_coin(coins, *wallet, 20*CENT); // and a mature 20 cent coin + add_coin(available_coins, *wallet, 5*CENT); // add a mature 5 cent coin, + add_coin(available_coins, *wallet, 10*CENT, CFeeRate(0), 3, true); // a new 10 cent coin sent from one of our own addresses + add_coin(available_coins, *wallet, 20*CENT); // and a mature 20 cent coin // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38 // we can't make 38 cents only if we disallow new coins: - BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 38 * CENT, CENT)); + BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 38 * CENT, CENT)); // we can't even make 37 cents if we don't allow new coins even if they're from us - BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard_extra), 38 * CENT, CENT)); + BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard_extra), 38 * CENT, CENT)); // but we can make 37 cents if we accept new coins from ourself - const auto result3 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 37 * CENT, CENT); + const auto result3 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 37 * CENT, CENT); BOOST_CHECK(result3); BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 37 * CENT); // and we can make 38 cents if we accept all new coins - const auto result4 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 38 * CENT, CENT); + const auto result4 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 38 * CENT, CENT); BOOST_CHECK(result4); BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 38 * CENT); // try making 34 cents from 1,2,5,10,20 - we can't do it exactly - const auto result5 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 34 * CENT, CENT); + const auto result5 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 34 * CENT, CENT); BOOST_CHECK(result5); BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 35 * CENT); // but 35 cents is closest 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) // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5 - const auto result6 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 7 * CENT, CENT); + const auto result6 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 7 * CENT, CENT); BOOST_CHECK(result6); BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 7 * CENT); BOOST_CHECK_EQUAL(result6->GetInputSet().size(), 2U); // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough. - const auto result7 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 8 * CENT, CENT); + const auto result7 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 8 * CENT, CENT); BOOST_CHECK(result7); BOOST_CHECK(result7->GetSelectedValue() == 8 * CENT); BOOST_CHECK_EQUAL(result7->GetInputSet().size(), 3U); // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10) - const auto result8 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 9 * CENT, CENT); + const auto result8 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 9 * CENT, CENT); BOOST_CHECK(result8); BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 10 * CENT); BOOST_CHECK_EQUAL(result8->GetInputSet().size(), 1U); // now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin - coins.clear(); + available_coins.clear(); - add_coin(coins, *wallet, 6*CENT); - add_coin(coins, *wallet, 7*CENT); - add_coin(coins, *wallet, 8*CENT); - add_coin(coins, *wallet, 20*CENT); - add_coin(coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total + add_coin(available_coins, *wallet, 6*CENT); + add_coin(available_coins, *wallet, 7*CENT); + add_coin(available_coins, *wallet, 8*CENT); + add_coin(available_coins, *wallet, 20*CENT); + add_coin(available_coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total // check that we have 71 and not 72 - const auto result9 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 71 * CENT, CENT); + const auto result9 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 71 * CENT, CENT); BOOST_CHECK(result9); - BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 72 * CENT, CENT)); + BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 72 * CENT, CENT)); // 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 - const auto result10 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT); + const auto result10 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 16 * CENT, CENT); BOOST_CHECK(result10); BOOST_CHECK_EQUAL(result10->GetSelectedValue(), 20 * CENT); // we should get 20 in one coin BOOST_CHECK_EQUAL(result10->GetInputSet().size(), 1U); - add_coin(coins, *wallet, 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total + add_coin(available_coins, *wallet, 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total // 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 - const auto result11 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT); + const auto result11 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 16 * CENT, CENT); BOOST_CHECK(result11); BOOST_CHECK_EQUAL(result11->GetSelectedValue(), 18 * CENT); // we should get 18 in 3 coins BOOST_CHECK_EQUAL(result11->GetInputSet().size(), 3U); - add_coin(coins, *wallet, 18*CENT); // now we have 5+6+7+8+18+20+30 + add_coin(available_coins, *wallet, 18*CENT); // now we have 5+6+7+8+18+20+30 // 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 - const auto result12 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT); + const auto result12 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 16 * CENT, CENT); BOOST_CHECK(result12); BOOST_CHECK_EQUAL(result12->GetSelectedValue(), 18 * CENT); // we should get 18 in 1 coin BOOST_CHECK_EQUAL(result12->GetInputSet().size(), 1U); // because in the event of a tie, the biggest coin wins // now try making 11 cents. we should get 5+6 - const auto result13 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 11 * CENT, CENT); + const auto result13 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 11 * CENT, CENT); BOOST_CHECK(result13); BOOST_CHECK_EQUAL(result13->GetSelectedValue(), 11 * CENT); BOOST_CHECK_EQUAL(result13->GetInputSet().size(), 2U); // check that the smallest bigger coin is used - add_coin(coins, *wallet, 1*COIN); - add_coin(coins, *wallet, 2*COIN); - add_coin(coins, *wallet, 3*COIN); - add_coin(coins, *wallet, 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents - const auto result14 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 95 * CENT, CENT); + add_coin(available_coins, *wallet, 1*COIN); + add_coin(available_coins, *wallet, 2*COIN); + add_coin(available_coins, *wallet, 3*COIN); + add_coin(available_coins, *wallet, 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents + const auto result14 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 95 * CENT, CENT); BOOST_CHECK(result14); BOOST_CHECK_EQUAL(result14->GetSelectedValue(), 1 * COIN); // we should get 1 BTC in 1 coin BOOST_CHECK_EQUAL(result14->GetInputSet().size(), 1U); - const auto result15 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 195 * CENT, CENT); + const auto result15 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 195 * CENT, CENT); BOOST_CHECK(result15); BOOST_CHECK_EQUAL(result15->GetSelectedValue(), 2 * COIN); // we should get 2 BTC in 1 coin BOOST_CHECK_EQUAL(result15->GetInputSet().size(), 1U); // empty the wallet and start again, now with fractions of a cent, to test small change avoidance - coins.clear(); - add_coin(coins, *wallet, CENT * 1 / 10); - add_coin(coins, *wallet, CENT * 2 / 10); - add_coin(coins, *wallet, CENT * 3 / 10); - add_coin(coins, *wallet, CENT * 4 / 10); - add_coin(coins, *wallet, CENT * 5 / 10); + available_coins.clear(); + add_coin(available_coins, *wallet, CENT * 1 / 10); + add_coin(available_coins, *wallet, CENT * 2 / 10); + add_coin(available_coins, *wallet, CENT * 3 / 10); + add_coin(available_coins, *wallet, CENT * 4 / 10); + add_coin(available_coins, *wallet, CENT * 5 / 10); // try making 1 * CENT from the 1.5 * CENT // we'll get change smaller than CENT whatever happens, so can expect CENT exactly - const auto result16 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT, CENT); + const auto result16 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT, CENT); BOOST_CHECK(result16); BOOST_CHECK_EQUAL(result16->GetSelectedValue(), CENT); // but if we add a bigger coin, small change is avoided - add_coin(coins, *wallet, 1111*CENT); + add_coin(available_coins, *wallet, 1111*CENT); // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5 - const auto result17 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT); + const auto result17 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT); BOOST_CHECK(result17); BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * CENT); // we should get the exact amount // if we add more small coins: - add_coin(coins, *wallet, CENT * 6 / 10); - add_coin(coins, *wallet, CENT * 7 / 10); + add_coin(available_coins, *wallet, CENT * 6 / 10); + add_coin(available_coins, *wallet, CENT * 7 / 10); // and try again to make 1.0 * CENT - const auto result18 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT); + const auto result18 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT); BOOST_CHECK(result18); BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * CENT); // we should get the exact amount // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf) // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change - coins.clear(); + available_coins.clear(); for (int j = 0; j < 20; j++) - add_coin(coins, *wallet, 50000 * COIN); + add_coin(available_coins, *wallet, 50000 * COIN); - const auto result19 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 500000 * COIN, CENT); + const auto result19 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 500000 * COIN, CENT); BOOST_CHECK(result19); BOOST_CHECK_EQUAL(result19->GetSelectedValue(), 500000 * COIN); // we should get the exact amount BOOST_CHECK_EQUAL(result19->GetInputSet().size(), 10U); // in ten coins @@ -587,41 +587,41 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // we need to try finding an exact subset anyway // sometimes it will fail, and so we use the next biggest coin: - coins.clear(); - add_coin(coins, *wallet, CENT * 5 / 10); - add_coin(coins, *wallet, CENT * 6 / 10); - add_coin(coins, *wallet, CENT * 7 / 10); - add_coin(coins, *wallet, 1111 * CENT); - const auto result20 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT); + available_coins.clear(); + add_coin(available_coins, *wallet, CENT * 5 / 10); + add_coin(available_coins, *wallet, CENT * 6 / 10); + add_coin(available_coins, *wallet, CENT * 7 / 10); + add_coin(available_coins, *wallet, 1111 * CENT); + const auto result20 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 1 * CENT, CENT); BOOST_CHECK(result20); BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * CENT); // we get the bigger coin BOOST_CHECK_EQUAL(result20->GetInputSet().size(), 1U); // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0) - coins.clear(); - add_coin(coins, *wallet, CENT * 4 / 10); - add_coin(coins, *wallet, CENT * 6 / 10); - add_coin(coins, *wallet, CENT * 8 / 10); - add_coin(coins, *wallet, 1111 * CENT); - const auto result21 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT, CENT); + available_coins.clear(); + add_coin(available_coins, *wallet, CENT * 4 / 10); + add_coin(available_coins, *wallet, CENT * 6 / 10); + add_coin(available_coins, *wallet, CENT * 8 / 10); + add_coin(available_coins, *wallet, 1111 * CENT); + const auto result21 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT, CENT); BOOST_CHECK(result21); BOOST_CHECK_EQUAL(result21->GetSelectedValue(), CENT); // we should get the exact amount BOOST_CHECK_EQUAL(result21->GetInputSet().size(), 2U); // in two coins 0.4+0.6 // test avoiding small change - coins.clear(); - add_coin(coins, *wallet, CENT * 5 / 100); - add_coin(coins, *wallet, CENT * 1); - add_coin(coins, *wallet, CENT * 100); + available_coins.clear(); + add_coin(available_coins, *wallet, CENT * 5 / 100); + add_coin(available_coins, *wallet, CENT * 1); + add_coin(available_coins, *wallet, CENT * 100); // trying to make 100.01 from these three coins - const auto result22 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT * 10001 / 100, CENT); + const auto result22 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT * 10001 / 100, CENT); BOOST_CHECK(result22); BOOST_CHECK_EQUAL(result22->GetSelectedValue(), CENT * 10105 / 100); // we should get all coins BOOST_CHECK_EQUAL(result22->GetInputSet().size(), 3U); // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change - const auto result23 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT * 9990 / 100, CENT); + const auto result23 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), CENT * 9990 / 100, CENT); BOOST_CHECK(result23); BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * CENT); BOOST_CHECK_EQUAL(result23->GetInputSet().size(), 2U); @@ -629,14 +629,14 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // test with many inputs for (CAmount amt=1500; amt < COIN; amt*=10) { - coins.clear(); + available_coins.clear(); // Create 676 inputs (= (old MAX_STANDARD_TX_SIZE == 100000) / 148 bytes per input) for (uint16_t j = 0; j < 676; j++) - add_coin(coins, *wallet, amt); + add_coin(available_coins, *wallet, amt); // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times. for (int i = 0; i < RUN_TESTS; i++) { - const auto result24 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 2000, CENT); + const auto result24 = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_confirmed), 2000, CENT); BOOST_CHECK(result24); if (amt - 2000 < CENT) { @@ -655,17 +655,17 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // test randomness { - coins.clear(); + available_coins.clear(); for (int i2 = 0; i2 < 100; i2++) - add_coin(coins, *wallet, COIN); + add_coin(available_coins, *wallet, COIN); // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times. for (int i = 0; i < RUN_TESTS; i++) { // picking 50 from 100 coins doesn't depend on the shuffle, // but does depend on randomness in the stochastic approximation code - const auto result25 = KnapsackSolver(GroupCoins(coins), 50 * COIN, CENT); + const auto result25 = KnapsackSolver(GroupCoins(available_coins.all()), 50 * COIN, CENT); BOOST_CHECK(result25); - const auto result26 = KnapsackSolver(GroupCoins(coins), 50 * COIN, CENT); + const auto result26 = KnapsackSolver(GroupCoins(available_coins.all()), 50 * COIN, CENT); BOOST_CHECK(result26); BOOST_CHECK(!EqualResult(*result25, *result26)); @@ -676,9 +676,9 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice // which will cause it to fail. // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail - const auto result27 = KnapsackSolver(GroupCoins(coins), COIN, CENT); + const auto result27 = KnapsackSolver(GroupCoins(available_coins.all()), COIN, CENT); BOOST_CHECK(result27); - const auto result28 = KnapsackSolver(GroupCoins(coins), COIN, CENT); + const auto result28 = KnapsackSolver(GroupCoins(available_coins.all()), COIN, CENT); BOOST_CHECK(result28); if (EqualResult(*result27, *result28)) fails++; @@ -689,19 +689,19 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // add 75 cents in small change. not enough to make 90 cents, // then try making 90 cents. there are multiple competing "smallest bigger" coins, // one of which should be picked at random - add_coin(coins, *wallet, 5 * CENT); - add_coin(coins, *wallet, 10 * CENT); - add_coin(coins, *wallet, 15 * CENT); - add_coin(coins, *wallet, 20 * CENT); - add_coin(coins, *wallet, 25 * CENT); + add_coin(available_coins, *wallet, 5 * CENT); + add_coin(available_coins, *wallet, 10 * CENT); + add_coin(available_coins, *wallet, 15 * CENT); + add_coin(available_coins, *wallet, 20 * CENT); + add_coin(available_coins, *wallet, 25 * CENT); for (int i = 0; i < RUN_TESTS; i++) { int fails = 0; for (int j = 0; j < RANDOM_REPEATS; j++) { - const auto result29 = KnapsackSolver(GroupCoins(coins), 90 * CENT, CENT); + const auto result29 = KnapsackSolver(GroupCoins(available_coins.all()), 90 * CENT, CENT); BOOST_CHECK(result29); - const auto result30 = KnapsackSolver(GroupCoins(coins), 90 * CENT, CENT); + const auto result30 = KnapsackSolver(GroupCoins(available_coins.all()), 90 * CENT, CENT); BOOST_CHECK(result30); if (EqualResult(*result29, *result30)) fails++; @@ -720,14 +720,14 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset) wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS); wallet->SetupDescriptorScriptPubKeyMans(); - std::vector<COutput> coins; + CoinsResult available_coins; // Test vValue sort order for (int i = 0; i < 1000; i++) - add_coin(coins, *wallet, 1000 * COIN); - add_coin(coins, *wallet, 3 * COIN); + add_coin(available_coins, *wallet, 1000 * COIN); + add_coin(available_coins, *wallet, 3 * COIN); - const auto result = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1003 * COIN, CENT, rand); + const auto result = KnapsackSolver(KnapsackGroupOutputs(available_coins.all(), *wallet, filter_standard), 1003 * COIN, CENT, rand); BOOST_CHECK(result); BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN); BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U); @@ -750,14 +750,14 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test) // Run this test 100 times for (int i = 0; i < 100; ++i) { - std::vector<COutput> coins; + CoinsResult available_coins; CAmount balance{0}; // Make a wallet with 1000 exponentially distributed random inputs for (int j = 0; j < 1000; ++j) { CAmount val = distribution(generator)*10000000; - add_coin(coins, *wallet, val); + add_coin(available_coins, *wallet, val); balance += val; } @@ -780,7 +780,7 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test) /*avoid_partial=*/ false, }; CCoinControl cc; - const auto result = SelectCoins(*wallet, coins, target, cc, cs_params); + const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params); BOOST_CHECK(result); BOOST_CHECK_GE(result->GetSelectedValue(), target); } diff --git a/src/wallet/test/wallet_tests.cpp b/src/wallet/test/wallet_tests.cpp index 7377a36f5e..81183aa738 100644 --- a/src/wallet/test/wallet_tests.cpp +++ b/src/wallet/test/wallet_tests.cpp @@ -591,7 +591,7 @@ BOOST_FIXTURE_TEST_CASE(ListCoinsTest, ListCoinsTestingSetup) // Lock both coins. Confirm number of available coins drops to 0. { LOCK(wallet->cs_wallet); - BOOST_CHECK_EQUAL(AvailableCoinsListUnspent(*wallet).coins.size(), 2U); + BOOST_CHECK_EQUAL(AvailableCoinsListUnspent(*wallet).size(), 2U); } for (const auto& group : list) { for (const auto& coin : group.second) { @@ -601,7 +601,7 @@ BOOST_FIXTURE_TEST_CASE(ListCoinsTest, ListCoinsTestingSetup) } { LOCK(wallet->cs_wallet); - BOOST_CHECK_EQUAL(AvailableCoinsListUnspent(*wallet).coins.size(), 0U); + BOOST_CHECK_EQUAL(AvailableCoinsListUnspent(*wallet).size(), 0U); } // Confirm ListCoins still returns same result as before, despite coins // being locked. diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py index c5a69afa6e..e5784eb614 100755 --- a/test/functional/test_runner.py +++ b/test/functional/test_runner.py @@ -156,6 +156,7 @@ BASE_SCRIPTS = [ 'mempool_spend_coinbase.py', 'wallet_avoidreuse.py --legacy-wallet', 'wallet_avoidreuse.py --descriptors', + 'wallet_avoid_mixing_output_types.py --descriptors', 'mempool_reorg.py', 'mempool_persist.py', 'p2p_block_sync.py', diff --git a/test/functional/wallet_avoid_mixing_output_types.py b/test/functional/wallet_avoid_mixing_output_types.py new file mode 100755 index 0000000000..46f41d9c22 --- /dev/null +++ b/test/functional/wallet_avoid_mixing_output_types.py @@ -0,0 +1,176 @@ +#!/usr/bin/env python3 +# Copyright (c) 2022 The Bitcoin Core developers +# Distributed under the MIT software license, see the accompanying +# file COPYING or https://www.opensource.org/licenses/mit-license.php. +"""Test output type mixing during coin selection + +A wallet may have different types of UTXOs to choose from during coin selection, +where output type is one of the following: + - BECH32M + - BECH32 + - P2SH-SEGWIT + - LEGACY + +This test verifies that mixing different output types is avoided unless +absolutely necessary. Both wallets start with zero funds. Alice mines +enough blocks to have spendable coinbase outputs. Alice sends three +random value payments which sum to 10BTC for each output type to Bob, +for a total of 40BTC in Bob's wallet. + +Bob then sends random valued payments back to Alice, some of which need +unconfirmed change, and we verify that none of these payments contain mixed +inputs. Finally, Bob sends the remainder of his funds, which requires mixing. + +The payment values are random, but chosen such that they sum up to a specified +total. This ensures we are not relying on specific values for the UTXOs, +but still know when to expect mixing due to the wallet being close to empty. + +""" + +import random +from test_framework.test_framework import BitcoinTestFramework +from test_framework.blocktools import COINBASE_MATURITY + +ADDRESS_TYPES = [ + "bech32m", + "bech32", + "p2sh-segwit", + "legacy", +] + + +def is_bech32_address(node, addr): + """Check if an address contains a bech32 output.""" + addr_info = node.getaddressinfo(addr) + return addr_info['desc'].startswith('wpkh(') + + +def is_bech32m_address(node, addr): + """Check if an address contains a bech32m output.""" + addr_info = node.getaddressinfo(addr) + return addr_info['desc'].startswith('tr(') + + +def is_p2sh_segwit_address(node, addr): + """Check if an address contains a P2SH-Segwit output. + Note: this function does not actually determine the type + of P2SH output, but is sufficient for this test in that + we are only generating P2SH-Segwit outputs. + """ + addr_info = node.getaddressinfo(addr) + return addr_info['desc'].startswith('sh(wpkh(') + + +def is_legacy_address(node, addr): + """Check if an address contains a legacy output.""" + addr_info = node.getaddressinfo(addr) + return addr_info['desc'].startswith('pkh(') + + +def is_same_type(node, tx): + """Check that all inputs are of the same OutputType""" + vins = node.getrawtransaction(tx, True)['vin'] + inputs = [] + for vin in vins: + prev_tx, n = vin['txid'], vin['vout'] + inputs.append( + node.getrawtransaction( + prev_tx, + True, + )['vout'][n]['scriptPubKey']['address'] + ) + has_legacy = False + has_p2sh = False + has_bech32 = False + has_bech32m = False + + for addr in inputs: + if is_legacy_address(node, addr): + has_legacy = True + if is_p2sh_segwit_address(node, addr): + has_p2sh = True + if is_bech32_address(node, addr): + has_bech32 = True + if is_bech32m_address(node, addr): + has_bech32m = True + + return (sum([has_legacy, has_p2sh, has_bech32, has_bech32m]) == 1) + + +def generate_payment_values(n, m): + """Return a randomly chosen list of n positive integers summing to m. + Each such list is equally likely to occur.""" + + dividers = sorted(random.sample(range(1, m), n - 1)) + return [a - b for a, b in zip(dividers + [m], [0] + dividers)] + + +class AddressInputTypeGrouping(BitcoinTestFramework): + def set_test_params(self): + self.setup_clean_chain = True + self.num_nodes = 2 + self.extra_args = [ + [ + "-addresstype=bech32", + "-whitelist=noban@127.0.0.1", + "-txindex", + ], + [ + "-addresstype=p2sh-segwit", + "-whitelist=noban@127.0.0.1", + "-txindex", + ], + ] + + def skip_test_if_missing_module(self): + self.skip_if_no_wallet() + + def make_payment(self, A, B, v, addr_type): + fee_rate = random.randint(1, 20) + self.log.debug(f"Making payment of {v} BTC at fee_rate {fee_rate}") + tx = B.sendtoaddress( + address=A.getnewaddress(address_type=addr_type), + amount=v, + fee_rate=fee_rate, + ) + return tx + + def run_test(self): + + # alias self.nodes[i] to A, B for readability + A, B = self.nodes[0], self.nodes[1] + self.generate(A, COINBASE_MATURITY + 5) + + self.log.info("Creating mixed UTXOs in B's wallet") + for v in generate_payment_values(3, 10): + self.log.debug(f"Making payment of {v} BTC to legacy") + A.sendtoaddress(B.getnewaddress(address_type="legacy"), v) + + for v in generate_payment_values(3, 10): + self.log.debug(f"Making payment of {v} BTC to p2sh") + A.sendtoaddress(B.getnewaddress(address_type="p2sh-segwit"), v) + + for v in generate_payment_values(3, 10): + self.log.debug(f"Making payment of {v} BTC to bech32") + A.sendtoaddress(B.getnewaddress(address_type="bech32"), v) + + for v in generate_payment_values(3, 10): + self.log.debug(f"Making payment of {v} BTC to bech32m") + A.sendtoaddress(B.getnewaddress(address_type="bech32m"), v) + + self.generate(A, 1) + + self.log.info("Sending payments from B to A") + for v in generate_payment_values(5, 9): + tx = self.make_payment( + A, B, v, random.choice(ADDRESS_TYPES) + ) + self.generate(A, 1) + assert is_same_type(B, tx) + + tx = self.make_payment(A, B, 30.99, random.choice(ADDRESS_TYPES)) + assert not is_same_type(B, tx) + + +if __name__ == '__main__': + AddressInputTypeGrouping().main() |