Bitcoin Core  24.99.0
P2P Digital Currency
coinselection.h
Go to the documentation of this file.
1 // Copyright (c) 2017-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 #ifndef BITCOIN_WALLET_COINSELECTION_H
6 #define BITCOIN_WALLET_COINSELECTION_H
7 
8 #include <consensus/amount.h>
9 #include <consensus/consensus.h>
10 #include <policy/feerate.h>
11 #include <primitives/transaction.h>
12 #include <random.h>
13 #include <util/system.h>
14 #include <util/check.h>
15 
16 #include <optional>
17 
18 namespace wallet {
20 static constexpr CAmount CHANGE_LOWER{50000};
22 static constexpr CAmount CHANGE_UPPER{1000000};
23 
25 struct COutput {
26 private:
28  std::optional<CAmount> effective_value;
29 
31  std::optional<CAmount> fee;
32 
33 public:
36 
39 
45  int depth;
46 
49 
51  bool spendable;
52 
54  bool solvable;
55 
61  bool safe;
62 
64  int64_t time;
65 
67  bool from_me;
68 
71 
72  COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const std::optional<CFeeRate> feerate = std::nullopt)
73  : outpoint{outpoint},
74  txout{txout},
75  depth{depth},
79  safe{safe},
80  time{time},
82  {
83  if (feerate) {
84  fee = input_bytes < 0 ? 0 : feerate.value().GetFee(input_bytes);
85  effective_value = txout.nValue - fee.value();
86  }
87  }
88 
89  COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const CAmount fees)
91  {
92  // if input_bytes is unknown, then fees should be 0, if input_bytes is known, then the fees should be a positive integer or 0 (input_bytes known and fees = 0 only happens in the tests)
93  assert((input_bytes < 0 && fees == 0) || (input_bytes > 0 && fees >= 0));
94  fee = fees;
95  effective_value = txout.nValue - fee.value();
96  }
97 
98  std::string ToString() const;
99 
100  bool operator<(const COutput& rhs) const
101  {
102  return outpoint < rhs.outpoint;
103  }
104 
105  CAmount GetFee() const
106  {
107  assert(fee.has_value());
108  return fee.value();
109  }
110 
112  {
113  assert(effective_value.has_value());
114  return effective_value.value();
115  }
116 
117  bool HasEffectiveValue() const { return effective_value.has_value(); }
118 };
119 
125  size_t change_output_size = 0;
127  size_t change_spend_size = 0;
148  size_t tx_noinputs_size = 0;
155 
157  CAmount min_change_target, CFeeRate effective_feerate,
158  CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial)
159  : rng_fast{rng_fast},
162  m_min_change_target(min_change_target),
163  m_effective_feerate(effective_feerate),
164  m_long_term_feerate(long_term_feerate),
165  m_discard_feerate(discard_feerate),
167  m_avoid_partial_spends(avoid_partial)
168  {
169  }
171  : rng_fast{rng_fast} {}
172 };
173 
178 {
181  const int conf_mine;
183  const int conf_theirs;
185  const uint64_t max_ancestors;
187  const uint64_t max_descendants;
189  const bool m_include_partial_groups{false};
190 
195 };
196 
199 {
201  std::vector<COutput> m_outputs;
205  bool m_from_me{true};
209  int m_depth{999};
212  size_t m_ancestors{0};
214  size_t m_descendants{0};
231  int m_weight{0};
232 
238  {}
239 
240  void Insert(const COutput& output, size_t ancestors, size_t descendants, bool positive_only);
241  bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
242  CAmount GetSelectionAmount() const;
243 };
244 
262 [[nodiscard]] CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
263 
264 
279 [[nodiscard]] CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng);
280 
281 enum class SelectionAlgorithm : uint8_t
282 {
283  BNB = 0,
284  KNAPSACK = 1,
285  SRD = 2,
286  MANUAL = 3,
287 };
288 
289 std::string GetAlgorithmName(const SelectionAlgorithm algo);
290 
292 {
293 private:
295  std::set<COutput> m_selected_inputs;
301  bool m_use_effective{false};
303  std::optional<CAmount> m_waste;
305  int m_weight{0};
306 
307  template<typename T>
308  void InsertInputs(const T& inputs)
309  {
310  // Store sum of combined input sets to check that the results have no shared UTXOs
311  const size_t expected_count = m_selected_inputs.size() + inputs.size();
313  if (m_selected_inputs.size() != expected_count) {
314  throw std::runtime_error(STR_INTERNAL_BUG("Shared UTXOs among selection results"));
315  }
316  }
317 
318 public:
319  explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
320  : m_target(target), m_algo(algo) {}
321 
322  SelectionResult() = delete;
323 
325  [[nodiscard]] CAmount GetSelectedValue() const;
326 
327  [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
328 
329  void Clear();
330 
331  void AddInput(const OutputGroup& group);
332  void AddInputs(const std::set<COutput>& inputs, bool subtract_fee_outputs);
333 
335  void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee);
336  [[nodiscard]] CAmount GetWaste() const;
337 
344  void Merge(const SelectionResult& other);
345 
347  const std::set<COutput>& GetInputSet() const;
349  std::vector<COutput> GetShuffledInputVector() const;
350 
351  bool operator<(SelectionResult other) const;
352 
370  CAmount GetChange(const CAmount min_viable_change, const CAmount change_fee) const;
371 
372  CAmount GetTarget() const { return m_target; }
373 
374  SelectionAlgorithm GetAlgo() const { return m_algo; }
375 
376  int GetWeight() const { return m_weight; }
377 };
378 
379 std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change);
380 
388 std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng);
389 
390 // Original coin selection algorithm as a fallback
391 std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
392  CAmount change_target, FastRandomContext& rng);
393 } // namespace wallet
394 
395 #endif // BITCOIN_WALLET_COINSELECTION_H
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
#define STR_INTERNAL_BUG(msg)
Definition: check.h:23
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
An output of a transaction.
Definition: transaction.h:158
CAmount nValue
Definition: transaction.h:160
Fast randomness source.
Definition: random.h:144
void insert(Tdst &dst, const Tsrc &src)
Simplification of std insertion.
Definition: system.h:539
Definition: node.h:39
static constexpr CAmount CHANGE_UPPER
upper bound for randomly-chosen target change amount
Definition: coinselection.h:22
CAmount GetSelectionWaste(const std::set< COutput > &inputs, CAmount change_cost, CAmount target, bool use_effective_value)
Compute the waste for this result given the cost of change and the opportunity cost of spending these...
static constexpr CAmount CHANGE_LOWER
lower bound for randomly-chosen target change amount
Definition: coinselection.h:20
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...
SelectionAlgorithm
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::string GetAlgorithmName(const SelectionAlgorithm algo)
std::optional< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change)
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:25
CAmount long_term_fee
The fee required to spend this output at the consolidation feerate.
Definition: coinselection.h:70
bool from_me
Whether the transaction containing this output is sent from the owning wallet.
Definition: coinselection.h:67
COutPoint outpoint
The outpoint identifying this UTXO.
Definition: coinselection.h:35
std::optional< CAmount > effective_value
The output's value minus fees required to spend it.
Definition: coinselection.h:28
bool solvable
Whether we know how to spend this output, ignoring the lack of keys.
Definition: coinselection.h:54
int64_t time
The time of the transaction containing this output as determined by CWalletTx::nTimeSmart.
Definition: coinselection.h:64
int depth
Depth in block chain.
Definition: coinselection.h:45
std::string ToString() const
bool safe
Whether this output is considered safe to spend.
Definition: coinselection.h:61
bool spendable
Whether we have the private keys to spend this output.
Definition: coinselection.h:51
CTxOut txout
The output itself.
Definition: coinselection.h:38
COutput(const COutPoint &outpoint, const CTxOut &txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const CAmount fees)
Definition: coinselection.h:89
CAmount GetFee() const
int input_bytes
Pre-computed estimated size of this output as a fully-signed input in a transaction.
Definition: coinselection.h:48
CAmount GetEffectiveValue() const
bool operator<(const COutput &rhs) const
bool HasEffectiveValue() const
std::optional< CAmount > fee
The fee required to spend this output at the transaction's target feerate.
Definition: coinselection.h:31
COutput(const COutPoint &outpoint, const CTxOut &txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const std::optional< CFeeRate > feerate=std::nullopt)
Definition: coinselection.h:72
Parameters for filtering which OutputGroups we may use in coin selection.
const uint64_t max_ancestors
Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup.
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants)
const bool m_include_partial_groups
When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any...
const uint64_t max_descendants
Maximum number of descendants that a single UTXO in the OutputGroup may have.
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors)
const int conf_theirs
Minimum number of confirmations for outputs received from a different wallet.
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants, bool include_partial)
const int conf_mine
Minimum number of confirmations for outputs that we sent to ourselves.
Parameters for one iteration of Coin Selection.
CoinSelectionParams(FastRandomContext &rng_fast, size_t change_output_size, size_t change_spend_size, CAmount min_change_target, CFeeRate effective_feerate, CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial)
FastRandomContext & rng_fast
Randomness to use in the context of coin selection.
CAmount m_min_change_target
Mininmum change to target in Knapsack solver: select coins to cover the payment and at least this val...
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
CoinSelectionParams(FastRandomContext &rng_fast)
size_t change_output_size
Size of a change output in bytes, determined by the output type.
CFeeRate m_effective_feerate
The targeted feerate of the transaction being built.
CAmount min_viable_change
Minimum amount for creating a change output.
CAmount m_cost_of_change
Cost of creating the change output + cost of spending the change output in the future.
CAmount m_change_fee
Cost of creating the change output.
CFeeRate m_long_term_feerate
The feerate estimate used to estimate an upper bound on what should be sufficient to spend the change...
CFeeRate m_discard_feerate
If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees.
size_t change_spend_size
Size of the input to spend a change output in virtual bytes.
size_t tx_noinputs_size
Size of the transaction before coin selection, consisting of the header and recipient output(s),...
bool m_avoid_partial_spends
When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs associated with t...
A group of UTXOs paid to the same output script.
CFeeRate m_long_term_feerate
The feerate for spending a created change output eventually (i.e.
bool m_from_me
Whether the UTXOs were sent by the wallet to itself.
OutputGroup(const CoinSelectionParams &params)
CAmount m_value
The total value of the UTXOs in sum.
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
void Insert(const COutput &output, size_t ancestors, size_t descendants, bool positive_only)
CAmount GetSelectionAmount() const
std::vector< COutput > m_outputs
The list of UTXOs contained in this output group.
int m_depth
The minimum number of confirmations the UTXOs in the group have.
int m_weight
Total weight of the UTXOs in this group.
bool EligibleForSpending(const CoinEligibilityFilter &eligibility_filter) const
CAmount effective_value
The value of the UTXOs after deducting the cost of spending them at the effective feerate.
size_t m_ancestors
The aggregated count of unconfirmed ancestors of all UTXOs in this group.
CAmount fee
The fee to spend these UTXOs at the effective feerate.
CAmount long_term_fee
The fee to spend these UTXOs at the long term feerate.
CFeeRate m_effective_feerate
The target feerate of the transaction we're trying to build.
size_t m_descendants
The maximum count of descendants of a single UTXO in this output group.
int m_weight
Total weight of the selected inputs.
bool operator<(SelectionResult other) const
void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
Calculates and stores the waste for this selection via GetSelectionWaste.
void AddInputs(const std::set< COutput > &inputs, bool subtract_fee_outputs)
std::vector< COutput > GetShuffledInputVector() const
Get the vector of COutputs that will be used to fill in a CTransaction's vin.
const std::set< COutput > & GetInputSet() const
Get m_selected_inputs.
void Merge(const SelectionResult &other)
Combines the.
SelectionAlgorithm m_algo
The algorithm used to produce this result.
void AddInput(const OutputGroup &group)
CAmount GetSelectedEffectiveValue() const
CAmount m_target
The target the algorithm selected for.
CAmount GetChange(const CAmount min_viable_change, const CAmount change_fee) const
Get the amount for the change output after paying needed fees.
void InsertInputs(const T &inputs)
SelectionResult(const CAmount target, SelectionAlgorithm algo)
std::set< COutput > m_selected_inputs
Set of inputs selected by the algorithm to use in the transaction.
CAmount GetSelectedValue() const
Get the sum of the input values.
CAmount GetTarget() const
SelectionAlgorithm GetAlgo() const
std::optional< CAmount > m_waste
The computed waste.
bool m_use_effective
Whether the input values for calculations should be the effective value (true) or normal value (false...
CAmount GetWaste() const
assert(!tx.IsCoinBase())