Grcov report - coinselection.cpp

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