Bitcoin Core  22.99.0
P2P Digital Currency
coinselection.h
Go to the documentation of this file.
1 // Copyright (c) 2017-2019 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 
16 static constexpr CAmount MIN_CHANGE{COIN / 100};
19 
21 class CInputCoin {
22 public:
23  CInputCoin(const CTransactionRef& tx, unsigned int i)
24  {
25  if (!tx)
26  throw std::invalid_argument("tx should not be null");
27  if (i >= tx->vout.size())
28  throw std::out_of_range("The output index is out of range");
29 
30  outpoint = COutPoint(tx->GetHash(), i);
31  txout = tx->vout[i];
33  }
34 
35  CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes) : CInputCoin(tx, i)
36  {
37  m_input_bytes = input_bytes;
38  }
39 
40  CInputCoin(const COutPoint& outpoint_in, const CTxOut& txout_in)
41  {
42  outpoint = outpoint_in;
43  txout = txout_in;
45  }
46 
47  CInputCoin(const COutPoint& outpoint_in, const CTxOut& txout_in, int input_bytes) : CInputCoin(outpoint_in, txout_in)
48  {
49  m_input_bytes = input_bytes;
50  }
51 
57 
59  int m_input_bytes{-1};
60 
61  bool operator<(const CInputCoin& rhs) const {
62  return outpoint < rhs.outpoint;
63  }
64 
65  bool operator!=(const CInputCoin& rhs) const {
66  return outpoint != rhs.outpoint;
67  }
68 
69  bool operator==(const CInputCoin& rhs) const {
70  return outpoint == rhs.outpoint;
71  }
72 };
73 
76 {
78  size_t change_output_size = 0;
80  size_t change_spend_size = 0;
94  size_t tx_noinputs_size = 0;
96  bool m_subtract_fee_outputs = false;
101 
103  CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) :
106  m_effective_feerate(effective_feerate),
107  m_long_term_feerate(long_term_feerate),
108  m_discard_feerate(discard_feerate),
110  m_avoid_partial_spends(avoid_partial)
111  {}
113 };
114 
119 {
122  const int conf_mine;
124  const int conf_theirs;
126  const uint64_t max_ancestors;
128  const uint64_t max_descendants;
130  const bool m_include_partial_groups{false};
131 
135 };
136 
139 {
141  std::vector<CInputCoin> m_outputs;
145  bool m_from_me{true};
149  int m_depth{999};
152  size_t m_ancestors{0};
154  size_t m_descendants{0};
170 
176  {}
177 
178  void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only);
179  bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
180  CAmount GetSelectionAmount() const;
181 };
182 
198 [[nodiscard]] CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
199 
200 bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);
201 
209 std::optional<std::pair<std::set<CInputCoin>, CAmount>> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value);
210 
211 // Original coin selection algorithm as a fallback
212 bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
213 
214 #endif // BITCOIN_WALLET_COINSELECTION_H
OutputGroup::Insert
void Insert(const CInputCoin &output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only)
Definition: coinselection.cpp:328
CoinSelectionParams::change_output_size
size_t change_output_size
Size of a change output in bytes, determined by the output type.
Definition: coinselection.h:78
OutputGroup::m_depth
int m_depth
The minimum number of confirmations the UTXOs in the group have.
Definition: coinselection.h:149
feerate.h
CoinEligibilityFilter::max_descendants
const uint64_t max_descendants
Maximum number of descendants that a single UTXO in the OutputGroup may have.
Definition: coinselection.h:128
MIN_CHANGE
static constexpr CAmount MIN_CHANGE
target minimum change amount
Definition: coinselection.h:16
OutputGroup::m_subtract_fee_outputs
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
Definition: coinselection.h:169
SelectCoinsBnB
bool SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, std::set< CInputCoin > &out_set, CAmount &value_ret)
Definition: coinselection.cpp:67
OutputGroup
A group of UTXOs paid to the same output script.
Definition: coinselection.h:138
OutputGroup::OutputGroup
OutputGroup()
Definition: coinselection.h:171
transaction.h
CoinEligibilityFilter::conf_theirs
const int conf_theirs
Minimum number of confirmations for outputs received from a different wallet.
Definition: coinselection.h:124
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:130
CInputCoin::operator!=
bool operator!=(const CInputCoin &rhs) const
Definition: coinselection.h:65
CoinEligibilityFilter::CoinEligibilityFilter
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors)
Definition: coinselection.h:132
OutputGroup::m_long_term_feerate
CFeeRate m_long_term_feerate
The feerate for spending a created change output eventually (i.e.
Definition: coinselection.h:166
CoinEligibilityFilter::max_ancestors
const uint64_t max_ancestors
Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup.
Definition: coinselection.h:126
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:156
CInputCoin::effective_value
CAmount effective_value
Definition: coinselection.h:54
OutputGroup::OutputGroup
OutputGroup(const CoinSelectionParams &params)
Definition: coinselection.h:172
CInputCoin::m_fee
CAmount m_fee
Definition: coinselection.h:55
CoinEligibilityFilter::CoinEligibilityFilter
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants)
Definition: coinselection.h:133
CoinEligibilityFilter
Parameters for filtering which OutputGroups we may use in coin selection.
Definition: coinselection.h:118
CTransactionRef
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:386
OutputGroup::m_outputs
std::vector< CInputCoin > m_outputs
The list of UTXOs contained in this output group.
Definition: coinselection.h:141
CFeeRate
Fee rate in satoshis per kilobyte: CAmount / kB.
Definition: feerate.h:29
OutputGroup::m_effective_feerate
CFeeRate m_effective_feerate
The target feerate of the transaction we're trying to build.
Definition: coinselection.h:160
CTxOut::nValue
CAmount nValue
Definition: transaction.h:131
CInputCoin::CInputCoin
CInputCoin(const CTransactionRef &tx, unsigned int i)
Definition: coinselection.h:23
CInputCoin::outpoint
COutPoint outpoint
Definition: coinselection.h:52
random.h
CInputCoin::CInputCoin
CInputCoin(const COutPoint &outpoint_in, const CTxOut &txout_in)
Definition: coinselection.h:40
OutputGroup::long_term_fee
CAmount long_term_fee
The fee to spend these UTXOs at the long term feerate.
Definition: coinselection.h:162
CTxOut
An output of a transaction.
Definition: transaction.h:128
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:89
MIN_FINAL_CHANGE
static const CAmount MIN_FINAL_CHANGE
final minimum change amount after paying for fees
Definition: coinselection.h:18
CInputCoin::operator==
bool operator==(const CInputCoin &rhs) const
Definition: coinselection.h:69
CoinSelectionParams
Parameters for one iteration of Coin Selection.
Definition: coinselection.h:75
GetSelectionWaste
CAmount GetSelectionWaste(const std::set< CInputCoin > &inputs, CAmount change_cost, CAmount target, bool use_effective_value=true)
Compute the waste for this result given the cost of change and the opportunity cost of spending these...
Definition: coinselection.cpp:372
CInputCoin::txout
CTxOut txout
Definition: coinselection.h:53
OutputGroup::m_value
CAmount m_value
The total value of the UTXOs in sum.
Definition: coinselection.h:147
CAmount
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
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:59
CoinEligibilityFilter::CoinEligibilityFilter
CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants, bool include_partial)
Definition: coinselection.h:134
CoinSelectionParams::m_change_fee
CAmount m_change_fee
Cost of creating the change output.
Definition: coinselection.h:82
OutputGroup::fee
CAmount fee
The fee to spend these UTXOs at the effective feerate.
Definition: coinselection.h:158
CoinSelectionParams::change_spend_size
size_t change_spend_size
Size of the input to spend a change output in virtual bytes.
Definition: coinselection.h:80
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:94
CInputCoin
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:21
SelectCoinsSRD
std::optional< std::pair< std::set< CInputCoin >, CAmount > > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value)
Select coins by Single Random Draw.
Definition: coinselection.cpp:174
CoinSelectionParams::m_subtract_fee_outputs
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
Definition: coinselection.h:96
OutputGroup::GetSelectionAmount
CAmount GetSelectionAmount() const
Definition: coinselection.cpp:367
CoinEligibilityFilter::conf_mine
const int conf_mine
Minimum number of confirmations for outputs that we sent to ourselves.
Definition: coinselection.h:122
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:84
CInputCoin::operator<
bool operator<(const CInputCoin &rhs) const
Definition: coinselection.h:61
CoinSelectionParams::m_effective_feerate
CFeeRate m_effective_feerate
The targeted feerate of the transaction being built.
Definition: coinselection.h:86
CInputCoin::CInputCoin
CInputCoin(const COutPoint &outpoint_in, const CTxOut &txout_in, int input_bytes)
Definition: coinselection.h:47
OutputGroup::m_from_me
bool m_from_me
Whether the UTXOs were sent by the wallet to itself.
Definition: coinselection.h:145
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:91
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:102
CInputCoin::CInputCoin
CInputCoin(const CTransactionRef &tx, unsigned int i, int input_bytes)
Definition: coinselection.h:35
COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:26
CoinSelectionParams::CoinSelectionParams
CoinSelectionParams()
Definition: coinselection.h:112
COIN
static constexpr CAmount COIN
Definition: amount.h:14
OutputGroup::m_descendants
size_t m_descendants
The maximum count of descendants of a single UTXO in this output group.
Definition: coinselection.h:154
OutputGroup::m_ancestors
size_t m_ancestors
The aggregated count of unconfirmed ancestors of all UTXOs in this group.
Definition: coinselection.h:152
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:100
amount.h
CInputCoin::m_long_term_fee
CAmount m_long_term_fee
Definition: coinselection.h:56
KnapsackSolver
bool KnapsackSolver(const CAmount &nTargetValue, std::vector< OutputGroup > &groups, std::set< CInputCoin > &setCoinsRet, CAmount &nValueRet)
Definition: coinselection.cpp:244
OutputGroup::EligibleForSpending
bool EligibleForSpending(const CoinEligibilityFilter &eligibility_filter) const
Definition: coinselection.cpp:360