diff options
author | Andrew Chow <github@achow101.com> | 2023-08-24 16:04:45 -0400 |
---|---|---|
committer | Andrew Chow <github@achow101.com> | 2023-08-24 16:11:20 -0400 |
commit | 74d66359dabd21f9e6ffc48c47f3588000171712 (patch) | |
tree | bb43f65fb05fea66567a935d6fe7449acae43541 /src | |
parent | 1fa6411dde3a6c4c4a89d7aebfba03f114f12bb1 (diff) | |
parent | bf26f978ffbe7e2fc681825de631600e24e5c93e (diff) | |
download | bitcoin-74d66359dabd21f9e6ffc48c47f3588000171712.tar.xz |
Merge bitcoin/bitcoin#27585: fuzz: improve `coinselection`
bf26f978ffbe7e2fc681825de631600e24e5c93e fuzz: coinselection, fix `m_cost_of_change` (brunoerg)
6d9b26d56ab5295dfcfe0f80a3069046a263fb2f fuzz: coinselection, BnB should never produce change (brunoerg)
b2eb55840778515d61465acc8106b27e16af1c88 fuzz: coinselection, compare `GetSelectedValue` with target (brunoerg)
0df0438c60e27df1aced6d31a192d6f334cef2d1 fuzz: coinselection, improve `ComputeAndSetWaste` (brunoerg)
1e351e5db1ced6a32681ceea8a111148bd83e323 fuzz: coinselection, add coverage for `Merge` (brunoerg)
f0244a8614ee35caef03bc326519823972ec61b4 fuzz: coinselection, add coverage for `GetShuffledInputVector`/`GetInputSet` (brunoerg)
808618b8a25b1d9cfc4e4f1a5b4c6fff02972396 fuzz: coinselection, add coverage for `AddInputs` (brunoerg)
90c4e6a241eee605809ab1b4331e620b92f05933 fuzz: coinselection, add coverage for `EligibleForSpending` (brunoerg)
2a031cb2c218e288a9784d677705a7d2bc1c2d2b fuzz: coinselection, add `CreateCoins` (brunoerg)
Pull request description:
This PR:
- Moves coin creation to its own function called `CreateCoins`.
- Add coverage for `EligibleForSpending`
- Add coverage for `AddInputs`: get result of each algorithm (srd, knapsack and bnb), call `CreateCoins` and add into them.
- Add coverage for `GetShuffledInputVector` and `GetInputSet` using the result of each algorithm (srd, knapsack and bnb).
- Add coverage for `Merge`: Call SRD with the new utxos and, if successful, try to merge with the previous SRD result.
ACKs for top commit:
murchandamus:
reACK with some minimal fuzzing bf26f978ffbe7e2fc681825de631600e24e5c93e
achow101:
ACK bf26f978ffbe7e2fc681825de631600e24e5c93e
furszy:
re-ACK bf26f97
Tree-SHA512: bdd2b0a39de37be0a9b21a7c51260b6b8abe538cc0ea74312eb658b90a121a1ae07306c09fb0e75e93b531ce9ea2402feb041b0d852902d07739257f792e64ab
Diffstat (limited to 'src')
-rw-r--r-- | src/wallet/test/fuzz/coinselection.cpp | 107 |
1 files changed, 90 insertions, 17 deletions
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp index bc935157b1..4caf96b18d 100644 --- a/src/wallet/test/fuzz/coinselection.cpp +++ b/src/wallet/test/fuzz/coinselection.cpp @@ -45,6 +45,35 @@ static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vect if (valid_outputgroup) output_groups.push_back(output_group); } +static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime) +{ + CAmount total_balance{0}; + LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000) + { + const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)}; + const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)}; + const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(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; + } + + return total_balance; +} + +static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs) +{ + SelectionResult result(total_amount, SelectionAlgorithm::MANUAL); + std::set<std::shared_ptr<COutput>> utxo_pool; + for (const auto& utxo : utxos) { + utxo_pool.insert(std::make_shared<COutput>(utxo)); + } + result.AddInputs(utxo_pool, subtract_fee_outputs); + return result; +} + // Returns true if the result contains an error and the message is not empty static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); } @@ -55,7 +84,9 @@ FUZZ_TARGET(coinselection) const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; - const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; + // Discard feerate must be at least dust relay feerate + const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)}; + const CAmount min_viable_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)}; const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)}; const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()}; @@ -64,47 +95,89 @@ FUZZ_TARGET(coinselection) coin_params.m_subtract_fee_outputs = subtract_fee_outputs; coin_params.m_long_term_feerate = long_term_fee_rate; coin_params.m_effective_feerate = effective_fee_rate; + coin_params.min_viable_change = min_viable_change; coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000); coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size); + coin_params.m_discard_feerate = discard_fee_rate; + coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000); + coin_params.m_cost_of_change = coin_params.m_change_fee + coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size); - // Create some coins - CAmount total_balance{0}; int next_locktime{0}; - LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000) - { - const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)}; - const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(100, 10000)}; - const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(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 total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)}; std::vector<OutputGroup> group_pos; GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos); std::vector<OutputGroup> group_all; GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all); + for (const OutputGroup& group : group_all) { + const CoinEligibilityFilter filter(fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>()); + (void)group.EligibleForSpending(filter); + } + // Run coinselection algorithms - const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change, MAX_STANDARD_TX_WEIGHT); + auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT); + if (result_bnb) { + assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0); + assert(result_bnb->GetSelectedValue() >= target); + (void)result_bnb->GetShuffledInputVector(); + (void)result_bnb->GetInputSet(); + } auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT); if (result_srd) { + assert(result_srd->GetSelectedValue() >= target); assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0); // Demonstrate that SRD creates change of at least CHANGE_LOWER - result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0); + result_srd->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee); + (void)result_srd->GetShuffledInputVector(); + (void)result_srd->GetInputSet(); } CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)}; auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT); - if (result_knapsack) result_knapsack->ComputeAndSetWaste(cost_of_change, cost_of_change, 0); + if (result_knapsack) { + assert(result_knapsack->GetSelectedValue() >= target); + result_knapsack->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee); + (void)result_knapsack->GetShuffledInputVector(); + (void)result_knapsack->GetInputSet(); + } // If the total balance is sufficient for the target and we are not using // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight). if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) { assert(result_knapsack); } + + std::vector<COutput> utxos; + std::vector<util::Result<SelectionResult>> results{result_srd, result_knapsack, result_bnb}; + CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)}; + if (new_total_balance > 0) { + std::set<std::shared_ptr<COutput>> new_utxo_pool; + for (const auto& utxo : utxos) { + new_utxo_pool.insert(std::make_shared<COutput>(utxo)); + } + for (auto& result : results) { + if (!result) continue; + const auto weight{result->GetWeight()}; + result->AddInputs(new_utxo_pool, subtract_fee_outputs); + assert(result->GetWeight() > weight); + } + } + + std::vector<COutput> manual_inputs; + CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)}; + if (manual_balance == 0) return; + auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)}; + for (auto& result : results) { + if (!result) continue; + const CAmount old_target{result->GetTarget()}; + const std::set<std::shared_ptr<COutput>> input_set{result->GetInputSet()}; + const int old_weight{result->GetWeight()}; + result->Merge(manual_selection); + assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size()); + assert(result->GetTarget() == old_target + manual_selection.GetTarget()); + assert(result->GetWeight() == old_weight + manual_selection.GetWeight()); + } } } // namespace wallet |