How a wallet chooses which coins to spend

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
20namespace wallet {
21// Common selection error across the algorithms
22static 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
29struct {
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
41struct {
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
113static const size_t TOTAL_TRIES = 100000;
114
115util::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());