Branch data Line data Source code
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 : :
18 : : namespace wallet {
19 : :
20 : 2120677 : static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
21 : : {
22 : 2120677 : CMutableTransaction tx;
23 [ + - ]: 2120677 : tx.vout.resize(n_input + 1);
24 [ + - ]: 2120677 : tx.vout[n_input].nValue = value;
25 : 2120677 : tx.nLockTime = locktime; // all transactions get different hashes
26 [ + - + - : 2120677 : 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 : 2120677 : }
28 : :
29 : : // Randomly distribute coins to instances of OutputGroup
30 : 3209 : static 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 : 3209 : auto output_group = OutputGroup(coin_params);
33 : 3209 : bool valid_outputgroup{false};
34 [ + + ]: 2265280 : for (auto& coin : coins) {
35 [ + + + + ]: 2262071 : if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
36 [ + - + - ]: 4266226 : 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 [ + + + - : 2262071 : valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
+ + ]
41 [ + + ]: 2136360 : if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
42 [ + - ]: 1094622 : output_groups.push_back(output_group);
43 : 1094622 : output_group = OutputGroup(coin_params);
44 : 1094622 : valid_outputgroup = false;
45 : : }
46 : : }
47 [ + + + - ]: 3209 : if (valid_outputgroup) output_groups.push_back(output_group);
48 : 3209 : }
49 : :
50 : 5097 : static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
51 : : {
52 : 5097 : CAmount total_balance{0};
53 [ + + + + ]: 1636304 : LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), 10000) {
54 : 1631928 : const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
55 : 1631928 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
56 : 1631928 : const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
57 [ + + ]: 1631928 : if (total_balance + amount >= MAX_MONEY) {
58 : : break;
59 : : }
60 : 1631207 : AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
61 : 1631207 : total_balance += amount;
62 : : }
63 : :
64 : 5097 : return total_balance;
65 : : }
66 : :
67 : 374 : static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
68 : : {
69 : 374 : SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
70 : 374 : OutputSet utxo_pool;
71 [ + + ]: 171190 : for (const auto& utxo : utxos) {
72 [ + - + - ]: 341632 : utxo_pool.insert(std::make_shared<COutput>(utxo));
73 : : }
74 [ + - ]: 374 : result.AddInputs(utxo_pool, subtract_fee_outputs);
75 : 374 : return result;
76 : 374 : }
77 : :
78 : : // Returns true if the result contains an error and the message is not empty
79 : 1093 : static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
80 : :
81 [ + - ]: 1303 : FUZZ_TARGET(coin_grinder)
82 : : {
83 : 829 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
84 : 829 : std::vector<COutput> utxo_pool;
85 : :
86 : 829 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
87 : :
88 : 829 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
89 : 829 : CoinSelectionParams coin_params{fast_random_context};
90 : 829 : coin_params.m_subtract_fee_outputs = fuzzed_data_provider.ConsumeBool();
91 : 829 : coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
92 : 829 : coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
93 : 829 : coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
94 : 829 : coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
95 [ + - + - ]: 829 : 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 [ + - ]: 829 : 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 : 829 : coin_params.m_min_change_target = CHANGE_LOWER + coin_params.m_change_fee;
99 : :
100 : : // Create some coins
101 : 829 : CAmount total_balance{0};
102 : 829 : CAmount max_spendable{0};
103 : 829 : int next_locktime{0};
104 [ + + + + ]: 485279 : LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), 10000) {
105 : 484784 : const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
106 : 484784 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
107 : 484784 : const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
108 [ + + ]: 484784 : if (total_balance + amount >= MAX_MONEY) {
109 : : break;
110 : : }
111 [ + - ]: 484450 : AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
112 : 484450 : total_balance += amount;
113 [ + - ]: 484450 : CAmount eff_value = amount - coin_params.m_effective_feerate.GetFee(n_input_bytes);
114 : 484450 : max_spendable += eff_value;
115 : : }
116 : :
117 : 829 : std::vector<OutputGroup> group_pos;
118 [ + - ]: 829 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
119 : :
120 : : // Run coinselection algorithms
121 [ + - ]: 829 : auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, MAX_STANDARD_TX_WEIGHT);
122 [ + + + - : 829 : 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 [ - + ]: 759 : assert(result_cg);
124 [ + - + + ]: 759 : if (!result_cg->GetAlgoCompleted()) return; // Bail out if CoinGrinder solution is not optimal
125 : :
126 [ + - ]: 749 : auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
127 [ + + + - : 1468 : 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 [ - + ]: 719 : assert(result_srd->GetWeight() >= result_cg->GetWeight());
129 : : }
130 : :
131 [ + - ]: 749 : auto result_knapsack = KnapsackSolver(group_pos, target, coin_params.m_min_change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
132 [ + + + - : 1487 : 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 [ - + ]: 680 : assert(result_knapsack->GetWeight() >= result_cg->GetWeight());
134 : : }
135 : 829 : }
136 : :
137 [ + - ]: 763 : FUZZ_TARGET(coin_grinder_is_optimal)
138 : : {
139 : 289 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
140 : :
141 : 289 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
142 : 289 : CoinSelectionParams coin_params{fast_random_context};
143 : 289 : 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 [ + - ]: 289 : coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, MAX_MONEY), 1'000'000};
146 : 289 : coin_params.m_min_change_target = ConsumeMoney(fuzzed_data_provider);
147 : :
148 : : // Create some coins
149 : 289 : CAmount max_spendable{0};
150 : 289 : int next_locktime{0};
151 : 289 : static constexpr unsigned max_output_groups{16};
152 : 289 : std::vector<OutputGroup> group_pos;
153 [ + + + + ]: 3059 : 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 : 2770 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 1'000'000)};
156 : : // Only make UTXOs with positive effective value
157 [ + - ]: 2770 : 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 [ - + ]: 2770 : const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
160 : 2770 : const CAmount amount{eff_value + input_fee};
161 : 2770 : std::vector<COutput> temp_utxo_pool;
162 : :
163 [ + - ]: 2770 : AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
164 : 2770 : max_spendable += eff_value;
165 : :
166 [ + - ]: 2770 : auto output_group = OutputGroup(coin_params);
167 [ + - + - : 2770 : output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*cluster_count=*/0);
+ - ]
168 [ + - ]: 2770 : group_pos.push_back(output_group);
169 : 2770 : }
170 [ - + ]: 289 : size_t num_groups = group_pos.size();
171 [ - + ]: 289 : assert(num_groups <= max_output_groups);
172 : :
173 : : // Only choose targets below max_spendable
174 [ + + ]: 350 : 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 : 289 : CAmount best_amount{MAX_MONEY};
178 : 289 : int best_weight{std::numeric_limits<int>::max()};
179 [ + + ]: 6492163 : for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
180 : : CAmount subset_amount{0};
181 : : int subset_weight{0};
182 [ + + ]: 109138882 : for (unsigned i = 0; i < num_groups; ++i) {
183 [ + + ]: 102647008 : if ((pattern >> i) & 1) {
184 [ + - ]: 51324889 : subset_amount += group_pos[i].GetSelectionAmount();
185 : 51324889 : subset_weight += group_pos[i].m_weight;
186 : : }
187 : : }
188 [ + + + + : 6491874 : if ((subset_amount >= target + coin_params.m_min_change_target) && (subset_weight < best_weight || (subset_weight == best_weight && subset_amount < best_amount))) {
+ + ]
189 : 1733 : best_weight = subset_weight;
190 : 1733 : best_amount = subset_amount;
191 : : }
192 : : }
193 : :
194 [ + + ]: 289 : if (best_weight < std::numeric_limits<int>::max()) {
195 : : // Sufficient funds and acceptable weight: CoinGrinder should find at least one solution
196 : 242 : int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
197 : :
198 [ + - ]: 242 : auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, high_max_selection_weight);
199 [ - + ]: 242 : assert(result_cg);
200 [ - + ]: 242 : assert(result_cg->GetWeight() <= high_max_selection_weight);
201 [ + - - + ]: 242 : assert(result_cg->GetSelectedEffectiveValue() >= target + coin_params.m_min_change_target);
202 [ + - + - : 242 : assert(best_weight < result_cg->GetWeight() || (best_weight == result_cg->GetWeight() && best_amount <= result_cg->GetSelectedEffectiveValue()));
+ - - + ]
203 [ + - + - ]: 242 : if (result_cg->GetAlgoCompleted()) {
204 : : // If CoinGrinder exhausted the search space, it must return the optimal solution
205 [ - + ]: 242 : assert(best_weight == result_cg->GetWeight());
206 [ + - - + ]: 242 : assert(best_amount == result_cg->GetSelectedEffectiveValue());
207 : : }
208 : 242 : }
209 : :
210 : : // CoinGrinder cannot ever find a better solution than the brute-forced best, or there is none in the first place
211 : 289 : int low_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, best_weight - 1);
212 [ + - ]: 289 : 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 [ - + ]: 289 : assert(!result_cg);
215 : 289 : }
216 : :
217 [ + - ]: 721 : FUZZ_TARGET(bnb_finds_min_waste)
218 : : {
219 : 247 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
220 : :
221 : 247 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
222 : 247 : CoinSelectionParams coin_params{fast_random_context};
223 : 247 : coin_params.m_subtract_fee_outputs = false;
224 : : // Set effective feerate up to 10'000'000 sats per kvB (10'000 sat/vB).
225 [ + - ]: 247 : coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
226 [ + - ]: 247 : coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
227 [ + - ]: 247 : coin_params.m_discard_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
228 : 247 : coin_params.m_cost_of_change = ConsumeMoney(fuzzed_data_provider);
229 : :
230 : 247 : coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
231 [ + - ]: 247 : coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
232 : 247 : coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
233 [ + - ]: 247 : const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
234 : 247 : coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
235 [ + - ]: 494 : CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
236 [ + - + - ]: 247 : const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
237 [ + + ]: 247 : coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
238 : :
239 : : // Create some coins
240 : 247 : CAmount max_spendable{0};
241 : 247 : 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 : 247 : static constexpr unsigned max_output_groups{16};
249 : 247 : std::vector<OutputGroup> group_pos;
250 [ + + + + ]: 2497 : LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), max_output_groups) {
251 : : // With maximum m_effective_feerate 10'000 s/vB and n_input_bytes = 20'000 B, input_fee <= MAX_MONEY.
252 : 2250 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 20'000)};
253 [ + - ]: 2250 : const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes);
254 : : // Ensure that each UTXO has at least an effective value of 1 sat
255 [ - + ]: 2250 : const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
256 : 2250 : const CAmount amount{eff_value + input_fee};
257 : 2250 : std::vector<COutput> temp_utxo_pool;
258 : :
259 [ + - ]: 2250 : AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
260 : 2250 : max_spendable += eff_value;
261 : :
262 [ + - ]: 2250 : auto output_group = OutputGroup(coin_params);
263 [ + - + - ]: 2250 : output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*cluster_count=*/0);
264 [ + - ]: 2250 : group_pos.push_back(output_group);
265 : 2250 : }
266 [ - + ]: 247 : size_t num_groups = group_pos.size();
267 [ - + ]: 247 : assert(num_groups <= max_output_groups);
268 : :
269 : : // Only choose targets below max_spendable
270 [ + + ]: 287 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_cost_of_change))};
271 : :
272 : : // Brute force optimal solution (lowest waste, but cannot be superset of another solution)
273 : 247 : std::vector<uint32_t> solutions;
274 : 247 : CAmount best_waste{std::numeric_limits<int64_t>::max()};
275 : 247 : int best_weight{std::numeric_limits<int>::max()};
276 [ + + ]: 4895628 : for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
277 : : // BnB does not permit adding more inputs to a solution, i.e. a superset of a solution cannot ever be a solution.
278 : : // The search pattern guarantees that any superset will only be visited after all its subsets have been traversed.
279 : 4895381 : bool is_superset = false;
280 [ + + ]: 95622397 : for (uint32_t sol : solutions) {
281 [ + + ]: 92776834 : if ((pattern & sol) == sol) {
282 : : is_superset = true;
283 : : break;
284 : : }
285 : : }
286 [ + + ]: 4895381 : if (is_superset) {
287 : 2049818 : continue;
288 : : }
289 : :
290 : : CAmount subset_amount{0};
291 : : CAmount subset_waste{0};
292 : : int subset_weight{0};
293 [ + + ]: 47740663 : for (unsigned i = 0; i < num_groups; ++i) {
294 [ + + ]: 44895100 : if ((pattern >> i) & 1) {
295 [ + - ]: 21364550 : subset_amount += group_pos[i].GetSelectionAmount();
296 : 21364550 : subset_waste += group_pos[i].fee - group_pos[i].long_term_fee;
297 : 21364550 : subset_weight += group_pos[i].m_weight;
298 : : }
299 : : }
300 [ + + + + ]: 2845563 : if (subset_amount >= target && subset_amount <= target + coin_params.m_cost_of_change) {
301 [ + - ]: 7334 : solutions.push_back(pattern);
302 : : // Add the excess (overselection that gets dropped to fees) to waste score
303 : 7334 : CAmount excess = subset_amount - target;
304 : 7334 : subset_waste += excess;
305 : 7334 : SelectionResult result_bf(target, SelectionAlgorithm::MANUAL);
306 : :
307 [ + + ]: 114171 : for (unsigned i = 0; i < num_groups; ++i) {
308 [ + + ]: 106837 : if ((pattern >> i) & 1) {
309 [ + - ]: 43727 : result_bf.AddInput(group_pos[i]);
310 : : }
311 : : }
312 [ + + ]: 7334 : if (subset_waste < best_waste) {
313 : 748 : best_waste = subset_waste;
314 [ + - ]: 748 : result_bf.RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
315 [ + - - + ]: 748 : assert(result_bf.GetWaste() == best_waste);
316 : : best_weight = subset_weight;
317 : : }
318 : 7334 : }
319 : : }
320 : :
321 : 247 : int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
322 [ + - ]: 247 : auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, high_max_selection_weight);
323 : :
324 [ - + + + : 247 : if (!solutions.size() || !result_bnb) {
+ - ]
325 : : // Either both BnB and Brute Force find a solution or neither does.
326 [ - + ]: 82 : assert(!result_bnb == !solutions.size());
327 : : } else {
328 : : // If brute forcing found a solution with an acceptable weight, BnB must find at least one solution with at most 16 output groups
329 : 165 : assert(result_bnb);
330 [ + - ]: 165 : result_bnb->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
331 [ - + ]: 165 : assert(result_bnb->GetWeight() <= high_max_selection_weight);
332 [ + - - + ]: 165 : assert(result_bnb->GetSelectedEffectiveValue() >= target);
333 [ + - - + ]: 165 : assert(result_bnb->GetSelectedEffectiveValue() <= target + coin_params.m_cost_of_change);
334 [ + - - + ]: 165 : assert(best_waste <= result_bnb->GetWaste());
335 [ + - + - ]: 165 : if (result_bnb->GetAlgoCompleted()) {
336 : : // If BnB exhausted the search space, it must return an optimal solution (tied on waste score)
337 [ + - - + ]: 165 : assert(best_waste == result_bnb->GetWaste());
338 : : }
339 : : }
340 : 247 : }
341 : :
342 : : enum class CoinSelectionAlgorithm {
343 : : BNB,
344 : : SRD,
345 : : KNAPSACK,
346 : : };
347 : :
348 : : template<CoinSelectionAlgorithm Algorithm>
349 : 1699 : void FuzzCoinSelectionAlgorithm(std::span<const uint8_t> buffer) {
350 : 1699 : SeedRandomStateForTest(SeedRand::ZEROS);
351 : 1699 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
352 : 1699 : std::vector<COutput> utxo_pool;
353 : :
354 : 1699 : const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
355 : 1699 : const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
356 : : // Discard feerate must be at least dust relay feerate
357 : 1699 : const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
358 : 1699 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
359 : 1699 : const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
360 : :
361 : 1699 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
362 : 1699 : CoinSelectionParams coin_params{fast_random_context};
363 : 1699 : coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
364 : 1699 : coin_params.m_long_term_feerate = long_term_fee_rate;
365 : 1699 : coin_params.m_effective_feerate = effective_fee_rate;
366 : 1699 : coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
367 [ + - ][ + - ]: 1699 : coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
[ + - ]
368 : 1699 : coin_params.m_discard_feerate = discard_fee_rate;
369 : 1699 : coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
370 [ + - ][ + - ]: 1699 : const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
[ + - ]
371 : 1699 : coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
372 [ + - ][ + - ]: 3398 : CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
[ + - ]
373 [ + - + - ]: 1699 : const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
[ + - + - ]
[ + - + - ]
374 [ + + ]: 1699 : coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
375 : :
376 : 1699 : int next_locktime{0};
377 [ + - ][ + - ]: 1699 : CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
[ + - ]
378 : :
379 : 1699 : std::vector<OutputGroup> group_pos;
380 [ + - ][ + - ]: 1699 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
[ + - ]
381 : :
382 : 1699 : int max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, std::numeric_limits<int>::max());
383 : :
384 : 1699 : std::optional<SelectionResult> result;
385 : :
386 : : if constexpr (Algorithm == CoinSelectionAlgorithm::BNB) {
387 [ + + ]: 558 : if (!coin_params.m_subtract_fee_outputs) {
388 [ + - ]: 499 : auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, max_selection_weight);
389 [ + + ]: 499 : if (result_bnb) {
390 [ + - ]: 234 : result = *result_bnb;
391 [ + - - + ]: 234 : assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
392 [ + - - + ]: 234 : assert(result_bnb->GetSelectedValue() >= target);
393 [ - + ]: 234 : assert(result_bnb->GetWeight() <= max_selection_weight);
394 [ + - ]: 234 : (void)result_bnb->GetShuffledInputVector();
395 [ + - ]: 234 : (void)result_bnb->GetInputSet();
396 : : }
397 : 499 : }
398 : : }
399 : :
400 : : if constexpr (Algorithm == CoinSelectionAlgorithm::SRD) {
401 [ + - ]: 460 : auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, max_selection_weight);
402 [ + + ]: 460 : if (result_srd) {
403 [ + - ]: 212 : result = *result_srd;
404 [ + - - + ]: 212 : assert(result_srd->GetSelectedValue() >= target);
405 [ + - - + ]: 212 : assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0);
406 [ - + ]: 212 : assert(result_srd->GetWeight() <= max_selection_weight);
407 [ + - ]: 212 : result_srd->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));
408 [ + - ]: 212 : result_srd->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
409 [ + - ]: 212 : (void)result_srd->GetShuffledInputVector();
410 [ + - ]: 212 : (void)result_srd->GetInputSet();
411 : : }
412 : 0 : }
413 : :
414 : : if constexpr (Algorithm == CoinSelectionAlgorithm::KNAPSACK) {
415 : 681 : std::vector<OutputGroup> group_all;
416 [ + - ]: 681 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
417 : :
418 [ + + ]: 248153 : for (const OutputGroup& group : group_all) {
419 [ + - ]: 247472 : const CoinEligibilityFilter filter{fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>()};
420 [ + - ]: 247472 : (void)group.EligibleForSpending(filter);
421 : : }
422 : :
423 [ + - ]: 681 : CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
424 [ + - ]: 681 : auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, max_selection_weight);
425 : : // If the total balance is sufficient for the target and we are not using
426 : : // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
427 [ + + + + : 681 : if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
+ - + + ]
428 [ - + ]: 294 : assert(result_knapsack);
429 : : }
430 [ + + ]: 681 : if (result_knapsack) {
431 [ + - ]: 527 : result = *result_knapsack;
432 [ + - - + ]: 527 : assert(result_knapsack->GetSelectedValue() >= target);
433 [ - + ]: 527 : assert(result_knapsack->GetWeight() <= max_selection_weight);
434 [ + - ]: 527 : result_knapsack->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));
435 [ + - ]: 527 : result_knapsack->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
436 [ + - ]: 527 : (void)result_knapsack->GetShuffledInputVector();
437 [ + - ]: 527 : (void)result_knapsack->GetInputSet();
438 : : }
439 : 681 : }
440 : :
441 : 1699 : std::vector<COutput> utxos;
442 [ + - ][ + - ]: 1699 : CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
[ + - ]
443 [ + + ][ + + ]: 1699 : if (new_total_balance > 0) {
[ + + ]
444 : 507 : OutputSet new_utxo_pool;
445 [ + - + + ]: 198756 : for (const auto& utxo : utxos) {
[ + - + + ]
[ + - + + ]
446 [ + - ][ + - ]: 396498 : new_utxo_pool.insert(std::make_shared<COutput>(utxo));
[ + - ]
447 : : }
448 [ + + ][ + + ]: 507 : if (result) {
[ + + ]
449 [ + - + - ]: 674 : const auto weight{result->GetWeight()};
[ + - + - ]
[ + - + - ]
450 [ + - ][ + - ]: 337 : result->AddInputs(new_utxo_pool, subtract_fee_outputs);
[ + - ]
451 [ - + ][ - + ]: 337 : assert(result->GetWeight() > weight);
[ - + ]
452 : : }
453 : 507 : }
454 : :
455 : 1699 : std::vector<COutput> manual_inputs;
456 [ + - ][ + - ]: 1699 : CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
[ + - ]
457 [ + + ][ + + ]: 1699 : if (manual_balance == 0) return;
[ + + ]
458 [ + - ][ + - ]: 374 : auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
[ + - ]
459 [ + + ][ + + ]: 374 : if (result) {
[ + + ]
460 [ + - ][ + - ]: 257 : const CAmount old_target{result->GetTarget()};
[ + - ]
461 [ + - + - : 257 : const OutputSet input_set{result->GetInputSet()};
+ - ][ + -
+ - + - ]
[ + - + -
+ - ]
462 [ + - ][ + - ]: 257 : const int old_weight{result->GetWeight()};
[ + - ]
463 [ + - ][ + - ]: 257 : result->Merge(manual_selection);
[ + - ]
464 [ + - - + : 257 : assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
- + ][ + -
- + - + ]
[ + - - +
- + ]
465 [ - + ][ - + ]: 257 : assert(result->GetTarget() == old_target + manual_selection.GetTarget());
[ - + ]
466 [ - + ][ - + ]: 257 : assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
[ - + ]
467 : 257 : }
468 : 1699 : }
469 : :
470 [ + - ]: 1032 : FUZZ_TARGET(coinselection_bnb) {
471 : 558 : FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::BNB>(buffer);
472 : 558 : }
473 : :
474 [ + - ]: 934 : FUZZ_TARGET(coinselection_srd) {
475 : 460 : FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::SRD>(buffer);
476 : 460 : }
477 : :
478 [ + - ]: 1155 : FUZZ_TARGET(coinselection_knapsack) {
479 : 681 : FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(buffer);
480 : 681 : }
481 : :
482 : : } // namespace wallet
|
