1
// Copyright (c) 2022 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 <primitives/transaction.h>
7
#include <test/fuzz/FuzzedDataProvider.h>
8
#include <test/fuzz/fuzz.h>
9
#include <test/fuzz/util.h>
10
#include <test/util/setup_common.h>
11
#include <wallet/coinselection.h>
12

            
13
#include <vector>
14

            
15
namespace wallet {
16

            
17
static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins)
18
{
19
    CMutableTransaction tx;
20
    tx.vout.resize(n_input + 1);
21
    tx.vout[n_input].nValue = value;
22
    tx.nLockTime = locktime; // all transactions get different hashes
23
    coins.emplace_back(COutPoint(tx.GetHash(), n_input), tx.vout.at(n_input), /*depth=*/0, n_input_bytes, /*spendable=*/true, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true);
24
}
25

            
26
// Randomly distribute coins to instances of OutputGroup
27
static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
28
{
29
    auto output_group = OutputGroup(coin_params);
30
    bool valid_outputgroup{false};
31
    for (auto& coin : coins) {
32
        output_group.Insert(coin, /*ancestors=*/0, /*descendants=*/0, positive_only);
33
        // If positive_only was specified, nothing may have been inserted, leading to an empty outpout group
34
        // that would be invalid for the BnB algorithm
35
        valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
36
        if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
37
            output_groups.push_back(output_group);
38
            output_group = OutputGroup(coin_params);
39
            valid_outputgroup = false;
40
        }
41
    }
42
    if (valid_outputgroup) output_groups.push_back(output_group);
43
}
44

            
45
FUZZ_TARGET(coinselection)
46
{
47
    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
48
    std::vector<COutput> utxo_pool;
49

            
50
    const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
51
    const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
52
    const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
53
    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
54
    const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
55

            
56
    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
57
    CoinSelectionParams coin_params{fast_random_context};
58
    coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
59
    coin_params.m_long_term_feerate = long_term_fee_rate;
60
    coin_params.m_effective_feerate = effective_fee_rate;
61

            
62
    // Create some coins
63
    CAmount total_balance{0};
64
    int next_locktime{0};
65
    LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
66
    {
67
        const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
68
        const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(100, 10000)};
69
        const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
70
        if (total_balance + amount >= MAX_MONEY) {
71
            break;
72
        }
73
        AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool);
74
        total_balance += amount;
75
    }
76

            
77
    std::vector<OutputGroup> group_pos;
78
    GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
79
    std::vector<OutputGroup> group_all;
80
    GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
81

            
82
    // Run coinselection algorithms
83
    const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change);
84

            
85
    auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context);
86
    if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change);
87

            
88
    CAmount change_target{GenerateChangeTarget(target, fast_random_context)};
89
    auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context);
90
    if (result_knapsack) result_knapsack->ComputeAndSetWaste(cost_of_change);
91

            
92
    // If the total balance is sufficient for the target and we are not using
93
    // effective values, Knapsack should always find a solution.
94
    if (total_balance >= target && subtract_fee_outputs) {
95
        assert(result_knapsack);
96
    }
97
}
98

            
99
} // namespace wallet