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