diff options
author | Andrew Chow <github@achow101.com> | 2023-04-20 16:25:38 -0400 |
---|---|---|
committer | Andrew Chow <github@achow101.com> | 2023-04-20 16:33:39 -0400 |
commit | 395b9328071f7764373605e12c47e08b87ffb4df (patch) | |
tree | 6fd35f13c6e342cbd55cd4c40284b807e0b8d580 /src/wallet/spend.cpp | |
parent | 5aa0c82ccd6ceb4a141686fc8658f679de75a787 (diff) | |
parent | 25ab14712b9d80276016f9fc9bff7fb9c1d09635 (diff) | |
download | bitcoin-395b9328071f7764373605e12c47e08b87ffb4df.tar.xz |
Merge bitcoin/bitcoin#26720: wallet: coin selection, don't return results that exceed the max allowed weight
25ab14712b9d80276016f9fc9bff7fb9c1d09635 refactor: coinselector_tests, unify wallet creation code (furszy)
ba9431c505e1590db6103b9632134985cd4704dc test: coverage for bnb max weight (furszy)
5a2bc45ee0b123e461c5191322ed0b43524c3d82 wallet: clean post coin selection max weight filter (furszy)
2d112584e384de10021c64e4700455d71326824e coin selection: BnB, don't return selection if exceeds max allowed tx weight (furszy)
d3a1c098e4b5df2ebbae20c6e390c3d783950e93 test: coin selection, add coverage for SRD (furszy)
9d9689e5a657956db8a30829c994600ec7d3098b coin selection: heap-ify SRD, don't return selection if exceeds max tx weight (furszy)
6107ec2229c5f5b4e944a6b10d38010c850094ac coin selection: knapsack, select closest UTXO above target if result exceeds max tx size (furszy)
1284223691127e76135a46d251c52416104f0ff1 wallet: refactor coin selection algos to return util::Result (furszy)
Pull request description:
Coming from the following comment https://github.com/bitcoin/bitcoin/pull/25729#discussion_r1029324367.
The reason why we are adding hundreds of UTXO from different sources when the target
amount is covered only by one of them is because only SRD returns a usable result.
Context:
In the test, we create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then
perform Coin Selection to fund 49.5 BTC.
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 following reason:
Knapsack returns a result that exceeds the max allowed transaction size, when
it should return the closest utxo above the target, so we fallback to SRD who
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.
ACKs for top commit:
S3RK:
ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
achow101:
ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
Xekyo:
reACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
theStack:
Code-review ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
Tree-SHA512: 2425de4cc479b4db999b3b2e02eb522a2130a06379cca0418672a51c4076971a1d427191173820db76a0f85a8edfff100114e1c38fb3b5dc51598d07cabe1a60
Diffstat (limited to 'src/wallet/spend.cpp')
-rw-r--r-- | src/wallet/spend.cpp | 45 |
1 files changed, 24 insertions, 21 deletions
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 57f3785a3a..c3303419d4 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -559,42 +559,45 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, { // Vector of results. We will choose the best one based on waste. std::vector<SelectionResult> results; + std::vector<util::Result<SelectionResult>> errors; + auto append_error = [&] (const util::Result<SelectionResult>& 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); + } + }; + + // 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); + + // 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); - 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); if (results.empty()) { - // No solution found - return util::Error(); - } - - std::vector<SelectionResult> 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<int>(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")}; + // 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(); } // 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<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const PreSelectedInputs& pre_set_inputs, |