doc/html/test_2fuzz_2coinselection_8cpp_source.html

// Copyright (c) 2022-present The Bitcoin Core developers

// Distributed under the MIT software license, see the accompanying

// file COPYING or http://www.opensource.org/licenses/mit-license.php.


#include <policy/feerate.h>

#include <policy/policy.h>

#include <primitives/transaction.h>

#include <test/fuzz/FuzzedDataProvider.h>

#include <test/fuzz/fuzz.h>

#include <test/fuzz/util.h>

#include <test/util/setup_common.h>

#include <wallet/coinselection.h>


#include <numeric>

#include <span>

#include <vector>


namespace wallet {


static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)

{

    CMutableTransaction tx;

    tx.vout.resize(n_input + 1);

    tx.vout[n_input].nValue = value;

    tx.nLockTime = locktime; // all transactions get different hashes

    coins.emplace_back(COutPoint(tx.GetHash(), n_input), tx.vout.at(n_input), /*depth=*/0, n_input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, fee_rate);

}


// Randomly distribute coins to instances of OutputGroup


static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)

{

    auto output_group = OutputGroup(coin_params);

    bool valid_outputgroup{false};

    for (auto& coin : coins) {

        if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {

            output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*cluster_count=*/0);

        }

        // If positive_only was specified, nothing was inserted, leading to an empty output group

        // that would be invalid for the BnB algorithm

        valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;

        if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {

            output_groups.push_back(output_group);

            output_group = OutputGroup(coin_params);

            valid_outputgroup = false;

        }

    }

    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);

    OutputSet 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(); }


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, /*cluster_count=*/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_selection_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_selection_weight);

        assert(result_cg);

        assert(result_cg->GetWeight() <= high_max_selection_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_selection_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_selection_weight);

    // Max_weight should have been exceeded, or there were insufficient funds

    assert(!result_cg);

}


FUZZ_TARGET(bnb_finds_min_waste)

{

    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 10'000'000 sats per kvB (10'000 sat/vB).

    coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};

    coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};

    coin_params.m_discard_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};

    coin_params.m_cost_of_change = ConsumeMoney(fuzzed_data_provider);


    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);

    coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);

    coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);

    const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};

    coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;

    CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);

    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};

    coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);


    // Create some coins

    CAmount max_spendable{0};

    int next_locktime{0};

    // Too many output groups (>17?) would make it possible to generate UTXO

    // pool and target combinations that cannot be completely searched by BnB

    // before running into the attempt limit (see BnB "Exhaust..." test). The

    // brute force search also gets exponentially more expensive with bigger

    // UTXO pools.

    // Choose 1–16 of 16 provides ample fuzzing space.

    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 10'000 s/vB and n_input_bytes = 20'000 B, input_fee <= MAX_MONEY.

        const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 20'000)};

        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, /*cluster_count=*/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_cost_of_change))};


    // Brute force optimal solution (lowest waste, but cannot be superset of another solution)

    std::vector<uint32_t> solutions;

    CAmount best_waste{std::numeric_limits<int64_t>::max()};

    int best_weight{std::numeric_limits<int>::max()};

    for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {

        // BnB does not permit adding more inputs to a solution, i.e. a superset of a solution cannot ever be a solution.

        // The search pattern guarantees that any superset will only be visited after all its subsets have been traversed.

        bool is_superset = false;

        for (uint32_t sol : solutions) {

            if ((pattern & sol) == sol) {

                is_superset = true;

                break;

            }

        }

        if (is_superset) {

            continue;

        }


        CAmount subset_amount{0};

        CAmount subset_waste{0};

        int subset_weight{0};

        for (unsigned i = 0; i < num_groups; ++i) {

            if ((pattern >> i) & 1) {

                subset_amount += group_pos[i].GetSelectionAmount();

                subset_waste += group_pos[i].fee - group_pos[i].long_term_fee;

                subset_weight += group_pos[i].m_weight;

            }

        }

        if (subset_amount >= target && subset_amount <= target + coin_params.m_cost_of_change) {

            solutions.push_back(pattern);

            // Add the excess (overselection that gets dropped to fees) to waste score

            CAmount excess = subset_amount - target;

            subset_waste += excess;

            SelectionResult result_bf(target, SelectionAlgorithm::MANUAL);


            for (unsigned i = 0; i < num_groups; ++i) {

                if ((pattern >> i) & 1) {

                    result_bf.AddInput(group_pos[i]);

                }

            }

            if (subset_waste < best_waste) {

                best_waste = subset_waste;

                result_bf.RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);

                assert(result_bf.GetWaste() == best_waste);

                best_weight = subset_weight;

            }

        }

    }


    int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());

    auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, high_max_selection_weight);


    if (!solutions.size() || !result_bnb) {

        // Either both BnB and Brute Force find a solution or neither does.

        assert(!result_bnb == !solutions.size());

    } else {

        // If brute forcing found a solution with an acceptable weight, BnB must find at least one solution with at most 16 output groups

        assert(result_bnb);

        result_bnb->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);

        assert(result_bnb->GetWeight() <= high_max_selection_weight);

        assert(result_bnb->GetSelectedEffectiveValue() >= target);

        assert(result_bnb->GetSelectedEffectiveValue() <= target + coin_params.m_cost_of_change);

        assert(best_waste <= result_bnb->GetWaste());

        if (result_bnb->GetAlgoCompleted()) {

            // If BnB exhausted the search space, it must return an optimal solution (tied on waste score)

            assert(best_waste == result_bnb->GetWaste());

        }

    }

}


