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;