diff options
author | Murch <murch@murch.one> | 2024-01-12 11:09:52 -0500 |
---|---|---|
committer | Murch <murch@murch.one> | 2024-02-09 10:50:10 +0100 |
commit | d68bc74fb2e3ae4ae775ab544fe5b4ab46025abb (patch) | |
tree | f44a1f53a613ba77a82893bfb552af618a907811 /src/wallet/test/fuzz | |
parent | 67df6c629a2e9878b06c1903e90b67087eaa3688 (diff) | |
download | bitcoin-d68bc74fb2e3ae4ae775ab544fe5b4ab46025abb.tar.xz |
fuzz: Test optimality of CoinGrinder
Co-authored-by: Pieter Wuille <pieter@wuille.net>
Diffstat (limited to 'src/wallet/test/fuzz')
-rw-r--r-- | src/wallet/test/fuzz/coinselection.cpp | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp index c54179d3c9..3ffeecdf34 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 { @@ -134,6 +135,87 @@ FUZZ_TARGET(coin_grinder) } } +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 - max_spendable - max_output_groups + group_pos.size())}; + 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()}; |