From 1284223691127e76135a46d251c52416104f0ff1 Mon Sep 17 00:00:00 2001 From: furszy Date: Wed, 4 Jan 2023 10:22:53 -0300 Subject: wallet: refactor coin selection algos to return util::Result so the selection processes can retrieve different errors and not uninformative std::nullopt --- src/wallet/spend.cpp | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-) (limited to 'src/wallet/spend.cpp') diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index a8ecce119a..a55e4c45a8 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -554,25 +554,34 @@ util::Result ChooseSelectionResult(const CAmount& nTargetValue, { // Vector of results. We will choose the best one based on waste. std::vector results; + std::vector> errors; + auto append_error = [&] (const util::Result& result) { + // If any specific error message appears here, then something different from a simple "no selection found" happened. + // Let's save it, so it can be retrieved to the user if no other selection algorithm succeeded. + if (HasErrorMsg(result)) { + errors.emplace_back(result); + } + }; if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) { results.push_back(*bnb_result); - } + } else append_error(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. if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) { knapsack_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); results.push_back(*knapsack_result); - } + } else append_error(knapsack_result); if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.rng_fast)}) { srd_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); results.push_back(*srd_result); - } + } else append_error(srd_result); if (results.empty()) { - // No solution found - return util::Error(); + // No solution found, retrieve the first explicit error (if any). + // future: add 'severity level' to errors so the worst one can be retrieved instead of the first one. + return errors.empty() ? util::Error() : errors.front(); } std::vector eligible_results; -- cgit v1.2.3 From 6107ec2229c5f5b4e944a6b10d38010c850094ac Mon Sep 17 00:00:00 2001 From: furszy Date: Sun, 18 Dec 2022 10:28:59 -0300 Subject: coin selection: knapsack, select closest UTXO above target if result exceeds max tx size The simplest scenario where this is useful is on the 'check_max_weight' unit test already: We create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then perform Coin Selection. As the selection of the 1515 small UTXOs exceeds the max allowed tx size, the expectation here is to receive a selection result that only contain the big UTXO (which is not happening for the reasons stated below). As knapsack returns a result that exceeds the max allowed transaction size, we fallback to SRD, which selects coins randomly up until the target is met. So we end up with a selection result with lot more coins than what is needed. --- src/wallet/spend.cpp | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'src/wallet/spend.cpp') diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index a55e4c45a8..b28da6ec42 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -563,12 +563,18 @@ util::Result ChooseSelectionResult(const CAmount& nTargetValue, } }; + // Maximum allowed weight + int max_inputs_weight = MAX_STANDARD_TX_WEIGHT - (coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR); + if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) { results.push_back(*bnb_result); } else append_error(bnb_result); + // As Knapsack and SRD can create change, also deduce change weight. + max_inputs_weight -= (coin_selection_params.change_output_size * WITNESS_SCALE_FACTOR); + // 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. - if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) { + if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast, max_inputs_weight)}) { knapsack_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); results.push_back(*knapsack_result); } else append_error(knapsack_result); -- cgit v1.2.3 From 9d9689e5a657956db8a30829c994600ec7d3098b Mon Sep 17 00:00:00 2001 From: furszy Date: Sun, 18 Dec 2022 10:39:19 -0300 Subject: coin selection: heap-ify SRD, don't return selection if exceeds max tx weight Uses a min-effective-value heap, so we can remove the least valuable input/s while the selected weight exceeds the maximum allowed weight. Co-authored-by: Murch --- src/wallet/spend.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/wallet/spend.cpp') diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index b28da6ec42..f81e91bcba 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -579,7 +579,7 @@ util::Result ChooseSelectionResult(const CAmount& nTargetValue, results.push_back(*knapsack_result); } else append_error(knapsack_result); - if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.rng_fast)}) { + if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.rng_fast, max_inputs_weight)}) { srd_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); results.push_back(*srd_result); } else append_error(srd_result); -- cgit v1.2.3 From 2d112584e384de10021c64e4700455d71326824e Mon Sep 17 00:00:00 2001 From: furszy Date: Sun, 18 Dec 2022 20:16:19 -0300 Subject: coin selection: BnB, don't return selection if exceeds max allowed tx weight --- src/wallet/spend.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/wallet/spend.cpp') diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index f81e91bcba..57fb7202bb 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -566,7 +566,7 @@ util::Result ChooseSelectionResult(const CAmount& nTargetValue, // Maximum allowed weight int max_inputs_weight = MAX_STANDARD_TX_WEIGHT - (coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR); - if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) { + if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change, max_inputs_weight)}) { results.push_back(*bnb_result); } else append_error(bnb_result); -- cgit v1.2.3 From 5a2bc45ee0b123e461c5191322ed0b43524c3d82 Mon Sep 17 00:00:00 2001 From: furszy Date: Sun, 18 Dec 2022 21:10:07 -0300 Subject: wallet: clean post coin selection max weight filter Now the coin selection algorithms contemplate the maximum allowed weight internally and return std::nullopt if their result exceeds it. --- src/wallet/spend.cpp | 14 +------------- 1 file changed, 1 insertion(+), 13 deletions(-) (limited to 'src/wallet/spend.cpp') diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 57fb7202bb..140b7720c7 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -590,21 +590,9 @@ util::Result ChooseSelectionResult(const CAmount& nTargetValue, return errors.empty() ? util::Error() : errors.front(); } - std::vector eligible_results; - std::copy_if(results.begin(), results.end(), std::back_inserter(eligible_results), [coin_selection_params](const SelectionResult& result) { - const auto initWeight{coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR}; - return initWeight + result.GetWeight() <= static_cast(MAX_STANDARD_TX_WEIGHT); - }); - - if (eligible_results.empty()) { - return util::Error{_("The inputs size exceeds the maximum weight. " - "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")}; - } - // Choose the result with the least waste // If the waste is the same, choose the one which spends more inputs. - auto& best_result = *std::min_element(eligible_results.begin(), eligible_results.end()); - return best_result; + return *std::min_element(results.begin(), results.end()); } util::Result SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const PreSelectedInputs& pre_set_inputs, -- cgit v1.2.3