Bitcoin Core  22.99.0
P2P Digital Currency
coinselection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017-2020 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 <wallet/coinselection.h>
6 
7 #include <policy/feerate.h>
8 #include <util/system.h>
9 #include <util/moneystr.h>
10 
11 #include <optional>
12 
13 // Descending order comparator
14 struct {
15  bool operator()(const OutputGroup& a, const OutputGroup& b) const
16  {
17  return a.GetSelectionAmount() > b.GetSelectionAmount();
18  }
19 } descending;
20 
21 /*
22  * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
23  * set that can pay for the spending target and does not exceed the spending target by more than the
24  * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
25  * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
26  * are sorted by their effective values and the trees is explored deterministically per the inclusion
27  * branch first. At each node, the algorithm checks whether the selection is within the target range.
28  * While the selection has not reached the target range, more UTXOs are included. When a selection's
29  * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
30  * At that point, the last included UTXO is deselected and the corresponding omission branch explored
31  * instead. The search ends after the complete tree has been searched or after a limited number of tries.
32  *
33  * The search continues to search for better solutions after one solution has been found. The best
34  * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
35  * spend the current inputs at the given fee rate minus the long term expected cost to spend the
36  * inputs, plus the amount the selection exceeds the spending target:
37  *
38  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
39  *
40  * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
41  * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
42  * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
43  * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
44  * predecessor.
45  *
46  * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
47  * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
48  *
49  * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
50  * These UTXOs will be sorted in descending order by effective value and the CInputCoins'
51  * values are their effective values.
52  * @param const CAmount& selection_target This is the value that we want to select. It is the lower
53  * bound of the range.
54  * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
55  * This plus selection_target is the upper bound of the range.
56  * @param std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins
57  * that have been selected.
58  * @param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins
59  * that were selected.
60  */
61 
62 static const size_t TOTAL_TRIES = 100000;
63 
64 bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret)
65 {
66  out_set.clear();
67  CAmount curr_value = 0;
68 
69  std::vector<bool> curr_selection; // select the utxo at this index
70  curr_selection.reserve(utxo_pool.size());
71 
72  // Calculate curr_available_value
73  CAmount curr_available_value = 0;
74  for (const OutputGroup& utxo : utxo_pool) {
75  // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
76  assert(utxo.GetSelectionAmount() > 0);
77  curr_available_value += utxo.GetSelectionAmount();
78  }
79  if (curr_available_value < selection_target) {
80  return false;
81  }
82 
83  // Sort the utxo_pool
84  std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
85 
86  CAmount curr_waste = 0;
87  std::vector<bool> best_selection;
88  CAmount best_waste = MAX_MONEY;
89 
90  // Depth First search loop for choosing the UTXOs
91  for (size_t i = 0; i < TOTAL_TRIES; ++i) {
92  // Conditions for starting a backtrack
93  bool backtrack = false;
94  if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
95  curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
96  (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing
97  backtrack = true;
98  } else if (curr_value >= selection_target) { // Selected value is within range
99  curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison
100  // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
101  // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
102  // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
103  // explore any more UTXOs to avoid burning money like that.
104  if (curr_waste <= best_waste) {
105  best_selection = curr_selection;
106  best_selection.resize(utxo_pool.size());
107  best_waste = curr_waste;
108  if (best_waste == 0) {
109  break;
110  }
111  }
112  curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
113  backtrack = true;
114  }
115 
116  // Backtracking, moving backwards
117  if (backtrack) {
118  // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.
119  while (!curr_selection.empty() && !curr_selection.back()) {
120  curr_selection.pop_back();
121  curr_available_value += utxo_pool.at(curr_selection.size()).GetSelectionAmount();
122  }
123 
124  if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
125  break;
126  }
127 
128  // Output was included on previous iterations, try excluding now.
129  curr_selection.back() = false;
130  OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
131  curr_value -= utxo.GetSelectionAmount();
132  curr_waste -= utxo.fee - utxo.long_term_fee;
133  } else { // Moving forwards, continuing down this branch
134  OutputGroup& utxo = utxo_pool.at(curr_selection.size());
135 
136  // Remove this utxo from the curr_available_value utxo amount
137  curr_available_value -= utxo.GetSelectionAmount();
138 
139  // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded. Since the ratio of fee to
140  // long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
141  if (!curr_selection.empty() && !curr_selection.back() &&
142  utxo.GetSelectionAmount() == utxo_pool.at(curr_selection.size() - 1).GetSelectionAmount() &&
143  utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
144  curr_selection.push_back(false);
145  } else {
146  // Inclusion branch first (Largest First Exploration)
147  curr_selection.push_back(true);
148  curr_value += utxo.GetSelectionAmount();
149  curr_waste += utxo.fee - utxo.long_term_fee;
150  }
151  }
152  }
153 
154  // Check for solution
155  if (best_selection.empty()) {
156  return false;
157  }
158 
159  // Set output set
160  value_ret = 0;
161  for (size_t i = 0; i < best_selection.size(); ++i) {
162  if (best_selection.at(i)) {
163  util::insert(out_set, utxo_pool.at(i).m_outputs);
164  value_ret += utxo_pool.at(i).m_value;
165  }
166  }
167 
168  return true;
169 }
170 
171 static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue,
172  std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
173 {
174  std::vector<char> vfIncluded;
175 
176  vfBest.assign(groups.size(), true);
177  nBest = nTotalLower;
178 
179  FastRandomContext insecure_rand;
180 
181  for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
182  {
183  vfIncluded.assign(groups.size(), false);
184  CAmount nTotal = 0;
185  bool fReachedTarget = false;
186  for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
187  {
188  for (unsigned int i = 0; i < groups.size(); i++)
189  {
190  //The solver here uses a randomized algorithm,
191  //the randomness serves no real security purpose but is just
192  //needed to prevent degenerate behavior and it is important
193  //that the rng is fast. We do not use a constant random sequence,
194  //because there may be some privacy improvement by making
195  //the selection random.
196  if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
197  {
198  nTotal += groups[i].m_value;
199  vfIncluded[i] = true;
200  if (nTotal >= nTargetValue)
201  {
202  fReachedTarget = true;
203  if (nTotal < nBest)
204  {
205  nBest = nTotal;
206  vfBest = vfIncluded;
207  }
208  nTotal -= groups[i].m_value;
209  vfIncluded[i] = false;
210  }
211  }
212  }
213  }
214  }
215 }
216 
217 bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
218 {
219  setCoinsRet.clear();
220  nValueRet = 0;
221 
222  // List of values less than target
223  std::optional<OutputGroup> lowest_larger;
224  std::vector<OutputGroup> applicable_groups;
225  CAmount nTotalLower = 0;
226 
227  Shuffle(groups.begin(), groups.end(), FastRandomContext());
228 
229  for (const OutputGroup& group : groups) {
230  if (group.GetSelectionAmount() == nTargetValue) {
231  util::insert(setCoinsRet, group.m_outputs);
232  nValueRet += group.m_value;
233  return true;
234  } else if (group.GetSelectionAmount() < nTargetValue + MIN_CHANGE) {
235  applicable_groups.push_back(group);
236  nTotalLower += group.GetSelectionAmount();
237  } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
238  lowest_larger = group;
239  }
240  }
241 
242  if (nTotalLower == nTargetValue) {
243  for (const auto& group : applicable_groups) {
244  util::insert(setCoinsRet, group.m_outputs);
245  nValueRet += group.m_value;
246  }
247  return true;
248  }
249 
250  if (nTotalLower < nTargetValue) {
251  if (!lowest_larger) return false;
252  util::insert(setCoinsRet, lowest_larger->m_outputs);
253  nValueRet += lowest_larger->m_value;
254  return true;
255  }
256 
257  // Solve subset sum by stochastic approximation
258  std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
259  std::vector<char> vfBest;
260  CAmount nBest;
261 
262  ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
263  if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
264  ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
265  }
266 
267  // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
268  // or the next bigger coin is closer), return the bigger coin
269  if (lowest_larger &&
270  ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->GetSelectionAmount() <= nBest)) {
271  util::insert(setCoinsRet, lowest_larger->m_outputs);
272  nValueRet += lowest_larger->m_value;
273  } else {
274  for (unsigned int i = 0; i < applicable_groups.size(); i++) {
275  if (vfBest[i]) {
276  util::insert(setCoinsRet, applicable_groups[i].m_outputs);
277  nValueRet += applicable_groups[i].m_value;
278  }
279  }
280 
282  LogPrint(BCLog::SELECTCOINS, "SelectCoins() best subset: "); /* Continued */
283  for (unsigned int i = 0; i < applicable_groups.size(); i++) {
284  if (vfBest[i]) {
285  LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(applicable_groups[i].m_value)); /* Continued */
286  }
287  }
288  LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));
289  }
290  }
291 
292  return true;
293 }
294 
295 /******************************************************************************
296 
297  OutputGroup
298 
299  ******************************************************************************/
300 
301 void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
302  // Compute the effective value first
303  const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
304  const CAmount ev = output.txout.nValue - coin_fee;
305 
306  // Filter for positive only here before adding the coin
307  if (positive_only && ev <= 0) return;
308 
309  m_outputs.push_back(output);
310  CInputCoin& coin = m_outputs.back();
311 
312  coin.m_fee = coin_fee;
313  fee += coin.m_fee;
314 
317 
318  coin.effective_value = ev;
320 
321  m_from_me &= from_me;
322  m_value += output.txout.nValue;
323  m_depth = std::min(m_depth, depth);
324  // ancestors here express the number of ancestors the new coin will end up having, which is
325  // the sum, rather than the max; this will overestimate in the cases where multiple inputs
326  // have common ancestors
327  m_ancestors += ancestors;
328  // descendants is the count as seen from the top ancestor, not the descendants as seen from the
329  // coin itself; thus, this value is counted as the max, not the sum
330  m_descendants = std::max(m_descendants, descendants);
331 }
332 
333 bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
334 {
335  return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
336  && m_ancestors <= eligibility_filter.max_ancestors
337  && m_descendants <= eligibility_filter.max_descendants;
338 }
339 
341 {
343 }
OutputGroup::Insert
void Insert(const CInputCoin &output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only)
Definition: coinselection.cpp:301
OutputGroup::m_depth
int m_depth
The minimum number of confirmations the UTXOs in the group have.
Definition: coinselection.h:135
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:114
MIN_CHANGE
static constexpr CAmount MIN_CHANGE
target minimum change amount
Definition: coinselection.h:14
OutputGroup::m_subtract_fee_outputs
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
Definition: coinselection.h:155
OutputGroup
A group of UTXOs paid to the same output script.
Definition: coinselection.h:124
moneystr.h
CoinEligibilityFilter::conf_theirs
const int conf_theirs
Minimum number of confirmations for outputs received from a different wallet.
Definition: coinselection.h:110
FastRandomContext::randbool
bool randbool() noexcept
Generate a random boolean.
Definition: random.h:211
OutputGroup::m_long_term_feerate
CFeeRate m_long_term_feerate
The feerate for spending a created change output eventually (i.e.
Definition: coinselection.h:152
CoinEligibilityFilter::max_ancestors
const uint64_t max_ancestors
Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup.
Definition: coinselection.h:112
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:142
CInputCoin::effective_value
CAmount effective_value
Definition: coinselection.h:40
CInputCoin::m_fee
CAmount m_fee
Definition: coinselection.h:41
CoinEligibilityFilter
Parameters for filtering which OutputGroups we may use in coin selection.
Definition: coinselection.h:104
OutputGroup::m_outputs
std::vector< CInputCoin > m_outputs
The list of UTXOs contained in this output group.
Definition: coinselection.h:127
ApproximateBestSubset
static void ApproximateBestSubset(const std::vector< OutputGroup > &groups, const CAmount &nTotalLower, const CAmount &nTargetValue, std::vector< char > &vfBest, CAmount &nBest, int iterations=1000)
Definition: coinselection.cpp:171
OutputGroup::m_effective_feerate
CFeeRate m_effective_feerate
The target feerate of the transaction we're trying to build.
Definition: coinselection.h:146
CTxOut::nValue
CAmount nValue
Definition: transaction.h:131
coinselection.h
descending
struct @16 descending
OutputGroup::long_term_fee
CAmount long_term_fee
The fee to spend these UTXOs at the long term feerate.
Definition: coinselection.h:148
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:64
TOTAL_TRIES
static const size_t TOTAL_TRIES
Definition: coinselection.cpp:62
CInputCoin::txout
CTxOut txout
Definition: coinselection.h:39
OutputGroup::m_value
CAmount m_value
The total value of the UTXOs in sum.
Definition: coinselection.h:133
CAmount
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
KnapsackSolver
bool KnapsackSolver(const CAmount &nTargetValue, std::vector< OutputGroup > &groups, std::set< CInputCoin > &setCoinsRet, CAmount &nValueRet)
Definition: coinselection.cpp:217
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:45
Shuffle
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
Definition: random.h:231
LogPrint
#define LogPrint(category,...)
Definition: logging.h:188
OutputGroup::fee
CAmount fee
The fee to spend these UTXOs at the effective feerate.
Definition: coinselection.h:144
CInputCoin
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:19
system.h
OutputGroup::GetSelectionAmount
CAmount GetSelectionAmount() const
Definition: coinselection.cpp:340
LogAcceptCategory
static bool LogAcceptCategory(BCLog::LogFlags category)
Return true if log accepts specified category.
Definition: logging.h:157
CoinEligibilityFilter::conf_mine
const int conf_mine
Minimum number of confirmations for outputs that we sent to ourselves.
Definition: coinselection.h:108
util::insert
void insert(Tdst &dst, const Tsrc &src)
Simplification of std insertion.
Definition: system.h:506
MAX_MONEY
static const CAmount MAX_MONEY
No amount larger than this (in satoshi) is valid.
Definition: amount.h:25
BCLog::SELECTCOINS
@ SELECTCOINS
Definition: logging.h:48
OutputGroup::m_from_me
bool m_from_me
Whether the UTXOs were sent by the wallet to itself.
Definition: coinselection.h:131
assert
assert(s1.IsAddrV1Compatible())
CFeeRate::GetFee
CAmount GetFee(uint32_t num_bytes) const
Return the fee in satoshis for the given size in bytes.
Definition: feerate.cpp:21
OutputGroup::m_descendants
size_t m_descendants
The maximum count of descendants of a single UTXO in this output group.
Definition: coinselection.h:140
OutputGroup::m_ancestors
size_t m_ancestors
The aggregated count of unconfirmed ancestors of all UTXOs in this group.
Definition: coinselection.h:138
CInputCoin::m_long_term_fee
CAmount m_long_term_fee
Definition: coinselection.h:42
FastRandomContext
Fast randomness source.
Definition: random.h:119
OutputGroup::EligibleForSpending
bool EligibleForSpending(const CoinEligibilityFilter &eligibility_filter) const
Definition: coinselection.cpp:333
FormatMoney
std::string FormatMoney(const CAmount n)
Money parsing/formatting utilities.
Definition: moneystr.cpp:12