1 // Copyright (c) 2017-present 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 <policy/feerate.h>
12 #include <util/check.h>
13 #include <util/log.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
22 static util::Result<SelectionResult> ErrorMaxWeightExceeded()
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 }
38 } descending;
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 }
50 } descending_effval_weight;
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, tie-broken by their waste score, and the tree is explored deterministically per the inclusion
58 * branch first. For each new input set candidate, 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 prefix can be omitted.
61 * At that point, the last included UTXO is deselected and the corresponding omission branch explored
62 * instead starting by adding the subsequent UTXO. The search ends after the complete tree has been searched or after a limited number of tries.
63 *
64 * The algorithm continues to search for better solutions after one solution has been found. The best
65 * solution is chosen by minimal waste score. 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 (the "excess"):
68 *
69 * excess = selected_amount - target
70 * waste = inputs × (currentFeeRate - longTermFeeRate) + excess
71 *
72 * Note that this means that at fee rates higher than longTermFeeRate additional inputs increase the
73 * waste score, while at fee rates lower than longTermFeeRate additional inputs decrease the waste
74 * score.
75 *
76 * The algorithm uses the following optimizations:
77 * 1. Lookahead: The lookahead stores the total remaining effective value of the undecided UTXOs for
78 * every depth of the search tree. Whenever the currently selected amount plus the potential
79 * amount from the lookahead falls short of the target, we can immediately stop searching the
80 * subtree as no more input set candidates can be found in it.
81 * 2. Skip clones: When two UTXOs match in weight and effective value ("are clones"), naive
82 * exploration would cause redundant work: e.g., given the UTXOs A, A', and B, where A and A' are
83 * clones, naive exploration would combine (read underscore as omission):
84 * [{}, {A}, {A, A'}, {A, A', B}, {A, _, B}, {_, A'}, {_, A', B}, {_, _, B}].
85 * In this case the input set candidates {A} and {A'} as well as {A, B} and {A', B} are
86 * equivalent. It is sufficient to explore combinations that select either both UTXOs or the
87 * first UTXO. Whenever the first UTXO is omitted, we can also skip the clone as we have already
88 * explored a set of equivalent combination as the one we could generate with the second clone.
89 * Concretely, we skip a UTXO when its predecessor is omitted and the UTXO matches the
90 * effective value and the waste of the predecessor.
91 * 3. Skip similar UTXOs that are more wasteful: This search algorithm operates on the list of UTXOs
92 * sorted by effective value, tie-broken to prefer lower waste. This means that among two
93 * subsequent UTXOs with the same effective value, the second UTXO’s waste score will either be
94 * equal _or higher_ than the first UTXO’s. This allows us to apply the clone skipping idea more
95 * broadly: any combination with the second UTXO is equivalent _or worse_ than what we already
96 * combined with the first UTXO. We skip a UTXO if its predecessor is omitted and the predecessor
97 * matches in effective value.
98 *
99 * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
100 * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
101 *
102 * @param const std::vector<OutputGroup>& utxo_pool The set of UTXO groups that we are choosing from.
103 * These UTXO groups will be sorted in descending order by effective value and the OutputGroups'
104 * values are their effective values.
105 * @param const CAmount& selection_target This is the value that we want to select. It is the lower
106 * bound of the range.
107 * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
108 * This plus selection_target is the upper bound of the range.
109 * @param int max_selection_weight The maximum allowed weight for a selection result to be valid.
110 * @returns The result of this coin selection algorithm, or std::nullopt
111 */
112 113 static const size_t TOTAL_TRIES = 100000;
114 115 util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
116 int max_selection_weight)
117 {
118 std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
119 // The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount)
120 std::vector<CAmount> lookahead(utxo_pool.size());
121 122 // Calculate lookahead values, and check that there are sufficient funds
123 CAmount total_available = 0;
124 for (int index = static_cast<int>(utxo_pool.size()) - 1; index >= 0; --index) {
125 lookahead[index] = total_available;
126 // UTXOs with non-positive effective value must have been filtered
127 Assume(utxo_pool[index].GetSelectionAmount() > 0);
128 total_available += utxo_pool[index].GetSelectionAmount();
129 }
130 131 if (total_available < selection_target) {
132 // Insufficient funds
133 return util::Error();
134 }
135 136 137 // The current selection and the best input set found so far, stored as the utxo_pool indices of the UTXOs forming them
138 std::vector<size_t> curr_selection;
139 std::vector<size_t> best_selection;
140 141 // The currently selected effective amount
142 CAmount curr_amount = 0;
143 144 // The waste score of the current selection, and the best waste score so far
145 CAmount curr_selection_waste = 0;
146 CAmount best_waste = MAX_MONEY;
147 148 // The weight of the currently selected input set
149 int curr_weight = 0;
150 151 // Whether the input sets generated during this search have exceeded the maximum transaction weight at any point
152 bool max_tx_weight_exceeded = false;
153 154 // Index of the next UTXO to consider in utxo_pool
155 size_t next_utxo = 0;
156 157 auto deselect_last = [&]() {
158 OutputGroup& utxo = utxo_pool[curr_selection.back()];
159 curr_amount -= utxo.GetSelectionAmount();
160 curr_weight -= utxo.m_weight;
161 curr_selection_waste -= utxo.fee - utxo.long_term_fee;
162 curr_selection.pop_back();
163 };
164 165 size_t curr_try = 0;
166 SelectionResult result(selection_target, SelectionAlgorithm::BNB);
167 bool is_done = false;
168 // We don’t have access to the feerate here, but fee to long_term_fee is as feerate to LTFRE
169 bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
170 while (!is_done) {
171 bool should_shift{false}, should_cut{false};
172 // Select `next_utxo`
173 OutputGroup& utxo = utxo_pool[next_utxo];
174 curr_amount += utxo.GetSelectionAmount();
175 curr_weight += utxo.m_weight;
176 curr_selection_waste += utxo.fee - utxo.long_term_fee;
177 curr_selection.push_back(next_utxo);
178 ++next_utxo;
179 ++curr_try;
180 181 // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further
182 if (curr_amount + lookahead[curr_selection.back()] < selection_target) {
183 // Insufficient funds with lookahead: CUT
184 should_cut = true;
185 } else if (curr_weight > max_selection_weight) {
186 // max_weight exceeded: SHIFT
187 max_tx_weight_exceeded = true;
188 should_shift = true;
189 } else if (curr_amount > selection_target + cost_of_change) {
190 // Overshot target range: SHIFT
191 should_shift = true;
192 } else if (is_feerate_high && curr_selection_waste > best_waste) {
193 // At high feerates adding more inputs will increase the waste score. If the current waste is already worse
194 // than the best selection’s while we have insufficient funds, it is impossible for this partial selection
195 // to beat the best selection by adding more inputs: SHIFT
196 // At low feerates, additional inputs lower the waste score, and using this would cause us to skip exploring
197 // combinations with more inputs of lower amounts.
198 should_shift = true;
199 } else if (curr_amount >= selection_target) {
200 // Selection is within target window: potential solution
201 // Adding more UTXOs only increases fees and cannot be better: SHIFT
202 should_shift = true;
203 // The amount exceeding the selection_target (the "excess"), would be dropped to the fees: it is waste.
204 CAmount curr_excess = curr_amount - selection_target;
205 CAmount curr_waste = curr_selection_waste + curr_excess;
206 if (curr_waste <= best_waste) {
207 // New best solution
208 best_selection = curr_selection;
209 best_waste = curr_waste;
210 }
211 }
212 213 if (curr_try >= TOTAL_TRIES) {
214 // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
215 result.SetAlgoCompleted(false);
216 break;
217 }
218 219 if (next_utxo == utxo_pool.size()) {
220 // Last added UTXO was end of UTXO pool, nothing left to add on inclusion or omission branch: CUT
221 should_cut = true;
222 }
223 224 if (should_cut) {
225 // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can
226 // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e.
227 // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs)
228 deselect_last();
229 should_shift = true;
230 }
231 232 while (should_shift) {
233 if (curr_selection.empty()) {
234 // Exhausted search space before running into attempt limit
235 is_done = true;
236 result.SetAlgoCompleted(true);
237 break;
238 }
239 // Set `next_utxo` to one after last selected, then deselect last selected UTXO
240 next_utxo = curr_selection.back() + 1;
241 deselect_last();
242 should_shift = false;
243 244 // After SHIFTing to an omission branch, the `next_utxo` might have the same effective value as the
245 // UTXO we just omitted. Since lower waste is our tiebreaker on UTXOs with equal effective value for sorting, if it
246 // ties on the effective value, it _must_ have the same waste (i.e. be a "clone" of the prior UTXO) or a
247 // higher waste. If so, selecting `next_utxo` would produce an equivalent or worse
248 // selection as one we previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a
249 // differing amount.
250 Assume(next_utxo < utxo_pool.size());
251 while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {
252 if (next_utxo >= utxo_pool.size() - 1) {
253 // Reached end of UTXO pool skipping clones: SHIFT instead
254 should_shift = true;
255 break;
256 }
257 // Skip clone: previous UTXO is equivalent and unselected
258 ++next_utxo;
259 }
260 }
261 }
262 263 result.SetSelectionsEvaluated(curr_try);
264 265 if (best_selection.empty()) {
266 return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
267 }
268 269 for (const size_t& i : best_selection) {
270 result.AddInput(utxo_pool.at(i));
271 }
272 273 return result;
274 }
275 276 277 /*
278 * TL;DR: Coin Grinder is a DFS-based algorithm that deterministically searches for the minimum-weight input set to fund
279 * the transaction. The algorithm is similar to the Branch and Bound algorithm, but will produce a transaction _with_ a
280 * change output instead of a changeless transaction.
281 *
282 * Full description: CoinGrinder can be thought of as a graph walking algorithm. It explores a binary tree
283 * representation of the powerset of the UTXO pool. Each node in the tree represents a candidate input set. The tree’s
284 * root is the empty set. Each node in the tree has two children which are formed by either adding or skipping the next
285 * UTXO ("inclusion/omission branch"). Each level in the tree after the root corresponds to a decision about one UTXO in
286 * the UTXO pool.
287 *
288 * Example:
289 * We represent UTXOs as _alias=[effective_value/weight]_ and indicate omitted UTXOs with an underscore. Given a UTXO
290 * pool {A=[10/2], B=[7/1], C=[5/1], D=[4/2]} sorted by descending effective value, our search tree looks as follows:
291 *
292 * _______________________ {} ________________________
293 * / \
294 * A=[10/2] __________ {A} _________ __________ {_} _________
295 * / \ / \
296 * B=[7/1] {AB} _ {A_} _ {_B} _ {__} _
297 * / \ / \ / \ / \
298 * C=[5/1] {ABC} {AB_} {A_C} {A__} {_BC} {_B_} {__C} {___}
299 * / \ / \ / \ / \ / \ / \ / \ / \
300 * D=[4/2] {ABCD} {ABC_} {AB_D} {AB__} {A_CD} {A_C_} {A__D} {A___} {_BCD} {_BC_} {_B_D} {_B__} {__CD} {__C_} {___D} {____}
301 *
302 *
303 * CoinGrinder uses a depth-first search to walk this tree. It first tries inclusion branches, then omission branches. A
304 * naive exploration of a tree with four UTXOs requires visiting all 31 nodes:
305 *
306 * {} {A} {AB} {ABC} {ABCD} {ABC_} {AB_} {AB_D} {AB__} {A_} {A_C} {A_CD} {A_C_} {A__} {A__D} {A___} {_} {_B} {_BC}
307 * {_BCD} {_BC_} {_B_} {_B_D} {_B__} {__} {__C} {__CD} {__C} {___} {___D} {____}
308 *
309 * As powersets grow exponentially with the set size, walking the entire tree would quickly get computationally
310 * infeasible with growing UTXO pools. Thanks to traversing the tree in a deterministic order, we can keep track of the
311 * progress of the search solely on basis of the current selection (and the best selection so far). We visit as few
312 * nodes as possible by recognizing and skipping any branches that can only contain solutions worse than the best
313 * solution so far. This makes CoinGrinder a branch-and-bound algorithm
314 * (https://en.wikipedia.org/wiki/Branch_and_bound).
315 * CoinGrinder is searching for the input set with lowest weight that can fund a transaction, so for example we can only
316 * ever find a _better_ candidate input set in a node that adds a UTXO, but never in a node that skips a UTXO. After
317 * visiting {A} and exploring the inclusion branch {AB} and its descendants, the candidate input set in the omission
318 * branch {A_} is equivalent to the parent {A} in effective value and weight. While CoinGrinder does need to visit the
319 * descendants of the omission branch {A_}, it is unnecessary to evaluate the candidate input set in the omission branch
320 * itself. By skipping evaluation of all nodes on an omission branch we reduce the visited nodes to 15:
321 *
322 * {A} {AB} {ABC} {ABCD} {AB_D} {A_C} {A_CD} {A__D} {_B} {_BC} {_BCD} {_B_D} {__C} {__CD} {___D}
323 *
324 * _______________________ {} ________________________
325 * / \
326 * A=[10/2] __________ {A} _________ ___________\____________
327 * / \ / \
328 * B=[7/1] {AB} __ __\_____ {_B} __ __\_____
329 * / \ / \ / \ / \
330 * C=[5/1] {ABC} \ {A_C} \ {_BC} \ {__C} \
331 * / / / / / / / /
332 * D=[4/2] {ABCD} {AB_D} {A_CD} {A__D} {_BCD} {_B_D} {__CD} {___D}
333 *
334 *
335 * We refer to the move from the inclusion branch {AB} via the omission branch {A_} to its inclusion-branch child {A_C}
336 * as _shifting to the omission branch_ or just _SHIFT_. (The index of the ultimate element in the candidate input set
337 * shifts right by one: {AB} ⇒ {A_C}.)
338 * When we reach a leaf node in the last level of the tree, shifting to the omission branch is not possible. Instead we
339 * go to the omission branch of the node’s last ancestor on an inclusion branch: from {ABCD}, we go to {AB_D}. From
340 * {AB_D}, we go to {A_C}. We refer to this operation as a _CUT_. (The ultimate element in
341 * the input set is deselected, and the penultimate element is shifted right by one: {AB_D} ⇒ {A_C}.)
342 * If a candidate input set in a node has not selected sufficient funds to build the transaction, we continue directly
343 * along the next inclusion branch. We call this operation _EXPLORE_. (We go from one inclusion branch to the next
344 * inclusion branch: {_B} ⇒ {_BC}.)
345 * Further, any prefix that already has selected sufficient effective value to fund the transaction cannot be improved
346 * by adding more UTXOs. If for example the candidate input set in {AB} is a valid solution, all potential descendant
347 * solutions {ABC}, {ABCD}, and {AB_D} must have a higher weight, thus instead of exploring the descendants of {AB}, we
348 * can SHIFT from {AB} to {A_C}.
349 *
350 * Given the above UTXO set, using a target of 11, and following these initial observations, the basic implementation of
351 * CoinGrinder visits the following 10 nodes:
352 *
353 * Node [eff_val/weight] Evaluation
354 * ---------------------------------------------------------------
355 * {A} [10/2] Insufficient funds: EXPLORE
356 * {AB} [17/3] Solution: SHIFT to omission branch
357 * {A_C} [15/3] Better solution: SHIFT to omission branch
358 * {A__D} [14/4] Worse solution, shift impossible due to leaf node: CUT to omission branch of {A__D},
359 * i.e. SHIFT to omission branch of {A}
360 * {_B} [7/1] Insufficient funds: EXPLORE
361 * {_BC} [12/2] Better solution: SHIFT to omission branch
362 * {_B_D} [11/3] Worse solution, shift impossible due to leaf node: CUT to omission branch of {_B_D},
363 * i.e. SHIFT to omission branch of {_B}
364 * {__C} [5/1] Insufficient funds: EXPLORE
365 * {__CD} [9/3] Insufficient funds, leaf node: CUT
366 * {___D} [4/2] Insufficient funds, leaf node, cannot CUT since only one UTXO selected: done.
367 *
368 * _______________________ {} ________________________
369 * / \
370 * A=[10/2] __________ {A} _________ ___________\____________
371 * / \ / \
372 * B=[7/1] {AB} __\_____ {_B} __ __\_____
373 * / \ / \ / \
374 * C=[5/1] {A_C} \ {_BC} \ {__C} \
375 * / / / /
376 * D=[4/2] {A__D} {_B_D} {__CD} {___D}
377 *
378 *
379 * We implement this tree walk in the following algorithm:
380 * 1. Add `next_utxo`
381 * 2. Evaluate candidate input set
382 * 3. Determine `next_utxo` by deciding whether to
383 * a) EXPLORE: Add next inclusion branch, e.g. {_B} ⇒ {_B} + `next_uxto`: C
384 * b) SHIFT: Replace last selected UTXO by next higher index, e.g. {A_C} ⇒ {A__} + `next_utxo`: D
385 * c) CUT: deselect last selected UTXO and shift to omission branch of penultimate UTXO, e.g. {AB_D} ⇒ {A_} + `next_utxo: C
386 *
387 * The implementation then adds further optimizations by discovering further situations in which either the inclusion
388 * branch can be skipped, or both the inclusion and omission branch can be skipped after evaluating the candidate input
389 * set in the node.
390 *
391 * @param std::vector<OutputGroup>& utxo_pool The UTXOs that we are choosing from. These UTXOs will be sorted in
392 * descending order by effective value, with lower weight preferred as a tie-breaker. (We can think of an output
393 * group with multiple as a heavier UTXO with the combined amount here.)
394 * @param const CAmount& selection_target This is the minimum amount that we need for the transaction without considering change.
395 * @param const CAmount& change_target The minimum budget for creating a change output, by which we increase the selection_target.
396 * @param int max_selection_weight The maximum allowed weight for a selection result to be valid.
397 * @returns The result of this coin selection algorithm, or std::nullopt
398 */
399 util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_selection_weight)
400 {
401 std::sort(utxo_pool.begin(), utxo_pool.end(), descending_effval_weight);
402 // The sum of UTXO amounts after this UTXO index, e.g. lookahead[5] = Σ(UTXO[6+].amount)
403 std::vector<CAmount> lookahead(utxo_pool.size());
404 // The minimum UTXO weight among the remaining UTXOs after this UTXO index, e.g. min_tail_weight[5] = min(UTXO[6+].weight)
405 std::vector<int> min_tail_weight(utxo_pool.size());
406 407 // Calculate lookahead values, min_tail_weights, and check that there are sufficient funds
408 CAmount total_available = 0;
409 int min_group_weight = std::numeric_limits<int>::max();
410 for (size_t i = 0; i < utxo_pool.size(); ++i) {
411 size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order
412 lookahead[index] = total_available;
413 min_tail_weight[index] = min_group_weight;
414 // UTXOs with non-positive effective value must have been filtered
415 Assume(utxo_pool[index].GetSelectionAmount() > 0);
416 total_available += utxo_pool[index].GetSelectionAmount();
417 min_group_weight = std::min(min_group_weight, utxo_pool[index].m_weight);
418 }
419 420 const CAmount total_target = selection_target + change_target;
421 if (total_available < total_target) {
422 // Insufficient funds
423 return util::Error();
424 }
425 426 // The current selection and the best input set found so far, stored as the utxo_pool indices of the UTXOs forming them
427 std::vector<size_t> curr_selection;
428 std::vector<size_t> best_selection;
429 430 // The currently selected effective amount, and the effective amount of the best selection so far
431 CAmount curr_amount = 0;
432 CAmount best_selection_amount = MAX_MONEY;
433 434 // The weight of the currently selected input set, and the weight of the best selection
435 int curr_weight = 0;
436 int best_selection_weight = max_selection_weight; // Tie is fine, because we prefer lower selection amount
437 438 // Whether the input sets generated during this search have exceeded the maximum transaction weight at any point
439 bool max_tx_weight_exceeded = false;
440 441 // Index of the next UTXO to consider in utxo_pool
442 size_t next_utxo = 0;
443 444 /*
445 * You can think of the current selection as a vector of booleans that has decided inclusion or exclusion of all
446 * UTXOs before `next_utxo`. When we consider the next UTXO, we extend this hypothetical boolean vector either with
447 * a true value if the UTXO is included or a false value if it is omitted. The equivalent state is stored more
448 * compactly as the list of indices of the included UTXOs and the `next_utxo` index.
449 *
450 * We can never find a new solution by deselecting a UTXO, because we then revisit a previously evaluated
451 * selection. Therefore, we only need to check whether we found a new solution _after adding_ a new UTXO.
452 *
453 * Each iteration of CoinGrinder starts by selecting the `next_utxo` and evaluating the current selection. We
454 * use three state transitions to progress from the current selection to the next promising selection:
455 *
456 * - EXPLORE inclusion branch: We do not have sufficient funds, yet. Add `next_utxo` to the current selection, then
457 * nominate the direct successor of the just selected UTXO as our `next_utxo` for the
458 * following iteration.
459 *
460 * Example:
461 * Current Selection: {0, 5, 7}
462 * Evaluation: EXPLORE, next_utxo: 8
463 * Next Selection: {0, 5, 7, 8}
464 *
465 * - SHIFT to omission branch: Adding more UTXOs to the current selection cannot produce a solution that is better
466 * than the current best, e.g. the current selection weight exceeds the max weight or
467 * the current selection amount is equal to or greater than the target.
468 * We designate our `next_utxo` the one after the tail of our current selection, then
469 * deselect the tail of our current selection.
470 *
471 * Example:
472 * Current Selection: {0, 5, 7}
473 * Evaluation: SHIFT, next_utxo: 8, omit last selected: {0, 5}
474 * Next Selection: {0, 5, 8}
475 *
476 * - CUT entire subtree: We have exhausted the inclusion branch for the penultimately selected UTXO, both the
477 * inclusion and the omission branch of the current prefix are barren. E.g. we have
478 * reached the end of the UTXO pool, so neither further EXPLORING nor SHIFTING can find
479 * any solutions. We designate our `next_utxo` the one after our penultimate selected,
480 * then deselect both the last and penultimate selected.
481 *
482 * Example:
483 * Current Selection: {0, 5, 7}
484 * Evaluation: CUT, next_utxo: 6, omit two last selected: {0}
485 * Next Selection: {0, 6}
486 */
487 auto deselect_last = [&]() {
488 OutputGroup& utxo = utxo_pool[curr_selection.back()];
489 curr_amount -= utxo.GetSelectionAmount();
490 curr_weight -= utxo.m_weight;
491 curr_selection.pop_back();
492 };
493 494 SelectionResult result(selection_target, SelectionAlgorithm::CG);
495 bool is_done = false;
496 size_t curr_try = 0;
497 while (!is_done) {
498 bool should_shift{false}, should_cut{false};
499 // Select `next_utxo`
500 OutputGroup& utxo = utxo_pool[next_utxo];
501 curr_amount += utxo.GetSelectionAmount();
502 curr_weight += utxo.m_weight;
503 curr_selection.push_back(next_utxo);
504 ++next_utxo;
505 ++curr_try;
506 507 // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further
508 auto curr_tail = curr_selection.back();
509 if (curr_amount + lookahead[curr_tail] < total_target) {
510 // Insufficient funds with lookahead: CUT
511 should_cut = true;
512 } else if (curr_weight > best_selection_weight) {
513 // best_selection_weight is initialized to max_selection_weight
514 if (curr_weight > max_selection_weight) max_tx_weight_exceeded = true;
515 // Worse weight than best solution. More UTXOs only increase weight:
516 // CUT if last selected group had minimal weight, else SHIFT
517 if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
518 should_cut = true;
519 } else {
520 should_shift = true;
521 }
522 } else if (curr_amount >= total_target) {
523 // Success, adding more weight cannot be better: SHIFT
524 should_shift = true;
525 if (curr_weight < best_selection_weight || (curr_weight == best_selection_weight && curr_amount < best_selection_amount)) {
526 // New lowest weight, or same weight with fewer funds tied up
527 best_selection = curr_selection;
528 best_selection_weight = curr_weight;
529 best_selection_amount = curr_amount;
530 }
531 } 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) {
532 // Compare minimal tail weight and last selected amount with the amount missing to gauge whether a better weight is still possible.
533 if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
534 should_cut = true;
535 } else {
536 should_shift = true;
537 }
538 }
539 540 if (curr_try >= TOTAL_TRIES) {
541 // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
542 result.SetAlgoCompleted(false);
543 break;
544 }
545 546 if (next_utxo == utxo_pool.size()) {
547 // Last added UTXO was end of UTXO pool, nothing left to add on inclusion or omission branch: CUT
548 should_cut = true;
549 }
550 551 if (should_cut) {
552 // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can
553 // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e.
554 // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs)
555 deselect_last();
556 should_shift = true;
557 }
558 559 while (should_shift) {
560 // Set `next_utxo` to one after last selected, then deselect last selected UTXO
561 if (curr_selection.empty()) {
562 // Exhausted search space before running into attempt limit
563 is_done = true;
564 result.SetAlgoCompleted(true);
565 break;
566 }
567 next_utxo = curr_selection.back() + 1;
568 deselect_last();
569 should_shift = false;
570 571 // After SHIFTing to an omission branch, the `next_utxo` might have the same effective value as the UTXO we
572 // just omitted. Since lower weight is our tiebreaker on UTXOs with equal effective value for sorting, if it
573 // ties on the effective value, it _must_ have the same weight (i.e. be a "clone" of the prior UTXO) or a
574 // higher weight. If so, selecting `next_utxo` would produce an equivalent or worse selection as one we
575 // previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a differing amount.
576 while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {
577 if (next_utxo >= utxo_pool.size() - 1) {
578 // Reached end of UTXO pool skipping clones: SHIFT instead
579 should_shift = true;
580 break;
581 }
582 // Skip clone: previous UTXO is equivalent and unselected
583 ++next_utxo;
584 }
585 }
586 }
587 588 result.SetSelectionsEvaluated(curr_try);
589 590 if (best_selection.empty()) {
591 return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
592 }
593 594 for (const size_t& i : best_selection) {
595 result.AddInput(utxo_pool[i]);
596 }
597 598 return result;
599 }
600 601 class MinOutputGroupComparator
602 {
603 public:
604 int operator() (const OutputGroup& group1, const OutputGroup& group2) const
605 {
606 return descending_effval_weight(group1, group2);
607 }
608 };
609 610 util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
611 int max_selection_weight)
612 {
613 SelectionResult result(target_value, SelectionAlgorithm::SRD);
614 std::priority_queue<OutputGroup, std::vector<OutputGroup>, MinOutputGroupComparator> heap;
615 616 // Include change for SRD as we want to avoid making really small change if the selection just
617 // barely meets the target. Just use the lower bound change target instead of the randomly
618 // generated one, since SRD will result in a random change amount anyway; avoid making the
619 // target needlessly large.
620 target_value += CHANGE_LOWER + change_fee;
621 622 std::vector<size_t> indexes;
623 indexes.resize(utxo_pool.size());
624 std::iota(indexes.begin(), indexes.end(), 0);
625 std::shuffle(indexes.begin(), indexes.end(), rng);
626 627 CAmount selected_eff_value = 0;
628 int weight = 0;
629 bool max_tx_weight_exceeded = false;
630 for (const size_t i : indexes) {
631 const OutputGroup& group = utxo_pool.at(i);
632 Assume(group.GetSelectionAmount() > 0);
633 634 // Add group to selection
635 heap.push(group);
636 selected_eff_value += group.GetSelectionAmount();
637 weight += group.m_weight;
638 639 // If the selection weight exceeds the maximum allowed size, remove the least valuable inputs until we
640 // are below max weight.
641 if (weight > max_selection_weight) {
642 max_tx_weight_exceeded = true; // mark it in case we don't find any useful result.
643 do {
644 const OutputGroup& to_remove_group = heap.top();
645 selected_eff_value -= to_remove_group.GetSelectionAmount();
646 weight -= to_remove_group.m_weight;
647 heap.pop();
648 } while (!heap.empty() && weight > max_selection_weight);
649 }
650 651 // Now check if we are above the target
652 if (selected_eff_value >= target_value) {
653 // Result found, add it.
654 while (!heap.empty()) {
655 result.AddInput(heap.top());
656 heap.pop();
657 }
658 return result;
659 }
660 }
661 return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
662 }
663 664 /** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
665 * target amount; solve subset sum.
666 * @param[in] groups OutputGroups to choose from, sorted by value in descending order.
667 * @param[in] nTotalLower Total (effective) value of the UTXOs in groups.
668 * @param[in] nTargetValue Subset sum target, not including change.
669 * @param[out] vfBest Boolean vector representing the subset chosen that is closest to
670 * nTargetValue, with indices corresponding to groups. If the ith
671 * entry is true, that means the ith group in groups was selected.
672 * @param[out] nBest Total amount of subset chosen that is closest to nTargetValue.
673 * @param[in] max_selection_weight The maximum allowed weight for a selection result to be valid.
674 * @param[in] iterations Maximum number of tries.
675 */
676 static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
677 const CAmount& nTotalLower, const CAmount& nTargetValue,
678 std::vector<char>& vfBest, CAmount& nBest, int max_selection_weight, int iterations = 1000)
679 {
680 std::vector<char> vfIncluded;
681 682 // Worst case "best" approximation is just all of the groups.
683 vfBest.assign(groups.size(), true);
684 nBest = nTotalLower;
685 686 for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
687 {
688 vfIncluded.assign(groups.size(), false);
689 CAmount nTotal = 0;
690 int selected_coins_weight{0};
691 bool fReachedTarget = false;
692 for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
693 {
694 for (unsigned int i = 0; i < groups.size(); i++)
695 {
696 //The solver here uses a randomized algorithm,
697 //the randomness serves no real security purpose but is just
698 //needed to prevent degenerate behavior and it is important
699 //that the rng is fast. We do not use a constant random sequence,
700 //because there may be some privacy improvement by making
701 //the selection random.
702 if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
703 {
704 nTotal += groups[i].GetSelectionAmount();
705 selected_coins_weight += groups[i].m_weight;
706 vfIncluded[i] = true;
707 if (nTotal >= nTargetValue && selected_coins_weight <= max_selection_weight) {
708 fReachedTarget = true;
709 // If the total is between nTargetValue and nBest, it's our new best
710 // approximation.
711 if (nTotal < nBest)
712 {
713 nBest = nTotal;
714 vfBest = vfIncluded;
715 }
716 nTotal -= groups[i].GetSelectionAmount();
717 selected_coins_weight -= groups[i].m_weight;
718 vfIncluded[i] = false;
719 }
720 }
721 }
722 }
723 }
724 }
725 726 util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
727 CAmount change_target, FastRandomContext& rng, int max_selection_weight)
728 {
729 SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
730 731 bool max_weight_exceeded{false};
732 // List of values less than target
733 std::optional<OutputGroup> lowest_larger;
734 // Groups with selection amount smaller than the target and any change we might produce.
735 // Don't include groups larger than this, because they will only cause us to overshoot.
736 std::vector<OutputGroup> applicable_groups;
737 CAmount nTotalLower = 0;
738 739 std::shuffle(groups.begin(), groups.end(), rng);
740 741 for (const OutputGroup& group : groups) {
742 if (group.m_weight > max_selection_weight) {
743 max_weight_exceeded = true;
744 continue;
745 }
746 if (group.GetSelectionAmount() == nTargetValue) {
747 result.AddInput(group);
748 return result;
749 } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
750 applicable_groups.push_back(group);
751 nTotalLower += group.GetSelectionAmount();
752 } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
753 lowest_larger = group;
754 }
755 }
756 757 if (nTotalLower == nTargetValue) {
758 for (const auto& group : applicable_groups) {
759 result.AddInput(group);
760 }
761 if (result.GetWeight() <= max_selection_weight) return result;
762 else max_weight_exceeded = true;
763 764 // Try something else
765 result.Clear();
766 }
767 768 if (nTotalLower < nTargetValue) {
769 if (!lowest_larger) {
770 if (max_weight_exceeded) return ErrorMaxWeightExceeded();
771 return util::Error();
772 }
773 result.AddInput(*lowest_larger);
774 return result;
775 }
776 777 // Solve subset sum by stochastic approximation
778 std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
779 std::vector<char> vfBest;
780 CAmount nBest;
781 782 ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest, max_selection_weight);
783 if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
784 ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest, max_selection_weight);
785 }
786 787 // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
788 // or the next bigger coin is closer), return the bigger coin
789 if (lowest_larger &&
790 ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
791 result.AddInput(*lowest_larger);
792 } else {
793 for (unsigned int i = 0; i < applicable_groups.size(); i++) {
794 if (vfBest[i]) {
795 result.AddInput(applicable_groups[i]);
796 }
797 }
798 799 // If the result exceeds the maximum allowed size, return closest UTXO above the target
800 if (result.GetWeight() > max_selection_weight) {
801 // No coin above target, nothing to do.
802 if (!lowest_larger) return ErrorMaxWeightExceeded();
803 804 // Return closest UTXO above target
805 result.Clear();
806 result.AddInput(*lowest_larger);
807 }
808 809 if (util::log::ShouldDebugLog(BCLog::SELECTCOINS)) {
810 std::string log_message{"Coin selection best subset: "};
811 for (unsigned int i = 0; i < applicable_groups.size(); i++) {
812 if (vfBest[i]) {
813 log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
814 }
815 }
816 LogDebug(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
817 }
818 }
819 Assume(result.GetWeight() <= max_selection_weight);
820 return result;
821 }
822 823 /******************************************************************************
824 825 OutputGroup
826 827 ******************************************************************************/
828 829 void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t cluster_count) {
830 m_outputs.push_back(output);
831 auto& coin = *m_outputs.back();
832 833 fee += coin.GetFee();
834 835 coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
836 long_term_fee += coin.long_term_fee;
837 838 effective_value += coin.GetEffectiveValue();
839 840 m_from_me &= coin.from_me;
841 m_value += coin.txout.nValue;
842 m_depth = std::min(m_depth, coin.depth);
843 // ancestors here express the number of ancestors the new coin will end up having, which is
844 // the sum, rather than the max; this will overestimate in the cases where multiple inputs
845 // have common ancestors
846 m_ancestors += ancestors;
847 // This is the maximum cluster count among all outputs. If these outputs are from distinct clusters but spent in the
848 // same transaction, their clusters will be merged, potentially exceeding the mempool's max cluster count.
849 m_max_cluster_count = std::max(m_max_cluster_count, cluster_count);
850 851 if (output->input_bytes > 0) {
852 m_weight += output->input_bytes * WITNESS_SCALE_FACTOR;
853 }
854 }
855 856 bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
857 {
858 return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
859 && m_ancestors <= eligibility_filter.max_ancestors
860 && m_max_cluster_count <= eligibility_filter.max_cluster_count;
861 }
862 863 CAmount OutputGroup::GetSelectionAmount() const
864 {
865 return m_subtract_fee_outputs ? m_value : effective_value;
866 }
867 868 void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed)
869 {
870 if (group.m_outputs.empty()) return;
871 872 Groups& groups = groups_by_type[type];
873 if (insert_positive && group.GetSelectionAmount() > 0) {
874 groups.positive_group.emplace_back(group);
875 all_groups.positive_group.emplace_back(group);
876 }
877 if (insert_mixed) {
878 groups.mixed_group.emplace_back(group);
879 all_groups.mixed_group.emplace_back(group);
880 }
881 }
882 883 CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
884 {
885 if (payment_value <= CHANGE_LOWER / 2) {
886 return change_fee + CHANGE_LOWER;
887 } else {
888 // random value between 50ksat and min (payment_value * 2, 1milsat)
889 const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
890 return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
891 }
892 }
893 894 void SelectionResult::SetBumpFeeDiscount(const CAmount discount)
895 {
896 // Overlapping ancestry can only lower the fees, not increase them
897 assert (discount >= 0);
898 bump_fee_group_discount = discount;
899 }
900 901 void SelectionResult::RecalculateWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
902 {
903 // This function should not be called with empty inputs as that would mean the selection failed
904 assert(!m_selected_inputs.empty());
905 906 // Always consider the cost of spending an input now vs in the future.
907 CAmount waste = 0;
908 for (const auto& coin_ptr : m_selected_inputs) {
909 const COutput& coin = *coin_ptr;
910 waste += coin.GetFee() - coin.long_term_fee;
911 }
912 // Bump fee of whole selection may diverge from sum of individual bump fees
913 waste -= bump_fee_group_discount;
914 915 if (GetChange(min_viable_change, change_fee)) {
916 // if we have a minimum viable amount after deducting fees, account for
917 // cost of creating and spending change
918 waste += change_cost;
919 } else {
920 // When we are not making change (GetChange(…) == 0), consider the excess we are throwing away to fees
921 CAmount selected_effective_value = m_use_effective ? GetSelectedEffectiveValue() : GetSelectedValue();
922 assert(selected_effective_value >= m_target);
923 waste += selected_effective_value - m_target;
924 }
925 926 m_waste = waste;
927 }
928 929 void SelectionResult::SetAlgoCompleted(bool algo_completed)
930 {
931 m_algo_completed = algo_completed;
932 }
933 934 bool SelectionResult::GetAlgoCompleted() const
935 {
936 return m_algo_completed;
937 }
938 939 void SelectionResult::SetSelectionsEvaluated(size_t attempts)
940 {
941 m_selections_evaluated = attempts;
942 }
943 944 size_t SelectionResult::GetSelectionsEvaluated() const
945 {
946 return m_selections_evaluated;
947 }
948 949 CAmount SelectionResult::GetWaste() const
950 {
951 return *Assert(m_waste);
952 }
953 954 CAmount SelectionResult::GetSelectedValue() const
955 {
956 return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->txout.nValue; });
957 }
958 959 CAmount SelectionResult::GetSelectedEffectiveValue() const
960 {
961 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;
962 }
963 964 CAmount SelectionResult::GetTotalBumpFees() const
965 {
966 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;
967 }
968 969 void SelectionResult::Clear()
970 {
971 m_selected_inputs.clear();
972 m_waste.reset();
973 m_weight = 0;
974 }
975 976 void SelectionResult::AddInput(const OutputGroup& group)
977 {
978 // As it can fail, combine inputs first
979 InsertInputs(group.m_outputs);
980 m_use_effective = !group.m_subtract_fee_outputs;
981 982 m_weight += group.m_weight;
983 }
984 985 void SelectionResult::AddInputs(const OutputSet& inputs, bool subtract_fee_outputs)
986 {
987 // As it can fail, combine inputs first
988 InsertInputs(inputs);
989 m_use_effective = !subtract_fee_outputs;
990 991 m_weight += std::accumulate(inputs.cbegin(), inputs.cend(), 0, [](int sum, const auto& coin) {
992 return sum + std::max(coin->input_bytes, 0) * WITNESS_SCALE_FACTOR;
993 });
994 }
995 996 void SelectionResult::Merge(const SelectionResult& other)
997 {
998 // As it can fail, combine inputs first
999 InsertInputs(other.m_selected_inputs);
1000 1001 m_target += other.m_target;
1002 m_use_effective |= other.m_use_effective;
1003 if (m_algo == SelectionAlgorithm::MANUAL) {
1004 m_algo = other.m_algo;
1005 }
1006 1007 m_weight += other.m_weight;
1008 }
1009 1010 const OutputSet& SelectionResult::GetInputSet() const
1011 {
1012 return m_selected_inputs;
1013 }
1014 1015 std::vector<std::shared_ptr<COutput>> SelectionResult::GetShuffledInputVector() const
1016 {
1017 std::vector<std::shared_ptr<COutput>> coins(m_selected_inputs.begin(), m_selected_inputs.end());
1018 std::shuffle(coins.begin(), coins.end(), FastRandomContext());
1019 return coins;
1020 }
1021 1022 bool SelectionResult::operator<(SelectionResult other) const
1023 {
1024 Assert(m_waste.has_value());
1025 Assert(other.m_waste.has_value());
1026 // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
1027 return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
1028 }
1029 1030 std::string COutput::ToString() const
1031 {
1032 return strprintf("COutput(%s, %d, %d) [%s]", outpoint.hash.ToString(), outpoint.n, depth, FormatMoney(txout.nValue));
1033 }
1034 1035 std::string GetAlgorithmName(const SelectionAlgorithm algo)
1036 {
1037 switch (algo)
1038 {
1039 case SelectionAlgorithm::BNB: return "bnb";
1040 case SelectionAlgorithm::KNAPSACK: return "knapsack";
1041 case SelectionAlgorithm::SRD: return "srd";
1042 case SelectionAlgorithm::CG: return "cg";
1043 case SelectionAlgorithm::MANUAL: return "manual";
1044 } // no default case, so the compiler can warn about missing cases
1045 assert(false);
1046 }
1047 1048 CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
1049 {
1050 // change = SUM(inputs) - SUM(outputs) - fees
1051 // 1) With SFFO we don't pay any fees
1052 // 2) Otherwise we pay all the fees:
1053 // - input fees are covered by GetSelectedEffectiveValue()
1054 // - non_input_fee is included in m_target
1055 // - change_fee
1056 const CAmount change = m_use_effective
1057 ? GetSelectedEffectiveValue() - m_target - change_fee
1058 : GetSelectedValue() - m_target;
1059 1060 if (change < min_viable_change) {
1061 return 0;
1062 }
1063 1064 return change;
1065 }
1066 1067 } // namespace wallet
1068