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 1761 : static int GetSelectionWeight(const SelectionResult& result)
33 : {
34 142050 : return std::accumulate(result.GetInputSet().cbegin(), result.GetInputSet().cend(), 0, [](int sum, const COutput& coin) {
35 140289 : return sum + std::max(coin.input_bytes, 0);
36 : });
37 : }
38 :
39 : // Descending order comparator
40 : struct {
41 1782219 : bool operator()(const OutputGroup& a, const OutputGroup& b) const
42 : {
43 1782219 : 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 430 : util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
88 : int max_weight)
89 : {
90 430 : 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 430 : }
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 319 : util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng,
209 : int max_weight)
210 : {
211 319 : 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 319 : }
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 2973 : 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 2973 : std::vector<char> vfIncluded;
269 :
270 : // Worst case "best" approximation is just all of the groups.
271 2973 : vfBest.assign(groups.size(), true);
272 2973 : nBest = nTotalLower;
273 2973 : int nBestInputCount = 0;
274 :
275 1768883 : for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
276 : {
277 346313256 : vfIncluded.assign(groups.size(), false);
278 1765910 : CAmount nTotal = 0;
279 1765910 : int nTotalInputCount = 0;
280 1765910 : bool fReachedTarget = false;
281 4421730 : for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
282 : {
283 364851146 : 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 362195326 : if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
292 : {
293 526011638 : nTotal += groups[i].GetSelectionAmount();
294 526011638 : ++nTotalInputCount;
295 526011638 : vfIncluded[i] = true;
296 526011638 : if (nTotal >= nTargetValue)
297 : {
298 512459488 : fReachedTarget = true;
299 : // If the total is between nTargetValue and nBest, it's our new best
300 : // approximation.
301 512459488 : if (nTotal < nBest || (nTotal == nBest && nTotalInputCount < nBestInputCount))
302 : {
303 344564464 : nBest = nTotal;
304 344564464 : nBestInputCount = nTotalInputCount;
305 344564464 : vfBest = vfIncluded;
306 17118 : }
307 167912142 : nTotal -= groups[i].GetSelectionAmount();
308 167912142 : --nTotalInputCount;
309 167912142 : vfIncluded[i] = false;
310 167912142 : }
311 181464292 : }
312 362195326 : }
313 2655820 : }
314 1765910 : }
315 1033639065 : }
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 1463198 : bool less_then_denom (const OutputGroup& group1, const OutputGroup& group2)
328 : {
329 1463198 : bool found1 = false;
330 1463198 : bool found2 = false;
331 8779188 : for (const auto& d : CoinJoin::GetStandardDenominations()) // loop through predefined denoms
332 : {
333 7315990 : if(group1.m_value == d) found1 = true;
334 7315990 : if(group2.m_value == d) found2 = true;
335 : }
336 1463198 : return (!found1 && found2);
337 : }
338 :
339 7739 : 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 7739 : if (groups.empty()) return util::Error();
344 :
345 7455 : SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
346 :
347 : // List of values less than target
348 7455 : 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 7455 : std::vector<OutputGroup> applicable_groups;
352 7455 : CAmount nTotalLower = 0;
353 :
354 7455 : Shuffle(groups.begin(), groups.end(), rng);
355 :
356 5633 : int tryDenomStart = 0;
357 :
358 5633 : 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 5633 : 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 6066 : for (unsigned int tryDenom = tryDenomStart; tryDenom < 2; tryDenom++) {
373 6066 : LogPrint(BCLog::SELECTCOINS, "tryDenom: %d\n", tryDenom);
374 6066 : applicable_groups.clear();
375 6066 : nTotalLower = 0;
376 608624 : for (const OutputGroup& group : groups) {
377 603667 : if (tryDenom == 0 && CoinJoin::IsDenominatedAmount(group.m_value)) {
378 2 : continue; // we don't want denom values on first run
379 : }
380 603665 : if (group.GetSelectionAmount() == nTargetValue) {
381 1109 : result.AddInput(group);
382 1109 : return result;
383 602556 : } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
384 364620 : applicable_groups.push_back(group);
385 364620 : nTotalLower += group.GetSelectionAmount();
386 602556 : } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
387 3113 : lowest_larger = group;
388 3113 : }
389 : }
390 :
391 4957 : if (nTotalLower == nTargetValue) {
392 2435 : for (const auto& group : applicable_groups) {
393 1932 : result.AddInput(group);
394 : }
395 503 : return result;
396 : }
397 :
398 4454 : if (nTotalLower < nTargetValue) {
399 2386 : if (!lowest_larger) { // there is no input larger than nTargetValue
400 866 : if (tryDenom == 0)
401 : // we didn't look at denom yet, let's do it
402 433 : continue;
403 : else
404 : // we looked at everything possible and didn't find anything, no luck
405 433 : return util::Error();
406 : }
407 1520 : 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 1520 : if (!fFullyMixedOnly || (result.GetSelectedValue() - nTargetValue <= maxTxFee)) {
411 1520 : return result;
412 : }
413 0 : return util::Error();
414 : }
415 :
416 : // nTotalLower > nTargetValue
417 2068 : break;
418 : }
419 :
420 : // Solve subset sum by stochastic approximation
421 2068 : std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
422 3890 : std::vector<char> vfBest;
423 : CAmount nBest;
424 :
425 3890 : ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
426 2068 : if (nBest != nTargetValue && change_target != 0 && nTotalLower >= nTargetValue + change_target) {
427 905 : ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest);
428 905 : }
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 2874 : if (lowest_larger &&
433 913 : ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
434 1218 : result.AddInput(*lowest_larger);
435 307 : } else {
436 1155 : std::string log_message{"Coin selection best subset: "};
437 352944 : for (unsigned int i = 0; i < applicable_groups.size(); i++) {
438 351183 : if (vfBest[i]) {
439 140289 : result.AddInput(applicable_groups[i]);
440 140289 : log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
441 140289 : }
442 351183 : }
443 :
444 1761 : 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 1750 : LogPrint(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
452 1761 : }
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 2057 : if (!fFullyMixedOnly || (result.GetSelectedValue() - nTargetValue <= maxTxFee)) {
457 2057 : return result;
458 : }
459 0 : return util::Error();
460 13205 : }
461 :
462 : /******************************************************************************
463 :
464 : OutputGroup
465 :
466 : ******************************************************************************/
467 :
468 875842 : 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 875842 : if (positive_only && output.GetEffectiveValue() <= 0) return;
471 :
472 875840 : m_outputs.push_back(output);
473 875840 : COutput& coin = m_outputs.back();
474 :
475 875840 : fee += coin.GetFee();
476 :
477 875840 : coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
478 875840 : long_term_fee += coin.long_term_fee;
479 :
480 875840 : effective_value += coin.GetEffectiveValue();
481 :
482 875840 : m_from_me &= coin.from_me;
483 875840 : m_value += coin.txout.nValue;
484 875840 : 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 875840 : 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 875840 : m_descendants = std::max(m_descendants, descendants);
492 875842 : }
493 :
494 598529 : bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter, bool isISLocked) const
495 : {
496 1197058 : return (m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs) || isISLocked)
497 598529 : && m_ancestors <= eligibility_filter.max_ancestors
498 598529 : && m_descendants <= eligibility_filter.max_descendants;
499 : }
500 :
501 356037455 : CAmount OutputGroup::GetSelectionAmount() const
502 : {
503 356037455 : return m_subtract_fee_outputs ? m_value : effective_value;
504 : }
505 :
506 306 : 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 306 : assert(!inputs.empty());
510 :
511 : // Always consider the cost of spending an input now vs in the future.
512 306 : CAmount waste = 0;
513 306 : CAmount selected_effective_value = 0;
514 35305 : for (const COutput& coin : inputs) {
515 34999 : waste += coin.GetFee() - coin.long_term_fee;
516 34999 : selected_effective_value += use_effective_value ? coin.GetEffectiveValue() : coin.txout.nValue;
517 : }
518 :
519 306 : 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 185 : assert(change_cost > 0);
523 185 : waste += change_cost;
524 185 : } 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 306 : return waste;
531 : }
532 :
533 226 : CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
534 : {
535 226 : if (payment_value <= CHANGE_LOWER / 2) {
536 121 : return CHANGE_LOWER;
537 : } else {
538 : // random value between 50ksat and min (payment_value * 2, 1milsat)
539 105 : const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
540 105 : return rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
541 : }
542 226 : }
543 :
544 294 : void SelectionResult::ComputeAndSetWaste(CAmount change_cost)
545 : {
546 294 : m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
547 294 : }
548 :
549 8 : CAmount SelectionResult::GetWaste() const
550 : {
551 8 : return *Assert(m_waste);
552 : }
553 :
554 3302 : CAmount SelectionResult::GetSelectedValue() const
555 : {
556 119638 : 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 145572 : void SelectionResult::AddInput(const OutputGroup& group)
566 : {
567 145572 : util::insert(m_selected_inputs, group.m_outputs);
568 145572 : m_use_effective = !group.m_subtract_fee_outputs;
569 145572 : }
570 :
571 10140 : const std::set<COutput>& SelectionResult::GetInputSet() const
572 : {
573 10140 : 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
|
