Branch data Line data Source code
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 <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 <vector>
15 : :
16 : : namespace wallet {
17 [ + - ]: 2 :
18 [ + - ]: 2 : static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
19 : : {
20 : 0 : CMutableTransaction tx;
21 [ # # ]: 0 : tx.vout.resize(n_input + 1);
22 : 0 : tx.vout[n_input].nValue = value;
23 : 0 : tx.nLockTime = locktime; // all transactions get different hashes
24 [ # # ][ # # ]: 0 : 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, fee_rate);
[ # # ][ # # ]
[ # # ]
25 : 2 : }
26 : :
27 : : // Randomly distribute coins to instances of OutputGroup
28 : 0 : static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
29 : : {
30 : 0 : auto output_group = OutputGroup(coin_params);
31 : 0 : bool valid_outputgroup{false};
32 [ # # ]: 0 : for (auto& coin : coins) {
33 [ # # ][ # # ]: 0 : if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
[ # # ][ # # ]
34 [ # # ][ # # ]: 0 : output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*descendants=*/0);
35 : 0 : }
36 : : // If positive_only was specified, nothing was inserted, leading to an empty output group
37 : : // that would be invalid for the BnB algorithm
38 [ # # ][ # # ]: 0 : valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
39 [ # # ][ # # ]: 0 : if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
[ # # ]
40 [ # # ]: 0 : output_groups.push_back(output_group);
41 [ # # ]: 0 : output_group = OutputGroup(coin_params);
42 : 0 : valid_outputgroup = false;
43 : 0 : }
44 : : }
45 [ # # ][ # # ]: 0 : if (valid_outputgroup) output_groups.push_back(output_group);
46 : 0 : }
47 : :
48 : 0 : static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
49 : : {
50 : 0 : CAmount total_balance{0};
51 [ # # ][ # # ]: 0 : LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
52 : : {
53 : 0 : const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
54 : 0 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
55 : 0 : const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
56 [ # # ]: 0 : if (total_balance + amount >= MAX_MONEY) {
57 : 0 : break;
58 : : }
59 : 0 : AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
60 : 0 : total_balance += amount;
61 : 0 : }
62 : :
63 : 0 : return total_balance;
64 : : }
65 : :
66 : 0 : static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
67 : : {
68 : 0 : SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
69 : 0 : std::set<std::shared_ptr<COutput>> utxo_pool;
70 [ # # ]: 0 : for (const auto& utxo : utxos) {
71 [ # # ][ # # ]: 0 : utxo_pool.insert(std::make_shared<COutput>(utxo));
72 : : }
73 [ # # ]: 0 : result.AddInputs(utxo_pool, subtract_fee_outputs);
74 : 0 : return result;
75 [ # # ]: 0 : }
76 : :
77 : : // Returns true if the result contains an error and the message is not empty
78 [ # # ]: 0 : static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
79 : :
80 [ + - ][ + - ]: 6 : FUZZ_TARGET(coinselection)
81 : : {
82 : 0 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
83 : 0 : std::vector<COutput> utxo_pool;
84 : :
85 [ # # ]: 0 : const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
86 [ # # ]: 0 : const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
87 : : // Discard feerate must be at least dust relay feerate
88 [ # # ][ # # ]: 0 : const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
89 : 0 : const CAmount min_viable_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
90 [ # # ]: 0 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
91 [ # # ]: 0 : const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
92 : :
93 : 0 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
94 [ # # ]: 0 : CoinSelectionParams coin_params{fast_random_context};
95 : 0 : coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
96 : 0 : coin_params.m_long_term_feerate = long_term_fee_rate;
97 : 0 : coin_params.m_effective_feerate = effective_fee_rate;
98 : 0 : coin_params.min_viable_change = min_viable_change;
99 [ # # ]: 0 : coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
100 [ # # ]: 0 : coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
101 : 0 : coin_params.m_discard_feerate = discard_fee_rate;
102 [ # # ]: 0 : coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
103 [ # # ]: 0 : coin_params.m_cost_of_change = coin_params.m_change_fee + coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);
104 : :
105 : 0 : int next_locktime{0};
106 [ # # ]: 0 : CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
107 : :
108 : 0 : std::vector<OutputGroup> group_pos;
109 [ # # ]: 0 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
110 : 0 : std::vector<OutputGroup> group_all;
111 [ # # ]: 0 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
112 : :
113 [ # # ]: 0 : for (const OutputGroup& group : group_all) {
114 [ # # ][ # # ]: 0 : const CoinEligibilityFilter filter(fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>());
[ # # ][ # # ]
115 [ # # ]: 0 : (void)group.EligibleForSpending(filter);
116 : : }
117 : :
118 : : // Run coinselection algorithms
119 [ # # ]: 0 : auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
120 [ # # ]: 0 : if (result_bnb) {
121 [ # # ][ # # ]: 0 : assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
[ # # ]
122 [ # # ][ # # ]: 0 : assert(result_bnb->GetSelectedValue() >= target);
[ # # ]
123 [ # # ][ # # ]: 0 : (void)result_bnb->GetShuffledInputVector();
124 [ # # ][ # # ]: 0 : (void)result_bnb->GetInputSet();
125 : 0 : }
126 : :
127 [ # # ]: 0 : auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
128 [ # # ]: 0 : if (result_srd) {
129 [ # # ][ # # ]: 0 : assert(result_srd->GetSelectedValue() >= target);
[ # # ]
130 [ # # ][ # # ]: 0 : assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0); // Demonstrate that SRD creates change of at least CHANGE_LOWER
[ # # ]
131 [ # # ][ # # ]: 0 : result_srd->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
132 [ # # ][ # # ]: 0 : (void)result_srd->GetShuffledInputVector();
133 [ # # ][ # # ]: 0 : (void)result_srd->GetInputSet();
134 : 0 : }
135 : :
136 [ # # ]: 0 : CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
137 [ # # ]: 0 : auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
138 [ # # ]: 0 : if (result_knapsack) {
139 [ # # ][ # # ]: 0 : assert(result_knapsack->GetSelectedValue() >= target);
[ # # ]
140 [ # # ][ # # ]: 0 : result_knapsack->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
141 [ # # ][ # # ]: 0 : (void)result_knapsack->GetShuffledInputVector();
142 [ # # ][ # # ]: 0 : (void)result_knapsack->GetInputSet();
143 : 0 : }
144 : :
145 : : // If the total balance is sufficient for the target and we are not using
146 : : // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
147 [ # # ][ # # ]: 0 : if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
[ # # ][ # # ]
148 [ # # ]: 0 : assert(result_knapsack);
149 : 0 : }
150 : :
151 : 0 : std::vector<COutput> utxos;
152 [ # # ][ # # ]: 0 : std::vector<util::Result<SelectionResult>> results{result_srd, result_knapsack, result_bnb};
[ # # ][ # # ]
153 [ # # ]: 0 : CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
154 [ # # ]: 0 : if (new_total_balance > 0) {
155 : 0 : std::set<std::shared_ptr<COutput>> new_utxo_pool;
156 [ # # ]: 0 : for (const auto& utxo : utxos) {
157 [ # # ][ # # ]: 0 : new_utxo_pool.insert(std::make_shared<COutput>(utxo));
158 : : }
159 [ # # ]: 0 : for (auto& result : results) {
160 [ # # ]: 0 : if (!result) continue;
161 [ # # ][ # # ]: 0 : const auto weight{result->GetWeight()};
162 [ # # ][ # # ]: 0 : result->AddInputs(new_utxo_pool, subtract_fee_outputs);
163 [ # # ][ # # ]: 0 : assert(result->GetWeight() > weight);
[ # # ]
164 : : }
165 : 0 : }
166 : :
167 : 0 : std::vector<COutput> manual_inputs;
168 [ # # ]: 0 : CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
169 [ # # ]: 0 : if (manual_balance == 0) return;
170 [ # # ]: 0 : auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
171 [ # # ]: 0 : for (auto& result : results) {
172 [ # # ]: 0 : if (!result) continue;
173 [ # # ][ # # ]: 0 : const CAmount old_target{result->GetTarget()};
174 [ # # ][ # # ]: 0 : const std::set<std::shared_ptr<COutput>> input_set{result->GetInputSet()};
[ # # ]
175 [ # # ][ # # ]: 0 : const int old_weight{result->GetWeight()};
176 [ # # ][ # # ]: 0 : result->Merge(manual_selection);
177 [ # # ][ # # ]: 0 : assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
[ # # ]
178 [ # # ][ # # ]: 0 : assert(result->GetTarget() == old_target + manual_selection.GetTarget());
[ # # ][ # # ]
179 [ # # ][ # # ]: 0 : assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
[ # # ][ # # ]
180 : 0 : }
181 [ # # ]: 0 : }
182 : :
183 : : } // namespace wallet
|
