Line data Source code
1 : // Copyright (c) 2017-2019 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 <optional.h>
8 : #include <policy/feerate.h>
9 : #include <util/system.h>
10 : #include <util/moneystr.h>
11 :
12 : // Descending order comparator
13 : struct {
14 4630760 : bool operator()(const OutputGroup& a, const OutputGroup& b) const
15 : {
16 4630760 : return a.effective_value > b.effective_value;
17 : }
18 : } descending;
19 :
20 : /*
21 : * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
22 : * set that can pay for the spending target and does not exceed the spending target by more than the
23 : * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
24 : * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
25 : * are sorted by their effective values and the trees is explored deterministically per the inclusion
26 : * branch first. At each node, the algorithm checks whether the selection is within the target range.
27 : * While the selection has not reached the target range, more UTXOs are included. When a selection's
28 : * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
29 : * At that point, the last included UTXO is deselected and the corresponding omission branch explored
30 : * instead. The search ends after the complete tree has been searched or after a limited number of tries.
31 : *
32 : * The search continues to search for better solutions after one solution has been found. The best
33 : * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
34 : * spend the current inputs at the given fee rate minus the long term expected cost to spend the
35 : * inputs, plus the amount the selection exceeds the spending target:
36 : *
37 : * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
38 : *
39 : * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
40 : * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
41 : * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
42 : * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
43 : * predecessor.
44 : *
45 : * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
46 : * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
47 : *
48 : * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
49 : * These UTXOs will be sorted in descending order by effective value and the CInputCoins'
50 : * values are their effective values.
51 : * @param const CAmount& target_value This is the value that we want to select. It is the lower
52 : * bound of the range.
53 : * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
54 : * This plus target_value is the upper bound of the range.
55 : * @param std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins
56 : * that have been selected.
57 : * @param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins
58 : * that were selected.
59 : * @param CAmount not_input_fees -> The fees that need to be paid for the outputs and fixed size
60 : * overhead (version, locktime, marker and flag)
61 : */
62 :
63 : static const size_t TOTAL_TRIES = 100000;
64 :
65 16657 : bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)
66 : {
67 16657 : out_set.clear();
68 79134216 : CAmount curr_value = 0;
69 :
70 16657 : std::vector<bool> curr_selection; // select the utxo at this index
71 16657 : curr_selection.reserve(utxo_pool.size());
72 16657 : CAmount actual_target = not_input_fees + target_value;
73 :
74 : // Calculate curr_available_value
75 158267663 : CAmount curr_available_value = 0;
76 850615 : for (const OutputGroup& utxo : utxo_pool) {
77 : // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
78 833958 : assert(utxo.effective_value > 0);
79 833958 : curr_available_value += utxo.effective_value;
80 : }
81 16657 : if (curr_available_value < actual_target) {
82 898 : return false;
83 : }
84 :
85 : // Sort the utxo_pool
86 15759 : std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
87 :
88 79134216 : CAmount curr_waste = 0;
89 15759 : std::vector<bool> best_selection;
90 79134216 : CAmount best_waste = MAX_MONEY;
91 :
92 : // Depth First search loop for choosing the UTXOs
93 79134216 : for (size_t i = 0; i < TOTAL_TRIES; ++i) {
94 : // Conditions for starting a backtrack
95 : bool backtrack = false;
96 79133455 : if (curr_value + curr_available_value < actual_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
97 65994551 : curr_value > actual_target + cost_of_change || // Selected value is out of range, go back and try other branch
98 51983763 : (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing
99 : backtrack = true;
100 79133447 : } else if (curr_value >= actual_target) { // Selected value is within range
101 43900 : curr_waste += (curr_value - actual_target); // This is the excess value which is added to the waste for the below comparison
102 : // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
103 : // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
104 : // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
105 : // explore any more UTXOs to avoid burning money like that.
106 43900 : if (curr_waste <= best_waste) {
107 2554 : best_selection = curr_selection;
108 2554 : best_selection.resize(utxo_pool.size());
109 : best_waste = curr_waste;
110 2554 : if (best_waste == 0) {
111 123 : break;
112 : }
113 : }
114 : curr_waste -= (curr_value - actual_target); // Remove the excess value as we will be selecting different coins now
115 : backtrack = true;
116 43777 : }
117 :
118 : // Backtracking, moving backwards
119 79133324 : if (backtrack) {
120 : // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.
121 78893422 : while (!curr_selection.empty() && !curr_selection.back()) {
122 51699961 : curr_selection.pop_back();
123 51699961 : curr_available_value += utxo_pool.at(curr_selection.size()).effective_value;
124 : }
125 :
126 27193461 : if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
127 14867 : break;
128 : }
129 :
130 : // Output was included on previous iterations, try excluding now.
131 27178594 : curr_selection.back() = false;
132 27178594 : OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
133 27178594 : curr_value -= utxo.effective_value;
134 27178594 : curr_waste -= utxo.fee - utxo.long_term_fee;
135 27178594 : } else { // Moving forwards, continuing down this branch
136 51939863 : OutputGroup& utxo = utxo_pool.at(curr_selection.size());
137 :
138 : // Remove this utxo from the curr_available_value utxo amount
139 51939863 : curr_available_value -= utxo.effective_value;
140 :
141 : // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded. Since the ratio of fee to
142 : // long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
143 90701991 : if (!curr_selection.empty() && !curr_selection.back() &&
144 38762128 : utxo.effective_value == utxo_pool.at(curr_selection.size() - 1).effective_value &&
145 24722883 : utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
146 24722883 : curr_selection.push_back(false);
147 24722883 : } else {
148 : // Inclusion branch first (Largest First Exploration)
149 27216980 : curr_selection.push_back(true);
150 27216980 : curr_value += utxo.effective_value;
151 27216980 : curr_waste += utxo.fee - utxo.long_term_fee;
152 : }
153 0 : }
154 79118457 : }
155 :
156 : // Check for solution
157 15759 : if (best_selection.empty()) {
158 15551 : return false;
159 : }
160 :
161 : // Set output set
162 208 : value_ret = 0;
163 161987 : for (size_t i = 0; i < best_selection.size(); ++i) {
164 161779 : if (best_selection.at(i)) {
165 24647 : util::insert(out_set, utxo_pool.at(i).m_outputs);
166 24647 : value_ret += utxo_pool.at(i).m_value;
167 24647 : }
168 : }
169 :
170 208 : return true;
171 16657 : }
172 :
173 3530 : static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue,
174 : std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
175 : {
176 3530 : std::vector<char> vfIncluded;
177 :
178 3530 : vfBest.assign(groups.size(), true);
179 3530 : nBest = nTotalLower;
180 :
181 3530 : FastRandomContext insecure_rand;
182 :
183 2304794 : for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
184 : {
185 2301264 : vfIncluded.assign(groups.size(), false);
186 5753420 : CAmount nTotal = 0;
187 5753420 : bool fReachedTarget = false;
188 5753420 : for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
189 : {
190 373908257 : for (unsigned int i = 0; i < groups.size(); i++)
191 : {
192 : //The solver here uses a randomized algorithm,
193 : //the randomness serves no real security purpose but is just
194 : //needed to prevent degenerate behavior and it is important
195 : //that the rng is fast. We do not use a constant random sequence,
196 : //because there may be some privacy improvement by making
197 : //the selection random.
198 370456101 : if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
199 : {
200 185693769 : nTotal += groups[i].m_value;
201 185693769 : vfIncluded[i] = true;
202 185693769 : if (nTotal >= nTargetValue)
203 : {
204 : fReachedTarget = true;
205 170015126 : if (nTotal < nBest)
206 : {
207 7422 : nBest = nTotal;
208 7422 : vfBest = vfIncluded;
209 : }
210 170015126 : nTotal -= groups[i].m_value;
211 170015126 : vfIncluded[i] = false;
212 170015126 : }
213 : }
214 : }
215 : }
216 0 : }
217 3530 : }
218 :
219 8991 : bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
220 : {
221 8991 : setCoinsRet.clear();
222 8991 : nValueRet = 0;
223 :
224 : // List of values less than target
225 8991 : Optional<OutputGroup> lowest_larger;
226 8991 : std::vector<OutputGroup> applicable_groups;
227 8991 : CAmount nTotalLower = 0;
228 :
229 8991 : Shuffle(groups.begin(), groups.end(), FastRandomContext());
230 :
231 596881 : for (const OutputGroup& group : groups) {
232 587890 : if (group.m_value == nTargetValue) {
233 1213 : util::insert(setCoinsRet, group.m_outputs);
234 1213 : nValueRet += group.m_value;
235 1213 : return true;
236 586677 : } else if (group.m_value < nTargetValue + MIN_CHANGE) {
237 259835 : applicable_groups.push_back(group);
238 259835 : nTotalLower += group.m_value;
239 586677 : } else if (!lowest_larger || group.m_value < lowest_larger->m_value) {
240 8064 : lowest_larger = group;
241 : }
242 586677 : }
243 :
244 7778 : if (nTotalLower == nTargetValue) {
245 2400 : for (const auto& group : applicable_groups) {
246 1900 : util::insert(setCoinsRet, group.m_outputs);
247 1900 : nValueRet += group.m_value;
248 : }
249 500 : return true;
250 : }
251 :
252 7278 : if (nTotalLower < nTargetValue) {
253 4935 : if (!lowest_larger) return false;
254 3497 : util::insert(setCoinsRet, lowest_larger->m_outputs);
255 3497 : nValueRet += lowest_larger->m_value;
256 3497 : return true;
257 : }
258 :
259 : // Solve subset sum by stochastic approximation
260 2343 : std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
261 2343 : std::vector<char> vfBest;
262 2343 : CAmount nBest;
263 :
264 2343 : ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
265 2343 : if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
266 1187 : ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
267 1187 : }
268 :
269 : // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
270 : // or the next bigger coin is closer), return the bigger coin
271 3455 : if (lowest_larger &&
272 1219 : ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) {
273 310 : util::insert(setCoinsRet, lowest_larger->m_outputs);
274 310 : nValueRet += lowest_larger->m_value;
275 310 : } else {
276 249027 : for (unsigned int i = 0; i < applicable_groups.size(); i++) {
277 246994 : if (vfBest[i]) {
278 93515 : util::insert(setCoinsRet, applicable_groups[i].m_outputs);
279 93515 : nValueRet += applicable_groups[i].m_value;
280 93515 : }
281 : }
282 :
283 2033 : if (LogAcceptCategory(BCLog::SELECTCOINS)) {
284 2033 : LogPrint(BCLog::SELECTCOINS, "SelectCoins() best subset: "); /* Continued */
285 249027 : for (unsigned int i = 0; i < applicable_groups.size(); i++) {
286 246994 : if (vfBest[i]) {
287 93515 : LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(applicable_groups[i].m_value)); /* Continued */
288 : }
289 : }
290 2033 : LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));
291 : }
292 : }
293 :
294 : return true;
295 8991 : }
296 :
297 : /******************************************************************************
298 :
299 : OutputGroup
300 :
301 : ******************************************************************************/
302 :
303 1159490 : void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
304 1159490 : m_outputs.push_back(output);
305 1159490 : m_from_me &= from_me;
306 1159490 : m_value += output.txout.nValue;
307 1159490 : m_depth = std::min(m_depth, depth);
308 : // ancestors here express the number of ancestors the new coin will end up having, which is
309 : // the sum, rather than the max; this will overestimate in the cases where multiple inputs
310 : // have common ancestors
311 1159490 : m_ancestors += ancestors;
312 : // descendants is the count as seen from the top ancestor, not the descendants as seen from the
313 : // coin itself; thus, this value is counted as the max, not the sum
314 1159490 : m_descendants = std::max(m_descendants, descendants);
315 1159490 : effective_value += output.effective_value;
316 1159490 : fee += output.m_fee;
317 1159490 : long_term_fee += output.m_long_term_fee;
318 1159490 : }
319 :
320 13 : std::vector<CInputCoin>::iterator OutputGroup::Discard(const CInputCoin& output) {
321 13 : auto it = m_outputs.begin();
322 13 : while (it != m_outputs.end() && it->outpoint != output.outpoint) ++it;
323 13 : if (it == m_outputs.end()) return it;
324 13 : m_value -= output.txout.nValue;
325 13 : effective_value -= output.effective_value;
326 13 : fee -= output.m_fee;
327 13 : long_term_fee -= output.m_long_term_fee;
328 13 : return m_outputs.erase(it);
329 13 : }
330 :
331 1507879 : bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
332 : {
333 2987792 : return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
334 1507879 : && m_ancestors <= eligibility_filter.max_ancestors
335 1479913 : && m_descendants <= eligibility_filter.max_descendants;
336 : }
337 :
338 781891 : void OutputGroup::SetFees(const CFeeRate effective_feerate, const CFeeRate long_term_feerate)
339 : {
340 781891 : fee = 0;
341 781891 : long_term_fee = 0;
342 781891 : effective_value = 0;
343 2043072 : for (CInputCoin& coin : m_outputs) {
344 1261181 : coin.m_fee = coin.m_input_bytes < 0 ? 0 : effective_feerate.GetFee(coin.m_input_bytes);
345 1261181 : fee += coin.m_fee;
346 :
347 1261181 : coin.m_long_term_fee = coin.m_input_bytes < 0 ? 0 : long_term_feerate.GetFee(coin.m_input_bytes);
348 1261181 : long_term_fee += coin.m_long_term_fee;
349 :
350 1261181 : coin.effective_value = coin.txout.nValue - coin.m_fee;
351 1261181 : effective_value += coin.effective_value;
352 : }
353 781891 : }
354 :
355 781891 : OutputGroup OutputGroup::GetPositiveOnlyGroup()
356 : {
357 781891 : OutputGroup group(*this);
358 2043072 : for (auto it = group.m_outputs.begin(); it != group.m_outputs.end(); ) {
359 1261181 : const CInputCoin& coin = *it;
360 : // Only include outputs that are positive effective value (i.e. not dust)
361 1261181 : if (coin.effective_value <= 0) {
362 13 : it = group.Discard(coin);
363 13 : } else {
364 1261168 : ++it;
365 : }
366 : }
367 : return group;
368 781891 : }
|
