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