enum class CoinSelectionAlgorithm {

    BNB,

    SRD,

    KNAPSACK,

};


template<CoinSelectionAlgorithm Algorithm>


void FuzzCoinSelectionAlgorithm(std::span<const uint8_t> buffer) {

    SeedRandomStateForTest(SeedRand::ZEROS);

    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};

    std::vector<COutput> utxo_pool;


    const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};

    const CFeeRate effective_fee_rate{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 target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};

    const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};


    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};

    CoinSelectionParams coin_params{fast_random_context};

    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.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);

    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);

    const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};

    coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;

    CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);

    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};

    coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);


    int next_locktime{0};

    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);


    int max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, std::numeric_limits<int>::max());


    std::optional<SelectionResult> result;


    if constexpr (Algorithm == CoinSelectionAlgorithm::BNB) {

        if (!coin_params.m_subtract_fee_outputs) {

            auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, max_selection_weight);

            if (result_bnb) {

                result = *result_bnb;

                assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);

                assert(result_bnb->GetSelectedValue() >= target);

                assert(result_bnb->GetWeight() <= max_selection_weight);

                (void)result_bnb->GetShuffledInputVector();

                (void)result_bnb->GetInputSet();

            }

        }

    }


    if constexpr (Algorithm == CoinSelectionAlgorithm::SRD) {

        auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, max_selection_weight);

        if (result_srd) {

            result = *result_srd;

            assert(result_srd->GetSelectedValue() >= target);

            assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0);

            assert(result_srd->GetWeight() <= max_selection_weight);

            result_srd->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));

            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();

        }

    }


    if constexpr (Algorithm == CoinSelectionAlgorithm::KNAPSACK) {

        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);

        }


        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_selection_weight);

        // 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);

        }

        if (result_knapsack) {

            result = *result_knapsack;

            assert(result_knapsack->GetSelectedValue() >= target);

            assert(result_knapsack->GetWeight() <= max_selection_weight);

            result_knapsack->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));

            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();

        }

    }


    std::vector<COutput> utxos;

    CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};

    if (new_total_balance > 0) {

        OutputSet new_utxo_pool;

        for (const auto& utxo : utxos) {

            new_utxo_pool.insert(std::make_shared<COutput>(utxo));

        }

        if (result) {

            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)};

    if (result) {

        const CAmount old_target{result->GetTarget()};

        const OutputSet 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());

    }

}


FUZZ_TARGET(coinselection_bnb) {

    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::BNB>(buffer);

}


FUZZ_TARGET(coinselection_srd) {

    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::SRD>(buffer);

}


FUZZ_TARGET(coinselection_knapsack) {

    FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(buffer);

}


} // namespace wallet

FuzzedDataProvider.h

MAX_MONEY
static constexpr CAmount MAX_MONEY
No amount larger than this (in satoshi) is valid.
Definition amount.h:26

CAmount
int64_t CAmount
Amount in satoshis (Can be negative).
Definition amount.h:12

COIN
static constexpr CAmount COIN
The amount of satoshis in one BTC.
Definition amount.h:15

CFeeRate
Fee rate in satoshis per virtualbyte: CAmount / vB the feerate is represented internally as FeeFrac.
Definition feerate.h:32

