Bitcoin Core  25.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>
6 #include <policy/policy.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 
18 static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
19 {
21  tx.vout.resize(n_input + 1);
22  tx.vout[n_input].nValue = value;
23  tx.nLockTime = locktime; // all transactions get different hashes
24  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 }
26 
27 // Randomly distribute coins to instances of OutputGroup
28 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  auto output_group = OutputGroup(coin_params);
31  bool valid_outputgroup{false};
32  for (auto& coin : coins) {
33  if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
34  output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*descendants=*/0);
35  }
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  valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
39  if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
40  output_groups.push_back(output_group);
41  output_group = OutputGroup(coin_params);
42  valid_outputgroup = false;
43  }
44  }
45  if (valid_outputgroup) output_groups.push_back(output_group);
46 }
47 
48 static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
49 {
50  CAmount total_balance{0};
51  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
52  {
53  const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
54  const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
55  const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
56  if (total_balance + amount >= MAX_MONEY) {
57  break;
58  }
59  AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
60  total_balance += amount;
61  }
62 
63  return total_balance;
64 }
65 
66 static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
67 {
68  SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
69  std::set<std::shared_ptr<COutput>> utxo_pool;
70  for (const auto& utxo : utxos) {
71  utxo_pool.insert(std::make_shared<COutput>(utxo));
72  }
73  result.AddInputs(utxo_pool, subtract_fee_outputs);
74  return result;
75 }
76 
77 // Returns true if the result contains an error and the message is not empty
78 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
79 
80 FUZZ_TARGET(coinselection)
81 {
82  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
83  std::vector<COutput> utxo_pool;
84 
85  const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
86  const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
87  // Discard feerate must be at least dust relay feerate
88  const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
89  const CAmount min_viable_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
90  const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
91  const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
92 
93  FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
94  CoinSelectionParams coin_params{fast_random_context};
95  coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
96  coin_params.m_long_term_feerate = long_term_fee_rate;
97  coin_params.m_effective_feerate = effective_fee_rate;
98  coin_params.min_viable_change = min_viable_change;
99  coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
100  coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
101  coin_params.m_discard_feerate = discard_fee_rate;
102  coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
103  coin_params.m_cost_of_change = coin_params.m_change_fee + coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);
104 
105  int next_locktime{0};
106  CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
107 
108  std::vector<OutputGroup> group_pos;
109  GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
110  std::vector<OutputGroup> group_all;
111  GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
112 
113  for (const OutputGroup& group : group_all) {
114  const CoinEligibilityFilter filter(fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>());
115  (void)group.EligibleForSpending(filter);
116  }
117 
118  // Run coinselection algorithms
119  auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
120  if (result_bnb) {
121  assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
122  assert(result_bnb->GetSelectedValue() >= target);
123  (void)result_bnb->GetShuffledInputVector();
124  (void)result_bnb->GetInputSet();
125  }
126 
127  auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
128  if (result_srd) {
129  assert(result_srd->GetSelectedValue() >= target);
130  assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0); // Demonstrate that SRD creates change of at least CHANGE_LOWER
131  result_srd->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
132  (void)result_srd->GetShuffledInputVector();
133  (void)result_srd->GetInputSet();
134  }
135 
136  CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
137  auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
138  if (result_knapsack) {
139  assert(result_knapsack->GetSelectedValue() >= target);
140  result_knapsack->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
141  (void)result_knapsack->GetShuffledInputVector();
142  (void)result_knapsack->GetInputSet();
143  }
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  if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
148  assert(result_knapsack);
149  }
150 
151  std::vector<COutput> utxos;
152  std::vector<util::Result<SelectionResult>> results{result_srd, result_knapsack, result_bnb};
153  CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
154  if (new_total_balance > 0) {
155  std::set<std::shared_ptr<COutput>> new_utxo_pool;
156  for (const auto& utxo : utxos) {
157  new_utxo_pool.insert(std::make_shared<COutput>(utxo));
158  }
159  for (auto& result : results) {
160  if (!result) continue;
161  const auto weight{result->GetWeight()};
162  result->AddInputs(new_utxo_pool, subtract_fee_outputs);
163  assert(result->GetWeight() > weight);
164  }
165  }
166 
167  std::vector<COutput> manual_inputs;
168  CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
169  if (manual_balance == 0) return;
170  auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
171  for (auto& result : results) {
172  if (!result) continue;
173  const CAmount old_target{result->GetTarget()};
174  const std::set<std::shared_ptr<COutput>> input_set{result->GetInputSet()};
175  const int old_weight{result->GetWeight()};
176  result->Merge(manual_selection);
177  assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
178  assert(result->GetTarget() == old_target + manual_selection.GetTarget());
179  assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
180  }
181 }
182 
183 } // 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:36
Fast randomness source.
Definition: random.h:144
T ConsumeIntegralInRange(T min, T max)
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:18
bilingual_str ErrorString(const Result< T > &result)
Definition: result.h:81
static CAmount CreateCoins(FuzzedDataProvider &fuzzed_data_provider, std::vector< COutput > &utxo_pool, CoinSelectionParams &coin_params, int &next_locktime)
util::Result< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, int max_weight)
static void AddCoin(const CAmount &value, int n_input, int n_input_bytes, int locktime, std::vector< COutput > &coins, CFeeRate fee_rate)
static constexpr CAmount CHANGE_LOWER
lower bound for randomly-chosen target change amount
Definition: coinselection.h:23
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, bool subtract_fee_outputs=false)
util::Result< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue, CAmount change_target, FastRandomContext &rng, int max_weight)
static SelectionResult ManualSelection(std::vector< COutput > &utxos, const CAmount &total_amount, const bool &subtract_fee_outputs)
FUZZ_TARGET(coinselection)
util::Result< SelectionResult > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext &rng, int max_weight)
Select coins by Single Random Draw.
static bool HasErrorMsg(const util::Result< SelectionResult > &res)
Definition: spend.cpp:651
static constexpr unsigned int DUST_RELAY_TX_FEE
Min feerate for defining dust.
Definition: policy.h:55
static constexpr int32_t MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
Definition: policy.h:27
A mutable version of CTransaction.
Definition: transaction.h:380
uint256 GetHash() const
Compute the hash of this CMutableTransaction.
Definition: transaction.cpp:68
std::vector< CTxOut > vout
Definition: transaction.h:382
bool empty() const
Definition: translation.h:29
Parameters for filtering which OutputGroups we may use in coin selection.
Parameters for one iteration of Coin Selection.
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
CFeeRate m_effective_feerate
The targeted feerate of the transaction being built.
A group of UTXOs paid to the same output script.
void AddInputs(const std::set< std::shared_ptr< COutput >> &inputs, bool subtract_fee_outputs)
CAmount GetTarget() const
CAmount ConsumeMoney(FuzzedDataProvider &fuzzed_data_provider, const std::optional< CAmount > &max) noexcept
Definition: util.cpp:30
uint256 ConsumeUInt256(FuzzedDataProvider &fuzzed_data_provider) noexcept
Definition: util.h:170
assert(!tx.IsCoinBase())