From aaee65823c6e620bef5cc96d8026567e64d822fe Mon Sep 17 00:00:00 2001 From: Murch Date: Tue, 13 Jun 2023 16:49:14 -0400 Subject: doc: Document max_weight on BnB --- src/wallet/coinselection.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 391e120932..7d15a9997a 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -68,6 +68,7 @@ struct { * bound of the range. * @param const CAmount& cost_of_change This is the cost of creating and spending a change output. * This plus selection_target is the upper bound of the range. + * @param int max_weight The maximum weight available for the input set. * @returns The result of this coin selection algorithm, or std::nullopt */ -- cgit v1.2.3 From 89d09566431f57034d9a7df32547ceb13d79c62c Mon Sep 17 00:00:00 2001 From: Murch Date: Tue, 13 Jun 2023 15:56:18 -0400 Subject: opt: Tie-break UTXO sort by waste for BnB Since we are searching for the minimal waste, we sort UTXOs with equal effective value by ascending waste to be able to cut barren branches earlier. --- src/wallet/coinselection.cpp | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 7d15a9997a..570fac6900 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -25,10 +25,14 @@ static util::Result ErrorMaxWeightExceeded() "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")}; } -// Descending order comparator +// Sort by descending (effective) value prefer lower waste on tie struct { bool operator()(const OutputGroup& a, const OutputGroup& b) const { + if (a.GetSelectionAmount() == b.GetSelectionAmount()) { + // Lower waste is better when effective_values are tied + return (a.fee - a.long_term_fee) < (b.fee - b.long_term_fee); + } return a.GetSelectionAmount() > b.GetSelectionAmount(); } } descending; -- cgit v1.2.3 From 6cc9a46cd0f4ed80d4523bbef1508142e0c80d27 Mon Sep 17 00:00:00 2001 From: Murch Date: Tue, 23 May 2023 19:36:04 -0400 Subject: coinselection: Add CoinGrinder algorithm CoinGrinder is a DFS-based coin selection algorithm that deterministically finds the input set with the lowest weight creating a change output. --- src/wallet/coinselection.cpp | 291 +++++++++++++++++++++++++++++++++ src/wallet/coinselection.h | 17 +- src/wallet/spend.cpp | 9 + src/wallet/test/coinselector_tests.cpp | 1 - 4 files changed, 314 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 570fac6900..20944b3c8d 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -188,6 +188,286 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool return result; } +/* + * TL;DR: Coin Grinder is a DFS-based algorithm that deterministically searches for the minimum-weight input set to fund + * the transaction. The algorithm is similar to the Branch and Bound algorithm, but will produce a transaction _with_ a + * change output instead of a changeless transaction. + * + * Full description: CoinGrinder can be thought of as a graph walking algorithm. It explores a binary tree + * representation of the powerset of the UTXO pool. Each node in the tree represents a candidate input set. The tree’s + * root is the empty set. Each node in the tree has two children which are formed by either adding or skipping the next + * UTXO ("inclusion/omission branch"). Each level in the tree after the root corresponds to a decision about one UTXO in + * the UTXO pool. + * + * Example: + * We represent UTXOs as _alias=[effective_value/weight]_ and indicate omitted UTXOs with an underscore. Given a UTXO + * pool {A=[10/2], B=[7/1], C=[5/1], D=[4/2]} sorted by descending effective value, our search tree looks as follows: + * + * _______________________ {} ________________________ + * / \ + * A=[10/2] __________ {A} _________ __________ {_} _________ + * / \ / \ + * B=[7/1] {AB} _ {A_} _ {_B} _ {__} _ + * / \ / \ / \ / \ + * C=[5/1] {ABC} {AB_} {A_C} {A__} {_BC} {_B_} {__C} {___} + * / \ / \ / \ / \ / \ / \ / \ / \ + * D=[4/2] {ABCD} {ABC_} {AB_D} {AB__} {A_CD} {A_C_} {A__D} {A___} {_BCD} {_BC_} {_B_D} {_B__} {__CD} {__C_} {___D} {____} + * + * + * CoinGrinder uses a depth-first search to walk this tree. It first tries inclusion branches, then omission branches. A + * naive exploration of a tree with four UTXOs requires visiting all 31 nodes: + * + * {} {A} {AB} {ABC} {ABCD} {ABC_} {AB_} {AB_D} {AB__} {A_} {A_C} {A_CD} {A_C_} {A__} {A__D} {A___} {_} {_B} {_BC} + * {_BCD} {_BC_} {_B_} {_B_D} {_B__} {__} {__C} {__CD} {__C} {___} {___D} {____} + * + * As powersets grow exponentially with the set size, walking the entire tree would quickly get computationally + * infeasible with growing UTXO pools. Thanks to traversing the tree in a deterministic order, we can keep track of the + * progress of the search solely on basis of the current selection (and the best selection so far). We visit as few + * nodes as possible by recognizing and skipping any branches that can only contain solutions worse than the best + * solution so far. This makes CoinGrinder a branch-and-bound algorithm + * (https://en.wikipedia.org/wiki/Branch_and_bound). + * CoinGrinder is searching for the input set with lowest weight that can fund a transaction, so for example we can only + * ever find a _better_ candidate input set in a node that adds a UTXO, but never in a node that skips a UTXO. After + * visiting {A} and exploring the inclusion branch {AB} and its descendants, the candidate input set in the omission + * branch {A_} is equivalent to the parent {A} in effective value and weight. While CoinGrinder does need to visit the + * descendants of the omission branch {A_}, it is unnecessary to evaluate the candidate input set in the omission branch + * itself. By skipping evaluation of all nodes on an omission branch we reduce the visited nodes to 15: + * + * {A} {AB} {ABC} {ABCD} {AB_D} {A_C} {A_CD} {A__D} {_B} {_BC} {_BCD} {_B_D} {__C} {__CD} {___D} + * + * _______________________ {} ________________________ + * / \ + * A=[10/2] __________ {A} _________ ___________\____________ + * / \ / \ + * B=[7/1] {AB} __ __\_____ {_B} __ __\_____ + * / \ / \ / \ / \ + * C=[5/1] {ABC} \ {A_C} \ {_BC} \ {__C} \ + * / / / / / / / / + * D=[4/2] {ABCD} {AB_D} {A_CD} {A__D} {_BCD} {_B_D} {__CD} {___D} + * + * + * We refer to the move from the inclusion branch {AB} via the omission branch {A_} to its inclusion-branch child {A_C} + * as _shifting to the omission branch_ or just _SHIFT_. (The index of the ultimate element in the candidate input set + * shifts right by one: {AB} ⇒ {A_C}.) + * When we reach a leaf node in the last level of the tree, shifting to the omission branch is not possible. Instead we + * go to the omission branch of the node’s last ancestor on an inclusion branch: from {ABCD}, we go to {AB_D}. From + * {AB_D}, we go to {A_C}. We refer to this operation as a _CUT_. (The ultimate element in + * the input set is deselected, and the penultimate element is shifted right by one: {AB_D} ⇒ {A_C}.) + * If a candidate input set in a node has not selected sufficient funds to build the transaction, we continue directly + * along the next inclusion branch. We call this operation _EXPLORE_. (We go from one inclusion branch to the next + * inclusion branch: {_B} ⇒ {_BC}.) + * Further, any prefix that already has selected sufficient effective value to fund the transaction cannot be improved + * by adding more UTXOs. If for example the candidate input set in {AB} is a valid solution, all potential descendant + * solutions {ABC}, {ABCD}, and {AB_D} must have a higher weight, thus instead of exploring the descendants of {AB}, we + * can SHIFT from {AB} to {A_C}. + * + * Given the above UTXO set, using a target of 11, and following these initial observations, the basic implementation of + * CoinGrinder visits the following 10 nodes: + * + * Node [eff_val/weight] Evaluation + * --------------------------------------------------------------- + * {A} [10/2] Insufficient funds: EXPLORE + * {AB} [17/3] Solution: SHIFT to omission branch + * {A_C} [15/3] Better solution: SHIFT to omission branch + * {A__D} [14/4] Worse solution, shift impossible due to leaf node: CUT to omission branch of {A__D}, + * i.e. SHIFT to omission branch of {A} + * {_B} [7/1] Insufficient funds: EXPLORE + * {_BC} [12/2] Better solution: SHIFT to omission branch + * {_B_D} [11/3] Worse solution, shift impossible due to leaf node: CUT to omission branch of {_B_D}, + * i.e. SHIFT to omission branch of {_B} + * {__C} [5/1] Insufficient funds: EXPLORE + * {__CD} [9/3] Insufficient funds, leaf node: CUT + * {___D} [4/2] Insufficient funds, leaf node, cannot CUT since only one UTXO selected: done. + * + * _______________________ {} ________________________ + * / \ + * A=[10/2] __________ {A} _________ ___________\____________ + * / \ / \ + * B=[7/1] {AB} __\_____ {_B} __ __\_____ + * / \ / \ / \ + * C=[5/1] {A_C} \ {_BC} \ {__C} \ + * / / / / + * D=[4/2] {A__D} {_B_D} {__CD} {___D} + * + * + * We implement this tree walk in the following algorithm: + * 1. Add `next_utxo` + * 2. Evaluate candidate input set + * 3. Determine `next_utxo` by deciding whether to + * a) EXPLORE: Add next inclusion branch, e.g. {_B} ⇒ {_B} + `next_uxto`: C + * b) SHIFT: Replace last selected UTXO by next higher index, e.g. {A_C} ⇒ {A__} + `next_utxo`: D + * c) CUT: deselect last selected UTXO and shift to omission branch of penultimate UTXO, e.g. {AB_D} ⇒ {A_} + `next_utxo: C + * + * The implementation then adds further optimizations by discovering further situations in which either the inclusion + * branch can be skipped, or both the inclusion and omission branch can be skipped after evaluating the candidate input + * set in the node. + * + * @param std::vector& utxo_pool The UTXOs that we are choosing from. These UTXOs will be sorted in + * descending order by effective value, with lower waste preferred as a tie-breaker. (We can think of an output + * group with multiple as a heavier UTXO with the combined amount here.) + * @param const CAmount& selection_target This is the minimum amount that we need for the transaction without considering change. + * @param const CAmount& change_target The minimum budget for creating a change output, by which we increase the selection_target. + * @param int max_weight The maximum permitted weight for the input set. + * @returns The result of this coin selection algorithm, or std::nullopt + */ +util::Result CoinGrinder(std::vector& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_weight) +{ + std::sort(utxo_pool.begin(), utxo_pool.end(), descending); + + // Check that there are sufficient funds + CAmount total_available = 0; + for (const OutputGroup& utxo : utxo_pool) { + // Assert UTXOs with non-positive effective value have been filtered + Assume(utxo.GetSelectionAmount() > 0); + total_available += utxo.GetSelectionAmount(); + } + + const CAmount total_target = selection_target + change_target; + if (total_available < total_target) { + // Insufficient funds + return util::Error(); + } + + // The current selection and the best input set found so far, stored as the utxo_pool indices of the UTXOs forming them + std::vector curr_selection; + std::vector best_selection; + + // The currently selected effective amount, and the effective amount of the best selection so far + CAmount curr_amount = 0; + CAmount best_selection_amount = MAX_MONEY; + + // The weight of the currently selected input set, and the weight of the best selection + int curr_weight = 0; + int best_selection_weight = std::numeric_limits::max(); + + // Whether the input sets generated during this search have exceeded the maximum transaction weight at any point + bool max_tx_weight_exceeded = false; + + // Index of the next UTXO to consider in utxo_pool + size_t next_utxo = 0; + + /* + * You can think of the current selection as a vector of booleans that has decided inclusion or exclusion of all + * UTXOs before `next_utxo`. When we consider the next UTXO, we extend this hypothetical boolean vector either with + * a true value if the UTXO is included or a false value if it is omitted. The equivalent state is stored more + * compactly as the list of indices of the included UTXOs and the `next_utxo` index. + * + * We can never find a new solution by deselecting a UTXO, because we then revisit a previously evaluated + * selection. Therefore, we only need to check whether we found a new solution _after adding_ a new UTXO. + * + * Each iteration of CoinGrinder starts by selecting the `next_utxo` and evaluating the current selection. We + * use three state transitions to progress from the current selection to the next promising selection: + * + * - EXPLORE inclusion branch: We do not have sufficient funds, yet. Add `next_utxo` to the current selection, then + * nominate the direct successor of the just selected UTXO as our `next_utxo` for the + * following iteration. + * + * Example: + * Current Selection: {0, 5, 7} + * Evaluation: EXPLORE, next_utxo: 8 + * Next Selection: {0, 5, 7, 8} + * + * - SHIFT to omission branch: Adding more UTXOs to the current selection cannot produce a solution that is better + * than the current best, e.g. the current selection weight exceeds the max weight or + * the current selection amount is equal to or greater than the target. + * We designate our `next_utxo` the one after the tail of our current selection, then + * deselect the tail of our current selection. + * + * Example: + * Current Selection: {0, 5, 7} + * Evaluation: SHIFT, next_utxo: 8, omit last selected: {0, 5} + * Next Selection: {0, 5, 8} + * + * - CUT entire subtree: We have exhausted the inclusion branch for the penultimately selected UTXO, both the + * inclusion and the omission branch of the current prefix are barren. E.g. we have + * reached the end of the UTXO pool, so neither further EXPLORING nor SHIFTING can find + * any solutions. We designate our `next_utxo` the one after our penultimate selected, + * then deselect both the last and penultimate selected. + * + * Example: + * Current Selection: {0, 5, 7} + * Evaluation: CUT, next_utxo: 6, omit two last selected: {0} + * Next Selection: {0, 6} + */ + auto deselect_last = [&]() { + OutputGroup& utxo = utxo_pool[curr_selection.back()]; + curr_amount -= utxo.GetSelectionAmount(); + curr_weight -= utxo.m_weight; + curr_selection.pop_back(); + }; + + SelectionResult result(selection_target, SelectionAlgorithm::CG); + size_t curr_try = 0; + while (true) { + bool should_shift{false}, should_cut{false}; + // Select `next_utxo` + OutputGroup& utxo = utxo_pool[next_utxo]; + curr_amount += utxo.GetSelectionAmount(); + curr_weight += utxo.m_weight; + curr_selection.push_back(next_utxo); + ++next_utxo; + ++curr_try; + + // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further + if (curr_weight > max_weight) { + // max_weight exceeded: SHIFT + max_tx_weight_exceeded = true; + should_shift = true; + } else if (curr_amount >= total_target) { + // Success, adding more weight cannot be better: SHIFT + should_shift = true; + if (curr_weight < best_selection_weight || (curr_weight == best_selection_weight && curr_amount < best_selection_amount)) { + // New lowest weight, or same weight with fewer funds tied up + best_selection = curr_selection; + best_selection_weight = curr_weight; + best_selection_amount = curr_amount; + } + } + + if (curr_try >= TOTAL_TRIES) { + // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES + break; + } + + if (next_utxo == utxo_pool.size()) { + // Last added UTXO was end of UTXO pool, nothing left to add on inclusion or omission branch: CUT + should_cut = true; + } + + if (should_cut) { + // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can + // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e. + // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs) + should_cut = false; + deselect_last(); + should_shift = true; + } + + if (should_shift) { + // Set `next_utxo` to one after last selected, then deselect last selected UTXO + if (curr_selection.empty()) { + // Exhausted search space before running into attempt limit + break; + } + next_utxo = curr_selection.back() + 1; + deselect_last(); + should_shift = false; + } + } + + result.SetSelectionsEvaluated(curr_try); + + if (best_selection.empty()) { + return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error(); + } + + for (const size_t& i : best_selection) { + result.AddInput(utxo_pool[i]); + } + + return result; +} + class MinOutputGroupComparator { public: @@ -514,6 +794,16 @@ void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const } } +void SelectionResult::SetSelectionsEvaluated(size_t attempts) +{ + m_selections_evaluated = attempts; +} + +size_t SelectionResult::GetSelectionsEvaluated() const +{ + return m_selections_evaluated; +} + CAmount SelectionResult::GetWaste() const { return *Assert(m_waste); @@ -607,6 +897,7 @@ std::string GetAlgorithmName(const SelectionAlgorithm algo) case SelectionAlgorithm::BNB: return "bnb"; case SelectionAlgorithm::KNAPSACK: return "knapsack"; case SelectionAlgorithm::SRD: return "srd"; + case SelectionAlgorithm::CG: return "cg"; case SelectionAlgorithm::MANUAL: return "manual"; // No default case to allow for compiler to warn } diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 20b2461c04..ba9e6bafd9 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -142,8 +142,8 @@ struct CoinSelectionParams { size_t change_output_size = 0; /** Size of the input to spend a change output in virtual bytes. */ size_t change_spend_size = 0; - /** Mininmum change to target in Knapsack solver: select coins to cover the payment and - * at least this value of change. */ + /** Mininmum change to target in Knapsack solver and CoinGrinder: + * select coins to cover the payment and at least this value of change. */ CAmount m_min_change_target{0}; /** Minimum amount for creating a change output. * If change budget is smaller than min_change then we forgo creation of change output. @@ -311,7 +311,8 @@ enum class SelectionAlgorithm : uint8_t BNB = 0, KNAPSACK = 1, SRD = 2, - MANUAL = 3, + CG = 3, + MANUAL = 4, }; std::string GetAlgorithmName(const SelectionAlgorithm algo); @@ -329,6 +330,8 @@ private: bool m_use_effective{false}; /** The computed waste */ std::optional m_waste; + /** The count of selections that were evaluated by this coin selection attempt */ + size_t m_selections_evaluated; /** Total weight of the selected inputs */ int m_weight{0}; /** How much individual inputs overestimated the bump fees for the shared ancestry */ @@ -386,6 +389,12 @@ public: void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee); [[nodiscard]] CAmount GetWaste() const; + /** Record the number of selections that were evaluated */ + void SetSelectionsEvaluated(size_t attempts); + + /** Get selections_evaluated */ + size_t GetSelectionsEvaluated() const ; + /** * Combines the @param[in] other selection result into 'this' selection result. * @@ -430,6 +439,8 @@ public: util::Result SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, int max_weight); +util::Result CoinGrinder(std::vector& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_weight); + /** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible * outputs until the target is satisfied * diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index b51cd6332f..c79079d33d 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -709,6 +709,15 @@ util::Result ChooseSelectionResult(interfaces::Chain& chain, co results.push_back(*knapsack_result); } else append_error(knapsack_result); + if (coin_selection_params.m_effective_feerate > CFeeRate{3 * coin_selection_params.m_long_term_feerate}) { // Minimize input set for feerates of at least 3×LTFRE (default: 30 ṩ/vB+) + if (auto cg_result{CoinGrinder(groups.positive_group, nTargetValue, coin_selection_params.m_min_change_target, max_inputs_weight)}) { + cg_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); + results.push_back(*cg_result); + } else { + append_error(cg_result); + } + } + if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.m_change_fee, coin_selection_params.rng_fast, max_inputs_weight)}) { results.push_back(*srd_result); } else append_error(srd_result); diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 9fea14145f..3b419ca765 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1090,7 +1090,6 @@ BOOST_AUTO_TEST_CASE(effective_value_test) BOOST_CHECK_EQUAL(output5.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1 } - static util::Result SelectCoinsSRD(const CAmount& target, const CoinSelectionParams& cs_params, const node::NodeContext& m_node, -- cgit v1.2.3 From 7488acc64685ae16e20b78e7ad018137f27fe404 Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 15:41:02 -0500 Subject: test: Add coin_grinder_tests --- src/wallet/test/coinselector_tests.cpp | 213 +++++++++++++++++++++++++++++++++ 1 file changed, 213 insertions(+) (limited to 'src') diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 3b419ca765..e23292d21f 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1090,6 +1090,218 @@ BOOST_AUTO_TEST_CASE(effective_value_test) BOOST_CHECK_EQUAL(output5.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1 } +static util::Result CoinGrinder(const CAmount& target, + const CoinSelectionParams& cs_params, + const node::NodeContext& m_node, + int max_weight, + std::function coin_setup) +{ + std::unique_ptr wallet = NewWallet(m_node); + CoinEligibilityFilter filter(0, 0, 0); // accept all coins without ancestors + Groups group = GroupOutputs(*wallet, coin_setup(*wallet), cs_params, {{filter}})[filter].all_groups; + return CoinGrinder(group.positive_group, target, cs_params.m_min_change_target, max_weight); +} + +BOOST_AUTO_TEST_CASE(coin_grinder_tests) +{ + // Test Coin Grinder: + // 1) Insufficient funds, select all provided coins and fail. + // 2) Exceeded max weight, coin selection always surpasses the max allowed weight. + // 3) Select coins without surpassing the max weight (some coins surpasses the max allowed weight, some others not) + // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO + // 5) Test finding a solution in a UTXO pool with mixed weights + // 6) Test that the lightest solution among many clones is found + // 7) Lots of tiny UTXOs of different amounts quickly exhausts the search attempts + + FastRandomContext rand; + CoinSelectionParams dummy_params{ // Only used to provide the 'avoid_partial' flag. + rand, + /*change_output_size=*/34, + /*change_spend_size=*/68, + /*min_change_target=*/CENT, + /*effective_feerate=*/CFeeRate(5000), + /*long_term_feerate=*/CFeeRate(2000), + /*discard_feerate=*/CFeeRate(1000), + /*tx_noinputs_size=*/10 + 34, // static header size + output size + /*avoid_partial=*/false, + }; + + { + // ######################################################### + // 1) Insufficient funds, select all provided coins and fail + // ######################################################### + CAmount target = 49.5L * COIN; + int max_weight = 10'000; // high enough to not fail for this reason. + const auto& res = CoinGrinder(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { + CoinsResult available_coins; + for (int j = 0; j < 10; ++j) { + add_coin(available_coins, wallet, CAmount(1 * COIN)); + add_coin(available_coins, wallet, CAmount(2 * COIN)); + } + return available_coins; + }); + BOOST_CHECK(!res); + BOOST_CHECK(util::ErrorString(res).empty()); // empty means "insufficient funds" + } + + { + // ########################### + // 2) Test max weight exceeded + // ########################### + CAmount target = 29.5L * COIN; + int max_weight = 3000; + const auto& res = CoinGrinder(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { + CoinsResult available_coins; + for (int j = 0; j < 10; ++j) { + add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true); + add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true); + } + return available_coins; + }); + BOOST_CHECK(!res); + BOOST_CHECK(util::ErrorString(res).original.find("The inputs size exceeds the maximum weight") != std::string::npos); + } + + { + // ############################################################################################################### + // 3) Test selection when some coins surpass the max allowed weight while others not. --> must find a good solution + // ################################################################################################################ + CAmount target = 25.33L * COIN; + int max_weight = 10'000; // WU + const auto& res = CoinGrinder(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { + CoinsResult available_coins; + for (int j = 0; j < 60; ++j) { // 60 UTXO --> 19,8 BTC total --> 60 × 272 WU = 16320 WU + add_coin(available_coins, wallet, CAmount(0.33 * COIN), CFeeRate(5000), 144, false, 0, true); + } + for (int i = 0; i < 10; i++) { // 10 UTXO --> 20 BTC total --> 10 × 272 WU = 2720 WU + add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true); + } + return available_coins; + }); + BOOST_CHECK(res); + // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. + size_t expected_attempts = 100'000; + BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); + } + + { + // ################################################################################################################# + // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO + // ################################################################################################################# + CAmount target = 1.9L * COIN; + int max_weight = 400'000; // WU + const auto& res = CoinGrinder(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { + CoinsResult available_coins; + add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true, 148); + add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68); + add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68); + return available_coins; + }); + SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); + add_coin(1 * COIN, 1, expected_result); + add_coin(1 * COIN, 2, expected_result); + BOOST_CHECK(EquivalentResult(expected_result, *res)); + // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. + size_t expected_attempts = 4; + BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); + } + + { + // ############################################################################################################### + // 5) Test finding a solution in a UTXO pool with mixed weights + // ################################################################################################################ + CAmount target = 30L * COIN; + int max_weight = 400'000; // WU + const auto& res = CoinGrinder(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { + CoinsResult available_coins; + for (int j = 0; j < 5; ++j) { + // Add heavy coins {3, 6, 9, 12, 15} + add_coin(available_coins, wallet, CAmount((3 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 350); + // Add medium coins {2, 5, 8, 11, 14} + add_coin(available_coins, wallet, CAmount((2 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 250); + // Add light coins {1, 4, 7, 10, 13} + add_coin(available_coins, wallet, CAmount((1 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 150); + } + return available_coins; + }); + BOOST_CHECK(res); + SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); + add_coin(14 * COIN, 1, expected_result); + add_coin(13 * COIN, 2, expected_result); + add_coin(4 * COIN, 3, expected_result); + BOOST_CHECK(EquivalentResult(expected_result, *res)); + // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. + size_t expected_attempts = 2041; + BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); + } + + { + // ################################################################################################################# + // 6) Test that the lightest solution among many clones is found + // ################################################################################################################# + CAmount target = 9.9L * COIN; + int max_weight = 400'000; // WU + const auto& res = CoinGrinder(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { + CoinsResult available_coins; + // Expected Result: 4 + 3 + 2 + 1 = 10 BTC at 400 vB + add_coin(available_coins, wallet, CAmount(4 * COIN), CFeeRate(5000), 144, false, 0, true, 100); + add_coin(available_coins, wallet, CAmount(3 * COIN), CFeeRate(5000), 144, false, 0, true, 100); + add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true, 100); + add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 100); + // Distracting clones: + for (int j = 0; j < 100; ++j) { + add_coin(available_coins, wallet, CAmount(8 * COIN), CFeeRate(5000), 144, false, 0, true, 1000); + } + for (int j = 0; j < 100; ++j) { + add_coin(available_coins, wallet, CAmount(7 * COIN), CFeeRate(5000), 144, false, 0, true, 800); + } + for (int j = 0; j < 100; ++j) { + add_coin(available_coins, wallet, CAmount(6 * COIN), CFeeRate(5000), 144, false, 0, true, 600); + } + for (int j = 0; j < 100; ++j) { + add_coin(available_coins, wallet, CAmount(5 * COIN), CFeeRate(5000), 144, false, 0, true, 400); + } + return available_coins; + }); + SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); + add_coin(4 * COIN, 0, expected_result); + add_coin(3 * COIN, 0, expected_result); + add_coin(2 * COIN, 0, expected_result); + add_coin(1 * COIN, 0, expected_result); + BOOST_CHECK(EquivalentResult(expected_result, *res)); + // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. + // If this takes more attempts, the implementation has regressed + size_t expected_attempts = 82'815; + BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); + } + + { + // ################################################################################################################# + // 7) Lots of tiny UTXOs of different amounts quickly exhausts the search attempts + // ################################################################################################################# + CAmount target = 1.9L * COIN; + int max_weight = 40000; // WU + const auto& res = CoinGrinder(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { + CoinsResult available_coins; + add_coin(available_coins, wallet, CAmount(1.8 * COIN), CFeeRate(5000), 144, false, 0, true, 2500); + add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000); + add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000); + for (int j = 0; j < 100; ++j) { + // make a 100 unique coins only differing by one sat + add_coin(available_coins, wallet, CAmount(0.01 * COIN + j), CFeeRate(5000), 144, false, 0, true, 110); + } + return available_coins; + }); + SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); + add_coin(1.8 * COIN, 1, expected_result); + add_coin(1 * COIN, 2, expected_result); + BOOST_CHECK(EquivalentResult(expected_result, *res)); + // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. + size_t expected_attempts = 100'000; + BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); + } +} + static util::Result SelectCoinsSRD(const CAmount& target, const CoinSelectionParams& cs_params, const node::NodeContext& m_node, @@ -1149,6 +1361,7 @@ BOOST_AUTO_TEST_CASE(srd_tests) const auto& res = SelectCoinsSRD(target, dummy_params, m_node, max_weight, [&](CWallet& wallet) { CoinsResult available_coins; for (int j = 0; j < 10; ++j) { + /* 10 × 1 BTC + 10 × 2 BTC = 30 BTC. 20 × 272 WU = 5440 WU */ add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(0), 144, false, 0, true); add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(0), 144, false, 0, true); } -- cgit v1.2.3 From 1502231229dbc32c94e80a2fc2959275c5d246ef Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 15:35:05 -0500 Subject: coinselection: Track whether CG completed CoinGrinder may not be able to exhaustively search all potentially interesting combinations for large UTXO pools, so we keep track of whether the search was terminated by the iteration limit. --- src/wallet/coinselection.cpp | 12 ++++++++++++ src/wallet/coinselection.h | 8 ++++++++ 2 files changed, 20 insertions(+) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 20944b3c8d..abd710d56d 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -426,6 +426,7 @@ util::Result CoinGrinder(std::vector& utxo_pool, c if (curr_try >= TOTAL_TRIES) { // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES + result.SetAlgoCompleted(false); break; } @@ -447,6 +448,7 @@ util::Result CoinGrinder(std::vector& utxo_pool, c // Set `next_utxo` to one after last selected, then deselect last selected UTXO if (curr_selection.empty()) { // Exhausted search space before running into attempt limit + result.SetAlgoCompleted(true); break; } next_utxo = curr_selection.back() + 1; @@ -794,6 +796,16 @@ void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const } } +void SelectionResult::SetAlgoCompleted(bool algo_completed) +{ + m_algo_completed = algo_completed; +} + +bool SelectionResult::GetAlgoCompleted() const +{ + return m_algo_completed; +} + void SelectionResult::SetSelectionsEvaluated(size_t attempts) { m_selections_evaluated = attempts; diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index ba9e6bafd9..80c92e1b0e 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -330,6 +330,8 @@ private: bool m_use_effective{false}; /** The computed waste */ std::optional m_waste; + /** False if algorithm was cut short by hitting limit of attempts and solution is non-optimal */ + bool m_algo_completed{true}; /** The count of selections that were evaluated by this coin selection attempt */ size_t m_selections_evaluated; /** Total weight of the selected inputs */ @@ -389,6 +391,12 @@ public: void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee); [[nodiscard]] CAmount GetWaste() const; + /** Tracks that algorithm was able to exhaustively search the entire combination space before hitting limit of tries */ + void SetAlgoCompleted(bool algo_completed); + + /** Get m_algo_completed */ + bool GetAlgoCompleted() const; + /** Record the number of selections that were evaluated */ void SetSelectionsEvaluated(size_t attempts); -- cgit v1.2.3 From 67df6c629a2e9878b06c1903e90b67087eaa3688 Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 15:30:40 -0500 Subject: fuzz: Add CoinGrinder fuzz target --- src/wallet/test/fuzz/coinselection.cpp | 57 ++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) (limited to 'src') diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp index 87d419493b..c54179d3c9 100644 --- a/src/wallet/test/fuzz/coinselection.cpp +++ b/src/wallet/test/fuzz/coinselection.cpp @@ -77,6 +77,63 @@ static SelectionResult ManualSelection(std::vector& utxos, const CAmoun // Returns true if the result contains an error and the message is not empty static bool HasErrorMsg(const util::Result& res) { return !util::ErrorString(res).empty(); } +FUZZ_TARGET(coin_grinder) +{ + FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()}; + std::vector utxo_pool; + + const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_MONEY)}; + + FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)}; + CoinSelectionParams coin_params{fast_random_context}; + coin_params.m_subtract_fee_outputs = fuzzed_data_provider.ConsumeBool(); + coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; + coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; + coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(10, 1000); + coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange(10, 1000); + coin_params.m_cost_of_change= coin_params.m_effective_feerate.GetFee(coin_params.change_output_size) + coin_params.m_long_term_feerate.GetFee(coin_params.change_spend_size); + coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size); + // For other results to be comparable to SRD, we must align the change_target with SRD’s hardcoded behavior + coin_params.m_min_change_target = CHANGE_LOWER + coin_params.m_change_fee; + + // Create some coins + CAmount total_balance{0}; + CAmount max_spendable{0}; + int next_locktime{0}; + LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000) + { + const int n_input{fuzzed_data_provider.ConsumeIntegralInRange(0, 10)}; + const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange(41, 10000)}; + const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_MONEY)}; + if (total_balance + amount >= MAX_MONEY) { + break; + } + AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate); + total_balance += amount; + CAmount eff_value = amount - coin_params.m_effective_feerate.GetFee(n_input_bytes); + max_spendable += eff_value; + } + + std::vector group_pos; + GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos); + + // Run coinselection algorithms + auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, MAX_STANDARD_TX_WEIGHT); + if (target + coin_params.m_min_change_target > max_spendable || HasErrorMsg(result_cg)) return; // We only need to compare algorithms if CoinGrinder has a solution + assert(result_cg); + if (!result_cg->GetAlgoCompleted()) return; // Bail out if CoinGrinder solution is not optimal + + auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT); + if (result_srd && result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0) { // exclude any srd solutions that don’t have change, err on excluding + assert(result_srd->GetWeight() >= result_cg->GetWeight()); + } + + auto result_knapsack = KnapsackSolver(group_pos, target, coin_params.m_min_change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT); + if (result_knapsack && result_knapsack->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0) { // exclude any knapsack solutions that don’t have change, err on excluding + assert(result_knapsack->GetWeight() >= result_cg->GetWeight()); + } +} + FUZZ_TARGET(coinselection) { FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()}; -- cgit v1.2.3 From d68bc74fb2e3ae4ae775ab544fe5b4ab46025abb Mon Sep 17 00:00:00 2001 From: Murch Date: Fri, 12 Jan 2024 11:09:52 -0500 Subject: fuzz: Test optimality of CoinGrinder Co-authored-by: Pieter Wuille --- src/wallet/test/fuzz/coinselection.cpp | 82 ++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) (limited to 'src') diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp index c54179d3c9..3ffeecdf34 100644 --- a/src/wallet/test/fuzz/coinselection.cpp +++ b/src/wallet/test/fuzz/coinselection.cpp @@ -11,6 +11,7 @@ #include #include +#include #include namespace wallet { @@ -134,6 +135,87 @@ FUZZ_TARGET(coin_grinder) } } +FUZZ_TARGET(coin_grinder_is_optimal) +{ + FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()}; + + FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)}; + CoinSelectionParams coin_params{fast_random_context}; + coin_params.m_subtract_fee_outputs = false; + // Set effective feerate up to MAX_MONEY sats per 1'000'000 vB (2'100'000'000 sat/vB = 21'000 BTC/kvB). + coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, MAX_MONEY), 1'000'000}; + coin_params.m_min_change_target = ConsumeMoney(fuzzed_data_provider); + + // Create some coins + CAmount max_spendable{0}; + int next_locktime{0}; + static constexpr unsigned max_output_groups{16}; + std::vector group_pos; + LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), max_output_groups) + { + // With maximum m_effective_feerate and n_input_bytes = 1'000'000, input_fee <= MAX_MONEY. + const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange(1, 1'000'000)}; + // Only make UTXOs with positive effective value + const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes); + // Ensure that each UTXO has at least an effective value of 1 sat + const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_MONEY - max_spendable - max_output_groups + group_pos.size())}; + const CAmount amount{eff_value + input_fee}; + std::vector temp_utxo_pool; + + AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate); + max_spendable += eff_value; + + auto output_group = OutputGroup(coin_params); + output_group.Insert(std::make_shared(temp_utxo_pool.at(0)), /*ancestors=*/0, /*descendants=*/0); + group_pos.push_back(output_group); + } + size_t num_groups = group_pos.size(); + assert(num_groups <= max_output_groups); + + // Only choose targets below max_spendable + const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange(1, std::max(CAmount{1}, max_spendable - coin_params.m_min_change_target))}; + + // Brute force optimal solution + CAmount best_amount{MAX_MONEY}; + int best_weight{std::numeric_limits::max()}; + for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) { + CAmount subset_amount{0}; + int subset_weight{0}; + for (unsigned i = 0; i < num_groups; ++i) { + if ((pattern >> i) & 1) { + subset_amount += group_pos[i].GetSelectionAmount(); + subset_weight += group_pos[i].m_weight; + } + } + if ((subset_amount >= target + coin_params.m_min_change_target) && (subset_weight < best_weight || (subset_weight == best_weight && subset_amount < best_amount))) { + best_weight = subset_weight; + best_amount = subset_amount; + } + } + + if (best_weight < std::numeric_limits::max()) { + // Sufficient funds and acceptable weight: CoinGrinder should find at least one solution + int high_max_weight = fuzzed_data_provider.ConsumeIntegralInRange(best_weight, std::numeric_limits::max()); + + auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, high_max_weight); + assert(result_cg); + assert(result_cg->GetWeight() <= high_max_weight); + assert(result_cg->GetSelectedEffectiveValue() >= target + coin_params.m_min_change_target); + assert(best_weight < result_cg->GetWeight() || (best_weight == result_cg->GetWeight() && best_amount <= result_cg->GetSelectedEffectiveValue())); + if (result_cg->GetAlgoCompleted()) { + // If CoinGrinder exhausted the search space, it must return the optimal solution + assert(best_weight == result_cg->GetWeight()); + assert(best_amount == result_cg->GetSelectedEffectiveValue()); + } + } + + // CoinGrinder cannot ever find a better solution than the brute-forced best, or there is none in the first place + int low_max_weight = fuzzed_data_provider.ConsumeIntegralInRange(0, best_weight - 1); + auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, low_max_weight); + // Max_weight should have been exceeded, or there were insufficient funds + assert(!result_cg); +} + FUZZ_TARGET(coinselection) { FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()}; -- cgit v1.2.3 From 5f84f3cc043c5fb15072f5072fee752eaa01a2ec Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 15:26:21 -0500 Subject: opt: Skip branches with worse weight Once we exceed the weight of the current best selection, we can always shift as adding more inputs can never yield a better solution. --- src/wallet/coinselection.cpp | 3 +++ src/wallet/test/coinselector_tests.cpp | 2 +- 2 files changed, 4 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index abd710d56d..cf666e7459 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -413,6 +413,9 @@ util::Result CoinGrinder(std::vector& utxo_pool, c // max_weight exceeded: SHIFT max_tx_weight_exceeded = true; should_shift = true; + } else if (curr_weight > best_selection_weight) { + // Worse weight than best solution. More UTXOs only increase weight: SHIFT + should_shift = true; } else if (curr_amount >= total_target) { // Success, adding more weight cannot be better: SHIFT should_shift = true; diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index e23292d21f..fe9922e31c 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1231,7 +1231,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(4 * COIN, 3, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 2041; + size_t expected_attempts = 525; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } -- cgit v1.2.3 From 407b1e3432b77511900b77be84d5d7450352f462 Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 15:17:36 -0500 Subject: opt: Track remaining effective_value in lookahead Introduces a dedicated data structure to track the total effective_value available in the remaining UTXOs at each index of the UTXO pool. In contrast to the approach in BnB, this allows us to immediately jump to a lower index instead of visiting every UTXO to add back their eff_value to the lookahead. --- src/wallet/coinselection.cpp | 19 +++++++++++++------ src/wallet/test/coinselector_tests.cpp | 4 ++-- 2 files changed, 15 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index cf666e7459..fb63e92bb8 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -313,13 +313,17 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool util::Result CoinGrinder(std::vector& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_weight) { std::sort(utxo_pool.begin(), utxo_pool.end(), descending); + // The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount) + std::vector lookahead(utxo_pool.size()); - // Check that there are sufficient funds + // Calculate lookahead values, and check that there are sufficient funds CAmount total_available = 0; - for (const OutputGroup& utxo : utxo_pool) { - // Assert UTXOs with non-positive effective value have been filtered - Assume(utxo.GetSelectionAmount() > 0); - total_available += utxo.GetSelectionAmount(); + for (size_t i = 0; i < utxo_pool.size(); ++i) { + size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order + lookahead[index] = total_available; + // UTXOs with non-positive effective value must have been filtered + Assume(utxo_pool[index].GetSelectionAmount() > 0); + total_available += utxo_pool[index].GetSelectionAmount(); } const CAmount total_target = selection_target + change_target; @@ -409,7 +413,10 @@ util::Result CoinGrinder(std::vector& utxo_pool, c ++curr_try; // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further - if (curr_weight > max_weight) { + if (curr_amount + lookahead[curr_selection.back()] < total_target) { + // Insufficient funds with lookahead: CUT + should_cut = true; + } else if (curr_weight > max_weight) { // max_weight exceeded: SHIFT max_tx_weight_exceeded = true; should_shift = true; diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index fe9922e31c..c335a32ec6 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1231,7 +1231,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(4 * COIN, 3, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 525; + size_t expected_attempts = 281; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1271,7 +1271,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. // If this takes more attempts, the implementation has regressed - size_t expected_attempts = 82'815; + size_t expected_attempts = 82'407; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } -- cgit v1.2.3 From 451be19dc10381122f705bbb2127b083f1d598c6 Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 15:08:57 -0500 Subject: opt: Skip evaluation of equivalent input sets When two successive UTXOs match in effective value and weight, we can skip the second if the prior is not selected: adding it would create an equivalent input set to a previously evaluated. E.g. if we have three UTXOs with effective values {5, 3, 3} of the same weight each, we want to evaluate {5, _, _}, {5, 3, _}, {5, 3, 3}, {_, 3, _}, {_, 3, 3}, but skip {5, _, 3}, and {_, _, 3}, because the first 3 is not selected, and we therefore do not need to evaluate the second 3 at the same position in the input set. If we reach the end of the branch, we must SHIFT the previously selected UTXO group instead. --- src/wallet/coinselection.cpp | 21 +++++++++++++++++++-- src/wallet/test/coinselector_tests.cpp | 6 +++--- 2 files changed, 22 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index fb63e92bb8..aca81353ef 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -401,8 +401,9 @@ util::Result CoinGrinder(std::vector& utxo_pool, c }; SelectionResult result(selection_target, SelectionAlgorithm::CG); + bool is_done = false; size_t curr_try = 0; - while (true) { + while (!is_done) { bool should_shift{false}, should_cut{false}; // Select `next_utxo` OutputGroup& utxo = utxo_pool[next_utxo]; @@ -454,16 +455,32 @@ util::Result CoinGrinder(std::vector& utxo_pool, c should_shift = true; } - if (should_shift) { + while (should_shift) { // Set `next_utxo` to one after last selected, then deselect last selected UTXO if (curr_selection.empty()) { // Exhausted search space before running into attempt limit + is_done = true; result.SetAlgoCompleted(true); break; } next_utxo = curr_selection.back() + 1; deselect_last(); should_shift = false; + + // After SHIFTing to an omission branch, the `next_utxo` might have the same value and same weight as the + // UTXO we just omitted (i.e. it is a "clone"). If so, selecting `next_utxo` would produce an equivalent + // selection as one we previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a + // differing amount or weight. + while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount() + && utxo_pool[next_utxo - 1].m_weight == utxo_pool[next_utxo].m_weight) { + if (next_utxo >= utxo_pool.size() - 1) { + // Reached end of UTXO pool skipping clones: SHIFT instead + should_shift = true; + break; + } + // Skip clone: previous UTXO is equivalent and unselected + ++next_utxo; + } } } diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index c335a32ec6..e1060cdfcc 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1180,7 +1180,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) }); BOOST_CHECK(res); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 100'000; + size_t expected_attempts = 184; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1202,7 +1202,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(1 * COIN, 2, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 4; + size_t expected_attempts = 3; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1271,7 +1271,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. // If this takes more attempts, the implementation has regressed - size_t expected_attempts = 82'407; + size_t expected_attempts = 43; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } -- cgit v1.2.3 From 9124c73742287b06dfe6e8a94be56ace25f07b2c Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 14:47:54 -0500 Subject: opt: Tiebreak UTXOs by weight for CoinGrinder --- src/wallet/coinselection.cpp | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index aca81353ef..9cad76574a 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -37,6 +37,18 @@ struct { } } descending; +// Sort by descending (effective) value prefer lower weight on tie +struct { + bool operator()(const OutputGroup& a, const OutputGroup& b) const + { + if (a.GetSelectionAmount() == b.GetSelectionAmount()) { + // Sort lower weight to front on tied effective_value + return a.m_weight < b.m_weight; + } + return a.GetSelectionAmount() > b.GetSelectionAmount(); + } +} descending_effval_weight; + /* * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input * set that can pay for the spending target and does not exceed the spending target by more than the @@ -303,7 +315,7 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool * set in the node. * * @param std::vector& utxo_pool The UTXOs that we are choosing from. These UTXOs will be sorted in - * descending order by effective value, with lower waste preferred as a tie-breaker. (We can think of an output + * descending order by effective value, with lower weight preferred as a tie-breaker. (We can think of an output * group with multiple as a heavier UTXO with the combined amount here.) * @param const CAmount& selection_target This is the minimum amount that we need for the transaction without considering change. * @param const CAmount& change_target The minimum budget for creating a change output, by which we increase the selection_target. @@ -312,7 +324,7 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool */ util::Result CoinGrinder(std::vector& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_weight) { - std::sort(utxo_pool.begin(), utxo_pool.end(), descending); + std::sort(utxo_pool.begin(), utxo_pool.end(), descending_effval_weight); // The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount) std::vector lookahead(utxo_pool.size()); -- cgit v1.2.3 From 5248e2a60d243b3d5c77ecd9e4c335daca399a48 Mon Sep 17 00:00:00 2001 From: Murch Date: Thu, 1 Feb 2024 16:25:45 -0500 Subject: opt: Skip heavier UTXOs with same effective value When two successive UTXOs differ in weight but match in effective value, we can skip the second if the first is not selected, because all input sets we can generate by swapping out a lighter UTXOs with a heavier UTXO of matching effective value would be strictly worse. --- src/wallet/coinselection.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 9cad76574a..1542871daf 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -479,12 +479,12 @@ util::Result CoinGrinder(std::vector& utxo_pool, c deselect_last(); should_shift = false; - // After SHIFTing to an omission branch, the `next_utxo` might have the same value and same weight as the - // UTXO we just omitted (i.e. it is a "clone"). If so, selecting `next_utxo` would produce an equivalent - // selection as one we previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a - // differing amount or weight. - while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount() - && utxo_pool[next_utxo - 1].m_weight == utxo_pool[next_utxo].m_weight) { + // After SHIFTing to an omission branch, the `next_utxo` might have the same effective value as the UTXO we + // just omitted. Since lower weight is our tiebreaker on UTXOs with equal effective value for sorting, if it + // ties on the effective value, it _must_ have the same weight (i.e. be a "clone" of the prior UTXO) or a + // higher weight. If so, selecting `next_utxo` would produce an equivalent or worse selection as one we + // previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a differing amount. + while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) { if (next_utxo >= utxo_pool.size() - 1) { // Reached end of UTXO pool skipping clones: SHIFT instead should_shift = true; -- cgit v1.2.3 From 1edd2baa37a69ff69c2eaeceaad1028f1968cbab Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 14:42:08 -0500 Subject: opt: Cut if last addition was minimal weight MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit In situations where we have UTXO groups of various weight, we can CUT rather than SHIFT when we exceeded the max_weight or the best selection’s weight while the last step was equal to the minimum weight in the lookahead. --- src/wallet/coinselection.cpp | 27 +++++++++++++++++++++------ src/wallet/test/coinselector_tests.cpp | 4 ++-- 2 files changed, 23 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 1542871daf..17aea43420 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -327,15 +327,20 @@ util::Result CoinGrinder(std::vector& utxo_pool, c std::sort(utxo_pool.begin(), utxo_pool.end(), descending_effval_weight); // The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount) std::vector lookahead(utxo_pool.size()); + // The minimum UTXO weight among the remaining UTXOs after this UTXO index, e.g. min_tail_weight[5] = min(UTXO[6+].weight) + std::vector min_tail_weight(utxo_pool.size()); - // Calculate lookahead values, and check that there are sufficient funds + // Calculate lookahead values, min_tail_weights, and check that there are sufficient funds CAmount total_available = 0; + int min_group_weight = std::numeric_limits::max(); for (size_t i = 0; i < utxo_pool.size(); ++i) { size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order lookahead[index] = total_available; + min_tail_weight[index] = min_group_weight; // UTXOs with non-positive effective value must have been filtered Assume(utxo_pool[index].GetSelectionAmount() > 0); total_available += utxo_pool[index].GetSelectionAmount(); + min_group_weight = std::min(min_group_weight, utxo_pool[index].m_weight); } const CAmount total_target = selection_target + change_target; @@ -426,16 +431,26 @@ util::Result CoinGrinder(std::vector& utxo_pool, c ++curr_try; // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further - if (curr_amount + lookahead[curr_selection.back()] < total_target) { + auto curr_tail = curr_selection.back(); + if (curr_amount + lookahead[curr_tail] < total_target) { // Insufficient funds with lookahead: CUT should_cut = true; } else if (curr_weight > max_weight) { - // max_weight exceeded: SHIFT + // max_weight exceeded: CUT if last selected group had minimal weight, else SHIFT max_tx_weight_exceeded = true; - should_shift = true; + if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) { + should_cut = true; + } else { + should_shift = true; + } } else if (curr_weight > best_selection_weight) { - // Worse weight than best solution. More UTXOs only increase weight: SHIFT - should_shift = true; + // Worse weight than best solution. More UTXOs only increase weight: + // CUT if last selected group had minimal weight, else SHIFT + if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) { + should_cut = true; + } else { + should_shift = true; + } } else if (curr_amount >= total_target) { // Success, adding more weight cannot be better: SHIFT should_shift = true; diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index e1060cdfcc..23df7e186c 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1231,7 +1231,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(4 * COIN, 3, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 281; + size_t expected_attempts = 218; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1271,7 +1271,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. // If this takes more attempts, the implementation has regressed - size_t expected_attempts = 43; + size_t expected_attempts = 42; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } -- cgit v1.2.3 From b7672c7cdd87acb105639f475744094b53cc9891 Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 14:30:40 -0500 Subject: opt: Skip checking max_weight separately Initialize `best_selection_weight` as `max_weight` allows us to skip the separate `max_weight` check on every loop. --- src/wallet/coinselection.cpp | 12 +++--------- 1 file changed, 3 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 17aea43420..37cfb5f1ef 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -359,7 +359,7 @@ util::Result CoinGrinder(std::vector& utxo_pool, c // The weight of the currently selected input set, and the weight of the best selection int curr_weight = 0; - int best_selection_weight = std::numeric_limits::max(); + int best_selection_weight = max_weight; // Tie is fine, because we prefer lower selection amount // Whether the input sets generated during this search have exceeded the maximum transaction weight at any point bool max_tx_weight_exceeded = false; @@ -435,15 +435,9 @@ util::Result CoinGrinder(std::vector& utxo_pool, c if (curr_amount + lookahead[curr_tail] < total_target) { // Insufficient funds with lookahead: CUT should_cut = true; - } else if (curr_weight > max_weight) { - // max_weight exceeded: CUT if last selected group had minimal weight, else SHIFT - max_tx_weight_exceeded = true; - if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) { - should_cut = true; - } else { - should_shift = true; - } } else if (curr_weight > best_selection_weight) { + // best_selection_weight is initialized to max_weight + if (curr_weight > max_weight) max_tx_weight_exceeded = true; // Worse weight than best solution. More UTXOs only increase weight: // CUT if last selected group had minimal weight, else SHIFT if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) { -- cgit v1.2.3 From 13161ecf032b7a850686e5942c12222c8f3d0d52 Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 8 Jan 2024 13:04:29 -0500 Subject: opt: Skip over barren combinations of tiny UTXOs Given a lot of small amount UTXOs it is possible that the lookahead indicates sufficient funds, but any combination of them would push us beyond the current best_weight. We can estimate a lower bound for the minimal necessary weight to reach target from the maximal amount and minimal weight in the tail of the UTXO pool: if adding a number of hypothetical UTXOs of this maximum amount and minimum weight would not be able to beat `best_weight`, we can SHIFT to the omission branch, and CUT if the last selected UTXO is not heavier than the minimum weight of the remainder. --- src/wallet/coinselection.cpp | 7 +++++++ src/wallet/test/coinselector_tests.cpp | 15 +++++++-------- 2 files changed, 14 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 37cfb5f1ef..42615b5d42 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -454,6 +454,13 @@ util::Result CoinGrinder(std::vector& utxo_pool, c best_selection_weight = curr_weight; best_selection_amount = curr_amount; } + } else if (!best_selection.empty() && curr_weight + int64_t{min_tail_weight[curr_tail]} * ((total_target - curr_amount + utxo_pool[curr_tail].GetSelectionAmount() - 1) / utxo_pool[curr_tail].GetSelectionAmount()) > best_selection_weight) { + // Compare minimal tail weight and last selected amount with the amount missing to gauge whether a better weight is still possible. + if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) { + should_cut = true; + } else { + should_shift = true; + } } if (curr_try >= TOTAL_TRIES) { diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 23df7e186c..9a349f0992 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -1111,7 +1111,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO // 5) Test finding a solution in a UTXO pool with mixed weights // 6) Test that the lightest solution among many clones is found - // 7) Lots of tiny UTXOs of different amounts quickly exhausts the search attempts + // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead FastRandomContext rand; CoinSelectionParams dummy_params{ // Only used to provide the 'avoid_partial' flag. @@ -1180,7 +1180,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) }); BOOST_CHECK(res); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 184; + size_t expected_attempts = 37; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1231,7 +1231,7 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(4 * COIN, 3, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 218; + size_t expected_attempts = 92; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } @@ -1270,14 +1270,13 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) add_coin(1 * COIN, 0, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - // If this takes more attempts, the implementation has regressed - size_t expected_attempts = 42; + size_t expected_attempts = 38; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } { // ################################################################################################################# - // 7) Lots of tiny UTXOs of different amounts quickly exhausts the search attempts + // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead // ################################################################################################################# CAmount target = 1.9L * COIN; int max_weight = 40000; // WU @@ -1293,11 +1292,11 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests) return available_coins; }); SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG); - add_coin(1.8 * COIN, 1, expected_result); + add_coin(1 * COIN, 1, expected_result); add_coin(1 * COIN, 2, expected_result); BOOST_CHECK(EquivalentResult(expected_result, *res)); // Demonstrate how following improvements reduce iteration count and catch any regressions in the future. - size_t expected_attempts = 100'000; + size_t expected_attempts = 7; BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated())); } } -- cgit v1.2.3