Bitcoin Core  24.99.0
P2P Digital Currency
coinselection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017-2021 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 <policy/feerate.h>
9 #include <util/check.h>
10 #include <util/system.h>
11 #include <util/moneystr.h>
12 
13 #include <numeric>
14 #include <optional>
15 
16 namespace wallet {
17 // Descending order comparator
18 struct {
19  bool operator()(const OutputGroup& a, const OutputGroup& b) const
20  {
21  return a.GetSelectionAmount() > b.GetSelectionAmount();
22  }
24 
25 /*
26  * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
27  * set that can pay for the spending target and does not exceed the spending target by more than the
28  * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
29  * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
30  * are sorted by their effective values and the tree is explored deterministically per the inclusion
31  * branch first. At each node, the algorithm checks whether the selection is within the target range.
32  * While the selection has not reached the target range, more UTXOs are included. When a selection's
33  * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
34  * At that point, the last included UTXO is deselected and the corresponding omission branch explored
35  * instead. The search ends after the complete tree has been searched or after a limited number of tries.
36  *
37  * The search continues to search for better solutions after one solution has been found. The best
38  * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
39  * spend the current inputs at the given fee rate minus the long term expected cost to spend the
40  * inputs, plus the amount by which the selection exceeds the spending target:
41  *
42  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
43  *
44  * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
45  * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
46  * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
47  * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
48  * predecessor.
49  *
50  * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
51  * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
52  *
53  * @param const std::vector<OutputGroup>& utxo_pool The set of UTXO groups that we are choosing from.
54  * These UTXO groups will be sorted in descending order by effective value and the OutputGroups'
55  * values are their effective values.
56  * @param const CAmount& selection_target This is the value that we want to select. It is the lower
57  * bound of the range.
58  * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
59  * This plus selection_target is the upper bound of the range.
60  * @returns The result of this coin selection algorithm, or std::nullopt
61  */
62 
63 static const size_t TOTAL_TRIES = 100000;
64 
65 std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
66 {
67  SelectionResult result(selection_target, SelectionAlgorithm::BNB);
68  CAmount curr_value = 0;
69  std::vector<size_t> curr_selection; // selected utxo indexes
70 
71  // Calculate curr_available_value
72  CAmount curr_available_value = 0;
73  for (const OutputGroup& utxo : utxo_pool) {
74  // Assert that this utxo is not negative. It should never be negative,
75  // effective value calculation should have removed it
76  assert(utxo.GetSelectionAmount() > 0);
77  curr_available_value += utxo.GetSelectionAmount();
78  }
79  if (curr_available_value < selection_target) {
80  return std::nullopt;
81  }
82 
83  // Sort the utxo_pool
84  std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
85 
86  CAmount curr_waste = 0;
87  std::vector<size_t> best_selection;
88  CAmount best_waste = MAX_MONEY;
89 
90  // Depth First search loop for choosing the UTXOs
91  for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
92  // Conditions for starting a backtrack
93  bool backtrack = false;
94  if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
95  curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
96  (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing
97  backtrack = true;
98  } else if (curr_value >= selection_target) { // Selected value is within range
99  curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison
100  // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
101  // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
102  // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
103  // explore any more UTXOs to avoid burning money like that.
104  if (curr_waste <= best_waste) {
105  best_selection = curr_selection;
106  best_waste = curr_waste;
107  }
108  curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
109  backtrack = true;
110  }
111 
112  if (backtrack) { // Backtracking, moving backwards
113  if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
114  break;
115  }
116 
117  // Add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO.
118  for (--utxo_pool_index; utxo_pool_index > curr_selection.back(); --utxo_pool_index) {
119  curr_available_value += utxo_pool.at(utxo_pool_index).GetSelectionAmount();
120  }
121 
122  // Output was included on previous iterations, try excluding now.
123  assert(utxo_pool_index == curr_selection.back());
124  OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
125  curr_value -= utxo.GetSelectionAmount();
126  curr_waste -= utxo.fee - utxo.long_term_fee;
127  curr_selection.pop_back();
128  } else { // Moving forwards, continuing down this branch
129  OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
130 
131  // Remove this utxo from the curr_available_value utxo amount
132  curr_available_value -= utxo.GetSelectionAmount();
133 
134  if (curr_selection.empty() ||
135  // The previous index is included and therefore not relevant for exclusion shortcut
136  (utxo_pool_index - 1) == curr_selection.back() ||
137  // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded.
138  // 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.
139  utxo.GetSelectionAmount() != utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() ||
140  utxo.fee != utxo_pool.at(utxo_pool_index - 1).fee)
141  {
142  // Inclusion branch first (Largest First Exploration)
143  curr_selection.push_back(utxo_pool_index);
144  curr_value += utxo.GetSelectionAmount();
145  curr_waste += utxo.fee - utxo.long_term_fee;
146  }
147  }
148  }
149 
150  // Check for solution
151  if (best_selection.empty()) {
152  return std::nullopt;
153  }
154 
155  // Set output set
156  for (const size_t& i : best_selection) {
157  result.AddInput(utxo_pool.at(i));
158  }
159  result.ComputeAndSetWaste(cost_of_change, cost_of_change, CAmount{0});
160  assert(best_waste == result.GetWaste());
161 
162  return result;
163 }
164 
165 std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng)
166 {
167  SelectionResult result(target_value, SelectionAlgorithm::SRD);
168 
169  // Include change for SRD as we want to avoid making really small change if the selection just
170  // barely meets the target. Just use the lower bound change target instead of the randomly
171  // generated one, since SRD will result in a random change amount anyway; avoid making the
172  // target needlessly large.
173  target_value += CHANGE_LOWER;
174 
175  std::vector<size_t> indexes;
176  indexes.resize(utxo_pool.size());
177  std::iota(indexes.begin(), indexes.end(), 0);
178  Shuffle(indexes.begin(), indexes.end(), rng);
179 
180  CAmount selected_eff_value = 0;
181  for (const size_t i : indexes) {
182  const OutputGroup& group = utxo_pool.at(i);
183  Assume(group.GetSelectionAmount() > 0);
184  selected_eff_value += group.GetSelectionAmount();
185  result.AddInput(group);
186  if (selected_eff_value >= target_value) {
187  return result;
188  }
189  }
190  return std::nullopt;
191 }
192 
204 static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
205  const CAmount& nTotalLower, const CAmount& nTargetValue,
206  std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
207 {
208  std::vector<char> vfIncluded;
209 
210  // Worst case "best" approximation is just all of the groups.
211  vfBest.assign(groups.size(), true);
212  nBest = nTotalLower;
213 
214  for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
215  {
216  vfIncluded.assign(groups.size(), false);
217  CAmount nTotal = 0;
218  bool fReachedTarget = false;
219  for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
220  {
221  for (unsigned int i = 0; i < groups.size(); i++)
222  {
223  //The solver here uses a randomized algorithm,
224  //the randomness serves no real security purpose but is just
225  //needed to prevent degenerate behavior and it is important
226  //that the rng is fast. We do not use a constant random sequence,
227  //because there may be some privacy improvement by making
228  //the selection random.
229  if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
230  {
231  nTotal += groups[i].GetSelectionAmount();
232  vfIncluded[i] = true;
233  if (nTotal >= nTargetValue)
234  {
235  fReachedTarget = true;
236  // If the total is between nTargetValue and nBest, it's our new best
237  // approximation.
238  if (nTotal < nBest)
239  {
240  nBest = nTotal;
241  vfBest = vfIncluded;
242  }
243  nTotal -= groups[i].GetSelectionAmount();
244  vfIncluded[i] = false;
245  }
246  }
247  }
248  }
249  }
250 }
251 
252 std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
253  CAmount change_target, FastRandomContext& rng)
254 {
255  SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
256 
257  // List of values less than target
258  std::optional<OutputGroup> lowest_larger;
259  // Groups with selection amount smaller than the target and any change we might produce.
260  // Don't include groups larger than this, because they will only cause us to overshoot.
261  std::vector<OutputGroup> applicable_groups;
262  CAmount nTotalLower = 0;
263 
264  Shuffle(groups.begin(), groups.end(), rng);
265 
266  for (const OutputGroup& group : groups) {
267  if (group.GetSelectionAmount() == nTargetValue) {
268  result.AddInput(group);
269  return result;
270  } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
271  applicable_groups.push_back(group);
272  nTotalLower += group.GetSelectionAmount();
273  } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
274  lowest_larger = group;
275  }
276  }
277 
278  if (nTotalLower == nTargetValue) {
279  for (const auto& group : applicable_groups) {
280  result.AddInput(group);
281  }
282  return result;
283  }
284 
285  if (nTotalLower < nTargetValue) {
286  if (!lowest_larger) return std::nullopt;
287  result.AddInput(*lowest_larger);
288  return result;
289  }
290 
291  // Solve subset sum by stochastic approximation
292  std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
293  std::vector<char> vfBest;
294  CAmount nBest;
295 
296  ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
297  if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
298  ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest);
299  }
300 
301  // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
302  // or the next bigger coin is closer), return the bigger coin
303  if (lowest_larger &&
304  ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
305  result.AddInput(*lowest_larger);
306  } else {
307  for (unsigned int i = 0; i < applicable_groups.size(); i++) {
308  if (vfBest[i]) {
309  result.AddInput(applicable_groups[i]);
310  }
311  }
312 
314  std::string log_message{"Coin selection best subset: "};
315  for (unsigned int i = 0; i < applicable_groups.size(); i++) {
316  if (vfBest[i]) {
317  log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
318  }
319  }
320  LogPrint(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
321  }
322  }
323 
324  return result;
325 }
326 
327 /******************************************************************************
328 
329  OutputGroup
330 
331  ******************************************************************************/
332 
333 void OutputGroup::Insert(const COutput& output, size_t ancestors, size_t descendants, bool positive_only) {
334  // Filter for positive only here before adding the coin
335  if (positive_only && output.GetEffectiveValue() <= 0) return;
336 
337  m_outputs.push_back(output);
338  COutput& coin = m_outputs.back();
339 
340  fee += coin.GetFee();
341 
342  coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
344 
346 
347  m_from_me &= coin.from_me;
348  m_value += coin.txout.nValue;
349  m_depth = std::min(m_depth, coin.depth);
350  // ancestors here express the number of ancestors the new coin will end up having, which is
351  // the sum, rather than the max; this will overestimate in the cases where multiple inputs
352  // have common ancestors
353  m_ancestors += ancestors;
354  // descendants is the count as seen from the top ancestor, not the descendants as seen from the
355  // coin itself; thus, this value is counted as the max, not the sum
356  m_descendants = std::max(m_descendants, descendants);
357 }
358 
359 bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
360 {
361  return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
362  && m_ancestors <= eligibility_filter.max_ancestors
363  && m_descendants <= eligibility_filter.max_descendants;
364 }
365 
367 {
369 }
370 
371 CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
372 {
373  // This function should not be called with empty inputs as that would mean the selection failed
374  assert(!inputs.empty());
375 
376  // Always consider the cost of spending an input now vs in the future.
377  CAmount waste = 0;
378  CAmount selected_effective_value = 0;
379  for (const COutput& coin : inputs) {
380  waste += coin.GetFee() - coin.long_term_fee;
381  selected_effective_value += use_effective_value ? coin.GetEffectiveValue() : coin.txout.nValue;
382  }
383 
384  if (change_cost) {
385  // Consider the cost of making change and spending it in the future
386  // If we aren't making change, the caller should've set change_cost to 0
387  assert(change_cost > 0);
388  waste += change_cost;
389  } else {
390  // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
391  assert(selected_effective_value >= target);
392  waste += selected_effective_value - target;
393  }
394 
395  return waste;
396 }
397 
398 CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
399 {
400  if (payment_value <= CHANGE_LOWER / 2) {
401  return change_fee + CHANGE_LOWER;
402  } else {
403  // random value between 50ksat and min (payment_value * 2, 1milsat)
404  const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
405  return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
406  }
407 }
408 
409 void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
410 {
411  const CAmount change = GetChange(min_viable_change, change_fee);
412 
413  if (change > 0) {
415  } else {
417  }
418 }
419 
421 {
422  return *Assert(m_waste);
423 }
424 
426 {
427  return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.txout.nValue; });
428 }
429 
431 {
432  return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.GetEffectiveValue(); });
433 }
434 
436 {
437  m_selected_inputs.clear();
438  m_waste.reset();
439 }
440 
442 {
445 }
446 
448 {
449  m_target += other.m_target;
452  m_algo = other.m_algo;
453  }
455 }
456 
457 const std::set<COutput>& SelectionResult::GetInputSet() const
458 {
459  return m_selected_inputs;
460 }
461 
462 std::vector<COutput> SelectionResult::GetShuffledInputVector() const
463 {
464  std::vector<COutput> coins(m_selected_inputs.begin(), m_selected_inputs.end());
465  Shuffle(coins.begin(), coins.end(), FastRandomContext());
466  return coins;
467 }
468 
470 {
471  Assert(m_waste.has_value());
472  Assert(other.m_waste.has_value());
473  // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
474  return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
475 }
476 
477 std::string COutput::ToString() const
478 {
479  return strprintf("COutput(%s, %d, %d) [%s]", outpoint.hash.ToString(), outpoint.n, depth, FormatMoney(txout.nValue));
480 }
481 
482 std::string GetAlgorithmName(const SelectionAlgorithm algo)
483 {
484  switch (algo)
485  {
486  case SelectionAlgorithm::BNB: return "bnb";
487  case SelectionAlgorithm::KNAPSACK: return "knapsack";
488  case SelectionAlgorithm::SRD: return "srd";
489  case SelectionAlgorithm::MANUAL: return "manual";
490  // No default case to allow for compiler to warn
491  }
492  assert(false);
493 }
494 
495 CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
496 {
497  // change = SUM(inputs) - SUM(outputs) - fees
498  // 1) With SFFO we don't pay any fees
499  // 2) Otherwise we pay all the fees:
500  // - input fees are covered by GetSelectedEffectiveValue()
501  // - non_input_fee is included in m_target
502  // - change_fee
503  const CAmount change = m_use_effective
504  ? GetSelectedEffectiveValue() - m_target - change_fee
506 
507  if (change < min_viable_change) {
508  return 0;
509  }
510 
511  return change;
512 }
513 
514 } // 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:74
#define Assume(val)
Assume is the identity function.
Definition: check.h:86
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:38
uint256 hash
Definition: transaction.h:37
CAmount nValue
Definition: transaction.h:159
Fast randomness source.
Definition: random.h:143
bool randbool() noexcept
Generate a random boolean.
Definition: random.h:234
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:213
std::string ToString() const
Definition: uint256.cpp:64
volatile double sum
Definition: examples.cpp:10
#define LogPrint(category,...)
Definition: logging.h:243
static bool LogAcceptCategory(BCLog::LogFlags category, BCLog::Level level)
Return true if log accepts specified category, at the specified level.
Definition: logging.h:204
std::string FormatMoney(const CAmount n)
Money parsing/formatting utilities.
Definition: moneystr.cpp:16
@ SELECTCOINS
Definition: logging.h:50
void insert(Tdst &dst, const Tsrc &src)
Simplification of std insertion.
Definition: system.h:547
Definition: node.h:39
static constexpr CAmount CHANGE_UPPER
upper bound for randomly-chosen target change amount
Definition: coinselection.h:19
CAmount GetSelectionWaste(const std::set< COutput > &inputs, CAmount change_cost, CAmount target, bool use_effective_value)
Compute the waste for this result given the cost of change and the opportunity cost of spending these...
static constexpr CAmount CHANGE_LOWER
lower bound for randomly-chosen target change amount
Definition: coinselection.h:17
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...
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,...
std::optional< SelectionResult > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value, FastRandomContext &rng)
Select coins by Single Random Draw.
std::optional< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue, CAmount change_target, FastRandomContext &rng)
std::string GetAlgorithmName(const SelectionAlgorithm algo)
std::optional< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change)
static const size_t TOTAL_TRIES
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
Definition: random.h:271
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:22
CAmount long_term_fee
The fee required to spend this output at the consolidation feerate.
Definition: coinselection.h:67
bool from_me
Whether the transaction containing this output is sent from the owning wallet.
Definition: coinselection.h:64
COutPoint outpoint
The outpoint identifying this UTXO.
Definition: coinselection.h:32
int depth
Depth in block chain.
Definition: coinselection.h:42
std::string ToString() const
CTxOut txout
The output itself.
Definition: coinselection.h:35
CAmount GetFee() const
int input_bytes
Pre-computed estimated size of this output as a fully-signed input in a transaction.
Definition: coinselection.h:45
CAmount GetEffectiveValue() 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.
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.
bool m_subtract_fee_outputs
Indicate that we are subtracting the fee from outputs.
void Insert(const COutput &output, size_t ancestors, size_t descendants, bool positive_only)
CAmount GetSelectionAmount() const
std::vector< COutput > m_outputs
The list of UTXOs contained in this output group.
int m_depth
The minimum number of confirmations the UTXOs in the group have.
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.
bool operator<(SelectionResult other) const
void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
Calculates and stores the waste for this selection via GetSelectionWaste.
std::vector< COutput > GetShuffledInputVector() const
Get the vector of COutputs that will be used to fill in a CTransaction's vin.
const std::set< COutput > & GetInputSet() const
Get m_selected_inputs.
void Merge(const SelectionResult &other)
SelectionAlgorithm m_algo
The algorithm used to produce this result.
void AddInput(const OutputGroup &group)
CAmount GetSelectedEffectiveValue() const
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.
std::set< COutput > m_selected_inputs
Set of inputs selected by the algorithm to use in the transaction.
CAmount GetSelectedValue() const
Get the sum of the input values.
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...
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:1164
assert(!tx.IsCoinBase())