Line data Source code
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 <policy/feerate.h>
8 : #include <util/check.h>
9 : #include <util/system.h>
10 : #include <util/moneystr.h>
11 :
12 : #include <coinjoin/common.h>
13 :
14 : #include <numeric>
15 : #include <optional>
16 : #include <queue>
17 :
18 : namespace wallet {
19 12 : static util::Result<SelectionResult> ErrorMaxWeightExceeded()
20 : {
21 12 : return util::Error{_("The inputs size exceeds the maximum weight. "
22 : "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")};
23 0 : }
24 :
25 185292 : static int GetSelectionWeight(const OutputGroup& group)
26 : {
27 370584 : return std::accumulate(group.m_outputs.cbegin(), group.m_outputs.cend(), 0, [](int sum, const COutput& coin) {
28 185292 : return sum + std::max(coin.input_bytes, 0);
29 : });
30 : }
31 :
32 3267 : static int GetSelectionWeight(const SelectionResult& result)
33 : {
34 151100 : return std::accumulate(result.GetInputSet().cbegin(), result.GetInputSet().cend(), 0, [](int sum, const COutput& coin) {
35 147833 : return sum + std::max(coin.input_bytes, 0);
36 : });
37 : }
38 :
39 : // Descending order comparator
40 : struct {
41 1909766 : bool operator()(const OutputGroup& a, const OutputGroup& b) const
42 : {
43 1909766 : return a.GetSelectionAmount() > b.GetSelectionAmount();
44 : }
45 : } descending;
46 :
47 : /*
48 : * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
49 : * set that can pay for the spending target and does not exceed the spending target by more than the
50 : * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
51 : * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
52 : * are sorted by their effective values and the tree is explored deterministically per the inclusion
53 : * branch first. At each node, the algorithm checks whether the selection is within the target range.
54 : * While the selection has not reached the target range, more UTXOs are included. When a selection's
55 : * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
56 : * At that point, the last included UTXO is deselected and the corresponding omission branch explored
57 : * instead. The search ends after the complete tree has been searched or after a limited number of tries.
58 : *
59 : * The search continues to search for better solutions after one solution has been found. The best
60 : * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
61 : * spend the current inputs at the given fee rate minus the long term expected cost to spend the
62 : * inputs, plus the amount by which the selection exceeds the spending target:
63 : *
64 : * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
65 : *
66 : * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
67 : * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
68 : * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
69 : * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
70 : * predecessor.
71 : *
72 : * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
73 : * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
74 : *
75 : * @param const std::vector<OutputGroup>& utxo_pool The set of UTXO groups that we are choosing from.
76 : * These UTXO groups will be sorted in descending order by effective value and the OutputGroups'
77 : * values are their effective values.
78 : * @param const CAmount& selection_target This is the value that we want to select. It is the lower
79 : * bound of the range.
80 : * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
81 : * This plus selection_target is the upper bound of the range.
82 : * @returns The result of this coin selection algorithm, or std::nullopt
83 : */
84 :
85 : static const size_t TOTAL_TRIES = 100000;
86 :
87 22374 : util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
88 : int max_weight)
89 : {
90 22374 : if (utxo_pool.empty()) return util::Error();
91 :
92 113 : SelectionResult result(selection_target, SelectionAlgorithm::BNB);
93 113 : CAmount curr_value = 0;
94 113 : std::vector<size_t> curr_selection; // selected utxo indexes
95 113 : int curr_selection_weight = 0; // sum of selected utxo weight
96 :
97 : // Calculate curr_available_value
98 113 : CAmount curr_available_value = 0;
99 51816 : for (const OutputGroup& utxo : utxo_pool) {
100 : // Assert that this utxo is not negative. It should never be negative,
101 : // effective value calculation should have removed it
102 51703 : assert(utxo.GetSelectionAmount() > 0);
103 51703 : curr_available_value += utxo.GetSelectionAmount();
104 : }
105 113 : if (curr_available_value < selection_target) {
106 2 : return util::Error();
107 : }
108 :
109 : // Sort the utxo_pool
110 111 : std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
111 :
112 111 : CAmount curr_waste = 0;
113 111 : std::vector<size_t> best_selection;
114 111 : CAmount best_waste = MAX_MONEY;
115 :
116 111 : bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
117 111 : bool max_tx_weight_exceeded = false;
118 :
119 : // Depth First search loop for choosing the UTXOs
120 285301 : for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
121 : // Conditions for starting a backtrack
122 285299 : bool backtrack = false;
123 285299 : if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
124 248810 : curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
125 192610 : (curr_waste > best_waste && is_feerate_high)) { // Don't select things which we know will be more wasteful if the waste is increasing
126 92689 : backtrack = true;
127 285299 : } else if (curr_selection_weight > max_weight) { // Exceeding weight for standard tx, cannot find more solutions by adding more inputs
128 0 : max_tx_weight_exceeded = true;
129 0 : backtrack = true;
130 192610 : } else if (curr_value >= selection_target) { // Selected value is within range
131 11 : curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison
132 : // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
133 : // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
134 : // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
135 : // explore any more UTXOs to avoid burning money like that.
136 11 : if (curr_waste <= best_waste) {
137 11 : best_selection = curr_selection;
138 11 : best_waste = curr_waste;
139 11 : }
140 11 : curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
141 11 : backtrack = true;
142 11 : }
143 :
144 285299 : if (backtrack) { // Backtracking, moving backwards
145 92700 : if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
146 109 : break;
147 : }
148 :
149 : // Add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO.
150 233536 : for (--utxo_pool_index; utxo_pool_index > curr_selection.back(); --utxo_pool_index) {
151 140945 : curr_available_value += utxo_pool.at(utxo_pool_index).GetSelectionAmount();
152 140945 : }
153 :
154 : // Output was included on previous iterations, try excluding now.
155 92591 : assert(utxo_pool_index == curr_selection.back());
156 92591 : OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
157 92591 : curr_value -= utxo.GetSelectionAmount();
158 92591 : curr_waste -= utxo.fee - utxo.long_term_fee;
159 92591 : curr_selection_weight -= GetSelectionWeight(utxo);
160 92591 : curr_selection.pop_back();
161 92591 : } else { // Moving forwards, continuing down this branch
162 192599 : OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
163 :
164 : // Remove this utxo from the curr_available_value utxo amount
165 192599 : curr_available_value -= utxo.GetSelectionAmount();
166 :
167 292587 : if (curr_selection.empty() ||
168 : // The previous index is included and therefore not relevant for exclusion shortcut
169 190970 : (utxo_pool_index - 1) == curr_selection.back() ||
170 : // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded.
171 : // 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.
172 154570 : utxo.GetSelectionAmount() != utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() ||
173 99988 : utxo.fee != utxo_pool.at(utxo_pool_index - 1).fee)
174 : {
175 : // Inclusion branch first (Largest First Exploration)
176 92611 : curr_selection.push_back(utxo_pool_index);
177 92611 : curr_value += utxo.GetSelectionAmount();
178 92611 : curr_waste += utxo.fee - utxo.long_term_fee;
179 92611 : curr_selection_weight += GetSelectionWeight(utxo);
180 92611 : }
181 : }
182 285190 : }
183 :
184 : // Check for solution
185 111 : if (best_selection.empty()) {
186 103 : return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
187 : }
188 :
189 : // Set output set
190 37 : for (const size_t& i : best_selection) {
191 29 : result.AddInput(utxo_pool.at(i));
192 : }
193 8 : result.ComputeAndSetWaste(CAmount{0});
194 8 : assert(best_waste == result.GetWaste());
195 :
196 8 : return result;
197 22374 : }
198 :
199 : class MinOutputGroupComparator
200 : {
201 : public:
202 322 : bool operator()(const OutputGroup& group1, const OutputGroup& group2) const
203 : {
204 322 : return group1.GetSelectionAmount() > group2.GetSelectionAmount();
205 : }
206 : };
207 :
208 22263 : util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng,
209 : int max_weight)
210 : {
211 22263 : if (utxo_pool.empty()) return util::Error();
212 :
213 3 : SelectionResult result(target_value, SelectionAlgorithm::SRD);
214 3 : std::priority_queue<OutputGroup, std::vector<OutputGroup>, MinOutputGroupComparator> heap;
215 :
216 3 : std::vector<size_t> indexes;
217 3 : indexes.resize(utxo_pool.size());
218 3 : std::iota(indexes.begin(), indexes.end(), 0);
219 3 : Shuffle(indexes.begin(), indexes.end(), rng);
220 :
221 3 : CAmount selected_eff_value = 0;
222 3 : int weight = 0;
223 3 : bool max_tx_weight_exceeded = false;
224 86 : for (const size_t i : indexes) {
225 84 : const OutputGroup& group = utxo_pool.at(i);
226 84 : Assume(group.GetSelectionAmount() > 0);
227 :
228 84 : heap.push(group);
229 84 : selected_eff_value += group.GetSelectionAmount();
230 84 : weight += GetSelectionWeight(group);
231 :
232 84 : if (weight > max_weight) {
233 6 : max_tx_weight_exceeded = true;
234 6 : do {
235 6 : const OutputGroup& to_remove_group = heap.top();
236 6 : selected_eff_value -= to_remove_group.GetSelectionAmount();
237 6 : weight -= GetSelectionWeight(to_remove_group);
238 6 : heap.pop();
239 6 : } while (!heap.empty() && weight > max_weight);
240 6 : }
241 :
242 84 : if (selected_eff_value >= target_value) {
243 45 : while (!heap.empty()) {
244 44 : result.AddInput(heap.top());
245 44 : heap.pop();
246 : }
247 1 : return result;
248 : }
249 : }
250 2 : return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
251 22263 : }
252 :
253 : /** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
254 : * target amount; solve subset sum.
255 : * param@[in] groups OutputGroups to choose from, sorted by value in descending order.
256 : * param@[in] nTotalLower Total (effective) value of the UTXOs in groups.
257 : * param@[in] nTargetValue Subset sum target, not including change.
258 : * param@[out] vfBest Boolean vector representing the subset chosen that is closest to
259 : * nTargetValue, with indices corresponding to groups. If the ith
260 : * entry is true, that means the ith group in groups was selected.
261 : * param@[out] nBest Total amount of subset chosen that is closest to nTargetValue.
262 : * param@[in] iterations Maximum number of tries.
263 : */
264 6095 : static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
265 : const CAmount& nTotalLower, const CAmount& nTargetValue,
266 : std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
267 : {
268 6095 : std::vector<char> vfIncluded;
269 :
270 : // Worst case "best" approximation is just all of the groups.
271 6095 : vfBest.assign(groups.size(), true);
272 6095 : nBest = nTotalLower;
273 6095 : int nBestInputCount = 0;
274 :
275 4876023 : for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
276 : {
277 391897962 : vfIncluded.assign(groups.size(), false);
278 4869928 : CAmount nTotal = 0;
279 4869928 : int nTotalInputCount = 0;
280 4869928 : bool fReachedTarget = false;
281 11995547 : for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
282 : {
283 428432144 : for (unsigned int i = 0; i < groups.size(); i++)
284 : {
285 : //The solver here uses a randomized algorithm,
286 : //the randomness serves no real security purpose but is just
287 : //needed to prevent degenerate behavior and it is important
288 : //that the rng is fast. We do not use a constant random sequence,
289 : //because there may be some privacy improvement by making
290 : //the selection random.
291 421306525 : if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
292 : {
293 598718036 : nTotal += groups[i].GetSelectionAmount();
294 598718036 : ++nTotalInputCount;
295 598718036 : vfIncluded[i] = true;
296 598718036 : if (nTotal >= nTargetValue)
297 : {
298 575857344 : fReachedTarget = true;
299 : // If the total is between nTargetValue and nBest, it's our new best
300 : // approximation.
301 575857344 : if (nTotal < nBest || (nTotal == nBest && nTotalInputCount < nBestInputCount))
302 : {
303 387052954 : nBest = nTotal;
304 387052954 : nBestInputCount = nTotalInputCount;
305 387052954 : vfBest = vfIncluded;
306 24920 : }
307 188829310 : nTotal -= groups[i].GetSelectionAmount();
308 188829310 : --nTotalInputCount;
309 188829310 : vfIncluded[i] = false;
310 188829310 : }
311 211690002 : }
312 421306525 : }
313 7125619 : }
314 4869928 : }
315 1161078007 : }
316 :
317 : struct CompareByPriority
318 : {
319 0 : bool operator()(const OutputGroup& group1,
320 : const OutputGroup& group2) const
321 : {
322 0 : return CoinJoin::CalculateAmountPriority(group1.m_value) > CoinJoin::CalculateAmountPriority(group2.m_value);
323 : }
324 : };
325 :
326 : // move denoms down
327 1895630 : bool less_then_denom (const OutputGroup& group1, const OutputGroup& group2)
328 : {
329 1895630 : bool found1 = false;
330 1895630 : bool found2 = false;
331 11373780 : for (const auto& d : CoinJoin::GetStandardDenominations()) // loop through predefined denoms
332 : {
333 9478150 : if(group1.m_value == d) found1 = true;
334 9478150 : if(group2.m_value == d) found2 = true;
335 : }
336 1895630 : return (!found1 && found2);
337 : }
338 :
339 32733 : util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
340 : CAmount change_target, FastRandomContext& rng, int max_weight, bool fFullyMixedOnly,
341 : CAmount maxTxFee)
342 : {
343 32733 : if (groups.empty()) return util::Error();
344 :
345 22547 : SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
346 :
347 : // List of values less than target
348 22547 : std::optional<OutputGroup> lowest_larger;
349 : // Groups with selection amount smaller than the target and any change we might produce.
350 : // Don't include groups larger than this, because they will only cause us to overshoot.
351 22547 : std::vector<OutputGroup> applicable_groups;
352 22547 : CAmount nTotalLower = 0;
353 :
354 22547 : Shuffle(groups.begin(), groups.end(), rng);
355 :
356 17675 : int tryDenomStart = 0;
357 :
358 17675 : if (fFullyMixedOnly) {
359 : // larger denoms first
360 0 : std::sort(groups.rbegin(), groups.rend(), CompareByPriority());
361 : // we actually want denoms only, so let's skip "non-denom only" step
362 0 : tryDenomStart = 1;
363 : // no change is allowed
364 0 : change_target = 0;
365 0 : } else {
366 : // move denoms down on the list
367 : // try not to use denominated coins when not needed, save denoms for coinjoin
368 17675 : std::sort(groups.begin(), groups.end(), less_then_denom);
369 : }
370 :
371 : // try to find nondenom first to prevent unneeded spending of mixed coins
372 18608 : for (unsigned int tryDenom = tryDenomStart; tryDenom < 2; tryDenom++) {
373 18608 : LogPrint(BCLog::SELECTCOINS, "tryDenom: %d\n", tryDenom);
374 18608 : applicable_groups.clear();
375 18608 : nTotalLower = 0;
376 864450 : for (const OutputGroup& group : groups) {
377 847069 : if (tryDenom == 0 && CoinJoin::IsDenominatedAmount(group.m_value)) {
378 2 : continue; // we don't want denom values on first run
379 : }
380 847067 : if (group.GetSelectionAmount() == nTargetValue) {
381 1227 : result.AddInput(group);
382 1227 : return result;
383 845840 : } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
384 396607 : applicable_groups.push_back(group);
385 396607 : nTotalLower += group.GetSelectionAmount();
386 845840 : } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
387 19942 : lowest_larger = group;
388 19942 : }
389 : }
390 :
391 17381 : if (nTotalLower == nTargetValue) {
392 2759 : for (const auto& group : applicable_groups) {
393 2212 : result.AddInput(group);
394 : }
395 547 : return result;
396 : }
397 :
398 16834 : if (nTotalLower < nTargetValue) {
399 13141 : if (!lowest_larger) { // there is no input larger than nTargetValue
400 1866 : if (tryDenom == 0)
401 : // we didn't look at denom yet, let's do it
402 933 : continue;
403 : else
404 : // we looked at everything possible and didn't find anything, no luck
405 933 : return util::Error();
406 : }
407 11275 : result.AddInput(*lowest_larger);
408 : // There is no change in PS, so we know the fee beforehand,
409 : // can see if we exceeded the max fee and thus fail quickly.
410 11275 : if (!fFullyMixedOnly || (result.GetSelectedValue() - nTargetValue <= maxTxFee)) {
411 11275 : return result;
412 : }
413 0 : return util::Error();
414 : }
415 :
416 : // nTotalLower > nTargetValue
417 3693 : break;
418 : }
419 :
420 : // Solve subset sum by stochastic approximation
421 3693 : std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
422 8565 : std::vector<char> vfBest;
423 : CAmount nBest;
424 :
425 8565 : ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
426 3693 : if (nBest != nTargetValue && change_target != 0 && nTotalLower >= nTargetValue + change_target) {
427 2402 : ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest);
428 2402 : }
429 :
430 : // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
431 : // or the next bigger coin is closer), return the bigger coin
432 5276 : if (lowest_larger &&
433 1780 : ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
434 2862 : result.AddInput(*lowest_larger);
435 426 : } else {
436 1913 : std::string log_message{"Coin selection best subset: "};
437 380062 : for (unsigned int i = 0; i < applicable_groups.size(); i++) {
438 376795 : if (vfBest[i]) {
439 146037 : result.AddInput(applicable_groups[i]);
440 146037 : log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
441 146037 : }
442 376795 : }
443 :
444 3267 : if (GetSelectionWeight(result) > max_weight) {
445 12 : if (!lowest_larger) return ErrorMaxWeightExceeded();
446 :
447 1 : result.Clear();
448 1 : result.AddInput(*lowest_larger);
449 1 : }
450 :
451 3256 : LogPrint(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
452 3267 : }
453 :
454 : // There is no change in PS, so we know the fee beforehand,
455 : // can see if we exceeded the max fee and thus fail quickly.
456 3682 : if (!fFullyMixedOnly || (result.GetSelectedValue() - nTargetValue <= maxTxFee)) {
457 3682 : return result;
458 : }
459 0 : return util::Error();
460 47349 : }
461 :
462 : /******************************************************************************
463 :
464 : OutputGroup
465 :
466 : ******************************************************************************/
467 :
468 2658039 : void OutputGroup::Insert(const COutput& output, size_t ancestors, size_t descendants, bool positive_only) {
469 : // Filter for positive only here before adding the coin
470 2658039 : if (positive_only && output.GetEffectiveValue() <= 0) return;
471 :
472 2657967 : m_outputs.push_back(output);
473 2657967 : COutput& coin = m_outputs.back();
474 :
475 2657967 : fee += coin.GetFee();
476 :
477 2657967 : coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
478 2657967 : long_term_fee += coin.long_term_fee;
479 :
480 2657967 : effective_value += coin.GetEffectiveValue();
481 :
482 2657967 : m_from_me &= coin.from_me;
483 2657967 : m_value += coin.txout.nValue;
484 2657967 : m_depth = std::min(m_depth, coin.depth);
485 : // ancestors here express the number of ancestors the new coin will end up having, which is
486 : // the sum, rather than the max; this will overestimate in the cases where multiple inputs
487 : // have common ancestors
488 2657967 : m_ancestors += ancestors;
489 : // descendants is the count as seen from the top ancestor, not the descendants as seen from the
490 : // coin itself; thus, this value is counted as the max, not the sum
491 2657967 : m_descendants = std::max(m_descendants, descendants);
492 2658039 : }
493 :
494 2010179 : bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter, bool isISLocked) const
495 : {
496 4020358 : return (m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs) || isISLocked)
497 2010179 : && m_ancestors <= eligibility_filter.max_ancestors
498 2010179 : && m_descendants <= eligibility_filter.max_descendants;
499 : }
500 :
501 409064191 : CAmount OutputGroup::GetSelectionAmount() const
502 : {
503 409064191 : return m_subtract_fee_outputs ? m_value : effective_value;
504 : }
505 :
506 14119 : CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
507 : {
508 : // This function should not be called with empty inputs as that would mean the selection failed
509 14119 : assert(!inputs.empty());
510 :
511 : // Always consider the cost of spending an input now vs in the future.
512 14119 : CAmount waste = 0;
513 14119 : CAmount selected_effective_value = 0;
514 100816 : for (const COutput& coin : inputs) {
515 86697 : waste += coin.GetFee() - coin.long_term_fee;
516 86697 : selected_effective_value += use_effective_value ? coin.GetEffectiveValue() : coin.txout.nValue;
517 : }
518 :
519 14119 : if (change_cost) {
520 : // Consider the cost of making change and spending it in the future
521 : // If we aren't making change, the caller should've set change_cost to 0
522 13998 : assert(change_cost > 0);
523 13998 : waste += change_cost;
524 13998 : } else {
525 : // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
526 121 : assert(selected_effective_value >= target);
527 121 : waste += selected_effective_value - target;
528 : }
529 :
530 14119 : return waste;
531 : }
532 :
533 14296 : CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
534 : {
535 14296 : if (payment_value <= CHANGE_LOWER / 2) {
536 1935 : return CHANGE_LOWER;
537 : } else {
538 : // random value between 50ksat and min (payment_value * 2, 1milsat)
539 12361 : const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
540 12361 : return rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
541 : }
542 14296 : }
543 :
544 14107 : void SelectionResult::ComputeAndSetWaste(CAmount change_cost)
545 : {
546 14107 : m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
547 14107 : }
548 :
549 8 : CAmount SelectionResult::GetWaste() const
550 : {
551 8 : return *Assert(m_waste);
552 : }
553 :
554 32807 : CAmount SelectionResult::GetSelectedValue() const
555 : {
556 255306 : return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.txout.nValue; });
557 : }
558 :
559 12 : void SelectionResult::Clear()
560 : {
561 12 : m_selected_inputs.clear();
562 12 : m_waste.reset();
563 12 : }
564 :
565 175462 : void SelectionResult::AddInput(const OutputGroup& group)
566 : {
567 175462 : util::insert(m_selected_inputs, group.m_outputs);
568 175462 : m_use_effective = !group.m_subtract_fee_outputs;
569 175462 : }
570 :
571 26965 : const std::set<COutput>& SelectionResult::GetInputSet() const
572 : {
573 26965 : return m_selected_inputs;
574 : }
575 :
576 0 : std::vector<COutput> SelectionResult::GetShuffledInputVector() const
577 : {
578 0 : std::vector<COutput> coins(m_selected_inputs.begin(), m_selected_inputs.end());
579 0 : Shuffle(coins.begin(), coins.end(), FastRandomContext());
580 0 : return coins;
581 0 : }
582 :
583 0 : bool SelectionResult::operator<(SelectionResult other) const
584 : {
585 0 : Assert(m_waste.has_value());
586 0 : Assert(other.m_waste.has_value());
587 : // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
588 0 : return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
589 : }
590 :
591 0 : std::string COutput::ToString() const
592 : {
593 0 : return strprintf("COutput(%s, %d, %d) [%s]", outpoint.hash.ToString(), outpoint.n, depth, FormatMoney(txout.nValue));
594 0 : }
595 :
596 0 : std::string GetAlgorithmName(const SelectionAlgorithm algo)
597 : {
598 0 : switch (algo)
599 : {
600 0 : case SelectionAlgorithm::BNB: return "bnb";
601 0 : case SelectionAlgorithm::KNAPSACK: return "knapsack";
602 0 : case SelectionAlgorithm::SRD: return "srd";
603 0 : case SelectionAlgorithm::MANUAL: return "manual";
604 : // No default case to allow for compiler to warn
605 : }
606 0 : assert(false);
607 0 : }
608 : } // namespace wallet
|
