Inside Bitcoin

251        // With maximum m_effective_feerate 10'000 s/vB and n_input_bytes = 20'000 B, input_fee <= MAX_MONEY.
252        const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 20'000)};
253        const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes);
254        // Ensure that each UTXO has at least an effective value of 1 sat
255        const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
256        const CAmount amount{eff_value + input_fee};
257        std::vector<COutput> temp_utxo_pool;
258
259        AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
260        max_spendable += eff_value;
261
262        auto output_group = OutputGroup(coin_params);
263        output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*cluster_count=*/0);
264        group_pos.push_back(output_group);
265    }
266    size_t num_groups = group_pos.size();
267    assert(num_groups <= max_output_groups);
268
269    // Only choose targets below max_spendable
270    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_cost_of_change))};
271
272    // Brute force optimal solution (lowest waste, but cannot be superset of another solution)
273    std::vector<uint32_t> solutions;
274    CAmount best_waste{std::numeric_limits<int64_t>::max()};
275    int best_weight{std::numeric_limits<int>::max()};
276    for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
277        // BnB does not permit adding more inputs to a solution, i.e. a superset of a solution cannot ever be a solution.
278        // The search pattern guarantees that any superset will only be visited after all its subsets have been traversed.
279        bool is_superset = false;
280        for (uint32_t sol : solutions) {
281            if ((pattern & sol) == sol) {
282                is_superset = true;
283                break;
284            }
285        }
286        if (is_superset) {
287            continue;
288        }
289
290        CAmount subset_amount{0};
291        CAmount subset_waste{0};
292        int subset_weight{0};
293        for (unsigned i = 0; i < num_groups; ++i) {
294            if ((pattern >> i) & 1) {
295                subset_amount += group_pos[i].GetSelectionAmount();
296                subset_waste += group_pos[i].fee - group_pos[i].long_term_fee;
297                subset_weight += group_pos[i].m_weight;
298            }
299        }
300        if (subset_amount >= target && subset_amount <= target + coin_params.m_cost_of_change) {
301            solutions.push_back(pattern);
302            // Add the excess (overselection that gets dropped to fees) to waste score
303            CAmount excess = subset_amount - target;
304            subset_waste += excess;
305            SelectionResult result_bf(target, SelectionAlgorithm::MANUAL);
306
307            for (unsigned i = 0; i < num_groups; ++i) {
308                if ((pattern >> i) & 1) {
309                    result_bf.AddInput(group_pos[i]);
310                }
311            }
312            if (subset_waste < best_waste) {
313                best_waste = subset_waste;
314                result_bf.RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
315                assert(result_bf.GetWaste() == best_waste);
316                best_weight = subset_weight;
317            }
318        }
319    }
320
321    int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
322    auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, high_max_selection_weight);
323
324    if (!solutions.size() || !result_bnb) {
325        // Either both BnB and Brute Force find a solution or neither does.
326        assert(!result_bnb == !solutions.size());
327    } else {
328        // If brute forcing found a solution with an acceptable weight, BnB must find at least one solution with at most 16 output groups
329        assert(result_bnb);
330        result_bnb->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
331        assert(result_bnb->GetWeight() <= high_max_selection_weight);
332        assert(result_bnb->GetSelectedEffectiveValue() >= target);
333        assert(result_bnb->GetSelectedEffectiveValue() <= target + coin_params.m_cost_of_change);
334        assert(best_waste <= result_bnb->GetWaste());
335        if (result_bnb->GetAlgoCompleted()) {
336            // If BnB exhausted the search space, it must return an optimal solution (tied on waste score)
337            assert(best_waste == result_bnb->GetWaste());
338        }
339    }
340}
341
342enum class CoinSelectionAlgorithm {
343    BNB,
344    SRD,
345    KNAPSACK,
346};
347
348template<CoinSelectionAlgorithm Algorithm>
349void FuzzCoinSelectionAlgorithm(std::span<const uint8_t> buffer) {
350    SeedRandomStateForTest(SeedRand::ZEROS);
351    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
352    std::vector<COutput> utxo_pool;
353
354    const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
355    const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
356    // Discard feerate must be at least dust relay feerate
357    const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
358    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
359    const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
360
361    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
362    CoinSelectionParams coin_params{fast_random_context};
363    coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
364    coin_params.m_long_term_feerate = long_term_fee_rate;
365    coin_params.m_effective_feerate = effective_fee_rate;
366    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
367    coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
368    coin_params.m_discard_feerate = discard_fee_rate;
369    coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
370    const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
371    coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
372    CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
373    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
374    coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
375
376    int next_locktime{0};
377    CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
378
379    std::vector<OutputGroup> group_pos;
380    GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
381
382    int max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, std::numeric_limits<int>::max());
383
384    std::optional<SelectionResult> result;
385
386    if constexpr (Algorithm == CoinSelectionAlgorithm::BNB) {
387        if (!coin_params.m_subtract_fee_outputs) {
388            auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, max_selection_weight);
389            if (result_bnb) {
390                result = *result_bnb;
391                assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
392                assert(result_bnb->GetSelectedValue() >= target);
393                assert(result_bnb->GetWeight() <= max_selection_weight);
394                (void)result_bnb->GetShuffledInputVector();
395                (void)result_bnb->GetInputSet();
396            }
397        }
398    }
399
400    if constexpr (Algorithm == CoinSelectionAlgorithm::SRD) {
401        auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, max_selection_weight);
402        if (result_srd) {
403            result = *result_srd;
404            assert(result_srd->GetSelectedValue() >= target);
405            assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0);
406            assert(result_srd->GetWeight() <= max_selection_weight);
407            result_srd->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));
408            result_srd->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
409            (void)result_srd->GetShuffledInputVector();
410            (void)result_srd->GetInputSet();
411        }
412    }
413
414    if constexpr (Algorithm == CoinSelectionAlgorithm::KNAPSACK) {
415        std::vector<OutputGroup> group_all;
416        GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
417
418        for (const OutputGroup& group : group_all) {
419            const CoinEligibilityFilter filter{fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>()};
420            (void)group.EligibleForSpending(filter);
421        }
422
423        CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
424        auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, max_selection_weight);
425        // If the total balance is sufficient for the target and we are not using
426        // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
427        if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
428            assert(result_knapsack);
429        }
430        if (result_knapsack) {
431            result = *result_knapsack;
432            assert(result_knapsack->GetSelectedValue() >= target);
433            assert(result_knapsack->GetWeight() <= max_selection_weight);
434            result_knapsack->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));
435            result_knapsack->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
436            (void)result_knapsack->GetShuffledInputVector();
437            (void)result_knapsack->GetInputSet();
438        }
439    }
440
441    std::vector<COutput> utxos;
442    CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
443    if (new_total_balance > 0) {
444        OutputSet new_utxo_pool;
445        for (const auto& utxo : utxos) {
446            new_utxo_pool.insert(std::make_shared<COutput>(utxo));
447        }
448        if (result) {
449            const auto weight{result->GetWeight()};
450            result->AddInputs(new_utxo_pool, subtract_fee_outputs);
451            assert(result->GetWeight() > weight);
452        }
453    }
454
455    std::vector<COutput> manual_inputs;
456    CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
457    if (manual_balance == 0) return;
458    auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
459    if (result) {
460        const CAmount old_target{result->GetTarget()};
461        const OutputSet input_set{result->GetInputSet()};
462        const int old_weight{result->GetWeight()};
463        result->Merge(manual_selection);
464        assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
465        assert(result->GetTarget() == old_target + manual_selection.GetTarget());
466        assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
467    }
468}
469
470FUZZ_TARGET(coinselection_bnb) {
471    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::BNB>(buffer);
472}
473
474FUZZ_TARGET(coinselection_srd) {
475    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::SRD>(buffer);
476}
477
478FUZZ_TARGET(coinselection_knapsack) {
479    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(buffer);
480}
481
482} // namespace wallet
483