CFeeRate::GetFee
CAmount GetFee(int32_t virtual_bytes) const
Return the fee in satoshis for the given vsize in vbytes.
Definition feerate.cpp:20

COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition transaction.h:29

CScript
Serialized script, used inside transaction inputs and outputs.
Definition script.h:405

CTxOut
An output of a transaction.
Definition transaction.h:140

FastRandomContext
Fast randomness source.
Definition random.h:386

FuzzedDataProvider
Definition FuzzedDataProvider.h:32

FuzzedDataProvider::ConsumeBool
bool ConsumeBool()
Definition FuzzedDataProvider.h:289

FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition FuzzedDataProvider.h:205

FuzzedDataProvider::ConsumeIntegral
T ConsumeIntegral()
Definition FuzzedDataProvider.h:195

util::Result
Definition result.h:36

coinselection.h

feerate.h

fuzz.h

FUZZ_TARGET
#define FUZZ_TARGET(...)
Definition fuzz.h:35

LIMITED_WHILE
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition fuzz.h:22

util::ErrorString
bilingual_str ErrorString(const Result< T > &result)
Definition result.h:93

wallet
Definition wallet_balance.cpp:26

wallet::CreateCoins
static CAmount CreateCoins(FuzzedDataProvider &fuzzed_data_provider, std::vector< COutput > &utxo_pool, CoinSelectionParams &coin_params, int &next_locktime)
Definition coinselection.cpp:50

wallet::AddCoin
static void AddCoin(const CAmount &value, int n_input, int n_input_bytes, int locktime, std::vector< COutput > &coins, CFeeRate fee_rate)
Definition coinselection.cpp:20

wallet::CHANGE_LOWER
static constexpr CAmount CHANGE_LOWER
lower bound for randomly-chosen target change amount
Definition coinselection.h:23

wallet::SelectCoinsBnB
util::Result< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, int max_selection_weight)
Definition coinselection.cpp:93

wallet::SelectionAlgorithm::KNAPSACK
@ KNAPSACK
Definition coinselection.h:315

wallet::SelectionAlgorithm::BNB
@ BNB
Definition coinselection.h:314

wallet::SelectionAlgorithm::SRD
@ SRD
Definition coinselection.h:316

wallet::SelectionAlgorithm::MANUAL
@ MANUAL
Definition coinselection.h:318

wallet::CoinGrinder
util::Result< SelectionResult > CoinGrinder(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, CAmount change_target, int max_selection_weight)
Definition coinselection.cpp:325

wallet::GroupCoins
std::vector< OutputGroup > & GroupCoins(const std::vector< COutput > &available_coins, bool subtract_fee_outputs=false)
Definition coinselector_tests.cpp:126

wallet::FuzzCoinSelectionAlgorithm
void FuzzCoinSelectionAlgorithm(std::span< const uint8_t > buffer)
Definition coinselection.cpp:353

wallet::KnapsackSolver
util::Result< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue, CAmount change_target, FastRandomContext &rng, int max_selection_weight)
Definition coinselection.cpp:652

wallet::ManualSelection
static SelectionResult ManualSelection(std::vector< COutput > &utxos, const CAmount &total_amount, const bool &subtract_fee_outputs)
Definition coinselection.cpp:68

wallet::GenerateChangeTarget
CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext &rng)
Choose a random change target for each transaction to make it harder to fingerprint the Core wallet b...
Definition coinselection.cpp:809

wallet::HasErrorMsg
static bool HasErrorMsg(const util::Result< SelectionResult > &res)
Definition spend.cpp:700

wallet::OutputSet
std::set< std::shared_ptr< COutput >, OutputPtrComparator > OutputSet
Definition coinselection.h:328

wallet::CoinSelectionAlgorithm
CoinSelectionAlgorithm
Definition coinselection.cpp:346

wallet::CoinSelectionAlgorithm::KNAPSACK
@ KNAPSACK
Definition coinselection.cpp:349

wallet::CoinSelectionAlgorithm::BNB
@ BNB
Definition coinselection.cpp:347

wallet::CoinSelectionAlgorithm::SRD
@ SRD
Definition coinselection.cpp:348

wallet::SelectCoinsSRD
util::Result< SelectionResult > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext &rng, int max_selection_weight)
Select coins by Single Random Draw (SRD).
Definition coinselection.cpp:536

