Bitcoin Core  26.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 <numeric>
15 #include <vector>
16 
17 namespace wallet {
18 
19 static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
20 {
22  tx.vout.resize(n_input + 1);
23  tx.vout[n_input].nValue = value;
24  tx.nLockTime = locktime; // all transactions get different hashes
25  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);
26 }
27 
28 // Randomly distribute coins to instances of OutputGroup
29 static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
30 {
31  auto output_group = OutputGroup(coin_params);
32  bool valid_outputgroup{false};
33  for (auto& coin : coins) {
34  if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
35  output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*descendants=*/0);
36  }
37  // If positive_only was specified, nothing was inserted, leading to an empty output group
38  // that would be invalid for the BnB algorithm
39  valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
40  if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
41  output_groups.push_back(output_group);
42  output_group = OutputGroup(coin_params);
43  valid_outputgroup = false;
44  }
45  }
46  if (valid_outputgroup) output_groups.push_back(output_group);
47 }
48 
49 static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
50 {
51  CAmount total_balance{0};
52  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
53  {
54  const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
55  const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
56  const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
57  if (total_balance + amount >= MAX_MONEY) {
58  break;
59  }
60  AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
61  total_balance += amount;
62  }
63 
64  return total_balance;
65 }
66 
67 static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
68 {
69  SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
70  std::set<std::shared_ptr<COutput>> utxo_pool;
71  for (const auto& utxo : utxos) {
72  utxo_pool.insert(std::make_shared<COutput>(utxo));
73  }
74  result.AddInputs(utxo_pool, subtract_fee_outputs);
75  return result;
76 }
77 
78 // Returns true if the result contains an error and the message is not empty
79 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
80 
81 FUZZ_TARGET(coin_grinder)
82 {
83  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
84  std::vector<COutput> utxo_pool;
85 
86  const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
87 
88  FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
89  CoinSelectionParams coin_params{fast_random_context};
90  coin_params.m_subtract_fee_outputs = fuzzed_data_provider.ConsumeBool();
91  coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
92  coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
93  coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
94  coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
95  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  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  coin_params.m_min_change_target = CHANGE_LOWER + coin_params.m_change_fee;
99 
100  // Create some coins
101  CAmount total_balance{0};
102  CAmount max_spendable{0};
103  int next_locktime{0};
104  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
105  {
106  const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
107  const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
108  const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
109  if (total_balance + amount >= MAX_MONEY) {
110  break;
111  }
112  AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
113  total_balance += amount;
114  CAmount eff_value = amount - coin_params.m_effective_feerate.GetFee(n_input_bytes);
115  max_spendable += eff_value;
116  }
117 
118  std::vector<OutputGroup> group_pos;
119  GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
120 
121  // Run coinselection algorithms
122  auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, MAX_STANDARD_TX_WEIGHT);
123  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
124  assert(result_cg);
125  if (!result_cg->GetAlgoCompleted()) return; // Bail out if CoinGrinder solution is not optimal
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 && result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0) { // exclude any srd solutions that don’t have change, err on excluding
129  assert(result_srd->GetWeight() >= result_cg->GetWeight());
130  }
131 
132  auto result_knapsack = KnapsackSolver(group_pos, target, coin_params.m_min_change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
133  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
134  assert(result_knapsack->GetWeight() >= result_cg->GetWeight());
135  }
136 }
137 
138 FUZZ_TARGET(coin_grinder_is_optimal)
139 {
140  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
141 
142  FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
143  CoinSelectionParams coin_params{fast_random_context};
144  coin_params.m_subtract_fee_outputs = false;
145  // Set effective feerate up to MAX_MONEY sats per 1'000'000 vB (2'100'000'000 sat/vB = 21'000 BTC/kvB).
146  coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, MAX_MONEY), 1'000'000};
147  coin_params.m_min_change_target = ConsumeMoney(fuzzed_data_provider);
148 
149  // Create some coins
150  CAmount max_spendable{0};
151  int next_locktime{0};
152  static constexpr unsigned max_output_groups{16};
153  std::vector<OutputGroup> group_pos;
154  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), max_output_groups)
155  {
156  // With maximum m_effective_feerate and n_input_bytes = 1'000'000, input_fee <= MAX_MONEY.
157  const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 1'000'000)};
158  // Only make UTXOs with positive effective value
159  const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes);
160  // Ensure that each UTXO has at least an effective value of 1 sat
161  const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
162  const CAmount amount{eff_value + input_fee};
163  std::vector<COutput> temp_utxo_pool;
164 
165  AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
166  max_spendable += eff_value;
167 
168  auto output_group = OutputGroup(coin_params);
169  output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*descendants=*/0);
170  group_pos.push_back(output_group);
171  }
172  size_t num_groups = group_pos.size();
173  assert(num_groups <= max_output_groups);
174 
175  // Only choose targets below max_spendable
176  const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_min_change_target))};
177 
178  // Brute force optimal solution
179  CAmount best_amount{MAX_MONEY};
180  int best_weight{std::numeric_limits<int>::max()};
181  for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
182  CAmount subset_amount{0};
183  int subset_weight{0};
184  for (unsigned i = 0; i < num_groups; ++i) {
185  if ((pattern >> i) & 1) {
186  subset_amount += group_pos[i].GetSelectionAmount();
187  subset_weight += group_pos[i].m_weight;
188  }
189  }
190  if ((subset_amount >= target + coin_params.m_min_change_target) && (subset_weight < best_weight || (subset_weight == best_weight && subset_amount < best_amount))) {
191  best_weight = subset_weight;
192  best_amount = subset_amount;
193  }
194  }
195 
196  if (best_weight < std::numeric_limits<int>::max()) {
197  // Sufficient funds and acceptable weight: CoinGrinder should find at least one solution
198  int high_max_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
199 
200  auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, high_max_weight);
201  assert(result_cg);
202  assert(result_cg->GetWeight() <= high_max_weight);
203  assert(result_cg->GetSelectedEffectiveValue() >= target + coin_params.m_min_change_target);
204  assert(best_weight < result_cg->GetWeight() || (best_weight == result_cg->GetWeight() && best_amount <= result_cg->GetSelectedEffectiveValue()));
205  if (result_cg->GetAlgoCompleted()) {
206  // If CoinGrinder exhausted the search space, it must return the optimal solution
207  assert(best_weight == result_cg->GetWeight());
208  assert(best_amount == result_cg->GetSelectedEffectiveValue());
209  }
210  }
211 
212  // CoinGrinder cannot ever find a better solution than the brute-forced best, or there is none in the first place
213  int low_max_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, best_weight - 1);
214  auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, low_max_weight);
215  // Max_weight should have been exceeded, or there were insufficient funds
216  assert(!result_cg);
217 }
218 
219 FUZZ_TARGET(coinselection)
220 {
221  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
222  std::vector<COutput> utxo_pool;
223 
224  const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
225  const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
226  // Discard feerate must be at least dust relay feerate
227  const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
228  const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
229  const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
230 
231  FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
232  CoinSelectionParams coin_params{fast_random_context};
233  coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
234  coin_params.m_long_term_feerate = long_term_fee_rate;
235  coin_params.m_effective_feerate = effective_fee_rate;
236  coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
237  coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
238  coin_params.m_discard_feerate = discard_fee_rate;
239  coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
240  const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
241  coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
242  CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
243  const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
244  coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
245 
246  int next_locktime{0};
247  CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
248 
249  std::vector<OutputGroup> group_pos;
250  GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
251  std::vector<OutputGroup> group_all;
252  GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
253 
254  for (const OutputGroup& group : group_all) {
255  const CoinEligibilityFilter filter(fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>());
256  (void)group.EligibleForSpending(filter);
257  }
258 
259  // Run coinselection algorithms
260  auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
261  SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
262  if (result_bnb) {
263  assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
264  assert(result_bnb->GetSelectedValue() >= target);
265  (void)result_bnb->GetShuffledInputVector();
266  (void)result_bnb->GetInputSet();
267  }
268 
269  auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
270  if (result_srd) {
271  assert(result_srd->GetSelectedValue() >= target);
272  assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0); // Demonstrate that SRD creates change of at least CHANGE_LOWER
273  result_srd->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
274  (void)result_srd->GetShuffledInputVector();
275  (void)result_srd->GetInputSet();
276  }
277 
278  CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
279  auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
280  if (result_knapsack) {
281  assert(result_knapsack->GetSelectedValue() >= target);
282  result_knapsack->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
283  (void)result_knapsack->GetShuffledInputVector();
284  (void)result_knapsack->GetInputSet();
285  }
286 
287  // If the total balance is sufficient for the target and we are not using
288  // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
289  if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
290  assert(result_knapsack);
291  }
292 
293  std::vector<COutput> utxos;
294  std::vector<util::Result<SelectionResult>> results{result_srd, result_knapsack, result_bnb};
295  CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
296  if (new_total_balance > 0) {
297  std::set<std::shared_ptr<COutput>> new_utxo_pool;
298  for (const auto& utxo : utxos) {
299  new_utxo_pool.insert(std::make_shared<COutput>(utxo));
300  }
301  for (auto& result : results) {
302  if (!result) continue;
303  const auto weight{result->GetWeight()};
304  result->AddInputs(new_utxo_pool, subtract_fee_outputs);
305  assert(result->GetWeight() > weight);
306  }
307  }
308 
309  std::vector<COutput> manual_inputs;
310  CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
311  if (manual_balance == 0) return;
312  auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
313  for (auto& result : results) {
314  if (!result) continue;
315  const CAmount old_target{result->GetTarget()};
316  const std::set<std::shared_ptr<COutput>> input_set{result->GetInputSet()};
317  const int old_weight{result->GetWeight()};
318  result->Merge(manual_selection);
319  assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
320  assert(result->GetTarget() == old_target + manual_selection.GetTarget());
321  assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
322  }
323 }
324 
325 } // 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:29
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:414
An output of a transaction.
Definition: transaction.h:150
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:23
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...
util::Result< SelectionResult > CoinGrinder(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, CAmount change_target, int max_weight)
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(coin_grinder)
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:652
CAmount GetDustThreshold(const CTxOut &txout, const CFeeRate &dustRelayFeeIn)
Definition: policy.cpp:26
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
static const int MAX_SCRIPT_SIZE
Definition: script.h:39
@ OP_TRUE
Definition: script.h:83
A mutable version of CTransaction.
Definition: transaction.h:378
std::vector< CTxOut > vout
Definition: transaction.h:380
Txid GetHash() const
Compute the hash of this CMutableTransaction.
Definition: transaction.cpp:69
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:29
uint256 ConsumeUInt256(FuzzedDataProvider &fuzzed_data_provider) noexcept
Definition: util.h:169
bilingual_str Untranslated(std::string original)
Mark a bilingual_str as untranslated.
Definition: translation.h:48
assert(!tx.IsCoinBase())