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