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