LCOV - code coverage report
Current view: top level - src/wallet - coinselection.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 3 322 0.9 %
Date: 2023-10-05 12:38:51 Functions: 3 36 8.3 %
Branches: 2 387 0.5 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2017-2022 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         [ +  - ]:          2 : #include <optional>
      18         [ +  - ]:          2 : #include <queue>
      19                 :            : 
      20                 :            : namespace wallet {
      21                 :            : // Common selection error across the algorithms
      22                 :          0 : static util::Result<SelectionResult> ErrorMaxWeightExceeded()
      23                 :            : {
      24         [ #  # ]:          0 :     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                 :          0 : }
      27                 :            : 
      28                 :            : // Descending order comparator
      29                 :            : struct {
      30                 :          0 :     bool operator()(const OutputGroup& a, const OutputGroup& b) const
      31                 :            :     {
      32                 :          0 :         return a.GetSelectionAmount() > b.GetSelectionAmount();
      33                 :            :     }
      34                 :            : } descending;
      35                 :            : 
      36                 :            : /*
      37                 :            :  * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
      38                 :            :  * set that can pay for the spending target and does not exceed the spending target by more than the
      39                 :            :  * cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
      40                 :            :  * tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
      41                 :            :  * are sorted by their effective values and the tree is explored deterministically per the inclusion
      42                 :            :  * branch first. At each node, the algorithm checks whether the selection is within the target range.
      43                 :            :  * While the selection has not reached the target range, more UTXOs are included. When a selection's
      44                 :            :  * value exceeds the target range, the complete subtree deriving from this selection can be omitted.
      45                 :            :  * At that point, the last included UTXO is deselected and the corresponding omission branch explored
      46                 :            :  * instead. The search ends after the complete tree has been searched or after a limited number of tries.
      47                 :            :  *
      48                 :            :  * The search continues to search for better solutions after one solution has been found. The best
      49                 :            :  * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
      50                 :            :  * spend the current inputs at the given fee rate minus the long term expected cost to spend the
      51                 :            :  * inputs, plus the amount by which the selection exceeds the spending target:
      52                 :            :  *
      53                 :            :  * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
      54                 :            :  *
      55                 :            :  * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
      56                 :            :  * the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
      57                 :            :  * cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
      58                 :            :  * to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
      59                 :            :  * predecessor.
      60                 :            :  *
      61                 :            :  * The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
      62                 :            :  * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
      63                 :            :  *
      64                 :            :  * @param const std::vector<OutputGroup>& utxo_pool The set of UTXO groups that we are choosing from.
      65                 :            :  *        These UTXO groups will be sorted in descending order by effective value and the OutputGroups'
      66                 :            :  *        values are their effective values.
      67                 :            :  * @param const CAmount& selection_target This is the value that we want to select. It is the lower
      68                 :            :  *        bound of the range.
      69                 :            :  * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
      70                 :            :  *        This plus selection_target is the upper bound of the range.
      71                 :            :  * @returns The result of this coin selection algorithm, or std::nullopt
      72                 :            :  */
      73                 :            : 
      74                 :          2 : static const size_t TOTAL_TRIES = 100000;
      75                 :            : 
      76                 :          0 : util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
      77                 :            :                                              int max_weight)
      78                 :            : {
      79                 :          0 :     SelectionResult result(selection_target, SelectionAlgorithm::BNB);
      80                 :          0 :     CAmount curr_value = 0;
      81                 :          0 :     std::vector<size_t> curr_selection; // selected utxo indexes
      82                 :          0 :     int curr_selection_weight = 0; // sum of selected utxo weight
      83                 :            : 
      84                 :            :     // Calculate curr_available_value
      85                 :          0 :     CAmount curr_available_value = 0;
      86         [ #  # ]:          0 :     for (const OutputGroup& utxo : utxo_pool) {
      87                 :            :         // Assert that this utxo is not negative. It should never be negative,
      88                 :            :         // effective value calculation should have removed it
      89   [ #  #  #  # ]:          0 :         assert(utxo.GetSelectionAmount() > 0);
      90         [ #  # ]:          0 :         curr_available_value += utxo.GetSelectionAmount();
      91                 :            :     }
      92         [ #  # ]:          0 :     if (curr_available_value < selection_target) {
      93         [ #  # ]:          0 :         return util::Error();
      94                 :            :     }
      95                 :            : 
      96                 :            :     // Sort the utxo_pool
      97         [ #  # ]:          0 :     std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
      98                 :            : 
      99                 :          0 :     CAmount curr_waste = 0;
     100                 :          0 :     std::vector<size_t> best_selection;
     101                 :          0 :     CAmount best_waste = MAX_MONEY;
     102                 :            : 
     103   [ #  #  #  # ]:          0 :     bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
     104                 :          0 :     bool max_tx_weight_exceeded = false;
     105                 :            : 
     106                 :            :     // Depth First search loop for choosing the UTXOs
     107         [ #  # ]:          0 :     for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
     108                 :            :         // Conditions for starting a backtrack
     109                 :          0 :         bool backtrack = false;
     110   [ #  #  #  # ]:          0 :         if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
     111         [ #  # ]:          0 :             curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
     112         [ #  # ]:          0 :             (curr_waste > best_waste && is_feerate_high)) { // Don't select things which we know will be more wasteful if the waste is increasing
     113                 :          0 :             backtrack = true;
     114         [ #  # ]:          0 :         } else if (curr_selection_weight > max_weight) { // Exceeding weight for standard tx, cannot find more solutions by adding more inputs
     115                 :          0 :             max_tx_weight_exceeded = true; // at least one selection attempt exceeded the max weight
     116                 :          0 :             backtrack = true;
     117         [ #  # ]:          0 :         } else if (curr_value >= selection_target) {       // Selected value is within range
     118                 :          0 :             curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison
     119                 :            :             // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
     120                 :            :             // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
     121                 :            :             // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
     122                 :            :             // explore any more UTXOs to avoid burning money like that.
     123         [ #  # ]:          0 :             if (curr_waste <= best_waste) {
     124         [ #  # ]:          0 :                 best_selection = curr_selection;
     125                 :          0 :                 best_waste = curr_waste;
     126                 :          0 :             }
     127                 :          0 :             curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
     128                 :          0 :             backtrack = true;
     129                 :          0 :         }
     130                 :            : 
     131         [ #  # ]:          0 :         if (backtrack) { // Backtracking, moving backwards
     132         [ #  # ]:          0 :             if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
     133                 :          0 :                 break;
     134                 :            :             }
     135                 :            : 
     136                 :            :             // Add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO.
     137         [ #  # ]:          0 :             for (--utxo_pool_index; utxo_pool_index > curr_selection.back(); --utxo_pool_index) {
     138   [ #  #  #  # ]:          0 :                 curr_available_value += utxo_pool.at(utxo_pool_index).GetSelectionAmount();
     139                 :          0 :             }
     140                 :            : 
     141                 :            :             // Output was included on previous iterations, try excluding now.
     142         [ #  # ]:          0 :             assert(utxo_pool_index == curr_selection.back());
     143         [ #  # ]:          0 :             OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
     144         [ #  # ]:          0 :             curr_value -= utxo.GetSelectionAmount();
     145                 :          0 :             curr_waste -= utxo.fee - utxo.long_term_fee;
     146                 :          0 :             curr_selection_weight -= utxo.m_weight;
     147                 :          0 :             curr_selection.pop_back();
     148                 :          0 :         } else { // Moving forwards, continuing down this branch
     149         [ #  # ]:          0 :             OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
     150                 :            : 
     151                 :            :             // Remove this utxo from the curr_available_value utxo amount
     152         [ #  # ]:          0 :             curr_available_value -= utxo.GetSelectionAmount();
     153                 :            : 
     154   [ #  #  #  # ]:          0 :             if (curr_selection.empty() ||
     155                 :            :                 // The previous index is included and therefore not relevant for exclusion shortcut
     156         [ #  # ]:          0 :                 (utxo_pool_index - 1) == curr_selection.back() ||
     157                 :            :                 // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded.
     158                 :            :                 // 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.
     159   [ #  #  #  #  :          0 :                 utxo.GetSelectionAmount() != utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() ||
             #  #  #  # ]
     160         [ #  # ]:          0 :                 utxo.fee != utxo_pool.at(utxo_pool_index - 1).fee)
     161                 :            :             {
     162                 :            :                 // Inclusion branch first (Largest First Exploration)
     163         [ #  # ]:          0 :                 curr_selection.push_back(utxo_pool_index);
     164         [ #  # ]:          0 :                 curr_value += utxo.GetSelectionAmount();
     165                 :          0 :                 curr_waste += utxo.fee - utxo.long_term_fee;
     166                 :          0 :                 curr_selection_weight += utxo.m_weight;
     167                 :          0 :             }
     168                 :            :         }
     169                 :          0 :     }
     170                 :            : 
     171                 :            :     // Check for solution
     172         [ #  # ]:          0 :     if (best_selection.empty()) {
     173   [ #  #  #  #  :          0 :         return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
          #  #  #  #  #  
                      # ]
     174                 :            :     }
     175                 :            : 
     176                 :            :     // Set output set
     177         [ #  # ]:          0 :     for (const size_t& i : best_selection) {
     178   [ #  #  #  # ]:          0 :         result.AddInput(utxo_pool.at(i));
     179                 :            :     }
     180         [ #  # ]:          0 :     result.ComputeAndSetWaste(cost_of_change, cost_of_change, CAmount{0});
     181   [ #  #  #  # ]:          0 :     assert(best_waste == result.GetWaste());
     182                 :            : 
     183         [ #  # ]:          0 :     return result;
     184                 :          0 : }
     185                 :            : 
     186                 :            : class MinOutputGroupComparator
     187                 :            : {
     188                 :            : public:
     189                 :          0 :     int operator() (const OutputGroup& group1, const OutputGroup& group2) const
     190                 :            :     {
     191                 :          0 :         return group1.GetSelectionAmount() > group2.GetSelectionAmount();
     192                 :            :     }
     193                 :            : };
     194                 :            : 
     195                 :          0 : util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
     196                 :            :                                              int max_weight)
     197                 :            : {
     198                 :          0 :     SelectionResult result(target_value, SelectionAlgorithm::SRD);
     199         [ #  # ]:          0 :     std::priority_queue<OutputGroup, std::vector<OutputGroup>, MinOutputGroupComparator> heap;
     200                 :            : 
     201                 :            :     // Include change for SRD as we want to avoid making really small change if the selection just
     202                 :            :     // barely meets the target. Just use the lower bound change target instead of the randomly
     203                 :            :     // generated one, since SRD will result in a random change amount anyway; avoid making the
     204                 :            :     // target needlessly large.
     205                 :          0 :     target_value += CHANGE_LOWER + change_fee;
     206                 :            : 
     207                 :          0 :     std::vector<size_t> indexes;
     208         [ #  # ]:          0 :     indexes.resize(utxo_pool.size());
     209         [ #  # ]:          0 :     std::iota(indexes.begin(), indexes.end(), 0);
     210         [ #  # ]:          0 :     Shuffle(indexes.begin(), indexes.end(), rng);
     211                 :            : 
     212                 :          0 :     CAmount selected_eff_value = 0;
     213                 :          0 :     int weight = 0;
     214                 :          0 :     bool max_tx_weight_exceeded = false;
     215         [ #  # ]:          0 :     for (const size_t i : indexes) {
     216         [ #  # ]:          0 :         const OutputGroup& group = utxo_pool.at(i);
     217   [ #  #  #  # ]:          0 :         Assume(group.GetSelectionAmount() > 0);
     218                 :            : 
     219                 :            :         // Add group to selection
     220         [ #  # ]:          0 :         heap.push(group);
     221         [ #  # ]:          0 :         selected_eff_value += group.GetSelectionAmount();
     222                 :          0 :         weight += group.m_weight;
     223                 :            : 
     224                 :            :         // If the selection weight exceeds the maximum allowed size, remove the least valuable inputs until we
     225                 :            :         // are below max weight.
     226         [ #  # ]:          0 :         if (weight > max_weight) {
     227                 :          0 :             max_tx_weight_exceeded = true; // mark it in case we don't find any useful result.
     228                 :          0 :             do {
     229         [ #  # ]:          0 :                 const OutputGroup& to_remove_group = heap.top();
     230         [ #  # ]:          0 :                 selected_eff_value -= to_remove_group.GetSelectionAmount();
     231                 :          0 :                 weight -= to_remove_group.m_weight;
     232         [ #  # ]:          0 :                 heap.pop();
     233   [ #  #  #  #  :          0 :             } while (!heap.empty() && weight > max_weight);
                   #  # ]
     234                 :          0 :         }
     235                 :            : 
     236                 :            :         // Now check if we are above the target
     237         [ #  # ]:          0 :         if (selected_eff_value >= target_value) {
     238                 :            :             // Result found, add it.
     239   [ #  #  #  # ]:          0 :             while (!heap.empty()) {
     240   [ #  #  #  # ]:          0 :                 result.AddInput(heap.top());
     241         [ #  # ]:          0 :                 heap.pop();
     242                 :            :             }
     243         [ #  # ]:          0 :             return result;
     244                 :            :         }
     245                 :            :     }
     246   [ #  #  #  #  :          0 :     return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
          #  #  #  #  #  
                      # ]
     247                 :          0 : }
     248                 :            : 
     249                 :            : /** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
     250                 :            :  * target amount; solve subset sum.
     251                 :            :  * param@[in]   groups          OutputGroups to choose from, sorted by value in descending order.
     252                 :            :  * param@[in]   nTotalLower     Total (effective) value of the UTXOs in groups.
     253                 :            :  * param@[in]   nTargetValue    Subset sum target, not including change.
     254                 :            :  * param@[out]  vfBest          Boolean vector representing the subset chosen that is closest to
     255                 :            :  *                              nTargetValue, with indices corresponding to groups. If the ith
     256                 :            :  *                              entry is true, that means the ith group in groups was selected.
     257                 :            :  * param@[out]  nBest           Total amount of subset chosen that is closest to nTargetValue.
     258                 :            :  * param@[in]   iterations      Maximum number of tries.
     259                 :            :  */
     260                 :          0 : static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
     261                 :            :                                   const CAmount& nTotalLower, const CAmount& nTargetValue,
     262                 :            :                                   std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
     263                 :            : {
     264                 :          0 :     std::vector<char> vfIncluded;
     265                 :            : 
     266                 :            :     // Worst case "best" approximation is just all of the groups.
     267         [ #  # ]:          0 :     vfBest.assign(groups.size(), true);
     268                 :          0 :     nBest = nTotalLower;
     269                 :            : 
     270   [ #  #  #  # ]:          0 :     for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
     271                 :            :     {
     272         [ #  # ]:          0 :         vfIncluded.assign(groups.size(), false);
     273                 :          0 :         CAmount nTotal = 0;
     274                 :          0 :         bool fReachedTarget = false;
     275   [ #  #  #  # ]:          0 :         for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
     276                 :            :         {
     277         [ #  # ]:          0 :             for (unsigned int i = 0; i < groups.size(); i++)
     278                 :            :             {
     279                 :            :                 //The solver here uses a randomized algorithm,
     280                 :            :                 //the randomness serves no real security purpose but is just
     281                 :            :                 //needed to prevent degenerate behavior and it is important
     282                 :            :                 //that the rng is fast. We do not use a constant random sequence,
     283                 :            :                 //because there may be some privacy improvement by making
     284                 :            :                 //the selection random.
     285   [ #  #  #  # ]:          0 :                 if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
     286                 :            :                 {
     287                 :          0 :                     nTotal += groups[i].GetSelectionAmount();
     288                 :          0 :                     vfIncluded[i] = true;
     289         [ #  # ]:          0 :                     if (nTotal >= nTargetValue)
     290                 :            :                     {
     291                 :          0 :                         fReachedTarget = true;
     292                 :            :                         // If the total is between nTargetValue and nBest, it's our new best
     293                 :            :                         // approximation.
     294         [ #  # ]:          0 :                         if (nTotal < nBest)
     295                 :            :                         {
     296                 :          0 :                             nBest = nTotal;
     297         [ #  # ]:          0 :                             vfBest = vfIncluded;
     298                 :          0 :                         }
     299                 :          0 :                         nTotal -= groups[i].GetSelectionAmount();
     300                 :          0 :                         vfIncluded[i] = false;
     301                 :          0 :                     }
     302                 :          0 :                 }
     303                 :          0 :             }
     304                 :          0 :         }
     305                 :          0 :     }
     306                 :          0 : }
     307                 :            : 
     308                 :          0 : util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
     309                 :            :                                              CAmount change_target, FastRandomContext& rng, int max_weight)
     310                 :            : {
     311                 :          0 :     SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
     312                 :            : 
     313                 :            :     // List of values less than target
     314                 :          0 :     std::optional<OutputGroup> lowest_larger;
     315                 :            :     // Groups with selection amount smaller than the target and any change we might produce.
     316                 :            :     // Don't include groups larger than this, because they will only cause us to overshoot.
     317                 :          0 :     std::vector<OutputGroup> applicable_groups;
     318                 :          0 :     CAmount nTotalLower = 0;
     319                 :            : 
     320         [ #  # ]:          0 :     Shuffle(groups.begin(), groups.end(), rng);
     321                 :            : 
     322         [ #  # ]:          0 :     for (const OutputGroup& group : groups) {
     323   [ #  #  #  # ]:          0 :         if (group.GetSelectionAmount() == nTargetValue) {
     324         [ #  # ]:          0 :             result.AddInput(group);
     325         [ #  # ]:          0 :             return result;
     326   [ #  #  #  # ]:          0 :         } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
     327         [ #  # ]:          0 :             applicable_groups.push_back(group);
     328         [ #  # ]:          0 :             nTotalLower += group.GetSelectionAmount();
     329   [ #  #  #  #  :          0 :         } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
          #  #  #  #  #  
                      # ]
     330         [ #  # ]:          0 :             lowest_larger = group;
     331                 :          0 :         }
     332                 :            :     }
     333                 :            : 
     334         [ #  # ]:          0 :     if (nTotalLower == nTargetValue) {
     335         [ #  # ]:          0 :         for (const auto& group : applicable_groups) {
     336         [ #  # ]:          0 :             result.AddInput(group);
     337                 :            :         }
     338         [ #  # ]:          0 :         return result;
     339                 :            :     }
     340                 :            : 
     341         [ #  # ]:          0 :     if (nTotalLower < nTargetValue) {
     342   [ #  #  #  # ]:          0 :         if (!lowest_larger) return util::Error();
     343   [ #  #  #  # ]:          0 :         result.AddInput(*lowest_larger);
     344         [ #  # ]:          0 :         return result;
     345                 :            :     }
     346                 :            : 
     347                 :            :     // Solve subset sum by stochastic approximation
     348         [ #  # ]:          0 :     std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
     349                 :          0 :     std::vector<char> vfBest;
     350                 :            :     CAmount nBest;
     351                 :            : 
     352         [ #  # ]:          0 :     ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
     353   [ #  #  #  # ]:          0 :     if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
     354         [ #  # ]:          0 :         ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest);
     355                 :          0 :     }
     356                 :            : 
     357                 :            :     // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
     358                 :            :     //                                   or the next bigger coin is closer), return the bigger coin
     359   [ #  #  #  # ]:          0 :     if (lowest_larger &&
     360   [ #  #  #  #  :          0 :         ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
                   #  # ]
     361   [ #  #  #  # ]:          0 :         result.AddInput(*lowest_larger);
     362                 :          0 :     } else {
     363         [ #  # ]:          0 :         for (unsigned int i = 0; i < applicable_groups.size(); i++) {
     364         [ #  # ]:          0 :             if (vfBest[i]) {
     365         [ #  # ]:          0 :                 result.AddInput(applicable_groups[i]);
     366                 :          0 :             }
     367                 :          0 :         }
     368                 :            : 
     369                 :            :         // If the result exceeds the maximum allowed size, return closest UTXO above the target
     370   [ #  #  #  # ]:          0 :         if (result.GetWeight() > max_weight) {
     371                 :            :             // No coin above target, nothing to do.
     372   [ #  #  #  # ]:          0 :             if (!lowest_larger) return ErrorMaxWeightExceeded();
     373                 :            : 
     374                 :            :             // Return closest UTXO above target
     375         [ #  # ]:          0 :             result.Clear();
     376   [ #  #  #  # ]:          0 :             result.AddInput(*lowest_larger);
     377                 :          0 :         }
     378                 :            : 
     379   [ #  #  #  # ]:          0 :         if (LogAcceptCategory(BCLog::SELECTCOINS, BCLog::Level::Debug)) {
     380         [ #  # ]:          0 :             std::string log_message{"Coin selection best subset: "};
     381         [ #  # ]:          0 :             for (unsigned int i = 0; i < applicable_groups.size(); i++) {
     382         [ #  # ]:          0 :                 if (vfBest[i]) {
     383   [ #  #  #  #  :          0 :                     log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
                   #  # ]
     384                 :          0 :                 }
     385                 :          0 :             }
     386   [ #  #  #  #  :          0 :             LogPrint(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
          #  #  #  #  #  
                #  #  # ]
     387                 :          0 :         }
     388                 :            :     }
     389                 :            : 
     390         [ #  # ]:          0 :     return result;
     391                 :          0 : }
     392                 :            : 
     393                 :            : /******************************************************************************
     394                 :            : 
     395                 :            :  OutputGroup
     396                 :            : 
     397                 :            :  ******************************************************************************/
     398                 :            : 
     399                 :          0 : void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t descendants) {
     400                 :          0 :     m_outputs.push_back(output);
     401                 :          0 :     auto& coin = *m_outputs.back();
     402                 :            : 
     403                 :          0 :     fee += coin.GetFee();
     404                 :            : 
     405         [ #  # ]:          0 :     coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
     406                 :          0 :     long_term_fee += coin.long_term_fee;
     407                 :            : 
     408                 :          0 :     effective_value += coin.GetEffectiveValue();
     409                 :            : 
     410                 :          0 :     m_from_me &= coin.from_me;
     411                 :          0 :     m_value += coin.txout.nValue;
     412                 :          0 :     m_depth = std::min(m_depth, coin.depth);
     413                 :            :     // ancestors here express the number of ancestors the new coin will end up having, which is
     414                 :            :     // the sum, rather than the max; this will overestimate in the cases where multiple inputs
     415                 :            :     // have common ancestors
     416                 :          0 :     m_ancestors += ancestors;
     417                 :            :     // descendants is the count as seen from the top ancestor, not the descendants as seen from the
     418                 :            :     // coin itself; thus, this value is counted as the max, not the sum
     419                 :          0 :     m_descendants = std::max(m_descendants, descendants);
     420                 :            : 
     421         [ #  # ]:          0 :     if (output->input_bytes > 0) {
     422                 :          0 :         m_weight += output->input_bytes * WITNESS_SCALE_FACTOR;
     423                 :          0 :     }
     424                 :          0 : }
     425                 :            : 
     426                 :          0 : bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
     427                 :            : {
     428         [ #  # ]:          0 :     return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
     429         [ #  # ]:          0 :         && m_ancestors <= eligibility_filter.max_ancestors
     430         [ #  # ]:          0 :         && m_descendants <= eligibility_filter.max_descendants;
     431                 :            : }
     432                 :            : 
     433                 :          0 : CAmount OutputGroup::GetSelectionAmount() const
     434                 :            : {
     435         [ #  # ]:          0 :     return m_subtract_fee_outputs ? m_value : effective_value;
     436                 :            : }
     437                 :            : 
     438                 :          0 : void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed)
     439                 :            : {
     440         [ #  # ]:          0 :     if (group.m_outputs.empty()) return;
     441                 :            : 
     442                 :          0 :     Groups& groups = groups_by_type[type];
     443   [ #  #  #  # ]:          0 :     if (insert_positive && group.GetSelectionAmount() > 0) {
     444                 :          0 :         groups.positive_group.emplace_back(group);
     445                 :          0 :         all_groups.positive_group.emplace_back(group);
     446                 :          0 :     }
     447         [ #  # ]:          0 :     if (insert_mixed) {
     448                 :          0 :         groups.mixed_group.emplace_back(group);
     449                 :          0 :         all_groups.mixed_group.emplace_back(group);
     450                 :          0 :     }
     451                 :          0 : }
     452                 :            : 
     453                 :          0 : CAmount SelectionResult::GetSelectionWaste(CAmount change_cost, CAmount target, bool use_effective_value)
     454                 :            : {
     455                 :            :     // This function should not be called with empty inputs as that would mean the selection failed
     456         [ #  # ]:          0 :     assert(!m_selected_inputs.empty());
     457                 :            : 
     458                 :            :     // Always consider the cost of spending an input now vs in the future.
     459                 :          0 :     CAmount waste = 0;
     460         [ #  # ]:          0 :     for (const auto& coin_ptr : m_selected_inputs) {
     461                 :          0 :         const COutput& coin = *coin_ptr;
     462                 :          0 :         waste += coin.GetFee() - coin.long_term_fee;
     463                 :            :     }
     464                 :            :     // Bump fee of whole selection may diverge from sum of individual bump fees
     465                 :          0 :     waste -= bump_fee_group_discount;
     466                 :            : 
     467         [ #  # ]:          0 :     if (change_cost) {
     468                 :            :         // Consider the cost of making change and spending it in the future
     469                 :            :         // If we aren't making change, the caller should've set change_cost to 0
     470         [ #  # ]:          0 :         assert(change_cost > 0);
     471                 :          0 :         waste += change_cost;
     472                 :          0 :     } else {
     473                 :            :         // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
     474         [ #  # ]:          0 :         CAmount selected_effective_value = use_effective_value ? GetSelectedEffectiveValue() : GetSelectedValue();
     475         [ #  # ]:          0 :         assert(selected_effective_value >= target);
     476                 :          0 :         waste += selected_effective_value - target;
     477                 :            :     }
     478                 :            : 
     479                 :          0 :     return waste;
     480                 :            : }
     481                 :            : 
     482                 :          0 : CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
     483                 :            : {
     484         [ #  # ]:          0 :     if (payment_value <= CHANGE_LOWER / 2) {
     485                 :          0 :         return change_fee + CHANGE_LOWER;
     486                 :            :     } else {
     487                 :            :         // random value between 50ksat and min (payment_value * 2, 1milsat)
     488                 :          0 :         const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
     489                 :          0 :         return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
     490                 :            :     }
     491                 :          0 : }
     492                 :            : 
     493                 :          0 : void SelectionResult::SetBumpFeeDiscount(const CAmount discount)
     494                 :            : {
     495                 :            :     // Overlapping ancestry can only lower the fees, not increase them
     496         [ #  # ]:          0 :     assert (discount >= 0);
     497                 :          0 :     bump_fee_group_discount = discount;
     498                 :          0 : }
     499                 :            : 
     500                 :            : 
     501                 :          0 : void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
     502                 :            : {
     503                 :          0 :     const CAmount change = GetChange(min_viable_change, change_fee);
     504                 :            : 
     505         [ #  # ]:          0 :     if (change > 0) {
     506                 :          0 :         m_waste = GetSelectionWaste(change_cost, m_target, m_use_effective);
     507                 :          0 :     } else {
     508                 :          0 :         m_waste = GetSelectionWaste(0, m_target, m_use_effective);
     509                 :            :     }
     510                 :          0 : }
     511                 :            : 
     512                 :          0 : CAmount SelectionResult::GetWaste() const
     513                 :            : {
     514                 :          0 :     return *Assert(m_waste);
     515                 :            : }
     516                 :            : 
     517                 :          0 : CAmount SelectionResult::GetSelectedValue() const
     518                 :            : {
     519                 :          0 :     return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->txout.nValue; });
     520                 :            : }
     521                 :            : 
     522                 :          0 : CAmount SelectionResult::GetSelectedEffectiveValue() const
     523                 :            : {
     524                 :          0 :     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;
     525                 :            : }
     526                 :            : 
     527                 :          0 : CAmount SelectionResult::GetTotalBumpFees() const
     528                 :            : {
     529                 :          0 :     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;
     530                 :            : }
     531                 :            : 
     532                 :          0 : void SelectionResult::Clear()
     533                 :            : {
     534                 :          0 :     m_selected_inputs.clear();
     535                 :          0 :     m_waste.reset();
     536                 :          0 :     m_weight = 0;
     537                 :          0 : }
     538                 :            : 
     539                 :          0 : void SelectionResult::AddInput(const OutputGroup& group)
     540                 :            : {
     541                 :            :     // As it can fail, combine inputs first
     542                 :          0 :     InsertInputs(group.m_outputs);
     543                 :          0 :     m_use_effective = !group.m_subtract_fee_outputs;
     544                 :            : 
     545                 :          0 :     m_weight += group.m_weight;
     546                 :          0 : }
     547                 :            : 
     548                 :          0 : void SelectionResult::AddInputs(const std::set<std::shared_ptr<COutput>>& inputs, bool subtract_fee_outputs)
     549                 :            : {
     550                 :            :     // As it can fail, combine inputs first
     551                 :          0 :     InsertInputs(inputs);
     552                 :          0 :     m_use_effective = !subtract_fee_outputs;
     553                 :            : 
     554                 :          0 :     m_weight += std::accumulate(inputs.cbegin(), inputs.cend(), 0, [](int sum, const auto& coin) {
     555                 :          0 :         return sum + std::max(coin->input_bytes, 0) * WITNESS_SCALE_FACTOR;
     556                 :            :     });
     557                 :          0 : }
     558                 :            : 
     559                 :          0 : void SelectionResult::Merge(const SelectionResult& other)
     560                 :            : {
     561                 :            :     // As it can fail, combine inputs first
     562                 :          0 :     InsertInputs(other.m_selected_inputs);
     563                 :            : 
     564                 :          0 :     m_target += other.m_target;
     565                 :          0 :     m_use_effective |= other.m_use_effective;
     566         [ #  # ]:          0 :     if (m_algo == SelectionAlgorithm::MANUAL) {
     567                 :          0 :         m_algo = other.m_algo;
     568                 :          0 :     }
     569                 :            : 
     570                 :          0 :     m_weight += other.m_weight;
     571                 :          0 : }
     572                 :            : 
     573                 :          0 : const std::set<std::shared_ptr<COutput>>& SelectionResult::GetInputSet() const
     574                 :            : {
     575                 :          0 :     return m_selected_inputs;
     576                 :            : }
     577                 :            : 
     578                 :          0 : std::vector<std::shared_ptr<COutput>> SelectionResult::GetShuffledInputVector() const
     579                 :            : {
     580         [ #  # ]:          0 :     std::vector<std::shared_ptr<COutput>> coins(m_selected_inputs.begin(), m_selected_inputs.end());
     581         [ #  # ]:          0 :     Shuffle(coins.begin(), coins.end(), FastRandomContext());
     582                 :          0 :     return coins;
     583         [ #  # ]:          0 : }
     584                 :            : 
     585                 :          0 : bool SelectionResult::operator<(SelectionResult other) const
     586                 :            : {
     587                 :          0 :     Assert(m_waste.has_value());
     588                 :          0 :     Assert(other.m_waste.has_value());
     589                 :            :     // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
     590   [ #  #  #  # ]:          0 :     return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
     591                 :            : }
     592                 :            : 
     593                 :          0 : std::string COutput::ToString() const
     594                 :            : {
     595   [ #  #  #  # ]:          0 :     return strprintf("COutput(%s, %d, %d) [%s]", outpoint.hash.ToString(), outpoint.n, depth, FormatMoney(txout.nValue));
     596                 :          0 : }
     597                 :            : 
     598                 :          0 : std::string GetAlgorithmName(const SelectionAlgorithm algo)
     599                 :            : {
     600   [ #  #  #  #  :          0 :     switch (algo)
                      # ]
     601                 :            :     {
     602         [ #  # ]:          0 :     case SelectionAlgorithm::BNB: return "bnb";
     603         [ #  # ]:          0 :     case SelectionAlgorithm::KNAPSACK: return "knapsack";
     604         [ #  # ]:          0 :     case SelectionAlgorithm::SRD: return "srd";
     605         [ #  # ]:          0 :     case SelectionAlgorithm::MANUAL: return "manual";
     606                 :            :     // No default case to allow for compiler to warn
     607                 :            :     }
     608                 :          0 :     assert(false);
     609                 :          0 : }
     610                 :            : 
     611                 :          0 : CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
     612                 :            : {
     613                 :            :     // change = SUM(inputs) - SUM(outputs) - fees
     614                 :            :     // 1) With SFFO we don't pay any fees
     615                 :            :     // 2) Otherwise we pay all the fees:
     616                 :            :     //  - input fees are covered by GetSelectedEffectiveValue()
     617                 :            :     //  - non_input_fee is included in m_target
     618                 :            :     //  - change_fee
     619         [ #  # ]:          0 :     const CAmount change = m_use_effective
     620                 :          0 :                            ? GetSelectedEffectiveValue() - m_target - change_fee
     621                 :          0 :                            : GetSelectedValue() - m_target;
     622                 :            : 
     623         [ #  # ]:          0 :     if (change < min_viable_change) {
     624                 :          0 :         return 0;
     625                 :            :     }
     626                 :            : 
     627                 :          0 :     return change;
     628                 :          0 : }
     629                 :            : 
     630                 :            : } // namespace wallet

Generated by: LCOV version 1.14