| 60 | static const size_t TOTAL_TRIES = 100000; |
| 61 | |
| 62 | bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees) |
| 63 | { |
| 64 | out_set.clear(); |
| 65 | CAmount curr_value = 0; |
| 66 | |
| 67 | std::vector<bool> curr_selection; // select the utxo at this index |
| 68 | curr_selection.reserve(utxo_pool.size()); |
| 69 | CAmount actual_target = not_input_fees + target_value; |
| 70 | |
| 71 | // Calculate curr_available_value |
| 72 | CAmount curr_available_value = 0; |
| 73 | for (const OutputGroup& utxo : utxo_pool) { |
| 74 | // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it |
| 75 | assert(utxo.effective_value > 0); |
| 76 | curr_available_value += utxo.effective_value; |
| 77 | } |
| 78 | if (curr_available_value < actual_target) { |
| 79 | return false; |
| 80 | } |
| 81 | |
| 82 | // Sort the utxo_pool |
| 83 | std::sort(utxo_pool.begin(), utxo_pool.end(), descending); |
| 84 | |
| 85 | CAmount curr_waste = 0; |
| 86 | std::vector<bool> best_selection; |
| 87 | CAmount best_waste = MAX_MONEY; |
| 88 | |
| 89 | // Depth First search loop for choosing the UTXOs |
| 90 | for (size_t i = 0; i < TOTAL_TRIES; ++i) { |
| 91 | // Conditions for starting a backtrack |
| 92 | bool backtrack = false; |
| 93 | if (curr_value + curr_available_value < actual_target || // Cannot possibly reach target with the amount remaining in the curr_available_value. |
| 94 | curr_value > actual_target + cost_of_change || // Selected value is out of range, go back and try other branch |
| 95 | (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 |
| 96 | backtrack = true; |
| 97 | } else if (curr_value >= actual_target) { // Selected value is within range |
| 98 | curr_waste += (curr_value - actual_target); // This is the excess value which is added to the waste for the below comparison |
| 99 | // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee. |
| 100 | // However we are not going to explore that because this optimization for the waste is only done when we have hit our target |
| 101 | // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to |
| 102 | // explore any more UTXOs to avoid burning money like that. |
| 103 | if (curr_waste <= best_waste) { |
| 104 | best_selection = curr_selection; |
| 105 | best_selection.resize(utxo_pool.size()); |
| 106 | best_waste = curr_waste; |
| 107 | } |
| 108 | curr_waste -= (curr_value - actual_target); // Remove the excess value as we will be selecting different coins now |
| 109 | backtrack = true; |
| 110 | } |
| 111 | |
| 112 | // Backtracking, moving backwards |
| 113 | if (backtrack) { |
| 114 | // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed. |
| 115 | while (!curr_selection.empty() && !curr_selection.back()) { |
| 116 | curr_selection.pop_back(); |
| 117 | curr_available_value += utxo_pool.at(curr_selection.size()).effective_value; |
| 118 | } |
| 119 | |