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/coinselection.cpp | 12 ++++++++++-- src/wallet/coinselection.h | 3 ++- src/wallet/spend.cpp | 2 +- src/wallet/test/coinselector_tests.cpp | 8 +++++++- src/wallet/test/fuzz/coinselection.cpp | 2 +- 5 files changed, 21 insertions(+), 6 deletions(-) (limited to 'src/wallet') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index f97df22b0e..aa977de6c3 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -71,11 +71,13 @@ struct { static const size_t TOTAL_TRIES = 100000; -util::Result SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change) +util::Result SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, + int max_weight) { SelectionResult result(selection_target, SelectionAlgorithm::BNB); CAmount curr_value = 0; std::vector curr_selection; // selected utxo indexes + int curr_selection_weight = 0; // sum of selected utxo weight // Calculate curr_available_value CAmount curr_available_value = 0; @@ -97,6 +99,7 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool CAmount best_waste = MAX_MONEY; bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee; + bool max_tx_weight_exceeded = false; // Depth First search loop for choosing the UTXOs for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) { @@ -106,6 +109,9 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch (curr_waste > best_waste && is_feerate_high)) { // Don't select things which we know will be more wasteful if the waste is increasing backtrack = true; + } else if (curr_selection_weight > max_weight) { // Exceeding weight for standard tx, cannot find more solutions by adding more inputs + max_tx_weight_exceeded = true; // at least one selection attempt exceeded the max weight + backtrack = true; } else if (curr_value >= selection_target) { // Selected value is within range curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee. @@ -135,6 +141,7 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool OutputGroup& utxo = utxo_pool.at(utxo_pool_index); curr_value -= utxo.GetSelectionAmount(); curr_waste -= utxo.fee - utxo.long_term_fee; + curr_selection_weight -= utxo.m_weight; curr_selection.pop_back(); } else { // Moving forwards, continuing down this branch OutputGroup& utxo = utxo_pool.at(utxo_pool_index); @@ -154,13 +161,14 @@ util::Result SelectCoinsBnB(std::vector& utxo_pool curr_selection.push_back(utxo_pool_index); curr_value += utxo.GetSelectionAmount(); curr_waste += utxo.fee - utxo.long_term_fee; + curr_selection_weight += utxo.m_weight; } } } // Check for solution if (best_selection.empty()) { - return util::Error(); + return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error(); } // Set output set diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 06506aec0d..4862efada8 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -409,7 +409,8 @@ public: int GetWeight() const { return m_weight; } }; -util::Result SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change); +util::Result SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, + 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 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); diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 01ce6d76f4..f511a449ed 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -87,7 +87,7 @@ static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmoun available_coins.Add(OutputType::BECH32, {COutPoint(wtx.GetHash(), nInput), txout, nAge, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate}); } -// Helper +// Helpers std::optional KnapsackSolver(std::vector& groups, const CAmount& nTargetValue, CAmount change_target, FastRandomContext& rng) { @@ -95,6 +95,12 @@ std::optional KnapsackSolver(std::vector& groups, return res ? std::optional(*res) : std::nullopt; } +std::optional SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change) +{ + auto res{SelectCoinsBnB(utxo_pool, selection_target, cost_of_change, MAX_STANDARD_TX_WEIGHT)}; + return res ? std::optional(*res) : std::nullopt; +} + /** Check if SelectionResult a is equivalent to SelectionResult b. * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */ static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b) diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp index a057eda393..9be8efab62 100644 --- a/src/wallet/test/fuzz/coinselection.cpp +++ b/src/wallet/test/fuzz/coinselection.cpp @@ -88,7 +88,7 @@ FUZZ_TARGET(coinselection) GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all); // Run coinselection algorithms - const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change); + const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change, MAX_STANDARD_TX_WEIGHT); auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context, MAX_STANDARD_TX_WEIGHT); if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0); -- cgit v1.2.3