Repository: bitcoin/bitcoin
File: src/wallet/test/fuzz/coinselection.cpp (C++)

Code before:
    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);
        // Only make UTXOs with positive effective value
        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_cost_of_change))};

    // Brute force optimal solution (lowest waste, but cannot be superset of another solution)
    std::vector<uint32_t> solutions;
    int best_waste{std::numeric_limits<int>::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;

Review comment (suggestion):
13288708523518b72663cbd257dcb7608025126b: Perhaps we could use same explanation from `coin_grinder_is_optimal`: "Ensure that each UTXO has at least an effective value of 1 sat".

Code after:
    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, /*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_cost_of_change))};

    // Brute force optimal solution (lowest waste, but cannot be superset of another solution)
    std::vector<uint32_t> solutions;
    int best_waste{std::numeric_limits<int>::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;