GetDustThreshold
CAmount GetDustThreshold(const CTxOut &txout, const CFeeRate &dustRelayFeeIn)
Definition policy.cpp:26

policy.h

DUST_RELAY_TX_FEE
static constexpr unsigned int DUST_RELAY_TX_FEE
Min feerate for defining dust.
Definition policy.h:67

MAX_STANDARD_TX_WEIGHT
static constexpr int32_t MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
Definition policy.h:37

transaction.h

MAX_SCRIPT_SIZE
static const int MAX_SCRIPT_SIZE
Definition script.h:40

OP_TRUE
@ OP_TRUE
Definition script.h:84

setup_common.h

CMutableTransaction
A mutable version of CTransaction.
Definition transaction.h:358

CMutableTransaction::vout
std::vector< CTxOut > vout
Definition transaction.h:360

CMutableTransaction::GetHash
Txid GetHash() const
Compute the hash of this CMutableTransaction.
Definition transaction.cpp:69

CMutableTransaction::nLockTime
uint32_t nLockTime
Definition transaction.h:362

bilingual_str::empty
bool empty() const
Definition translation.h:35

wallet::CoinEligibilityFilter
Parameters for filtering which OutputGroups we may use in coin selection.
Definition coinselection.h:202

wallet::CoinSelectionParams
Parameters for one iteration of Coin Selection.
Definition coinselection.h:134

wallet::CoinSelectionParams::m_min_change_target
CAmount m_min_change_target
Mininmum change to target in Knapsack solver and CoinGrinder: select coins to cover the payment and a...
Definition coinselection.h:143

wallet::CoinSelectionParams::m_subtract_fee_outputs
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
Definition coinselection.h:163

wallet::CoinSelectionParams::m_effective_feerate
CFeeRate m_effective_feerate
The targeted feerate of the transaction being built.
Definition coinselection.h:153

wallet::CoinSelectionParams::min_viable_change
CAmount min_viable_change
Minimum amount for creating a change output.
Definition coinselection.h:147

wallet::CoinSelectionParams::change_spend_size
int change_spend_size
Size of the input to spend a change output in virtual bytes.
Definition coinselection.h:140

wallet::CoinSelectionParams::m_cost_of_change
CAmount m_cost_of_change
Cost of creating the change output + cost of spending the change output in the future.
Definition coinselection.h:151

wallet::CoinSelectionParams::m_change_fee
CAmount m_change_fee
Cost of creating the change output.
Definition coinselection.h:149

wallet::CoinSelectionParams::change_output_size
int change_output_size
Size of a change output in bytes, determined by the output type.
Definition coinselection.h:138

wallet::CoinSelectionParams::m_long_term_feerate
CFeeRate m_long_term_feerate
The feerate estimate used to estimate an upper bound on what should be sufficient to spend the change...
Definition coinselection.h:156

wallet::CoinSelectionParams::m_discard_feerate
CFeeRate m_discard_feerate
If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees.
Definition coinselection.h:158

wallet::OutputGroup
A group of UTXOs paid to the same output script.
Definition coinselection.h:229

wallet::SelectionResult
Definition coinselection.h:331

wallet::SelectionResult::AddInputs
void AddInputs(const OutputSet &inputs, bool subtract_fee_outputs)
Definition coinselection.cpp:911

wallet::SelectionResult::RecalculateWaste
void RecalculateWaste(CAmount min_viable_change, CAmount change_cost, CAmount change_fee)
Calculates and stores the waste for this result given the cost of change and the opportunity cost of ...
Definition coinselection.cpp:827

wallet::SelectionResult::AddInput
void AddInput(const OutputGroup &group)
Definition coinselection.cpp:902

wallet::SelectionResult::GetWaste
CAmount GetWaste() const
Definition coinselection.cpp:875

ConsumeMoney
CAmount ConsumeMoney(FuzzedDataProvider &fuzzed_data_provider, const std::optional< CAmount > &max) noexcept
Definition util.cpp:29

util.h

ConsumeUInt256
uint256 ConsumeUInt256(FuzzedDataProvider &fuzzed_data_provider) noexcept
Definition util.h:167

SeedRandomStateForTest
void SeedRandomStateForTest(SeedRand seedtype)
Seed the global RNG state for testing and log the seed value.
Definition random.cpp:19

SeedRand::ZEROS
@ ZEROS
Seed with a compile time constant of zeros.
Definition random.h:19

assert
assert(!tx.IsCoinBase())