diff options
-rw-r--r-- | src/bench/coin_selection.cpp | 3 | ||||
-rw-r--r-- | src/wallet/coinselection.h | 9 | ||||
-rw-r--r-- | src/wallet/spend.cpp | 63 | ||||
-rw-r--r-- | src/wallet/spend.h | 15 | ||||
-rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 2 | ||||
-rw-r--r-- | src/wallet/test/group_outputs_tests.cpp | 2 |
6 files changed, 55 insertions, 39 deletions
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 8a78783517..265d4bf655 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -75,8 +75,9 @@ static void CoinSelection(benchmark::Bench& bench) /*tx_noinputs_size=*/ 0, /*avoid_partial=*/ false, }; + auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard]; bench.run([&] { - auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, available_coins, coin_selection_params, /*allow_mixed_output_types=*/true); + auto result = AttemptSelection(1003 * COIN, group, 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/coinselection.h b/src/wallet/coinselection.h index 420892e06e..3abd22c207 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -193,6 +193,11 @@ struct CoinEligibilityFilter CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_ancestors) {} CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants) {} CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants, bool include_partial) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants), m_include_partial_groups(include_partial) {} + + bool operator<(const CoinEligibilityFilter& other) const { + return std::tie(conf_mine, conf_theirs, max_ancestors, max_descendants, m_include_partial_groups) + < std::tie(other.conf_mine, other.conf_theirs, other.max_ancestors, other.max_descendants, other.m_include_partial_groups); + } }; /** A group of UTXOs paid to the same output script. */ @@ -263,8 +268,12 @@ struct OutputGroupTypeMap void Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed); // Retrieves 'Groups' filtered by type std::optional<Groups> Find(OutputType type); + // Different output types count + size_t TypesCount() { return groups_by_type.size(); } }; +typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups; + /** Compute the waste for this result given the cost of change * and the opportunity cost of spending these inputs now vs in the future. * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate) diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 9e1c9a6f6f..a8ecce119a 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -404,12 +404,12 @@ std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet) return result; } -OutputGroupTypeMap GroupOutputs(const CWallet& wallet, +FilteredOutputGroups GroupOutputs(const CWallet& wallet, const CoinsResult& coins, const CoinSelectionParams& coin_sel_params, - const CoinEligibilityFilter& filter) + const std::vector<SelectionFilter>& filters) { - OutputGroupTypeMap output_groups; + FilteredOutputGroups filtered_groups; if (!coin_sel_params.m_avoid_partial_spends) { // Allowing partial spends means no grouping. Each COutput gets its own OutputGroup @@ -426,11 +426,15 @@ OutputGroupTypeMap GroupOutputs(const CWallet& wallet, OutputGroup group(coin_sel_params); group.Insert(std::make_shared<COutput>(output), ancestors, descendants); - if (!group.EligibleForSpending(filter)) continue; - output_groups.Push(group, type, /*insert_positive=*/true, /*insert_mixed=*/true); + // Each filter maps to a different set of groups + for (const auto& sel_filter : filters) { + const auto& filter = sel_filter.filter; + if (!group.EligibleForSpending(filter)) continue; + filtered_groups[filter].Push(group, type, /*insert_positive=*/true, /*insert_mixed=*/true); + } } } - return output_groups; + return filtered_groups; } // We want to combine COutputs that have the same scriptPubKey into single OutputGroups @@ -492,16 +496,20 @@ OutputGroupTypeMap GroupOutputs(const CWallet& wallet, for (auto group_it = groups.rbegin(); group_it != groups.rend(); group_it++) { const OutputGroup& group = *group_it; - if (!group.EligibleForSpending(filter)) continue; + // Each filter maps to a different set of groups + for (const auto& sel_filter : filters) { + const auto& filter = sel_filter.filter; + if (!group.EligibleForSpending(filter)) continue; - // Don't include partial groups if there are full groups too and we don't want partial groups - if (group_it == groups.rbegin() && groups.size() > 1 && !filter.m_include_partial_groups) { - continue; - } + // Don't include partial groups if there are full groups too and we don't want partial groups + if (group_it == groups.rbegin() && groups.size() > 1 && !filter.m_include_partial_groups) { + continue; + } - OutputType type = script.second; - // Either insert the group into the positive-only groups or the mixed ones. - output_groups.Push(group, type, positive_only, /*insert_mixed=*/!positive_only); + OutputType type = script.second; + // Either insert the group into the positive-only groups or the mixed ones. + filtered_groups[filter].Push(group, type, positive_only, /*insert_mixed=*/!positive_only); + } } } }; @@ -509,24 +517,19 @@ OutputGroupTypeMap GroupOutputs(const CWallet& wallet, push_output_groups(spk_to_groups_map, /*positive_only=*/ false); push_output_groups(spk_to_positive_groups_map, /*positive_only=*/ true); - return output_groups; + return filtered_groups; } // Returns true if the result contains an error and the message is not empty static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); } -util::Result<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const CoinsResult& available_coins, +util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, OutputGroupTypeMap& groups, const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types) { - // Calculate all the output groups filtered by type at once - OutputGroupTypeMap groups = GroupOutputs(wallet, available_coins, coin_selection_params, {eligibility_filter}); - // Run coin selection on each OutputType and compute the Waste Metric std::vector<SelectionResult> results; - for (const auto& [type, coins] : available_coins.coins) { - auto group_for_type = groups.Find(type); - if (!group_for_type) continue; - auto result{ChooseSelectionResult(nTargetValue, *group_for_type, coin_selection_params)}; + for (auto& [type, group] : groups.groups_by_type) { + auto result{ChooseSelectionResult(nTargetValue, group, coin_selection_params)}; // If any specific error message appears here, then something particularly wrong happened. if (HasErrorMsg(result)) return result; // So let's return the specific error. // Append the favorable result. @@ -539,7 +542,7 @@ util::Result<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmo // If we can't fund the transaction from any individual OutputType, run coin selection one last time // over all available coins, which would allow mixing. // If TypesCount() <= 1, there is nothing to mix. - if (allow_mixed_output_types && available_coins.TypesCount() > 1) { + if (allow_mixed_output_types && groups.TypesCount() > 1) { return ChooseSelectionResult(nTargetValue, groups.all_groups, coin_selection_params); } // Either mixing is not allowed and we couldn't find a solution from any single OutputType, or mixing was allowed and we still couldn't @@ -634,11 +637,6 @@ util::Result<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& av return op_selection_result; } -struct SelectionFilter { - CoinEligibilityFilter filter; - bool allow_mixed_output_types{true}; -}; - util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, CoinsResult& available_coins, const CAmount& value_to_select, const CCoinControl& coin_control, const CoinSelectionParams& coin_selection_params) { unsigned int limit_ancestor_count = 0; @@ -693,12 +691,17 @@ util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, Coin } } + // Group outputs and map them by coin eligibility filter + FilteredOutputGroups filtered_groups = GroupOutputs(wallet, available_coins, coin_selection_params, ordered_filters); + // Walk-through the filters until the solution gets found. // If no solution is found, return the first detailed error (if any). // future: add "error level" so the worst one can be picked instead. std::vector<util::Result<SelectionResult>> res_detailed_errors; for (const auto& select_filter : ordered_filters) { - if (auto res{AttemptSelection(wallet, value_to_select, select_filter.filter, available_coins, + auto it = filtered_groups.find(select_filter.filter); + if (it == filtered_groups.end()) continue; + if (auto res{AttemptSelection(value_to_select, it->second, coin_selection_params, select_filter.allow_mixed_output_types)}) { return res; // result found } else { diff --git a/src/wallet/spend.h b/src/wallet/spend.h index 315f8a7fe9..b8bc82db7a 100644 --- a/src/wallet/spend.h +++ b/src/wallet/spend.h @@ -106,13 +106,18 @@ const CTxOut& FindNonChangeParentOutput(const CWallet& wallet, const COutPoint& */ std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet); +struct SelectionFilter { + CoinEligibilityFilter filter; + bool allow_mixed_output_types{true}; +}; + /** * Group coins by the provided filters. */ -OutputGroupTypeMap GroupOutputs(const CWallet& wallet, +FilteredOutputGroups GroupOutputs(const CWallet& wallet, const CoinsResult& coins, const CoinSelectionParams& coin_sel_params, - const CoinEligibilityFilter& filter); + const std::vector<SelectionFilter>& filters); /** * Attempt to find a valid input set that preserves privacy by not mixing OutputTypes. @@ -120,10 +125,8 @@ OutputGroupTypeMap GroupOutputs(const CWallet& wallet, * 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] groups The grouped outputs mapped by coin eligibility filters * 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 @@ -131,7 +134,7 @@ OutputGroupTypeMap GroupOutputs(const CWallet& wallet, * or (2) an specific error message if there was something particularly wrong (e.g. a selection * result that surpassed the tx max weight size). */ -util::Result<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const CoinsResult& available_coins, +util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, OutputGroupTypeMap& groups, const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types); /** diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 841d762932..8f626addde 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -154,7 +154,7 @@ inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinsResult& availab /*avoid_partial=*/ false, }; static OutputGroupTypeMap static_groups; - static_groups = GroupOutputs(wallet, available_coins, coin_selection_params, {filter}); + static_groups = GroupOutputs(wallet, available_coins, coin_selection_params, {{filter}})[filter]; return static_groups.all_groups.mixed_group; } diff --git a/src/wallet/test/group_outputs_tests.cpp b/src/wallet/test/group_outputs_tests.cpp index 352ec44d5d..283e87989c 100644 --- a/src/wallet/test/group_outputs_tests.cpp +++ b/src/wallet/test/group_outputs_tests.cpp @@ -86,7 +86,7 @@ public: bool positive_only, int expected_size) { - OutputGroupTypeMap groups = GroupOutputs(*wallet, coins_pool, makeSelectionParams(rand, avoid_partial_spends), filter); + OutputGroupTypeMap groups = GroupOutputs(*wallet, coins_pool, makeSelectionParams(rand, avoid_partial_spends), {{filter}})[filter]; std::vector<OutputGroup>& groups_out = positive_only ? groups.groups_by_type[type].positive_group : groups.groups_by_type[type].mixed_group; BOOST_CHECK_EQUAL(groups_out.size(), expected_size); |