Inside Bitcoin

1// Copyright (c) 2022-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <policy/feerate.h>
6#include <policy/policy.h>
7#include <primitives/transaction.h>
8#include <test/fuzz/FuzzedDataProvider.h>
9#include <test/fuzz/fuzz.h>
10#include <test/fuzz/util.h>
11#include <test/util/setup_common.h>
12#include <wallet/coinselection.h>
13
14#include <numeric>
15#include <span>
16#include <vector>
17
18namespace wallet {
19
20static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
21{
22    CMutableTransaction tx;
23    tx.vout.resize(n_input + 1);
24    tx.vout[n_input].nValue = value;
25    tx.nLockTime = locktime; // all transactions get different hashes
26    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);
27}
28
29// Randomly distribute coins to instances of OutputGroup
30static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
31{
32    auto output_group = OutputGroup(coin_params);
33    bool valid_outputgroup{false};
34    for (auto& coin : coins) {
35        if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
36            output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*cluster_count=*/0);
37        }
38        // If positive_only was specified, nothing was inserted, leading to an empty output group
39        // that would be invalid for the BnB algorithm
40        valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
41        if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
42            output_groups.push_back(output_group);
43            output_group = OutputGroup(coin_params);
44            valid_outputgroup = false;
45        }
46    }
47    if (valid_outputgroup) output_groups.push_back(output_group);
48}
49
50static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
51{
52    CAmount total_balance{0};
53    LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), 10000) {
54        const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
55        const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
56        const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
57        if (total_balance + amount >= MAX_MONEY) {
58            break;
59        }
60        AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
61        total_balance += amount;
62    }
63
64    return total_balance;
65}
66
67static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
68{
69    SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
70    OutputSet utxo_pool;
71    for (const auto& utxo : utxos) {
72        utxo_pool.insert(std::make_shared<COutput>(utxo));
73    }
74    result.AddInputs(utxo_pool, subtract_fee_outputs);
75    return result;
76}
77
78// Returns true if the result contains an error and the message is not empty
79static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
80
81FUZZ_TARGET(coin_grinder)
82{
83    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
84    std::vector<COutput> utxo_pool;
85
86    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
87
88    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
89    CoinSelectionParams coin_params{fast_random_context};
90    coin_params.m_subtract_fee_outputs = fuzzed_data_provider.ConsumeBool();
91    coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
92    coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
93    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
94    coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
95    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);
96    coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
97    // For other results to be comparable to SRD, we must align the change_target with SRD’s hardcoded behavior
98    coin_params.m_min_change_target = CHANGE_LOWER + coin_params.m_change_fee;
99
100    // Create some coins
101    CAmount total_balance{0};
102    CAmount max_spendable{0};
103    int next_locktime{0};
104    LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), 10000) {
105        const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
106        const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
107        const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
108        if (total_balance + amount >= MAX_MONEY) {
109            break;
110        }
111        AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
112        total_balance += amount;
113        CAmount eff_value = amount - coin_params.m_effective_feerate.GetFee(n_input_bytes);
114        max_spendable += eff_value;
115    }
116
117    std::vector<OutputGroup> group_pos;
118    GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
119
120    // Run coinselection algorithms
121    auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, MAX_STANDARD_TX_WEIGHT);
122    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
123    assert(result_cg);
124    if (!result_cg->GetAlgoCompleted()) return; // Bail out if CoinGrinder solution is not optimal
125
126    auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
127    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
128        assert(result_srd->GetWeight() >= result_cg->GetWeight());
129    }
130
131    auto result_knapsack = KnapsackSolver(group_pos, target, coin_params.m_min_change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
132    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
133        assert(result_knapsack->GetWeight() >= result_cg->GetWeight());
134    }
135}
136
137FUZZ_TARGET(coin_grinder_is_optimal)
138{
139    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
140
141    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
142    CoinSelectionParams coin_params{fast_random_context};
143    coin_params.m_subtract_fee_outputs = false;
144    // Set effective feerate up to MAX_MONEY sats per 1'000'000 vB (2'100'000'000 sat/vB = 21'000 BTC/kvB).
145    coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, MAX_MONEY), 1'000'000};
146    coin_params.m_min_change_target = ConsumeMoney(fuzzed_data_provider);
147
148    // Create some coins
149    CAmount max_spendable{0};
150    int next_locktime{0};
151    static constexpr unsigned max_output_groups{16};
152    std::vector<OutputGroup> group_pos;
153    LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), max_output_groups) {
154        // With maximum m_effective_feerate and n_input_bytes = 1'000'000, input_fee <= MAX_MONEY.
155        const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 1'000'000)};
156        // Only make UTXOs with positive effective value
157        const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes);
158        // Ensure that each UTXO has at least an effective value of 1 sat
159        const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
160        const CAmount amount{eff_value + input_fee};
161        std::vector<COutput> temp_utxo_pool;
162
163        AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
164        max_spendable += eff_value;
165
166        auto output_group = OutputGroup(coin_params);
167        output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*cluster_count=*/0);
168        group_pos.push_back(output_group);
169    }
170    size_t num_groups = group_pos.size();
171    assert(num_groups <= max_output_groups);
172
173    // Only choose targets below max_spendable
174    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_min_change_target))};
175
176    // Brute force optimal solution
177    CAmount best_amount{MAX_MONEY};
178    int best_weight{std::numeric_limits<int>::max()};
179    for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
180        CAmount subset_amount{0};
181        int subset_weight{0};
182        for (unsigned i = 0; i < num_groups; ++i) {
183            if ((pattern >> i) & 1) {
184                subset_amount += group_pos[i].GetSelectionAmount();
185                subset_weight += group_pos[i].m_weight;
186            }
187        }
188        if ((subset_amount >= target + coin_params.m_min_change_target) && (subset_weight < best_weight || (subset_weight == best_weight && subset_amount < best_amount))) {
189            best_weight = subset_weight;
190            best_amount = subset_amount;
191        }
192    }
193
194    if (best_weight < std::numeric_limits<int>::max()) {
195        // Sufficient funds and acceptable weight: CoinGrinder should find at least one solution
196        int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
197
198        auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, high_max_selection_weight);
199        assert(result_cg);
200        assert(result_cg->GetWeight() <= high_max_selection_weight);
201        assert(result_cg->GetSelectedEffectiveValue() >= target + coin_params.m_min_change_target);
202        assert(best_weight < result_cg->GetWeight() || (best_weight == result_cg->GetWeight() && best_amount <= result_cg->GetSelectedEffectiveValue()));
203        if (result_cg->GetAlgoCompleted()) {
204            // If CoinGrinder exhausted the search space, it must return the optimal solution
205            assert(best_weight == result_cg->GetWeight());
206            assert(best_amount == result_cg->GetSelectedEffectiveValue());
207        }
208    }
209
210    // CoinGrinder cannot ever find a better solution than the brute-forced best, or there is none in the first place
211    int low_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, best_weight - 1);
212    auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, low_max_selection_weight);
213    // Max_weight should have been exceeded, or there were insufficient funds
214    assert(!result_cg);
215}
216
217FUZZ_TARGET(bnb_finds_min_waste)
218{
219    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
220
221    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
222    CoinSelectionParams coin_params{fast_random_context};
223    coin_params.m_subtract_fee_outputs = false;
224    // Set effective feerate up to 10'000'000 sats per kvB (10'000 sat/vB).
225    coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
226    coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
227    coin_params.m_discard_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
228    coin_params.m_cost_of_change = ConsumeMoney(fuzzed_data_provider);
229
230    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
231    coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
232    coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
233    const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
234    coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
235    CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
236    const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
237    coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
238
239    // Create some coins
240    CAmount max_spendable{0};
241    int next_locktime{0};
242    // Too many output groups (>17?) would make it possible to generate UTXO
243    // pool and target combinations that cannot be completely searched by BnB
244    // before running into the attempt limit (see BnB "Exhaust..." test). The
245    // brute force search also gets exponentially more expensive with bigger
246    // UTXO pools.
247    // Choose 1–16 of 16 provides ample fuzzing space.
248    static constexpr unsigned max_output_groups{16};
249    std::vector<OutputGroup> group_pos;
250    LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), max_output_groups) {