Branch data Line data Source code
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 : 138 : static util::Result<SelectionResult> ErrorMaxWeightExceeded()
23 : : {
24 : 138 : return util::Error{_("The inputs size exceeds the maximum weight. "
25 : 138 : "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 : 11536391 : bool operator()(const OutputGroup& a, const OutputGroup& b) const
31 : : {
32 [ + + ]: 11536391 : if (a.GetSelectionAmount() == b.GetSelectionAmount()) {
33 : : // Lower waste is better when effective_values are tied
34 : 8989100 : return (a.fee - a.long_term_fee) < (b.fee - b.long_term_fee);
35 : : }
36 : 2547291 : return a.GetSelectionAmount() > b.GetSelectionAmount();
37 : : }
38 : : } descending;
39 : :
40 : : // Sort by descending (effective) value prefer lower weight on tie
41 : : struct {
42 : 715000 : bool operator()(const OutputGroup& a, const OutputGroup& b) const
43 : : {
44 [ + + ]: 715000 : if (a.GetSelectionAmount() == b.GetSelectionAmount()) {
45 : : // Sort lower weight to front on tied effective_value
46 : 161530 : return a.m_weight < b.m_weight;
47 : : }
48 : 553470 : 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 : 4574 : 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 : 4574 : 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 [ - + ]: 4574 : std::vector<CAmount> lookahead(utxo_pool.size());
121 : :
122 : : // Calculate lookahead values, and check that there are sufficient funds
123 : 4574 : CAmount total_available = 0;
124 [ - + + + ]: 701125 : for (int index = static_cast<int>(utxo_pool.size()) - 1; index >= 0; --index) {
125 [ + - ]: 696551 : lookahead[index] = total_available;
126 : : // UTXOs with non-positive effective value must have been filtered
127 [ + - + - ]: 696551 : Assume(utxo_pool[index].GetSelectionAmount() > 0);
128 [ + - ]: 696551 : total_available += utxo_pool[index].GetSelectionAmount();
129 : : }
130 : :
131 [ + + ]: 4574 : if (total_available < selection_target) {
132 : : // Insufficient funds
133 : 1472 : 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 : 3838 : std::vector<size_t> curr_selection;
139 : 3838 : std::vector<size_t> best_selection;
140 : :
141 : : // The currently selected effective amount
142 : 3838 : CAmount curr_amount = 0;
143 : :
144 : : // The waste score of the current selection, and the best waste score so far
145 : 3838 : CAmount curr_selection_waste = 0;
146 : 3838 : CAmount best_waste = MAX_MONEY;
147 : :
148 : : // The weight of the currently selected input set
149 : 3838 : int curr_weight = 0;
150 : :
151 : : // Whether the input sets generated during this search have exceeded the maximum transaction weight at any point
152 : 3838 : bool max_tx_weight_exceeded = false;
153 : :
154 : : // Index of the next UTXO to consider in utxo_pool
155 : 3838 : size_t next_utxo = 0;
156 : :
157 : 12525668 : auto deselect_last = [&]() {
158 : 12521830 : OutputGroup& utxo = utxo_pool[curr_selection.back()];
159 : 12521830 : curr_amount -= utxo.GetSelectionAmount();
160 : 12521830 : curr_weight -= utxo.m_weight;
161 : 12521830 : curr_selection_waste -= utxo.fee - utxo.long_term_fee;
162 : 12521830 : curr_selection.pop_back();
163 : 12525668 : };
164 : :
165 : 3838 : size_t curr_try = 0;
166 [ + - ]: 3838 : SelectionResult result(selection_target, SelectionAlgorithm::BNB);
167 : 3838 : 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 [ + - + - ]: 3838 : bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
170 : 3838 : while (!is_done) {
171 : 12546573 : bool should_shift{false}, should_cut{false};
172 : : // Select `next_utxo`
173 [ + - ]: 12546573 : OutputGroup& utxo = utxo_pool[next_utxo];
174 [ + - ]: 12546573 : curr_amount += utxo.GetSelectionAmount();
175 : 12546573 : curr_weight += utxo.m_weight;
176 : 12546573 : curr_selection_waste += utxo.fee - utxo.long_term_fee;
177 [ + - ]: 12546573 : curr_selection.push_back(next_utxo);
178 : 12546573 : ++next_utxo;
179 : 12546573 : ++curr_try;
180 : :
181 : : // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further
182 [ + + ]: 12546573 : if (curr_amount + lookahead[curr_selection.back()] < selection_target) {
183 : : // Insufficient funds with lookahead: CUT
184 : : should_cut = true;
185 [ + + ]: 10558822 : } else if (curr_weight > max_selection_weight) {
186 : : // max_weight exceeded: SHIFT
187 : : max_tx_weight_exceeded = true;
188 : : should_shift = true;
189 [ + + ]: 10558734 : } else if (curr_amount > selection_target + cost_of_change) {
190 : : // Overshot target range: SHIFT
191 : : should_shift = true;
192 [ + + + + ]: 3419839 : } 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 [ + + ]: 3419836 : } 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 : 43367 : should_shift = true;
203 : : // The amount exceeding the selection_target (the "excess"), would be dropped to the fees: it is waste.
204 : 43367 : CAmount curr_excess = curr_amount - selection_target;
205 : 43367 : CAmount curr_waste = curr_selection_waste + curr_excess;
206 [ + + ]: 43367 : if (curr_waste <= best_waste) {
207 : : // New best solution
208 [ + - ]: 21783 : best_selection = curr_selection;
209 : : best_waste = curr_waste;
210 : : }
211 : : }
212 : :
213 [ + + ]: 12546573 : if (curr_try >= TOTAL_TRIES) {
214 : : // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
215 [ + - ]: 111 : result.SetAlgoCompleted(false);
216 : : break;
217 : : }
218 : :
219 [ - + + + ]: 12546462 : 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 [ + + ]: 10462572 : 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 [ + - ]: 3228626 : deselect_last();
229 : : should_shift = true;
230 : : }
231 : :
232 [ + + ]: 21839666 : while (should_shift) {
233 [ + + ]: 9296931 : if (curr_selection.empty()) {
234 : : // Exhausted search space before running into attempt limit
235 : 3727 : is_done = true;
236 [ + - ]: 3727 : result.SetAlgoCompleted(true);
237 : : break;
238 : : }
239 : : // Set `next_utxo` to one after last selected, then deselect last selected UTXO
240 : 9293204 : next_utxo = curr_selection.back() + 1;
241 [ + - ]: 9293204 : deselect_last();
242 : 9293204 : 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 [ - + ]: 9293204 : Assume(next_utxo < utxo_pool.size());
251 [ + - + - : 179130672 : while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {
+ + ]
252 [ - + + + ]: 169964373 : 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 : 169837468 : ++next_utxo;
259 : : }
260 : : }
261 : : }
262 : :
263 [ + - ]: 3838 : result.SetSelectionsEvaluated(curr_try);
264 : :
265 [ + + ]: 3838 : if (best_selection.empty()) {
266 [ + + + - ]: 7184 : return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
267 : : }
268 : :
269 [ + + ]: 25585 : for (const size_t& i : best_selection) {
270 [ + - + - ]: 25365 : result.AddInput(utxo_pool.at(i));
271 : : }
272 : :
273 : 220 : return result;
274 : 8412 : }
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 : 859 : util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, CAmount change_target, int max_selection_weight)
400 : : {
401 : 859 : 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 [ - + ]: 859 : 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 [ - + + - ]: 859 : 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 : 859 : CAmount total_available = 0;
409 : 859 : int min_group_weight = std::numeric_limits<int>::max();
410 [ - + + + ]: 9776 : for (size_t i = 0; i < utxo_pool.size(); ++i) {
411 : 8917 : size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order
412 [ + - ]: 8917 : lookahead[index] = total_available;
413 : 8917 : min_tail_weight[index] = min_group_weight;
414 : : // UTXOs with non-positive effective value must have been filtered
415 [ + - + - ]: 8917 : Assume(utxo_pool[index].GetSelectionAmount() > 0);
416 [ + - ]: 8917 : total_available += utxo_pool[index].GetSelectionAmount();
417 [ + + ]: 16966 : min_group_weight = std::min(min_group_weight, utxo_pool[index].m_weight);
418 : : }
419 : :
420 : 859 : const CAmount total_target = selection_target + change_target;
421 [ + + ]: 859 : if (total_available < total_target) {
422 : : // Insufficient funds
423 : 766 : 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 : 476 : std::vector<size_t> curr_selection;
428 : 476 : std::vector<size_t> best_selection;
429 : :
430 : : // The currently selected effective amount, and the effective amount of the best selection so far
431 : 476 : CAmount curr_amount = 0;
432 : 476 : CAmount best_selection_amount = MAX_MONEY;
433 : :
434 : : // The weight of the currently selected input set, and the weight of the best selection
435 : 476 : int curr_weight = 0;
436 : 476 : 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 : 476 : bool max_tx_weight_exceeded = false;
440 : :
441 : : // Index of the next UTXO to consider in utxo_pool
442 : 476 : 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 : 1194861 : auto deselect_last = [&]() {
488 : 1194385 : OutputGroup& utxo = utxo_pool[curr_selection.back()];
489 : 1194385 : curr_amount -= utxo.GetSelectionAmount();
490 : 1194385 : curr_weight -= utxo.m_weight;
491 : 1194385 : curr_selection.pop_back();
492 : 1194861 : };
493 : :
494 : 476 : SelectionResult result(selection_target, SelectionAlgorithm::CG);
495 : 476 : bool is_done = false;
496 : 476 : size_t curr_try = 0;
497 : 476 : while (!is_done) {
498 : 1194585 : bool should_shift{false}, should_cut{false};
499 : : // Select `next_utxo`
500 [ + - ]: 1194585 : OutputGroup& utxo = utxo_pool[next_utxo];
501 [ + - ]: 1194585 : curr_amount += utxo.GetSelectionAmount();
502 : 1194585 : curr_weight += utxo.m_weight;
503 [ + - ]: 1194585 : curr_selection.push_back(next_utxo);
504 : 1194585 : ++next_utxo;
505 : 1194585 : ++curr_try;
506 : :
507 : : // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further
508 : 1194585 : auto curr_tail = curr_selection.back();
509 [ + + ]: 1194585 : if (curr_amount + lookahead[curr_tail] < total_target) {
510 : : // Insufficient funds with lookahead: CUT
511 : : should_cut = true;
512 [ + + ]: 1085153 : } else if (curr_weight > best_selection_weight) {
513 : : // best_selection_weight is initialized to max_selection_weight
514 [ + + ]: 99742 : 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 [ + + ]: 99742 : if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
518 : : should_cut = true;
519 : : } else {
520 : 58422 : should_shift = true;
521 : : }
522 [ + + ]: 985411 : } else if (curr_amount >= total_target) {
523 : : // Success, adding more weight cannot be better: SHIFT
524 : 555819 : should_shift = true;
525 [ + + + - : 555819 : 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 [ + - ]: 13110 : best_selection = curr_selection;
528 : 13110 : best_selection_weight = curr_weight;
529 : 13110 : best_selection_amount = curr_amount;
530 : : }
531 [ + + + - : 429592 : } 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 [ + + ]: 72760 : if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
534 : : should_cut = true;
535 : : } else {
536 : 54674 : should_shift = true;
537 : : }
538 : : }
539 : :
540 [ + + ]: 1194585 : if (curr_try >= TOTAL_TRIES) {
541 : : // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
542 [ + - ]: 11 : result.SetAlgoCompleted(false);
543 : : break;
544 : : }
545 : :
546 [ - + + + ]: 1194574 : 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 [ + + ]: 973706 : 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 [ + - ]: 302354 : deselect_last();
556 : : should_shift = true;
557 : : }
558 : :
559 [ + + ]: 2086605 : while (should_shift) {
560 : : // Set `next_utxo` to one after last selected, then deselect last selected UTXO
561 [ + + ]: 892496 : if (curr_selection.empty()) {
562 : : // Exhausted search space before running into attempt limit
563 : 465 : is_done = true;
564 [ + - ]: 465 : result.SetAlgoCompleted(true);
565 : : break;
566 : : }
567 : 892031 : next_utxo = curr_selection.back() + 1;
568 [ + - ]: 892031 : deselect_last();
569 : 1055906 : 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 [ + - + - : 1055906 : while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {
+ + ]
577 [ - + + + ]: 218627 : 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 : 163875 : ++next_utxo;
584 : : }
585 : : }
586 : : }
587 : :
588 [ + - ]: 476 : result.SetSelectionsEvaluated(curr_try);
589 : :
590 [ + + ]: 476 : if (best_selection.empty()) {
591 [ + - + - ]: 2 : return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
592 : : }
593 : :
594 [ + + ]: 1477 : for (const size_t& i : best_selection) {
595 [ + - ]: 1003 : result.AddInput(utxo_pool[i]);
596 : : }
597 : :
598 : 474 : return result;
599 : 1335 : }
600 : :
601 : : class MinOutputGroupComparator
602 : : {
603 : : public:
604 : 673081 : int operator() (const OutputGroup& group1, const OutputGroup& group2) const
605 : : {
606 : 673081 : return descending_effval_weight(group1, group2);
607 : : }
608 : : };
609 : :
610 : 5992 : 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 [ - + ]: 5992 : SelectionResult result(target_value, SelectionAlgorithm::SRD);
614 [ - + ]: 5992 : 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 : 5992 : target_value += CHANGE_LOWER + change_fee;
621 : :
622 : 5992 : std::vector<size_t> indexes;
623 [ - + + - ]: 5992 : indexes.resize(utxo_pool.size());
624 : 5992 : std::iota(indexes.begin(), indexes.end(), 0);
625 : 5992 : std::shuffle(indexes.begin(), indexes.end(), rng);
626 : :
627 : 5992 : CAmount selected_eff_value = 0;
628 : 5992 : int weight = 0;
629 : 5992 : bool max_tx_weight_exceeded = false;
630 [ + + ]: 106274 : for (const size_t i : indexes) {
631 [ + - ]: 104601 : const OutputGroup& group = utxo_pool.at(i);
632 [ + - + - ]: 104601 : Assume(group.GetSelectionAmount() > 0);
633 : :
634 : : // Add group to selection
635 [ + - ]: 104601 : heap.push(group);
636 [ + - ]: 104601 : selected_eff_value += group.GetSelectionAmount();
637 : 104601 : 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 [ + + ]: 104601 : if (weight > max_selection_weight) {
642 : 11062 : max_tx_weight_exceeded = true; // mark it in case we don't find any useful result.
643 : 11062 : do {
644 [ + - ]: 11062 : const OutputGroup& to_remove_group = heap.top();
645 [ + - ]: 11062 : selected_eff_value -= to_remove_group.GetSelectionAmount();
646 : 11062 : weight -= to_remove_group.m_weight;
647 [ + - ]: 11062 : heap.pop();
648 [ + + + - : 22124 : } while (!heap.empty() && weight > max_selection_weight);
- + ]
649 : : }
650 : :
651 : : // Now check if we are above the target
652 [ + + ]: 104601 : if (selected_eff_value >= target_value) {
653 : : // Result found, add it.
654 [ + + ]: 64598 : while (!heap.empty()) {
655 [ + - ]: 60279 : result.AddInput(heap.top());
656 [ + - ]: 60279 : heap.pop();
657 : : }
658 : 4319 : return result;
659 : : }
660 : : }
661 [ + + + - ]: 3299 : return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
662 : 5992 : }
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 : 5129 : 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 : 5129 : std::vector<char> vfIncluded;
681 : :
682 : : // Worst case "best" approximation is just all of the groups.
683 [ - + + - ]: 5129 : vfBest.assign(groups.size(), true);
684 : 5129 : nBest = nTotalLower;
685 : :
686 [ + + + + ]: 3942017 : for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
687 : : {
688 [ - + + - ]: 3936888 : vfIncluded.assign(groups.size(), false);
689 : : CAmount nTotal = 0;
690 : : int selected_coins_weight{0};
691 : : bool fReachedTarget = false;
692 [ + + ]: 9784128 : for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
693 : : {
694 [ - + + + ]: 536752750 : 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 [ + + + + ]: 530905510 : if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
703 : : {
704 [ + - ]: 266385019 : nTotal += groups[i].GetSelectionAmount();
705 [ + + ]: 266385019 : selected_coins_weight += groups[i].m_weight;
706 [ + + ]: 266385019 : vfIncluded[i] = true;
707 [ + + + + ]: 266385019 : if (nTotal >= nTargetValue && selected_coins_weight <= max_selection_weight) {
708 : 173897358 : fReachedTarget = true;
709 : : // If the total is between nTargetValue and nBest, it's our new best
710 : : // approximation.
711 [ + + ]: 173897358 : if (nTotal < nBest)
712 : : {
713 : 27584 : nBest = nTotal;
714 [ + - ]: 27584 : vfBest = vfIncluded;
715 : : }
716 [ + - ]: 173897358 : nTotal -= groups[i].GetSelectionAmount();
717 : 173897358 : selected_coins_weight -= groups[i].m_weight;
718 : 173897358 : vfIncluded[i] = false;
719 : : }
720 : : }
721 : : }
722 : : }
723 : : }
724 : 5129 : }
725 : :
726 : 11463 : util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
727 : : CAmount change_target, FastRandomContext& rng, int max_selection_weight)
728 : : {
729 : 11463 : SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
730 : :
731 : 11463 : bool max_weight_exceeded{false};
732 : : // List of values less than target
733 : 11463 : 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 : 11463 : std::vector<OutputGroup> applicable_groups;
737 : 11463 : CAmount nTotalLower = 0;
738 : :
739 : 11463 : std::shuffle(groups.begin(), groups.end(), rng);
740 : :
741 [ + + ]: 698840 : for (const OutputGroup& group : groups) {
742 [ + + ]: 688509 : if (group.m_weight > max_selection_weight) {
743 : 168 : max_weight_exceeded = true;
744 : 168 : continue;
745 : : }
746 [ + - + + ]: 688341 : if (group.GetSelectionAmount() == nTargetValue) {
747 [ + - ]: 1132 : result.AddInput(group);
748 : 1132 : return result;
749 [ + - + + ]: 687209 : } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
750 [ + - ]: 397976 : applicable_groups.push_back(group);
751 [ + - ]: 397976 : nTotalLower += group.GetSelectionAmount();
752 [ + + + - : 289233 : } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
+ - + + ]
753 [ + - ]: 9105 : lowest_larger = group;
754 : : }
755 : : }
756 : :
757 [ + + ]: 10331 : if (nTotalLower == nTargetValue) {
758 [ + + ]: 2484 : for (const auto& group : applicable_groups) {
759 [ + - ]: 1972 : result.AddInput(group);
760 : : }
761 [ + - ]: 512 : if (result.GetWeight() <= max_selection_weight) return result;
762 : 0 : else max_weight_exceeded = true;
763 : :
764 : : // Try something else
765 [ # # ]: 0 : result.Clear();
766 : : }
767 : :
768 [ + + ]: 9819 : if (nTotalLower < nTargetValue) {
769 [ + + ]: 6690 : if (!lowest_larger) {
770 [ + + + - ]: 2146 : if (max_weight_exceeded) return ErrorMaxWeightExceeded();
771 : 4262 : return util::Error();
772 : : }
773 [ + - ]: 4544 : result.AddInput(*lowest_larger);
774 : 4544 : return result;
775 : : }
776 : :
777 : : // Solve subset sum by stochastic approximation
778 [ + - ]: 3129 : std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
779 : 3129 : std::vector<char> vfBest;
780 : 3129 : CAmount nBest;
781 : :
782 [ + - ]: 3129 : ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest, max_selection_weight);
783 [ + + + + ]: 3129 : if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
784 [ + - ]: 2000 : 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 [ + + ]: 3129 : if (lowest_larger &&
790 [ + + + + : 1588 : ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
+ - + + ]
791 [ + - ]: 315 : result.AddInput(*lowest_larger);
792 : : } else {
793 [ - + + + ]: 379138 : for (unsigned int i = 0; i < applicable_groups.size(); i++) {
794 [ + + ]: 376324 : if (vfBest[i]) {
795 [ + - ]: 163992 : result.AddInput(applicable_groups[i]);
796 : : }
797 : : }
798 : :
799 : : // If the result exceeds the maximum allowed size, return closest UTXO above the target
800 [ + + ]: 2814 : if (result.GetWeight() > max_selection_weight) {
801 : : // No coin above target, nothing to do.
802 [ + + + - ]: 23 : if (!lowest_larger) return ErrorMaxWeightExceeded();
803 : :
804 : : // Return closest UTXO above target
805 [ + - ]: 1 : result.Clear();
806 [ + - ]: 1 : result.AddInput(*lowest_larger);
807 : : }
808 : :
809 [ + - + - ]: 2792 : if (util::log::ShouldDebugLog(BCLog::SELECTCOINS)) {
810 [ + - ]: 2792 : std::string log_message{"Coin selection best subset: "};
811 [ - + + + ]: 346306 : for (unsigned int i = 0; i < applicable_groups.size(); i++) {
812 [ + + ]: 343514 : if (vfBest[i]) {
813 [ + - + - ]: 262364 : log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
814 : : }
815 : : }
816 [ + - + - : 2792 : LogDebug(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
+ - + - ]
817 : 2792 : }
818 : : }
819 : 3107 : Assume(result.GetWeight() <= max_selection_weight);
820 : 3107 : return result;
821 : 11463 : }
822 : :
823 : : /******************************************************************************
824 : :
825 : : OutputGroup
826 : :
827 : : ******************************************************************************/
828 : :
829 : 1373698 : void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t cluster_count) {
830 : 1373698 : m_outputs.push_back(output);
831 : 1373698 : auto& coin = *m_outputs.back();
832 : :
833 : 1373698 : fee += coin.GetFee();
834 : :
835 [ + + ]: 1373698 : coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
836 : 1373698 : long_term_fee += coin.long_term_fee;
837 : :
838 : 1373698 : effective_value += coin.GetEffectiveValue();
839 : :
840 : 1373698 : m_from_me &= coin.from_me;
841 : 1373698 : m_value += coin.txout.nValue;
842 [ + + ]: 1373698 : 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 : 1373698 : 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 [ + + ]: 1373698 : m_max_cluster_count = std::max(m_max_cluster_count, cluster_count);
850 : :
851 [ + + ]: 1373698 : if (output->input_bytes > 0) {
852 : 694023 : m_weight += output->input_bytes * WITNESS_SCALE_FACTOR;
853 : : }
854 : 1373698 : }
855 : :
856 : 1811225 : bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
857 : : {
858 [ + + ]: 1811225 : return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
859 [ + + ]: 1657507 : && m_ancestors <= eligibility_filter.max_ancestors
860 [ + + + + ]: 3460732 : && m_max_cluster_count <= eligibility_filter.max_cluster_count;
861 : : }
862 : :
863 : 864984450 : CAmount OutputGroup::GetSelectionAmount() const
864 : : {
865 [ + + ]: 864984450 : return m_subtract_fee_outputs ? m_value : effective_value;
866 : : }
867 : :
868 : 1649267 : void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed)
869 : : {
870 [ + - ]: 1649267 : if (group.m_outputs.empty()) return;
871 : :
872 : 1649267 : Groups& groups = groups_by_type[type];
873 [ + + + + ]: 1649267 : if (insert_positive && group.GetSelectionAmount() > 0) {
874 : 1466200 : groups.positive_group.emplace_back(group);
875 : 1466200 : all_groups.positive_group.emplace_back(group);
876 : : }
877 [ + + ]: 1649267 : if (insert_mixed) {
878 : 1466376 : groups.mixed_group.emplace_back(group);
879 : 1466376 : all_groups.mixed_group.emplace_back(group);
880 : : }
881 : : }
882 : :
883 : 3604 : CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
884 : : {
885 [ + + ]: 3604 : if (payment_value <= CHANGE_LOWER / 2) {
886 : 80 : return change_fee + CHANGE_LOWER;
887 : : } else {
888 : : // random value between 50ksat and min (payment_value * 2, 1milsat)
889 [ + + ]: 3524 : const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
890 : 3524 : return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
891 : : }
892 : : }
893 : :
894 : 22 : void SelectionResult::SetBumpFeeDiscount(const CAmount discount)
895 : : {
896 : : // Overlapping ancestry can only lower the fees, not increase them
897 [ - + ]: 22 : assert (discount >= 0);
898 : 22 : bump_fee_group_discount = discount;
899 : 22 : }
900 : :
901 : 10100 : 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 [ - + ]: 10100 : assert(!m_selected_inputs.empty());
905 : :
906 : : // Always consider the cost of spending an input now vs in the future.
907 : 10100 : CAmount waste = 0;
908 [ + + ]: 172984 : for (const auto& coin_ptr : m_selected_inputs) {
909 : 162884 : const COutput& coin = *coin_ptr;
910 : 162884 : waste += coin.GetFee() - coin.long_term_fee;
911 : : }
912 : : // Bump fee of whole selection may diverge from sum of individual bump fees
913 : 10100 : waste -= bump_fee_group_discount;
914 : :
915 [ + + ]: 10100 : 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 : 9799 : waste += change_cost;
919 : : } else {
920 : : // When we are not making change (GetChange(…) == 0), consider the excess we are throwing away to fees
921 [ + + ]: 301 : CAmount selected_effective_value = m_use_effective ? GetSelectedEffectiveValue() : GetSelectedValue();
922 [ - + ]: 301 : assert(selected_effective_value >= m_target);
923 : 301 : waste += selected_effective_value - m_target;
924 : : }
925 : :
926 : 10100 : m_waste = waste;
927 : 10100 : }
928 : :
929 : 4314 : void SelectionResult::SetAlgoCompleted(bool algo_completed)
930 : : {
931 : 4314 : m_algo_completed = algo_completed;
932 : 4314 : }
933 : :
934 : 0 : bool SelectionResult::GetAlgoCompleted() const
935 : : {
936 : 0 : return m_algo_completed;
937 : : }
938 : :
939 : 4314 : void SelectionResult::SetSelectionsEvaluated(size_t attempts)
940 : : {
941 : 4314 : m_selections_evaluated = attempts;
942 : 4314 : }
943 : :
944 : 228 : size_t SelectionResult::GetSelectionsEvaluated() const
945 : : {
946 : 228 : return m_selections_evaluated;
947 : : }
948 : :
949 : 3537 : CAmount SelectionResult::GetWaste() const
950 : : {
951 [ - + ]: 3537 : return *Assert(m_waste);
952 : : }
953 : :
954 : 11604 : CAmount SelectionResult::GetSelectedValue() const
955 : : {
956 : 167884 : 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 : 11294 : CAmount SelectionResult::GetSelectedEffectiveValue() const
960 : : {
961 : 240816 : 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 : 3541 : CAmount SelectionResult::GetTotalBumpFees() const
965 : : {
966 : 18088 : 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 : 3 : void SelectionResult::Clear()
970 : : {
971 : 3 : m_selected_inputs.clear();
972 [ - + ]: 3 : m_waste.reset();
973 : 3 : m_weight = 0;
974 : 3 : }
975 : :
976 : 259000 : void SelectionResult::AddInput(const OutputGroup& group)
977 : : {
978 : : // As it can fail, combine inputs first
979 : 259000 : InsertInputs(group.m_outputs);
980 : 259000 : m_use_effective = !group.m_subtract_fee_outputs;
981 : :
982 : 259000 : m_weight += group.m_weight;
983 : 259000 : }
984 : :
985 : 501 : void SelectionResult::AddInputs(const OutputSet& inputs, bool subtract_fee_outputs)
986 : : {
987 : : // As it can fail, combine inputs first
988 : 501 : InsertInputs(inputs);
989 : 501 : m_use_effective = !subtract_fee_outputs;
990 : :
991 : 501 : m_weight += std::accumulate(inputs.cbegin(), inputs.cend(), 0, [](int sum, const auto& coin) {
992 [ + - ]: 11050 : return sum + std::max(coin->input_bytes, 0) * WITNESS_SCALE_FACTOR;
993 : : });
994 : 501 : }
995 : :
996 : 84 : void SelectionResult::Merge(const SelectionResult& other)
997 : : {
998 : : // As it can fail, combine inputs first
999 : 84 : InsertInputs(other.m_selected_inputs);
1000 : :
1001 : 84 : m_target += other.m_target;
1002 : 84 : m_use_effective |= other.m_use_effective;
1003 [ - + ]: 84 : if (m_algo == SelectionAlgorithm::MANUAL) {
1004 : 0 : m_algo = other.m_algo;
1005 : : }
1006 : :
1007 : 84 : m_weight += other.m_weight;
1008 : 84 : }
1009 : :
1010 : 15963 : const OutputSet& SelectionResult::GetInputSet() const
1011 : : {
1012 : 15963 : return m_selected_inputs;
1013 : : }
1014 : :
1015 : 3544 : std::vector<std::shared_ptr<COutput>> SelectionResult::GetShuffledInputVector() const
1016 : : {
1017 : 3544 : std::vector<std::shared_ptr<COutput>> coins(m_selected_inputs.begin(), m_selected_inputs.end());
1018 : 3544 : std::shuffle(coins.begin(), coins.end(), FastRandomContext());
1019 : 3544 : return coins;
1020 : : }
1021 : :
1022 : 5883 : bool SelectionResult::operator<(SelectionResult other) const
1023 : : {
1024 [ - + ]: 5883 : Assert(m_waste.has_value());
1025 [ - + ]: 5883 : 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 [ + + + + : 5883 : return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
+ + ]
1028 : : }
1029 : :
1030 : 0 : std::string COutput::ToString() const
1031 : : {
1032 [ # # # # ]: 0 : return strprintf("COutput(%s, %d, %d) [%s]", outpoint.hash.ToString(), outpoint.n, depth, FormatMoney(txout.nValue));
1033 : : }
1034 : :
1035 : 3516 : std::string GetAlgorithmName(const SelectionAlgorithm algo)
1036 : : {
1037 [ + + + + : 3516 : switch (algo)
+ - ]
1038 : : {
1039 : 11 : case SelectionAlgorithm::BNB: return "bnb";
1040 : 2532 : case SelectionAlgorithm::KNAPSACK: return "knapsack";
1041 : 515 : case SelectionAlgorithm::SRD: return "srd";
1042 : 48 : case SelectionAlgorithm::CG: return "cg";
1043 : 410 : case SelectionAlgorithm::MANUAL: return "manual";
1044 : : } // no default case, so the compiler can warn about missing cases
1045 : 0 : assert(false);
1046 : : }
1047 : :
1048 : 13642 : 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 : 13642 : const CAmount change = m_use_effective
1057 [ + + ]: 13642 : ? GetSelectedEffectiveValue() - m_target - change_fee
1058 : 13642 : : GetSelectedValue() - m_target;
1059 : :
1060 [ + + ]: 13642 : if (change < min_viable_change) {
1061 : 375 : return 0;
1062 : : }
1063 : :
1064 : : return change;
1065 : : }
1066 : :
1067 : : } // namespace wallet
|
