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