Bitcoin ABC  0.26.3
P2P Digital Currency
coinselection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017 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 <consensus/amount.h>
8 #include <feerate.h>
9 #include <util/moneystr.h>
10 #include <util/system.h>
11 
12 #include <optional>
13 
14 // Descending order comparator
15 struct {
16  bool operator()(const OutputGroup &a, const OutputGroup &b) const {
17  return a.effective_value > b.effective_value;
18  }
20 
21 static const size_t TOTAL_TRIES = 100000;
22 
71 bool SelectCoinsBnB(std::vector<OutputGroup> &utxo_pool,
72  const Amount &target_value, const Amount &cost_of_change,
73  std::set<CInputCoin> &out_set, Amount &value_ret,
74  const Amount not_input_fees) {
75  out_set.clear();
76  Amount curr_value = Amount::zero();
77 
78  // select the utxo at this index
79  std::vector<bool> curr_selection;
80  curr_selection.reserve(utxo_pool.size());
81  Amount actual_target = not_input_fees + target_value;
82 
83  // Calculate curr_available_value
84  Amount curr_available_value = Amount::zero();
85  for (const OutputGroup &utxo : utxo_pool) {
86  // Assert that this utxo is not negative. It should never be negative,
87  // effective value calculation should have removed it
88  assert(utxo.effective_value > Amount::zero());
89  curr_available_value += utxo.effective_value;
90  }
91  if (curr_available_value < actual_target) {
92  return false;
93  }
94 
95  // Sort the utxo_pool
96  std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
97 
98  Amount curr_waste = Amount::zero();
99  std::vector<bool> best_selection;
100  Amount best_waste = MAX_MONEY;
101 
102  // Depth First search loop for choosing the UTXOs
103  for (size_t i = 0; i < TOTAL_TRIES; ++i) {
104  // Conditions for starting a backtrack
105  bool backtrack = false;
106  if (curr_value + curr_available_value <
107  actual_target || // Cannot possibly reach target with the amount
108  // remaining in the curr_available_value.
109  curr_value >
110  actual_target +
111  cost_of_change || // Selected value is out of range, go back
112  // and try other branch
113  (curr_waste > best_waste &&
114  (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) >
115  Amount::zero())) {
116  // Don't select things which we know will be more wasteful if the
117  // waste is increasing
118  backtrack = true;
119  }
120 
121  // Selected value is within range
122  else if (curr_value >= actual_target) {
123  // This is the excess value which is added to the waste for the
124  // below comparison. Adding another UTXO after this check could
125  // bring the waste down if the long term fee is higher than the
126  // current fee. However we are not going to explore that because
127  // this optimization for the waste is only done when we have hit our
128  // target value. Adding any more UTXOs will be just burning the
129  // UTXO; it will go entirely to fees. Thus we aren't going to
130  // explore any more UTXOs to avoid burning money like that.
131  curr_waste += (curr_value - actual_target);
132 
133  if (curr_waste <= best_waste) {
134  best_selection = curr_selection;
135  best_selection.resize(utxo_pool.size());
136  best_waste = curr_waste;
137  if (best_waste == Amount::zero()) {
138  break;
139  }
140  }
141  // Remove the excess value as we will be selecting different coins
142  // now
143  curr_waste -= (curr_value - actual_target);
144  backtrack = true;
145  }
146 
147  // Backtracking, moving backwards
148  if (backtrack) {
149  // Walk backwards to find the last included UTXO that still needs to
150  // have its omission branch traversed.
151  while (!curr_selection.empty() && !curr_selection.back()) {
152  curr_selection.pop_back();
153  curr_available_value +=
154  utxo_pool.at(curr_selection.size()).effective_value;
155  }
156 
157  if (curr_selection.empty()) {
158  // We have walked back to the first utxo and no branch is
159  // untraversed. All solutions searched
160  break;
161  }
162 
163  // Output was included on previous iterations, try excluding now.
164  curr_selection.back() = false;
165  OutputGroup &utxo = utxo_pool.at(curr_selection.size() - 1);
166  curr_value -= utxo.effective_value;
167  curr_waste -= utxo.fee - utxo.long_term_fee;
168  }
169 
170  // Moving forwards, continuing down this branch
171  else {
172  OutputGroup &utxo = utxo_pool.at(curr_selection.size());
173 
174  // Remove this utxo from the curr_available_value utxo amount
175  curr_available_value -= utxo.effective_value;
176 
177  // Avoid searching a branch if the previous UTXO has the same value
178  // and same waste and was excluded. Since the ratio of fee to long
179  // term fee is the same, we only need to check if one of those
180  // values match in order to know that the waste is the same.
181  if (!curr_selection.empty() && !curr_selection.back() &&
182  utxo.effective_value ==
183  utxo_pool.at(curr_selection.size() - 1).effective_value &&
184  utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
185  curr_selection.push_back(false);
186  } else {
187  // Inclusion branch first (Largest First Exploration)
188  curr_selection.push_back(true);
189  curr_value += utxo.effective_value;
190  curr_waste += utxo.fee - utxo.long_term_fee;
191  }
192  }
193  }
194 
195  // Check for solution
196  if (best_selection.empty()) {
197  return false;
198  }
199 
200  // Set output set
201  value_ret = Amount::zero();
202  for (size_t i = 0; i < best_selection.size(); ++i) {
203  if (best_selection.at(i)) {
204  util::insert(out_set, utxo_pool.at(i).m_outputs);
205  value_ret += utxo_pool.at(i).m_value;
206  }
207  }
208 
209  return true;
210 }
211 
212 static void ApproximateBestSubset(const std::vector<OutputGroup> &groups,
213  const Amount &nTotalLower,
214  const Amount &nTargetValue,
215  std::vector<char> &vfBest, Amount &nBest,
216  int iterations = 1000) {
217  std::vector<char> vfIncluded;
218 
219  vfBest.assign(groups.size(), true);
220  nBest = nTotalLower;
221 
222  FastRandomContext insecure_rand;
223 
224  for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++) {
225  vfIncluded.assign(groups.size(), false);
226  Amount nTotal = Amount::zero();
227  bool fReachedTarget = false;
228  for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++) {
229  for (size_t i = 0; i < groups.size(); i++) {
230  // The solver here uses a randomized algorithm, the randomness
231  // serves no real security purpose but is just needed to prevent
232  // degenerate behavior and it is important that the rng is fast.
233  // We do not use a constant random sequence, because there may
234  // be some privacy improvement by making the selection random.
235  if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i]) {
236  nTotal += groups[i].m_value;
237  vfIncluded[i] = true;
238  if (nTotal >= nTargetValue) {
239  fReachedTarget = true;
240  if (nTotal < nBest) {
241  nBest = nTotal;
242  vfBest = vfIncluded;
243  }
244 
245  nTotal -= groups[i].m_value;
246  vfIncluded[i] = false;
247  }
248  }
249  }
250  }
251  }
252 }
253 
254 bool KnapsackSolver(const Amount nTargetValue, std::vector<OutputGroup> &groups,
255  std::set<CInputCoin> &setCoinsRet, Amount &nValueRet) {
256  setCoinsRet.clear();
257  nValueRet = Amount::zero();
258 
259  // List of values less than target
260  std::optional<OutputGroup> lowest_larger;
261  std::vector<OutputGroup> applicable_groups;
262  Amount nTotalLower = Amount::zero();
263 
264  Shuffle(groups.begin(), groups.end(), FastRandomContext());
265 
266  for (const OutputGroup &group : groups) {
267  if (group.m_value == nTargetValue) {
268  util::insert(setCoinsRet, group.m_outputs);
269  nValueRet += group.m_value;
270  return true;
271  } else if (group.m_value < nTargetValue + MIN_CHANGE) {
272  applicable_groups.push_back(group);
273  nTotalLower += group.m_value;
274  } else if (!lowest_larger || group.m_value < lowest_larger->m_value) {
275  lowest_larger = group;
276  }
277  }
278 
279  if (nTotalLower == nTargetValue) {
280  for (const auto &group : applicable_groups) {
281  util::insert(setCoinsRet, group.m_outputs);
282  nValueRet += group.m_value;
283  }
284  return true;
285  }
286 
287  if (nTotalLower < nTargetValue) {
288  if (!lowest_larger) {
289  return false;
290  }
291  util::insert(setCoinsRet, lowest_larger->m_outputs);
292  nValueRet += lowest_larger->m_value;
293  return true;
294  }
295 
296  // Solve subset sum by stochastic approximation
297  std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
298  std::vector<char> vfBest;
299  Amount nBest;
300 
301  ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest,
302  nBest);
303  if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
304  ApproximateBestSubset(applicable_groups, nTotalLower,
305  nTargetValue + MIN_CHANGE, vfBest, nBest);
306  }
307 
308  // If we have a bigger coin and (either the stochastic approximation didn't
309  // find a good solution, or the next bigger coin is closer), return the
310  // bigger coin
311  if (lowest_larger &&
312  ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) ||
313  lowest_larger->m_value <= nBest)) {
314  util::insert(setCoinsRet, lowest_larger->m_outputs);
315  nValueRet += lowest_larger->m_value;
316  } else {
317  for (size_t i = 0; i < applicable_groups.size(); i++) {
318  if (vfBest[i]) {
319  util::insert(setCoinsRet, applicable_groups[i].m_outputs);
320  nValueRet += applicable_groups[i].m_value;
321  }
322  }
323 
325  /* Continued */
327  "SelectCoins() best subset: ");
328  for (size_t i = 0; i < applicable_groups.size(); i++) {
329  if (vfBest[i]) {
330  /* Continued */
332  BCLog::SELECTCOINS, "%s ",
333  FormatMoney(applicable_groups[i].m_value));
334  }
335  }
336  LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));
337  }
338  }
339 
340  return true;
341 }
342 
343 /******************************************************************************
344 
345  OutputGroup
346 
347  ******************************************************************************/
348 
349 void OutputGroup::Insert(const CInputCoin &output, int depth, bool from_me,
350  size_t ancestors, size_t descendants) {
351  m_outputs.push_back(output);
352  m_from_me &= from_me;
353  m_value += output.txout.nValue;
354  m_depth = std::min(m_depth, depth);
355  // ancestors here express the number of ancestors the new coin will end up
356  // having, which is the sum, rather than the max; this will overestimate in
357  // the cases where multiple inputs have common ancestors
358  m_ancestors += ancestors;
359  // descendants is the count as seen from the top ancestor, not the
360  // descendants as seen from the coin itself; thus, this value is counted as
361  // the max, not the sum
362  m_descendants = std::max(m_descendants, descendants);
364  fee += output.m_fee;
365  long_term_fee += output.m_long_term_fee;
366 }
367 
368 std::vector<CInputCoin>::iterator
370  auto it = m_outputs.begin();
371  while (it != m_outputs.end() && it->outpoint != output.outpoint) {
372  ++it;
373  }
374  if (it == m_outputs.end()) {
375  return it;
376  }
377  m_value -= output.txout.nValue;
379  fee -= output.m_fee;
380  long_term_fee -= output.m_long_term_fee;
381  return m_outputs.erase(it);
382 }
383 
385  const CoinEligibilityFilter &eligibility_filter) const {
386  return m_depth >= (m_from_me ? eligibility_filter.conf_mine
387  : eligibility_filter.conf_theirs) &&
388  m_ancestors <= eligibility_filter.max_ancestors &&
389  m_descendants <= eligibility_filter.max_descendants;
390 }
391 
392 void OutputGroup::SetFees(const CFeeRate effective_feerate,
393  const CFeeRate long_term_feerate) {
394  fee = Amount::zero();
397  for (CInputCoin &coin : m_outputs) {
398  coin.m_fee = coin.m_input_bytes < 0
399  ? Amount::zero()
400  : effective_feerate.GetFee(coin.m_input_bytes);
401  fee += coin.m_fee;
402 
403  coin.m_long_term_fee =
404  coin.m_input_bytes < 0
405  ? Amount::zero()
406  : long_term_feerate.GetFee(coin.m_input_bytes);
407  long_term_fee += coin.m_long_term_fee;
408 
409  coin.effective_value = coin.txout.nValue - coin.m_fee;
410  effective_value += coin.effective_value;
411  }
412 }
413 
415  OutputGroup group(*this);
416  for (auto it = group.m_outputs.begin(); it != group.m_outputs.end();) {
417  const CInputCoin &coin = *it;
418  // Only include outputs that are positive effective value (i.e. not
419  // dust)
420  if (coin.effective_value <= Amount::zero()) {
421  it = group.Discard(coin);
422  } else {
423  ++it;
424  }
425  }
426  return group;
427 }
static constexpr Amount MAX_MONEY
No amount larger than this (in satoshi) is valid.
Definition: amount.h:175
Fee rate in satoshis per kilobyte: Amount / kB.
Definition: feerate.h:21
Amount GetFee(size_t nBytes) const
Return the fee in satoshis for the given size in bytes.
Definition: feerate.cpp:49
Amount m_fee
Definition: coinselection.h:42
Amount m_long_term_fee
Definition: coinselection.h:43
CTxOut txout
Definition: coinselection.h:40
Amount effective_value
Definition: coinselection.h:41
COutPoint outpoint
Definition: coinselection.h:39
Amount nValue
Definition: transaction.h:132
Fast randomness source.
Definition: random.h:129
bool randbool() noexcept
Generate a random boolean.
Definition: random.h:229
static void ApproximateBestSubset(const std::vector< OutputGroup > &groups, const Amount &nTotalLower, const Amount &nTargetValue, std::vector< char > &vfBest, Amount &nBest, int iterations=1000)
static const size_t TOTAL_TRIES
bool KnapsackSolver(const Amount nTargetValue, std::vector< OutputGroup > &groups, std::set< CInputCoin > &setCoinsRet, Amount &nValueRet)
bool SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const Amount &target_value, const Amount &cost_of_change, std::set< CInputCoin > &out_set, Amount &value_ret, const Amount not_input_fees)
This is the Branch and Bound Coin Selection algorithm designed by Murch.
struct @19 descending
static constexpr Amount MIN_CHANGE
target minimum change amount
Definition: coinselection.h:15
static bool LogAcceptCategory(BCLog::LogFlags category)
Return true if log accepts specified category.
Definition: logging.h:174
#define LogPrint(category,...)
Definition: logging.h:208
#define LogPrintToBeContinued
Definition: logging.h:221
std::string FormatMoney(const Amount amt)
Do not use these functions to represent or parse monetary amounts to or from JSON but use AmountFromV...
Definition: moneystr.cpp:13
@ SELECTCOINS
Definition: logging.h:49
void insert(Tdst &dst, const Tsrc &src)
Simplification of std insertion.
Definition: system.h:493
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
Definition: random.h:251
Definition: amount.h:19
static constexpr Amount zero()
Definition: amount.h:42
const uint64_t max_ancestors
Definition: coinselection.h:67
const uint64_t max_descendants
Definition: coinselection.h:68
std::vector< CInputCoin > m_outputs
Definition: coinselection.h:81
std::vector< CInputCoin >::iterator Discard(const CInputCoin &output)
void SetFees(const CFeeRate effective_feerate, const CFeeRate long_term_feerate)
Update the OutputGroup's fee, long_term_fee, and effective_value based on the given feerates.
Amount m_value
Definition: coinselection.h:83
Amount long_term_fee
Definition: coinselection.h:89
size_t m_descendants
Definition: coinselection.h:86
OutputGroup GetPositiveOnlyGroup()
Amount effective_value
Definition: coinselection.h:87
size_t m_ancestors
Definition: coinselection.h:85
bool EligibleForSpending(const CoinEligibilityFilter &eligibility_filter) const
void Insert(const CInputCoin &output, int depth, bool from_me, size_t ancestors, size_t descendants)
assert(!tx.IsCoinBase())