Bitcoin Core  24.99.0
P2P Digital Currency
coinselection.cpp
Go to the documentation of this file.
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>
8 #include <test/fuzz/fuzz.h>
9 #include <test/fuzz/util.h>
10 #include <test/util/setup_common.h>
11 #include <wallet/coinselection.h>
12 
13 #include <vector>
14 
15 namespace wallet {
16 
17 static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
18 {
20  tx.vout.resize(n_input + 1);
21  tx.vout[n_input].nValue = value;
22  tx.nLockTime = locktime; // all transactions get different hashes
23  coins.emplace_back(COutPoint(tx.GetHash(), n_input), tx.vout.at(n_input), /*depth=*/0, n_input_bytes, /*spendable=*/true, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, fee_rate);
24 }
25 
26 // Randomly distribute coins to instances of OutputGroup
27 static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
28 {
29  auto output_group = OutputGroup(coin_params);
30  bool valid_outputgroup{false};
31  for (auto& coin : coins) {
32  output_group.Insert(coin, /*ancestors=*/0, /*descendants=*/0, positive_only);
33  // If positive_only was specified, nothing may have been inserted, leading to an empty output group
34  // that would be invalid for the BnB algorithm
35  valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
36  if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
37  output_groups.push_back(output_group);
38  output_group = OutputGroup(coin_params);
39  valid_outputgroup = false;
40  }
41  }
42  if (valid_outputgroup) output_groups.push_back(output_group);
43 }
44 
45 FUZZ_TARGET(coinselection)
46 {
47  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
48  std::vector<COutput> utxo_pool;
49 
50  const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
51  const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
52  const CAmount cost_of_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
53  const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
54  const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
55 
56  FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
57  CoinSelectionParams coin_params{fast_random_context};
58  coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
59  coin_params.m_long_term_feerate = long_term_fee_rate;
60  coin_params.m_effective_feerate = effective_fee_rate;
61  coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
62  coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
63 
64  // Create some coins
65  CAmount total_balance{0};
66  int next_locktime{0};
67  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
68  {
69  const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
70  const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(100, 10000)};
71  const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
72  if (total_balance + amount >= MAX_MONEY) {
73  break;
74  }
75  AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
76  total_balance += amount;
77  }
78 
79  std::vector<OutputGroup> group_pos;
80  GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
81  std::vector<OutputGroup> group_all;
82  GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
83 
84  // Run coinselection algorithms
85  const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change);
86 
87  auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context);
88  if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
89 
90  CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
91  auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context);
92  if (result_knapsack) result_knapsack->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
93 
94  // If the total balance is sufficient for the target and we are not using
95  // effective values, Knapsack should always find a solution.
96  if (total_balance >= target && subtract_fee_outputs) {
97  assert(result_knapsack);
98  }
99 }
100 
101 } // namespace wallet
static constexpr CAmount MAX_MONEY
No amount larger than this (in satoshi) is valid.
Definition: amount.h:26
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
static constexpr CAmount COIN
The amount of satoshis in one BTC.
Definition: amount.h:15
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:35
Fast randomness source.
Definition: random.h:143
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:18
Definition: node.h:39
static void AddCoin(const CAmount &value, int n_input, int n_input_bytes, int locktime, std::vector< COutput > &coins, CFeeRate fee_rate)
CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext &rng)
Choose a random change target for each transaction to make it harder to fingerprint the Core wallet b...
std::vector< OutputGroup > & GroupCoins(const std::vector< COutput > &available_coins)
FUZZ_TARGET(coinselection)
std::optional< SelectionResult > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value, FastRandomContext &rng)
Select coins by Single Random Draw.
std::optional< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue, CAmount change_target, FastRandomContext &rng)
std::optional< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change)
A mutable version of CTransaction.
Definition: transaction.h:373
uint256 GetHash() const
Compute the hash of this CMutableTransaction.
Definition: transaction.cpp:68
std::vector< CTxOut > vout
Definition: transaction.h:375
Parameters for one iteration of Coin Selection.
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
A group of UTXOs paid to the same output script.
CAmount ConsumeMoney(FuzzedDataProvider &fuzzed_data_provider, const std::optional< CAmount > &max) noexcept
Definition: util.cpp:302
uint256 ConsumeUInt256(FuzzedDataProvider &fuzzed_data_provider) noexcept
Definition: util.h:202
assert(!tx.IsCoinBase())