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