Bitcoin Core  27.99.0
P2P Digital Currency
coinselection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017-2022 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 <common/system.h>
8 #include <consensus/amount.h>
9 #include <consensus/consensus.h>
10 #include <interfaces/chain.h>
11 #include <logging.h>
12 #include <policy/feerate.h>
13 #include <util/check.h>
14 #include <util/moneystr.h>
15 
16 #include <numeric>
17 #include <optional>
18 #include <queue>
19 
20 namespace wallet {
21 // Common selection error across the algorithms
23 {
24  return util::Error{_("The inputs size exceeds the maximum weight. "
25  "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")};
26 }
27 
28 // Sort by descending (effective) value prefer lower waste on tie
29 struct {
30  bool operator()(const OutputGroup& a, const OutputGroup& b) const
31  {
32  if (a.GetSelectionAmount() == b.GetSelectionAmount()) {
33  // Lower waste is better when effective_values are tied
34  return (a.fee - a.long_term_fee) < (b.fee - b.long_term_fee);
35  }
36  return a.GetSelectionAmount() > b.GetSelectionAmount();
37  }
39 
40 // Sort by descending (effective) value prefer lower weight on tie
41 struct {
42  bool operator()(const OutputGroup& a, const OutputGroup& b) const
43  {
44  if (a.GetSelectionAmount() == b.GetSelectionAmount()) {
45  // Sort lower weight to front on tied effective_value
46  return a.m_weight < b.m_weight;
47  }
48  return a.GetSelectionAmount() > b.GetSelectionAmount();
49  }
51 
52 /*
53  * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
54  * set that can pay for the spending target and does not exceed the spending target by more than the
55  * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
56  * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
57  * are sorted by their effective values and the tree is explored deterministically per the inclusion
58  * branch first. At each node, the algorithm checks whether the selection is within the target range.
59  * While the selection has not reached the target range, more UTXOs are included. When a selection's
60  * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
61  * At that point, the last included UTXO is deselected and the corresponding omission branch explored
62  * instead. The search ends after the complete tree has been searched or after a limited number of tries.
63  *
64  * The search continues to search for better solutions after one solution has been found. The best
65  * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
66  * spend the current inputs at the given fee rate minus the long term expected cost to spend the
67  * inputs, plus the amount by which the selection exceeds the spending target:
68  *
69  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
70  *
71  * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
72  * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
73  * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
74  * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
75  * predecessor.
76  *
77  * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
78  * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
79  *
80  * @param const std::vector<OutputGroup>& utxo_pool The set of UTXO groups that we are choosing from.
81  * These UTXO groups will be sorted in descending order by effective value and the OutputGroups'
82  * values are their effective values.
83  * @param const CAmount& selection_target This is the value that we want to select. It is the lower
84  * bound of the range.
85  * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
86  * This plus selection_target is the upper bound of the range.
87  * @param int max_weight The maximum weight available for the input set.
88  * @returns The result of this coin selection algorithm, or std::nullopt
89  */
90 
91 static const size_t TOTAL_TRIES = 100000;
92 
93 util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
94  int max_weight)
95 {
96  SelectionResult result(selection_target, SelectionAlgorithm::BNB);
97  CAmount curr_value = 0;
98  std::vector<size_t> curr_selection; // selected utxo indexes
99  int curr_selection_weight = 0; // sum of selected utxo weight
100 
101  // Calculate curr_available_value
102  CAmount curr_available_value = 0;
103  for (const OutputGroup& utxo : utxo_pool) {
104  // Assert that this utxo is not negative. It should never be negative,
105  // effective value calculation should have removed it
106  assert(utxo.GetSelectionAmount() > 0);
107  curr_available_value += utxo.GetSelectionAmount();
108  }
109  if (curr_available_value < selection_target) {
110  return util::Error();
111  }
112 
113  // Sort the utxo_pool
114  std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
115 
116  CAmount curr_waste = 0;
117  std::vector<size_t> best_selection;
118  CAmount best_waste = MAX_MONEY;
119 
120  bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
121  bool max_tx_weight_exceeded = false;
122 
123  // Depth First search loop for choosing the UTXOs
124  for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
125  // Conditions for starting a backtrack
126  bool backtrack = false;
127  if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
128  curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
129  (curr_waste > best_waste && is_feerate_high)) { // Don't select things which we know will be more wasteful if the waste is increasing
130  backtrack = true;
131  } else if (curr_selection_weight > max_weight) { // Exceeding weight for standard tx, cannot find more solutions by adding more inputs
132  max_tx_weight_exceeded = true; // at least one selection attempt exceeded the max weight
133  backtrack = true;
134  } else if (curr_value >= selection_target) { // Selected value is within range
135  curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison
136  // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
137  // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
138  // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
139  // explore any more UTXOs to avoid burning money like that.
140  if (curr_waste <= best_waste) {
141  best_selection = curr_selection;
142  best_waste = curr_waste;
143  }
144  curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
145  backtrack = true;
146  }
147 
148  if (backtrack) { // Backtracking, moving backwards
149  if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
150  break;
151  }
152 
153  // Add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO.
154  for (--utxo_pool_index; utxo_pool_index > curr_selection.back(); --utxo_pool_index) {
155  curr_available_value += utxo_pool.at(utxo_pool_index).GetSelectionAmount();
156  }
157 
158  // Output was included on previous iterations, try excluding now.
159  assert(utxo_pool_index == curr_selection.back());
160  OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
161  curr_value -= utxo.GetSelectionAmount();
162  curr_waste -= utxo.fee - utxo.long_term_fee;
163  curr_selection_weight -= utxo.m_weight;
164  curr_selection.pop_back();
165  } else { // Moving forwards, continuing down this branch
166  OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
167 
168  // Remove this utxo from the curr_available_value utxo amount
169  curr_available_value -= utxo.GetSelectionAmount();
170 
171  if (curr_selection.empty() ||
172  // The previous index is included and therefore not relevant for exclusion shortcut
173  (utxo_pool_index - 1) == curr_selection.back() ||
174  // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded.
175  // Since the ratio of fee to 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.
176  utxo.GetSelectionAmount() != utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() ||
177  utxo.fee != utxo_pool.at(utxo_pool_index - 1).fee)
178  {
179  // Inclusion branch first (Largest First Exploration)
180  curr_selection.push_back(utxo_pool_index);
181  curr_value += utxo.GetSelectionAmount();
182  curr_waste += utxo.fee - utxo.long_term_fee;
183  curr_selection_weight += utxo.m_weight;
184  }
185  }
186  }
187 
188  // Check for solution
189  if (best_selection.empty()) {
190  return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
191  }
192 
193  // Set output set
194  for (const size_t& i : best_selection) {
195  result.AddInput(utxo_pool.at(i));
196  }
197  result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
198  assert(best_waste == result.GetWaste());
199 
200  return result;
201 }
202 
203 /*
204  * TL;DR: Coin Grinder is a DFS-based algorithm that deterministically searches for the minimum-weight input set to fund
205  * the transaction. The algorithm is similar to the Branch and Bound algorithm, but will produce a transaction _with_ a
206  * change output instead of a changeless transaction.
207  *
208  * Full description: CoinGrinder can be thought of as a graph walking algorithm. It explores a binary tree
209  * representation of the powerset of the UTXO pool. Each node in the tree represents a candidate input set. The tree’s
210  * root is the empty set. Each node in the tree has two children which are formed by either adding or skipping the next
211  * UTXO ("inclusion/omission branch"). Each level in the tree after the root corresponds to a decision about one UTXO in
212  * the UTXO pool.
213  *
214  * Example:
215  * We represent UTXOs as _alias=[effective_value/weight]_ and indicate omitted UTXOs with an underscore. Given a UTXO
216  * pool {A=[10/2], B=[7/1], C=[5/1], D=[4/2]} sorted by descending effective value, our search tree looks as follows:
217  *
218  * _______________________ {} ________________________
219  * / \
220  * A=[10/2] __________ {A} _________ __________ {_} _________
221  * / \ / \
222  * B=[7/1] {AB} _ {A_} _ {_B} _ {__} _
223  * / \ / \ / \ / \
224  * C=[5/1] {ABC} {AB_} {A_C} {A__} {_BC} {_B_} {__C} {___}
225  * / \ / \ / \ / \ / \ / \ / \ / \
226  * D=[4/2] {ABCD} {ABC_} {AB_D} {AB__} {A_CD} {A_C_} {A__D} {A___} {_BCD} {_BC_} {_B_D} {_B__} {__CD} {__C_} {___D} {____}
227  *
228  *
229  * CoinGrinder uses a depth-first search to walk this tree. It first tries inclusion branches, then omission branches. A
230  * naive exploration of a tree with four UTXOs requires visiting all 31 nodes:
231  *
232  * {} {A} {AB} {ABC} {ABCD} {ABC_} {AB_} {AB_D} {AB__} {A_} {A_C} {A_CD} {A_C_} {A__} {A__D} {A___} {_} {_B} {_BC}
233  * {_BCD} {_BC_} {_B_} {_B_D} {_B__} {__} {__C} {__CD} {__C} {___} {___D} {____}
234  *
235  * As powersets grow exponentially with the set size, walking the entire tree would quickly get computationally
236  * infeasible with growing UTXO pools. Thanks to traversing the tree in a deterministic order, we can keep track of the
237  * progress of the search solely on basis of the current selection (and the best selection so far). We visit as few
238  * nodes as possible by recognizing and skipping any branches that can only contain solutions worse than the best
239  * solution so far. This makes CoinGrinder a branch-and-bound algorithm
240  * (https://en.wikipedia.org/wiki/Branch_and_bound).
241  * CoinGrinder is searching for the input set with lowest weight that can fund a transaction, so for example we can only
242  * ever find a _better_ candidate input set in a node that adds a UTXO, but never in a node that skips a UTXO. After
243  * visiting {A} and exploring the inclusion branch {AB} and its descendants, the candidate input set in the omission
244  * branch {A_} is equivalent to the parent {A} in effective value and weight. While CoinGrinder does need to visit the
245  * descendants of the omission branch {A_}, it is unnecessary to evaluate the candidate input set in the omission branch
246  * itself. By skipping evaluation of all nodes on an omission branch we reduce the visited nodes to 15:
247  *
248  * {A} {AB} {ABC} {ABCD} {AB_D} {A_C} {A_CD} {A__D} {_B} {_BC} {_BCD} {_B_D} {__C} {__CD} {___D}
249  *
250  * _______________________ {} ________________________
251  * / \
252  * A=[10/2] __________ {A} _________ ___________\____________
253  * / \ / \
254  * B=[7/1] {AB} __ __\_____ {_B} __ __\_____
255  * / \ / \ / \ / \
256  * C=[5/1] {ABC} \ {A_C} \ {_BC} \ {__C} \
257  * / / / / / / / /
258  * D=[4/2] {ABCD} {AB_D} {A_CD} {A__D} {_BCD} {_B_D} {__CD} {___D}
259  *
260  *
261  * We refer to the move from the inclusion branch {AB} via the omission branch {A_} to its inclusion-branch child {A_C}
262  * as _shifting to the omission branch_ or just _SHIFT_. (The index of the ultimate element in the candidate input set
263  * shifts right by one: {AB} ⇒ {A_C}.)
264  * When we reach a leaf node in the last level of the tree, shifting to the omission branch is not possible. Instead we
265  * go to the omission branch of the node’s last ancestor on an inclusion branch: from {ABCD}, we go to {AB_D}. From
266  * {AB_D}, we go to {A_C}. We refer to this operation as a _CUT_. (The ultimate element in
267  * the input set is deselected, and the penultimate element is shifted right by one: {AB_D} ⇒ {A_C}.)
268  * If a candidate input set in a node has not selected sufficient funds to build the transaction, we continue directly
269  * along the next inclusion branch. We call this operation _EXPLORE_. (We go from one inclusion branch to the next
270  * inclusion branch: {_B} ⇒ {_BC}.)
271  * Further, any prefix that already has selected sufficient effective value to fund the transaction cannot be improved
272  * by adding more UTXOs. If for example the candidate input set in {AB} is a valid solution, all potential descendant
273  * solutions {ABC}, {ABCD}, and {AB_D} must have a higher weight, thus instead of exploring the descendants of {AB}, we
274  * can SHIFT from {AB} to {A_C}.
275  *
276  * Given the above UTXO set, using a target of 11, and following these initial observations, the basic implementation of
277  * CoinGrinder visits the following 10 nodes:
278  *
279  * Node [eff_val/weight] Evaluation
280  * ---------------------------------------------------------------
281  * {A} [10/2] Insufficient funds: EXPLORE
282  * {AB} [17/3] Solution: SHIFT to omission branch
283  * {A_C} [15/3] Better solution: SHIFT to omission branch
284  * {A__D} [14/4] Worse solution, shift impossible due to leaf node: CUT to omission branch of {A__D},
285  * i.e. SHIFT to omission branch of {A}
286  * {_B} [7/1] Insufficient funds: EXPLORE
287  * {_BC} [12/2] Better solution: SHIFT to omission branch
288  * {_B_D} [11/3] Worse solution, shift impossible due to leaf node: CUT to omission branch of {_B_D},
289  * i.e. SHIFT to omission branch of {_B}
290  * {__C} [5/1] Insufficient funds: EXPLORE
291  * {__CD} [9/3] Insufficient funds, leaf node: CUT
292  * {___D} [4/2] Insufficient funds, leaf node, cannot CUT since only one UTXO selected: done.
293  *
294  * _______________________ {} ________________________
295  * / \
296  * A=[10/2] __________ {A} _________ ___________\____________
297  * / \ / \
298  * B=[7/1] {AB} __\_____ {_B} __ __\_____
299  * / \ / \ / \
300  * C=[5/1] {A_C} \ {_BC} \ {__C} \
301  * / / / /
302  * D=[4/2] {A__D} {_B_D} {__CD} {___D}
303  *
304  *
305  * We implement this tree walk in the following algorithm:
306  * 1. Add `next_utxo`
307  * 2. Evaluate candidate input set
308  * 3. Determine `next_utxo` by deciding whether to
309  * a) EXPLORE: Add next inclusion branch, e.g. {_B} ⇒ {_B} + `next_uxto`: C
310  * b) SHIFT: Replace last selected UTXO by next higher index, e.g. {A_C} ⇒ {A__} + `next_utxo`: D
311  * c) CUT: deselect last selected UTXO and shift to omission branch of penultimate UTXO, e.g. {AB_D} ⇒ {A_} + `next_utxo: C
312  *
313  * The implementation then adds further optimizations by discovering further situations in which either the inclusion
314  * branch can be skipped, or both the inclusion and omission branch can be skipped after evaluating the candidate input
315  * set in the node.
316  *
317  * @param std::vector<OutputGroup>& utxo_pool The UTXOs that we are choosing from. These UTXOs will be sorted in
318  * descending order by effective value, with lower weight preferred as a tie-breaker. (We can think of an output
319  * group with multiple as a heavier UTXO with the combined amount here.)
320  * @param const CAmount& selection_target This is the minimum amount that we need for the transaction without considering change.
321  * @param const CAmount& change_target The minimum budget for creating a change output, by which we increase the selection_target.
322  * @param int max_weight The maximum permitted weight for the input set.
323  * @returns The result of this coin selection algorithm, or std::nullopt
324  */
325 util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_weight)
326 {
327  std::sort(utxo_pool.begin(), utxo_pool.end(), descending_effval_weight);
328  // The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount)
329  std::vector<CAmount> lookahead(utxo_pool.size());
330  // The minimum UTXO weight among the remaining UTXOs after this UTXO index, e.g. min_tail_weight[5] = min(UTXO[6+].weight)
331  std::vector<int> min_tail_weight(utxo_pool.size());
332 
333  // Calculate lookahead values, min_tail_weights, and check that there are sufficient funds
334  CAmount total_available = 0;
335  int min_group_weight = std::numeric_limits<int>::max();
336  for (size_t i = 0; i < utxo_pool.size(); ++i) {
337  size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order
338  lookahead[index] = total_available;
339  min_tail_weight[index] = min_group_weight;
340  // UTXOs with non-positive effective value must have been filtered
341  Assume(utxo_pool[index].GetSelectionAmount() > 0);
342  total_available += utxo_pool[index].GetSelectionAmount();
343  min_group_weight = std::min(min_group_weight, utxo_pool[index].m_weight);
344  }
345 
346  const CAmount total_target = selection_target + change_target;
347  if (total_available < total_target) {
348  // Insufficient funds
349  return util::Error();
350  }
351 
352  // The current selection and the best input set found so far, stored as the utxo_pool indices of the UTXOs forming them
353  std::vector<size_t> curr_selection;
354  std::vector<size_t> best_selection;
355 
356  // The currently selected effective amount, and the effective amount of the best selection so far
357  CAmount curr_amount = 0;
358  CAmount best_selection_amount = MAX_MONEY;
359 
360  // The weight of the currently selected input set, and the weight of the best selection
361  int curr_weight = 0;
362  int best_selection_weight = max_weight; // Tie is fine, because we prefer lower selection amount
363 
364  // Whether the input sets generated during this search have exceeded the maximum transaction weight at any point
365  bool max_tx_weight_exceeded = false;
366 
367  // Index of the next UTXO to consider in utxo_pool
368  size_t next_utxo = 0;
369 
370  /*
371  * You can think of the current selection as a vector of booleans that has decided inclusion or exclusion of all
372  * UTXOs before `next_utxo`. When we consider the next UTXO, we extend this hypothetical boolean vector either with
373  * a true value if the UTXO is included or a false value if it is omitted. The equivalent state is stored more
374  * compactly as the list of indices of the included UTXOs and the `next_utxo` index.
375  *
376  * We can never find a new solution by deselecting a UTXO, because we then revisit a previously evaluated
377  * selection. Therefore, we only need to check whether we found a new solution _after adding_ a new UTXO.
378  *
379  * Each iteration of CoinGrinder starts by selecting the `next_utxo` and evaluating the current selection. We
380  * use three state transitions to progress from the current selection to the next promising selection:
381  *
382  * - EXPLORE inclusion branch: We do not have sufficient funds, yet. Add `next_utxo` to the current selection, then
383  * nominate the direct successor of the just selected UTXO as our `next_utxo` for the
384  * following iteration.
385  *
386  * Example:
387  * Current Selection: {0, 5, 7}
388  * Evaluation: EXPLORE, next_utxo: 8
389  * Next Selection: {0, 5, 7, 8}
390  *
391  * - SHIFT to omission branch: Adding more UTXOs to the current selection cannot produce a solution that is better
392  * than the current best, e.g. the current selection weight exceeds the max weight or
393  * the current selection amount is equal to or greater than the target.
394  * We designate our `next_utxo` the one after the tail of our current selection, then
395  * deselect the tail of our current selection.
396  *
397  * Example:
398  * Current Selection: {0, 5, 7}
399  * Evaluation: SHIFT, next_utxo: 8, omit last selected: {0, 5}
400  * Next Selection: {0, 5, 8}
401  *
402  * - CUT entire subtree: We have exhausted the inclusion branch for the penultimately selected UTXO, both the
403  * inclusion and the omission branch of the current prefix are barren. E.g. we have
404  * reached the end of the UTXO pool, so neither further EXPLORING nor SHIFTING can find
405  * any solutions. We designate our `next_utxo` the one after our penultimate selected,
406  * then deselect both the last and penultimate selected.
407  *
408  * Example:
409  * Current Selection: {0, 5, 7}
410  * Evaluation: CUT, next_utxo: 6, omit two last selected: {0}
411  * Next Selection: {0, 6}
412  */
413  auto deselect_last = [&]() {
414  OutputGroup& utxo = utxo_pool[curr_selection.back()];
415  curr_amount -= utxo.GetSelectionAmount();
416  curr_weight -= utxo.m_weight;
417  curr_selection.pop_back();
418  };
419 
420  SelectionResult result(selection_target, SelectionAlgorithm::CG);
421  bool is_done = false;
422  size_t curr_try = 0;
423  while (!is_done) {
424  bool should_shift{false}, should_cut{false};
425  // Select `next_utxo`
426  OutputGroup& utxo = utxo_pool[next_utxo];
427  curr_amount += utxo.GetSelectionAmount();
428  curr_weight += utxo.m_weight;
429  curr_selection.push_back(next_utxo);
430  ++next_utxo;
431  ++curr_try;
432 
433  // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further
434  auto curr_tail = curr_selection.back();
435  if (curr_amount + lookahead[curr_tail] < total_target) {
436  // Insufficient funds with lookahead: CUT
437  should_cut = true;
438  } else if (curr_weight > best_selection_weight) {
439  // best_selection_weight is initialized to max_weight
440  if (curr_weight > max_weight) max_tx_weight_exceeded = true;
441  // Worse weight than best solution. More UTXOs only increase weight:
442  // CUT if last selected group had minimal weight, else SHIFT
443  if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
444  should_cut = true;
445  } else {
446  should_shift = true;
447  }
448  } else if (curr_amount >= total_target) {
449  // Success, adding more weight cannot be better: SHIFT
450  should_shift = true;
451  if (curr_weight < best_selection_weight || (curr_weight == best_selection_weight && curr_amount < best_selection_amount)) {
452  // New lowest weight, or same weight with fewer funds tied up
453  best_selection = curr_selection;
454  best_selection_weight = curr_weight;
455  best_selection_amount = curr_amount;
456  }
457  } else if (!best_selection.empty() && curr_weight + int64_t{min_tail_weight[curr_tail]} * ((total_target - curr_amount + utxo_pool[curr_tail].GetSelectionAmount() - 1) / utxo_pool[curr_tail].GetSelectionAmount()) > best_selection_weight) {
458  // Compare minimal tail weight and last selected amount with the amount missing to gauge whether a better weight is still possible.
459  if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
460  should_cut = true;
461  } else {
462  should_shift = true;
463  }
464  }
465 
466  if (curr_try >= TOTAL_TRIES) {
467  // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
468  result.SetAlgoCompleted(false);
469  break;
470  }
471 
472  if (next_utxo == utxo_pool.size()) {
473  // Last added UTXO was end of UTXO pool, nothing left to add on inclusion or omission branch: CUT
474  should_cut = true;
475  }
476 
477  if (should_cut) {
478  // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can
479  // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e.
480  // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs)
481  should_cut = false;
482  deselect_last();
483  should_shift = true;
484  }
485 
486  while (should_shift) {
487  // Set `next_utxo` to one after last selected, then deselect last selected UTXO
488  if (curr_selection.empty()) {
489  // Exhausted search space before running into attempt limit
490  is_done = true;
491  result.SetAlgoCompleted(true);
492  break;
493  }
494  next_utxo = curr_selection.back() + 1;
495  deselect_last();
496  should_shift = false;
497 
498  // After SHIFTing to an omission branch, the `next_utxo` might have the same effective value as the UTXO we
499  // just omitted. Since lower weight is our tiebreaker on UTXOs with equal effective value for sorting, if it
500  // ties on the effective value, it _must_ have the same weight (i.e. be a "clone" of the prior UTXO) or a
501  // higher weight. If so, selecting `next_utxo` would produce an equivalent or worse selection as one we
502  // previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a differing amount.
503  while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {
504  if (next_utxo >= utxo_pool.size() - 1) {
505  // Reached end of UTXO pool skipping clones: SHIFT instead
506  should_shift = true;
507  break;
508  }
509  // Skip clone: previous UTXO is equivalent and unselected
510  ++next_utxo;
511  }
512  }
513  }
514 
515  result.SetSelectionsEvaluated(curr_try);
516 
517  if (best_selection.empty()) {
518  return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
519  }
520 
521  for (const size_t& i : best_selection) {
522  result.AddInput(utxo_pool[i]);
523  }
524 
525  return result;
526 }
527 
529 {
530 public:
531  int operator() (const OutputGroup& group1, const OutputGroup& group2) const
532  {
533  return group1.GetSelectionAmount() > group2.GetSelectionAmount();
534  }
535 };
536 
537 util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
538  int max_weight)
539 {
540  SelectionResult result(target_value, SelectionAlgorithm::SRD);
541  std::priority_queue<OutputGroup, std::vector<OutputGroup>, MinOutputGroupComparator> heap;
542 
543  // Include change for SRD as we want to avoid making really small change if the selection just
544  // barely meets the target. Just use the lower bound change target instead of the randomly
545  // generated one, since SRD will result in a random change amount anyway; avoid making the
546  // target needlessly large.
547  target_value += CHANGE_LOWER + change_fee;
548 
549  std::vector<size_t> indexes;
550  indexes.resize(utxo_pool.size());
551  std::iota(indexes.begin(), indexes.end(), 0);
552  Shuffle(indexes.begin(), indexes.end(), rng);
553 
554  CAmount selected_eff_value = 0;
555  int weight = 0;
556  bool max_tx_weight_exceeded = false;
557  for (const size_t i : indexes) {
558  const OutputGroup& group = utxo_pool.at(i);
559  Assume(group.GetSelectionAmount() > 0);
560 
561  // Add group to selection
562  heap.push(group);
563  selected_eff_value += group.GetSelectionAmount();
564  weight += group.m_weight;
565 
566  // If the selection weight exceeds the maximum allowed size, remove the least valuable inputs until we
567  // are below max weight.
568  if (weight > max_weight) {
569  max_tx_weight_exceeded = true; // mark it in case we don't find any useful result.
570  do {
571  const OutputGroup& to_remove_group = heap.top();
572  selected_eff_value -= to_remove_group.GetSelectionAmount();
573  weight -= to_remove_group.m_weight;
574  heap.pop();
575  } while (!heap.empty() && weight > max_weight);
576  }
577 
578  // Now check if we are above the target
579  if (selected_eff_value >= target_value) {
580  // Result found, add it.
581  while (!heap.empty()) {
582  result.AddInput(heap.top());
583  heap.pop();
584  }
585  return result;
586  }
587  }
588  return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
589 }
590 
602 static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
603  const CAmount& nTotalLower, const CAmount& nTargetValue,
604  std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
605 {
606  std::vector<char> vfIncluded;
607 
608  // Worst case "best" approximation is just all of the groups.
609  vfBest.assign(groups.size(), true);
610  nBest = nTotalLower;
611 
612  for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
613  {
614  vfIncluded.assign(groups.size(), false);
615  CAmount nTotal = 0;
616  bool fReachedTarget = false;
617  for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
618  {
619  for (unsigned int i = 0; i < groups.size(); i++)
620  {
621  //The solver here uses a randomized algorithm,
622  //the randomness serves no real security purpose but is just
623  //needed to prevent degenerate behavior and it is important
624  //that the rng is fast. We do not use a constant random sequence,
625  //because there may be some privacy improvement by making
626  //the selection random.
627  if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
628  {
629  nTotal += groups[i].GetSelectionAmount();
630  vfIncluded[i] = true;
631  if (nTotal >= nTargetValue)
632  {
633  fReachedTarget = true;
634  // If the total is between nTargetValue and nBest, it's our new best
635  // approximation.
636  if (nTotal < nBest)
637  {
638  nBest = nTotal;
639  vfBest = vfIncluded;
640  }
641  nTotal -= groups[i].GetSelectionAmount();
642  vfIncluded[i] = false;
643  }
644  }
645  }
646  }
647  }
648 }
649 
650 util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
651  CAmount change_target, FastRandomContext& rng, int max_weight)
652 {
653  SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
654 
655  // List of values less than target
656  std::optional<OutputGroup> lowest_larger;
657  // Groups with selection amount smaller than the target and any change we might produce.
658  // Don't include groups larger than this, because they will only cause us to overshoot.
659  std::vector<OutputGroup> applicable_groups;
660  CAmount nTotalLower = 0;
661 
662  Shuffle(groups.begin(), groups.end(), rng);
663 
664  for (const OutputGroup& group : groups) {
665  if (group.GetSelectionAmount() == nTargetValue) {
666  result.AddInput(group);
667  return result;
668  } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
669  applicable_groups.push_back(group);
670  nTotalLower += group.GetSelectionAmount();
671  } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
672  lowest_larger = group;
673  }
674  }
675 
676  if (nTotalLower == nTargetValue) {
677  for (const auto& group : applicable_groups) {
678  result.AddInput(group);
679  }
680  return result;
681  }
682 
683  if (nTotalLower < nTargetValue) {
684  if (!lowest_larger) return util::Error();
685  result.AddInput(*lowest_larger);
686  return result;
687  }
688 
689  // Solve subset sum by stochastic approximation
690  std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
691  std::vector<char> vfBest;
692  CAmount nBest;
693 
694  ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
695  if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
696  ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest);
697  }
698 
699  // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
700  // or the next bigger coin is closer), return the bigger coin
701  if (lowest_larger &&
702  ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
703  result.AddInput(*lowest_larger);
704  } else {
705  for (unsigned int i = 0; i < applicable_groups.size(); i++) {
706  if (vfBest[i]) {
707  result.AddInput(applicable_groups[i]);
708  }
709  }
710 
711  // If the result exceeds the maximum allowed size, return closest UTXO above the target
712  if (result.GetWeight() > max_weight) {
713  // No coin above target, nothing to do.
714  if (!lowest_larger) return ErrorMaxWeightExceeded();
715 
716  // Return closest UTXO above target
717  result.Clear();
718  result.AddInput(*lowest_larger);
719  }
720 
722  std::string log_message{"Coin selection best subset: "};
723  for (unsigned int i = 0; i < applicable_groups.size(); i++) {
724  if (vfBest[i]) {
725  log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
726  }
727  }
728  LogPrint(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
729  }
730  }
731 
732  return result;
733 }
734 
735 /******************************************************************************
736 
737  OutputGroup
738 
739  ******************************************************************************/
740 
741 void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t descendants) {
742  m_outputs.push_back(output);
743  auto& coin = *m_outputs.back();
744 
745  fee += coin.GetFee();
746 
747  coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
748  long_term_fee += coin.long_term_fee;
749 
750  effective_value += coin.GetEffectiveValue();
751 
752  m_from_me &= coin.from_me;
753  m_value += coin.txout.nValue;
754  m_depth = std::min(m_depth, coin.depth);
755  // ancestors here express the number of ancestors the new coin will end up having, which is
756  // the sum, rather than the max; this will overestimate in the cases where multiple inputs
757  // have common ancestors
758  m_ancestors += ancestors;
759  // descendants is the count as seen from the top ancestor, not the descendants as seen from the
760  // coin itself; thus, this value is counted as the max, not the sum
761  m_descendants = std::max(m_descendants, descendants);
762 
763  if (output->input_bytes > 0) {
764  m_weight += output->input_bytes * WITNESS_SCALE_FACTOR;
765  }
766 }
767 
768 bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
769 {
770  return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
771  && m_ancestors <= eligibility_filter.max_ancestors
772  && m_descendants <= eligibility_filter.max_descendants;
773 }
774 
776 {
778 }
779 
780 void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed)
781 {
782  if (group.m_outputs.empty()) return;
783 
784  Groups& groups = groups_by_type[type];
785  if (insert_positive && group.GetSelectionAmount() > 0) {
786  groups.positive_group.emplace_back(group);
787  all_groups.positive_group.emplace_back(group);
788  }
789  if (insert_mixed) {
790  groups.mixed_group.emplace_back(group);
791  all_groups.mixed_group.emplace_back(group);
792  }
793 }
794 
795 CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
796 {
797  if (payment_value <= CHANGE_LOWER / 2) {
798  return change_fee + CHANGE_LOWER;
799  } else {
800  // random value between 50ksat and min (payment_value * 2, 1milsat)
801  const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
802  return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
803  }
804 }
805 
807 {
808  // Overlapping ancestry can only lower the fees, not increase them
809  assert (discount >= 0);
810  bump_fee_group_discount = discount;
811 }
812 
813 void SelectionResult::RecalculateWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
814 {
815  // This function should not be called with empty inputs as that would mean the selection failed
816  assert(!m_selected_inputs.empty());
817 
818  // Always consider the cost of spending an input now vs in the future.
819  CAmount waste = 0;
820  for (const auto& coin_ptr : m_selected_inputs) {
821  const COutput& coin = *coin_ptr;
822  waste += coin.GetFee() - coin.long_term_fee;
823  }
824  // Bump fee of whole selection may diverge from sum of individual bump fees
825  waste -= bump_fee_group_discount;
826 
827  if (GetChange(min_viable_change, change_fee)) {
828  // if we have a minimum viable amount after deducting fees, account for
829  // cost of creating and spending change
830  waste += change_cost;
831  } else {
832  // When we are not making change (GetChange(…) == 0), consider the excess we are throwing away to fees
833  CAmount selected_effective_value = m_use_effective ? GetSelectedEffectiveValue() : GetSelectedValue();
834  assert(selected_effective_value >= m_target);
835  waste += selected_effective_value - m_target;
836  }
837 
838  m_waste = waste;
839 }
840 
841 void SelectionResult::SetAlgoCompleted(bool algo_completed)
842 {
843  m_algo_completed = algo_completed;
844 }
845 
847 {
848  return m_algo_completed;
849 }
850 
852 {
853  m_selections_evaluated = attempts;
854 }
855 
857 {
858  return m_selections_evaluated;
859 }
860 
862 {
863  return *Assert(m_waste);
864 }
865 
867 {
868  return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->txout.nValue; });
869 }
870 
872 {
873  return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->GetEffectiveValue(); }) + bump_fee_group_discount;
874 }
875 
877 {
878  return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->ancestor_bump_fees; }) - bump_fee_group_discount;
879 }
880 
882 {
883  m_selected_inputs.clear();
884  m_waste.reset();
885  m_weight = 0;
886 }
887 
889 {
890  // As it can fail, combine inputs first
891  InsertInputs(group.m_outputs);
892  m_use_effective = !group.m_subtract_fee_outputs;
893 
894  m_weight += group.m_weight;
895 }
896 
897 void SelectionResult::AddInputs(const std::set<std::shared_ptr<COutput>>& inputs, bool subtract_fee_outputs)
898 {
899  // As it can fail, combine inputs first
900  InsertInputs(inputs);
901  m_use_effective = !subtract_fee_outputs;
902 
903  m_weight += std::accumulate(inputs.cbegin(), inputs.cend(), 0, [](int sum, const auto& coin) {
904  return sum + std::max(coin->input_bytes, 0) * WITNESS_SCALE_FACTOR;
905  });
906 }
907 
909 {
910  // As it can fail, combine inputs first
912 
913  m_target += other.m_target;
916  m_algo = other.m_algo;
917  }
918 
919  m_weight += other.m_weight;
920 }
921 
922 const std::set<std::shared_ptr<COutput>>& SelectionResult::GetInputSet() const
923 {
924  return m_selected_inputs;
925 }
926 
927 std::vector<std::shared_ptr<COutput>> SelectionResult::GetShuffledInputVector() const
928 {
929  std::vector<std::shared_ptr<COutput>> coins(m_selected_inputs.begin(), m_selected_inputs.end());
930  Shuffle(coins.begin(), coins.end(), FastRandomContext());
931  return coins;
932 }
933 
935 {
936  Assert(m_waste.has_value());
937  Assert(other.m_waste.has_value());
938  // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
939  return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
940 }
941 
942 std::string COutput::ToString() const
943 {
944  return strprintf("COutput(%s, %d, %d) [%s]", outpoint.hash.ToString(), outpoint.n, depth, FormatMoney(txout.nValue));
945 }
946 
947 std::string GetAlgorithmName(const SelectionAlgorithm algo)
948 {
949  switch (algo)
950  {
951  case SelectionAlgorithm::BNB: return "bnb";
952  case SelectionAlgorithm::KNAPSACK: return "knapsack";
953  case SelectionAlgorithm::SRD: return "srd";
954  case SelectionAlgorithm::CG: return "cg";
955  case SelectionAlgorithm::MANUAL: return "manual";
956  // No default case to allow for compiler to warn
957  }
958  assert(false);
959 }
960 
961 CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
962 {
963  // change = SUM(inputs) - SUM(outputs) - fees
964  // 1) With SFFO we don't pay any fees
965  // 2) Otherwise we pay all the fees:
966  // - input fees are covered by GetSelectedEffectiveValue()
967  // - non_input_fee is included in m_target
968  // - change_fee
969  const CAmount change = m_use_effective
970  ? GetSelectedEffectiveValue() - m_target - change_fee
972 
973  if (change < min_viable_change) {
974  return 0;
975  }
976 
977  return change;
978 }
979 
980 } // namespace wallet
static constexpr CAmount MAX_MONEY
No amount larger than this (in satoshi) is valid.
Definition: amount.h:26
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
#define Assert(val)
Identity function.
Definition: check.h:77
#define Assume(val)
Assume is the identity function.
Definition: check.h:89
CAmount GetFee(uint32_t num_bytes) const
Return the fee in satoshis for the given vsize in vbytes.
Definition: feerate.cpp:23
uint32_t n
Definition: transaction.h:32
Txid hash
Definition: transaction.h:31
CAmount nValue
Definition: transaction.h:152
Fast randomness source.
Definition: random.h:145
bool randbool() noexcept
Generate a random boolean.
Definition: random.h:228
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:203
std::string ToString() const
int operator()(const OutputGroup &group1, const OutputGroup &group2) const
static const int WITNESS_SCALE_FACTOR
Definition: consensus.h:21
volatile double sum
Definition: examples.cpp:10
#define LogPrint(category,...)
Definition: logging.h:263
static bool LogAcceptCategory(BCLog::LogFlags category, BCLog::Level level)
Return true if log accepts specified category, at the specified level.
Definition: logging.h:209
std::string FormatMoney(const CAmount n)
Money parsing/formatting utilities.
Definition: moneystr.cpp:19
@ SELECTCOINS
Definition: logging.h:51
util::Result< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, int max_weight)
static constexpr CAmount CHANGE_UPPER
upper bound for randomly-chosen target change amount
Definition: coinselection.h:25
struct wallet::@17 descending_effval_weight
static constexpr CAmount CHANGE_LOWER
lower bound for randomly-chosen target change amount
Definition: coinselection.h:23
CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext &rng)
Choose a random change target for each transaction to make it harder to fingerprint the Core wallet b...
util::Result< SelectionResult > CoinGrinder(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, CAmount change_target, int max_weight)
SelectionAlgorithm
struct wallet::@16 descending
static void ApproximateBestSubset(FastRandomContext &insecure_rand, const std::vector< OutputGroup > &groups, const CAmount &nTotalLower, const CAmount &nTargetValue, std::vector< char > &vfBest, CAmount &nBest, int iterations=1000)
Find a subset of the OutputGroups that is at least as large as, but as close as possible to,...
util::Result< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue, CAmount change_target, FastRandomContext &rng, int max_weight)
util::Result< SelectionResult > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext &rng, int max_weight)
Select coins by Single Random Draw.
std::string GetAlgorithmName(const SelectionAlgorithm algo)
static const size_t TOTAL_TRIES
static util::Result< SelectionResult > ErrorMaxWeightExceeded()
OutputType
Definition: outputtype.h:17
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
Definition: random.h:265
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:28
CAmount long_term_fee
The fee required to spend this output at the consolidation feerate.
Definition: coinselection.h:73
COutPoint outpoint
The outpoint identifying this UTXO.
Definition: coinselection.h:38
int depth
Depth in block chain.
Definition: coinselection.h:48
std::string ToString() const
CTxOut txout
The output itself.
Definition: coinselection.h:41
CAmount GetFee() const
Parameters for filtering which OutputGroups we may use in coin selection.
const uint64_t max_ancestors
Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup.
const uint64_t max_descendants
Maximum number of descendants that a single UTXO in the OutputGroup may have.
const int conf_theirs
Minimum number of confirmations for outputs received from a different wallet.
const int conf_mine
Minimum number of confirmations for outputs that we sent to ourselves.
std::vector< OutputGroup > positive_group
std::vector< OutputGroup > mixed_group
A group of UTXOs paid to the same output script.
CFeeRate m_long_term_feerate
The feerate for spending a created change output eventually (i.e.
bool m_from_me
Whether the UTXOs were sent by the wallet to itself.
CAmount m_value
The total value of the UTXOs in sum.
void Insert(const std::shared_ptr< COutput > &output, size_t ancestors, size_t descendants)
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
CAmount GetSelectionAmount() const
int m_depth
The minimum number of confirmations the UTXOs in the group have.
int m_weight
Total weight of the UTXOs in this group.
bool EligibleForSpending(const CoinEligibilityFilter &eligibility_filter) const
CAmount effective_value
The value of the UTXOs after deducting the cost of spending them at the effective feerate.
size_t m_ancestors
The aggregated count of unconfirmed ancestors of all UTXOs in this group.
CAmount fee
The fee to spend these UTXOs at the effective feerate.
CAmount long_term_fee
The fee to spend these UTXOs at the long term feerate.
size_t m_descendants
The maximum count of descendants of a single UTXO in this output group.
std::vector< std::shared_ptr< COutput > > m_outputs
The list of UTXOs contained in this output group.
void Push(const OutputGroup &group, OutputType type, bool insert_positive, bool insert_mixed)
std::map< OutputType, Groups > groups_by_type
int m_weight
Total weight of the selected inputs.
bool operator<(SelectionResult other) const
size_t m_selections_evaluated
The count of selections that were evaluated by this coin selection attempt.
std::set< std::shared_ptr< COutput > > m_selected_inputs
Set of inputs selected by the algorithm to use in the transaction.
CAmount bump_fee_group_discount
How much individual inputs overestimated the bump fees for the shared ancestry.
void Merge(const SelectionResult &other)
Combines the.
size_t GetSelectionsEvaluated() const
Get selections_evaluated.
const std::set< std::shared_ptr< COutput > > & GetInputSet() const
Get m_selected_inputs.
SelectionAlgorithm m_algo
The algorithm used to produce this result.
bool GetAlgoCompleted() const
Get m_algo_completed.
void SetBumpFeeDiscount(const CAmount discount)
How much individual inputs overestimated the bump fees for shared ancestries.
void AddInput(const OutputGroup &group)
void AddInputs(const std::set< std::shared_ptr< COutput >> &inputs, bool subtract_fee_outputs)
CAmount GetSelectedEffectiveValue() const
CAmount GetTotalBumpFees() const
bool m_algo_completed
False if algorithm was cut short by hitting limit of attempts and solution is non-optimal.
CAmount m_target
The target the algorithm selected for.
CAmount GetChange(const CAmount min_viable_change, const CAmount change_fee) const
Get the amount for the change output after paying needed fees.
void InsertInputs(const T &inputs)
void SetAlgoCompleted(bool algo_completed)
Tracks that algorithm was able to exhaustively search the entire combination space before hitting lim...
CAmount GetSelectedValue() const
Get the sum of the input values.
void RecalculateWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
Calculates and stores the waste for this result given the cost of change and the opportunity cost of ...
std::optional< CAmount > m_waste
The computed waste.
bool m_use_effective
Whether the input values for calculations should be the effective value (true) or normal value (false...
void SetSelectionsEvaluated(size_t attempts)
Record the number of selections that were evaluated.
std::vector< std::shared_ptr< COutput > > GetShuffledInputVector() const
Get the vector of COutputs that will be used to fill in a CTransaction's vin.
CAmount GetWaste() const
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1162
bilingual_str _(const char *psz)
Translation function.
Definition: translation.h:74
assert(!tx.IsCoinBase())