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      int best_waste{std::numeric_limits<int>::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