| 80 | static const size_t TOTAL_TRIES = 100000; |
| 81 | |
| 82 | std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change) |
| 83 | { |
| 84 | CAmountMap map_target{{ ::policyAsset, selection_target}}; |
| 85 | SelectionResult result(map_target); |
| 86 | CAmount curr_value = 0; |
| 87 | |
| 88 | std::vector<bool> curr_selection; // select the utxo at this index |
| 89 | curr_selection.reserve(utxo_pool.size()); |
| 90 | |
| 91 | // Calculate curr_available_value |
| 92 | CAmount curr_available_value = 0; |
| 93 | for (const OutputGroup& utxo : utxo_pool) { |
| 94 | // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it |
| 95 | assert(utxo.GetSelectionAmount() > 0); |
| 96 | curr_available_value += utxo.GetSelectionAmount(); |
| 97 | } |
| 98 | if (curr_available_value < selection_target) { |
| 99 | return std::nullopt; |
| 100 | } |
| 101 | |
| 102 | // Sort the utxo_pool |
| 103 | std::sort(utxo_pool.begin(), utxo_pool.end(), descending); |
| 104 | |
| 105 | CAmount curr_waste = 0; |
| 106 | std::vector<bool> best_selection; |
| 107 | CAmount best_waste = MAX_MONEY; |
| 108 | |
| 109 | // Depth First search loop for choosing the UTXOs |
| 110 | for (size_t i = 0; i < TOTAL_TRIES; ++i) { |
| 111 | // Conditions for starting a backtrack |
| 112 | bool backtrack = false; |
| 113 | if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value. |
| 114 | curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch |
| 115 | (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 |
| 116 | backtrack = true; |
| 117 | } else if (curr_value >= selection_target) { // Selected value is within range |
| 118 | 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 | if (curr_waste <= best_waste) { |
| 124 | best_selection = curr_selection; |
| 125 | best_selection.resize(utxo_pool.size()); |
| 126 | best_waste = curr_waste; |
| 127 | if (best_waste == 0) { |
| 128 | break; |
| 129 | } |
| 130 | } |
| 131 | curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now |
| 132 | backtrack = true; |
| 133 | } |
| 134 | |
| 135 | // Backtracking, moving backwards |
| 136 | if (backtrack) { |
| 137 | // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed. |
| 138 | while (!curr_selection.empty() && !curr_selection.back()) { |
| 139 | curr_selection.pop_back(); |