Bitcoin Core  22.99.0
P2P Digital Currency
coinselection.h
Go to the documentation of this file.
1 // Copyright (c) 2017-2021 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 <policy/feerate.h>
10 #include <primitives/transaction.h>
11 #include <random.h>
12 
13 #include <optional>
14 
15 namespace wallet {
17 static constexpr CAmount MIN_CHANGE{COIN / 100};
20 
22 class CInputCoin {
23 public:
24  CInputCoin(const CTransactionRef& tx, unsigned int i)
25  {
26  if (!tx)
27  throw std::invalid_argument("tx should not be null");
28  if (i >= tx->vout.size())
29  throw std::out_of_range("The output index is out of range");
30 
31  outpoint = COutPoint(tx->GetHash(), i);
32  txout = tx->vout[i];
34  }
35 
36  CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes) : CInputCoin(tx, i)
37  {
38  m_input_bytes = input_bytes;
39  }
40 
41  CInputCoin(const COutPoint& outpoint_in, const CTxOut& txout_in)
42  {
43  outpoint = outpoint_in;
44  txout = txout_in;
46  }
47 
48  CInputCoin(const COutPoint& outpoint_in, const CTxOut& txout_in, int input_bytes) : CInputCoin(outpoint_in, txout_in)
49  {
50  m_input_bytes = input_bytes;
51  }
52 
58 
60  int m_input_bytes{-1};
61 
62  bool operator<(const CInputCoin& rhs) const {
63  return outpoint < rhs.outpoint;
64  }
65 
66  bool operator!=(const CInputCoin& rhs) const {
67  return outpoint != rhs.outpoint;
68  }
69 
70  bool operator==(const CInputCoin& rhs) const {
71  return outpoint == rhs.outpoint;
72  }
73 };
74 
77 {
79  size_t change_output_size = 0;
81  size_t change_spend_size = 0;
95  size_t tx_noinputs_size = 0;
97  bool m_subtract_fee_outputs = false;
102 
104  CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) :
107  m_effective_feerate(effective_feerate),
108  m_long_term_feerate(long_term_feerate),
109  m_discard_feerate(discard_feerate),
111  m_avoid_partial_spends(avoid_partial)
112  {}
114 };
115 
120 {
123  const int conf_mine;
125  const int conf_theirs;
127  const uint64_t max_ancestors;
129  const uint64_t max_descendants;
131  const bool m_include_partial_groups{false};
132 
136 };
137 
140 {
142  std::vector<CInputCoin> m_outputs;
146  bool m_from_me{true};
150  int m_depth{999};
153  size_t m_ancestors{0};
155  size_t m_descendants{0};
171 
177  {}
178 
179  void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only);
180  bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
181  CAmount GetSelectionAmount() const;
182 };
183 
201 [[nodiscard]] CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
202 
204 {
205 private:
207  std::set<CInputCoin> m_selected_inputs;
211  bool m_use_effective{false};
213  std::optional<CAmount> m_waste;
214 
215 public:
216  explicit SelectionResult(const CAmount target)
217  : m_target(target) {}
218 
219  SelectionResult() = delete;
220 
222  [[nodiscard]] CAmount GetSelectedValue() const;
223 
224  void Clear();
225 
226  void AddInput(const OutputGroup& group);
227 
229  void ComputeAndSetWaste(CAmount change_cost);
230  [[nodiscard]] CAmount GetWaste() const;
231 
233  const std::set<CInputCoin>& GetInputSet() const;
235  std::vector<CInputCoin> GetShuffledInputVector() const;
236 
237  bool operator<(SelectionResult other) const;
238 };
239 
240 std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change);
241 
249 std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value);
250 
251 // Original coin selection algorithm as a fallback
252 std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue);
253 } // namespace wallet
254 
255 #endif // BITCOIN_WALLET_COINSELECTION_H
wallet::CoinSelectionParams::tx_noinputs_size
size_t tx_noinputs_size
Size of the transaction before coin selection, consisting of the header and recipient output(s),...
Definition: coinselection.h:95
wallet::SelectCoinsSRD
std::optional< SelectionResult > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value)
Select coins by Single Random Draw.
Definition: coinselection.cpp:170
wallet::OutputGroup::m_subtract_fee_outputs
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
Definition: coinselection.h:170
feerate.h
wallet::OutputGroup::m_outputs
std::vector< CInputCoin > m_outputs
The list of UTXOs contained in this output group.
Definition: coinselection.h:142
wallet::CoinEligibilityFilter::CoinEligibilityFilter
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors)
Definition: coinselection.h:133
wallet::SelectionResult::GetSelectedValue
CAmount GetSelectedValue() const
Get the sum of the input values.
Definition: coinselection.cpp:397
wallet::CoinSelectionParams::m_discard_feerate
CFeeRate m_discard_feerate
If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees.
Definition: coinselection.h:92
transaction.h
wallet::CInputCoin::CInputCoin
CInputCoin(const COutPoint &outpoint_in, const CTxOut &txout_in)
Definition: coinselection.h:41
wallet::CInputCoin::CInputCoin
CInputCoin(const CTransactionRef &tx, unsigned int i, int input_bytes)
Definition: coinselection.h:36
wallet::SelectionResult::Clear
void Clear()
Definition: coinselection.cpp:402
wallet::OutputGroup::long_term_fee
CAmount long_term_fee
The fee to spend these UTXOs at the long term feerate.
Definition: coinselection.h:163
wallet::OutputGroup::Insert
void Insert(const CInputCoin &output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only)
Definition: coinselection.cpp:316
wallet::CoinEligibilityFilter::m_include_partial_groups
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...
Definition: coinselection.h:131
wallet::GetSelectionWaste
CAmount GetSelectionWaste(const std::set< CInputCoin > &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...
Definition: coinselection.cpp:360
wallet::CInputCoin::txout
CTxOut txout
Definition: coinselection.h:54
wallet::SelectionResult::SelectionResult
SelectionResult(const CAmount target)
Definition: coinselection.h:216
wallet
Definition: node.h:38
wallet::OutputGroup::m_long_term_feerate
CFeeRate m_long_term_feerate
The feerate for spending a created change output eventually (i.e.
Definition: coinselection.h:167
wallet::OutputGroup::m_descendants
size_t m_descendants
The maximum count of descendants of a single UTXO in this output group.
Definition: coinselection.h:155
wallet::OutputGroup::effective_value
CAmount effective_value
The value of the UTXOs after deducting the cost of spending them at the effective feerate.
Definition: coinselection.h:157
wallet::SelectionResult::GetInputSet
const std::set< CInputCoin > & GetInputSet() const
Get m_selected_inputs.
Definition: coinselection.cpp:414
CTransactionRef
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:406
wallet::OutputGroup::GetSelectionAmount
CAmount GetSelectionAmount() const
Definition: coinselection.cpp:355
wallet::SelectionResult::GetWaste
CAmount GetWaste() const
Definition: coinselection.cpp:392
wallet::KnapsackSolver
std::optional< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue)
Definition: coinselection.cpp:238
wallet::CoinSelectionParams::m_cost_of_change
CAmount m_cost_of_change
Cost of creating the change output + cost of spending the change output in the future.
Definition: coinselection.h:85
CFeeRate
Fee rate in satoshis per kilobyte: CAmount / kB.
Definition: feerate.h:29
wallet::CoinSelectionParams::m_avoid_partial_spends
bool m_avoid_partial_spends
When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs associated with t...
Definition: coinselection.h:101
wallet::CoinEligibilityFilter::max_ancestors
const uint64_t max_ancestors
Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup.
Definition: coinselection.h:127
wallet::CInputCoin::operator!=
bool operator!=(const CInputCoin &rhs) const
Definition: coinselection.h:66
CTxOut::nValue
CAmount nValue
Definition: transaction.h:151
wallet::OutputGroup::m_effective_feerate
CFeeRate m_effective_feerate
The target feerate of the transaction we're trying to build.
Definition: coinselection.h:161
random.h
wallet::SelectionResult::m_use_effective
bool m_use_effective
Whether the input values for calculations should be the effective value (true) or normal value (false...
Definition: coinselection.h:211
wallet::CoinSelectionParams::m_effective_feerate
CFeeRate m_effective_feerate
The targeted feerate of the transaction being built.
Definition: coinselection.h:87
wallet::SelectionResult::ComputeAndSetWaste
void ComputeAndSetWaste(CAmount change_cost)
Calculates and stores the waste for this selection via GetSelectionWaste.
Definition: coinselection.cpp:387
wallet::CoinEligibilityFilter::CoinEligibilityFilter
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants, bool include_partial)
Definition: coinselection.h:135
wallet::CInputCoin::operator<
bool operator<(const CInputCoin &rhs) const
Definition: coinselection.h:62
CTxOut
An output of a transaction.
Definition: transaction.h:148
wallet::SelectionResult::m_target
const CAmount m_target
The target the algorithm selected for.
Definition: coinselection.h:209
wallet::CoinSelectionParams::CoinSelectionParams
CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial)
Definition: coinselection.h:103
wallet::SelectionResult::SelectionResult
SelectionResult()=delete
wallet::OutputGroup::m_value
CAmount m_value
The total value of the UTXOs in sum.
Definition: coinselection.h:148
wallet::OutputGroup::m_from_me
bool m_from_me
Whether the UTXOs were sent by the wallet to itself.
Definition: coinselection.h:146
CAmount
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
wallet::OutputGroup::m_depth
int m_depth
The minimum number of confirmations the UTXOs in the group have.
Definition: coinselection.h:150
wallet::CoinEligibilityFilter::max_descendants
const uint64_t max_descendants
Maximum number of descendants that a single UTXO in the OutputGroup may have.
Definition: coinselection.h:129
wallet::OutputGroup
A group of UTXOs paid to the same output script.
Definition: coinselection.h:139
wallet::CoinSelectionParams::change_spend_size
size_t change_spend_size
Size of the input to spend a change output in virtual bytes.
Definition: coinselection.h:81
wallet::CInputCoin
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:22
wallet::CInputCoin::m_input_bytes
int m_input_bytes
Pre-computed estimated size of this output as a fully-signed input in a transaction.
Definition: coinselection.h:60
wallet::SelectCoinsBnB
std::optional< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change)
Definition: coinselection.cpp:65
wallet::CInputCoin::outpoint
COutPoint outpoint
Definition: coinselection.h:53
wallet::OutputGroup::EligibleForSpending
bool EligibleForSpending(const CoinEligibilityFilter &eligibility_filter) const
Definition: coinselection.cpp:348
wallet::CInputCoin::m_long_term_fee
CAmount m_long_term_fee
Definition: coinselection.h:57
wallet::CInputCoin::effective_value
CAmount effective_value
Definition: coinselection.h:55
wallet::CoinSelectionParams::m_change_fee
CAmount m_change_fee
Cost of creating the change output.
Definition: coinselection.h:83
wallet::OutputGroup::OutputGroup
OutputGroup()
Definition: coinselection.h:172
wallet::CInputCoin::CInputCoin
CInputCoin(const CTransactionRef &tx, unsigned int i)
Definition: coinselection.h:24
wallet::MIN_CHANGE
static constexpr CAmount MIN_CHANGE
target minimum change amount
Definition: coinselection.h:17
wallet::CInputCoin::operator==
bool operator==(const CInputCoin &rhs) const
Definition: coinselection.h:70
wallet::CoinSelectionParams::m_long_term_feerate
CFeeRate m_long_term_feerate
The feerate estimate used to estimate an upper bound on what should be sufficient to spend the change...
Definition: coinselection.h:90
wallet::SelectionResult::GetShuffledInputVector
std::vector< CInputCoin > GetShuffledInputVector() const
Get the vector of CInputCoins that will be used to fill in a CTransaction's vin.
Definition: coinselection.cpp:419
wallet::MIN_FINAL_CHANGE
static const CAmount MIN_FINAL_CHANGE
final minimum change amount after paying for fees
Definition: coinselection.h:19
wallet::CoinSelectionParams
Parameters for one iteration of Coin Selection.
Definition: coinselection.h:76
wallet::CoinEligibilityFilter::CoinEligibilityFilter
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants)
Definition: coinselection.h:134
wallet::OutputGroup::m_ancestors
size_t m_ancestors
The aggregated count of unconfirmed ancestors of all UTXOs in this group.
Definition: coinselection.h:153
wallet::CoinSelectionParams::CoinSelectionParams
CoinSelectionParams()
Definition: coinselection.h:113
wallet::CoinSelectionParams::m_subtract_fee_outputs
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
Definition: coinselection.h:97
wallet::SelectionResult::AddInput
void AddInput(const OutputGroup &group)
Definition: coinselection.cpp:408
wallet::CoinEligibilityFilter::conf_mine
const int conf_mine
Minimum number of confirmations for outputs that we sent to ourselves.
Definition: coinselection.h:123
wallet::CInputCoin::CInputCoin
CInputCoin(const COutPoint &outpoint_in, const CTxOut &txout_in, int input_bytes)
Definition: coinselection.h:48
wallet::SelectionResult::m_waste
std::optional< CAmount > m_waste
The computed waste.
Definition: coinselection.h:213
COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:26
wallet::CInputCoin::m_fee
CAmount m_fee
Definition: coinselection.h:56
wallet::OutputGroup::fee
CAmount fee
The fee to spend these UTXOs at the effective feerate.
Definition: coinselection.h:159
COIN
static constexpr CAmount COIN
The amount of satoshis in one BTC.
Definition: amount.h:15
wallet::CoinEligibilityFilter::conf_theirs
const int conf_theirs
Minimum number of confirmations for outputs received from a different wallet.
Definition: coinselection.h:125
wallet::SelectionResult
Definition: coinselection.h:203
amount.h
wallet::CoinEligibilityFilter
Parameters for filtering which OutputGroups we may use in coin selection.
Definition: coinselection.h:119
wallet::OutputGroup::OutputGroup
OutputGroup(const CoinSelectionParams &params)
Definition: coinselection.h:173
wallet::SelectionResult::m_selected_inputs
std::set< CInputCoin > m_selected_inputs
Set of inputs selected by the algorithm to use in the transaction.
Definition: coinselection.h:207
wallet::CoinSelectionParams::change_output_size
size_t change_output_size
Size of a change output in bytes, determined by the output type.
Definition: coinselection.h:79
wallet::SelectionResult::operator<
bool operator<(SelectionResult other) const
Definition: coinselection.cpp:426