diff options
Diffstat (limited to 'src/wallet/test/fuzz/coinselection.cpp')
-rw-r--r-- | src/wallet/test/fuzz/coinselection.cpp | 148 |
1 files changed, 145 insertions, 3 deletions
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp index 87d419493b..644a8dd7ad 100644 --- a/src/wallet/test/fuzz/coinselection.cpp +++ b/src/wallet/test/fuzz/coinselection.cpp @@ -11,6 +11,7 @@ #include <test/util/setup_common.h> #include <wallet/coinselection.h> +#include <numeric> #include <vector> namespace wallet { @@ -77,6 +78,144 @@ static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmoun // 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(); } +FUZZ_TARGET(coin_grinder) +{ + FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()}; + std::vector<COutput> utxo_pool; + + const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(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<int>(10, 1000); + coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(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<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; + CAmount eff_value = amount - coin_params.m_effective_feerate.GetFee(n_input_bytes); + max_spendable += eff_value; + } + + std::vector<OutputGroup> 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(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<OutputGroup> 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<int>(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<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)}; + const CAmount amount{eff_value + input_fee}; + std::vector<COutput> 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<COutput>(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<CAmount>(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<int>::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<int>::max()) { + // Sufficient funds and acceptable weight: CoinGrinder should find at least one solution + int high_max_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::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<int>(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()}; @@ -131,7 +270,7 @@ FUZZ_TARGET(coinselection) 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(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee); + result_srd->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee); (void)result_srd->GetShuffledInputVector(); (void)result_srd->GetInputSet(); } @@ -140,7 +279,7 @@ FUZZ_TARGET(coinselection) auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT); 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); + result_knapsack->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee); (void)result_knapsack->GetShuffledInputVector(); (void)result_knapsack->GetInputSet(); } @@ -152,7 +291,10 @@ FUZZ_TARGET(coinselection) } std::vector<COutput> utxos; - std::vector<util::Result<SelectionResult>> results{result_srd, result_knapsack, result_bnb}; + std::vector<util::Result<SelectionResult>> results; + results.emplace_back(std::move(result_srd)); + results.emplace_back(std::move(result_knapsack)); + results.emplace_back(std::move(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; |