wallet: Add CoinGrinder coin selection algorithm #27877

272+        curr_selection.push_back(utxo_pool_index);
273+        next_op = operations::add;
274+    };
275+
276+    for (size_t curr_try = 0;;) {
277+        if (curr_try >= TOTAL_TRIES || next_op == operations::done) {

173@@ -174,6 +174,10 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
174                 curr_selection_weight += utxo.m_weight;
175             }
176         }
177+        if (curr_try >= TOTAL_TRIES - 1) {
178+            // On last attempt and didn’t break due to full traversal: solution is non-optimal
179+            result.SetAlgoCompleted(false);

32+            // Sort lower waste to front on tied effective_value
33+            if (a.long_term_fee < a.fee) {
34+                return a.m_weight < b.m_weight;
35+            } else {
36+                return a.m_weight > b.m_weight;
37+            }

584@@ -585,6 +585,13 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue,
585         results.push_back(*knapsack_result);
586     } else append_error(knapsack_result);
587 
588+    if (coin_selection_params.m_effective_feerate > CFeeRate{coin_selection_params.m_long_term_feerate.GetFee(3000)}) { // Minimize input set for feerates of at least 3×LTFRE (default: 30 ṩ/vB+)

269+        OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
270+        curr_amount += utxo.GetSelectionAmount();
271+        curr_weight += utxo.m_weight;
272+        curr_selection.push_back(utxo_pool_index);
273+        next_op = operations::add;
274+    };

256@@ -257,17 +257,21 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c
257     // Sort the utxo_pool
258     std::sort(utxo_pool.begin(), utxo_pool.end(), descending_effval_weight);
259     std::vector<CAmount> lookahead(utxo_pool.size());
260+    std::vector<int> min_tail_weight(utxo_pool.size());
261 
262     // Calculate lookahead and check that there are sufficient funds
263     CAmount total_available = 0;
264+    int min_group_weight = 2*max_weight;

207+ * • ADD:   010100 ⇒ 010110
208+ *          the UTXO at the index (here 5th) is additionally selected
209+ * • SHIFT: 010100 ⇒ 010010
210+ *          the 4th is deselected and the 5th is selected instead
211+ * • CUT:   010100 ⇒ 001000
212+ *          the third is deselected, the first is deselected and the second is selected

209+ * • SHIFT: 010100 ⇒ 010010
210+ *          the 4th is deselected and the 5th is selected instead
211+ * • CUT:   010100 ⇒ 001000
212+ *          the third is deselected, the first is deselected and the second is selected
213+ *
214+ * @param const std::vector<OutputGroup>& utxo_pool The UTXO groups that we are choosing from.

214+ * @param const std::vector<OutputGroup>& utxo_pool The UTXO groups that we are choosing from.
215+ *        These UTXO groups will be sorted in descending order by effective
216+ *        value, with lower weight preferred as a tie-breaker.
217+ * @param const CAmount& selection_target This is the minimum amount that we need for the transaction without
218+ *        considering change.
219+ * @param CAmount& change_target The minimum budget for creating a change output that we add to the selection_target.

193+ * searches for the minimum-weight input set producing a change output. The
194+ * algorithm is closely related to the Branch and Bound algorithm, but will
195+ * produce a transaction with a change output instead of aiming to create a
196+ * changeless transaction.
197+ *
198+ * This implementation produces a new input set in every loop iteration. It

196+ * changeless transaction.
197+ *
198+ * This implementation produces a new input set in every loop iteration. It
199+ * uses three operations to transition between input set candidates:
200+ *
201+ * • ADD: select the UTXO group at the current index into the input set

333+            curr_amount += utxo.GetSelectionAmount();
334+            curr_weight += utxo.m_weight;
335+            curr_selection.push_back(utxo_pool_index);
336+            next_op = operations::add;
337+
338+            // Depending on evaluation of current selection, ADD next, SHIFT latest, or CUT latest and shift prior

256+    CAmount total_available = 0;
257+    int min_group_weight = std::numeric_limits<int>::max();
258+    size_t i = utxo_pool.size();
259+    while (i > 0) {
260+        --i;
261+        lookahead.at(i) = total_available;

316+            if (utxo_pool_index > 0
317+                    && (curr_selection.empty() || curr_selection.back() != utxo_pool_index - 1)
318+                    && utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() == utxo_pool.at(utxo_pool_index).GetSelectionAmount()
319+                    && utxo_pool.at(utxo_pool_index - 1).fee == utxo_pool.at(utxo_pool_index).fee) {
320+                if (utxo_pool_index < utxo_pool.size() - 1) {
321+                    // Skip if previous UTXO is equivalent and unselected

345-                // Exhausted search space before running into attempt limit
346-                result.SetSelectionsEvaluated(curr_try);
347-                result.SetAlgoCompleted(true);
348-                break;
349+        while (!is_done && should_shift) {
350+            if (should_shift) {

336@@ -336,6 +337,9 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c
337                 best_selection_weight = curr_weight;
338                 best_selection_amount = curr_amount;
339             }
340+        } else if (!best_selection.empty() && curr_weight + min_tail_weight[curr_selection.back()] * std::ceil((selection_target + change_target - curr_amount) / utxo_pool[curr_selection.back()].GetSelectionAmount()) > best_selection_weight) {

296@@ -292,7 +297,10 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c
297         ++curr_try;
298 
299         // EVALUATE current selection, default to EXPLORING the inclusion branch further, else do exactly one SHIFT or CUT.
300-        if (curr_weight > max_weight) {
301+        if (curr_amount + lookahead[curr_selection.back()] < selection_target + change_target) {

296@@ -292,7 +297,10 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c
297         ++curr_try;
298 
299         // EVALUATE current selection, default to EXPLORING the inclusion branch further, else do exactly one SHIFT or CUT.

363+
364+            // After SHIFTing to an omission branch, the `next_utxo` might have the same value and same weight as the
365+            // UTXO we just omitted (i.e. it is a "clone"). If so, selecting `next_utxo` would produce an equivalent
366+            // selection as one we previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a
367+            // differing amount or weight.
368+            while (!should_shift && next_utxo > 0

239+     *
240+     * Each iteration of CoinGrinder starts by selecting the `next_utxo` and evaluating the current selection. We
241+     * use three state transactions to progress from the current selection to the next promising selection:
242+     *
243+     * - EXPLORE inclusion branch: We do not have sufficient funds yet and the lookahead promises sufficient funds to
244+     *                             reach the target. We continue with the direct successor as our `next_utxo` for the

295+        if (curr_weight > max_weight) {
296+            // max_weight exceeded: SHIFT
297+            max_tx_weight_exceeded = true;
298+            should_shift  = true;
299+        } else if (curr_amount >= selection_target + change_target) {
300+            // Potential solution, adding more weight cannot be better: SHIFT

24@@ -25,7 +25,7 @@ static util::Result<SelectionResult> ErrorMaxWeightExceeded()
25                          "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")};
26 }
27 
28-// Descending order comparator
29+// Sort by descending (effective) value prefer lower waste on tie

708@@ -709,6 +709,13 @@ util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, co
709         results.push_back(*knapsack_result);
710     } else append_error(knapsack_result);
711 
712+    if (coin_selection_params.m_effective_feerate > CFeeRate{3 * coin_selection_params.m_long_term_feerate}) { // Minimize input set for feerates of at least 3×LTFRE (default: 30 ṩ/vB+)
713+        if (auto cg_result{CoinGrinder(groups.positive_group, nTargetValue, coin_selection_params.m_min_change_target, max_inputs_weight)}) {

301+            should_shift  = true;
302+            if (curr_weight < best_selection_weight || curr_amount < best_selection_amount) {
303+                best_selection = curr_selection;
304+                best_selection_weight = curr_weight;
305+                best_selection_amount = curr_amount;
306+            }

206+    std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
207+
208+    // Check that there are sufficient funds
209+    CAmount total_available = 0;
210+    for (const OutputGroup& utxo : utxo_pool) {
211+        // Assert UTXOs with negative effective value have been filtered

210+    for (const OutputGroup& utxo : utxo_pool) {
211+        // Assert UTXOs with negative effective value have been filtered
212+        assert(utxo.GetSelectionAmount() > 0);
213+        total_available += utxo.GetSelectionAmount();
214+    }
215+    if (total_available < selection_target + change_target) {

338+            should_shift  = false;
339+        }
340+    }
341+
342+    if (best_selection.empty()) {
343+        return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();

215+    if (total_available < selection_target + change_target) {
216+        // Insufficient funds
217+        return util::Error();
218+    }
219+
220+    // CoinGrinder tracks selection via the indices of the currently selected UTXOs

236+     *
237+     * We can never find a new solution by deselecting a UTXO, because we then revisit a previously evaluated
238+     * selection. Therefore, we only need to check whether we found a new solution _after adding_ a new UTXO.
239+     *
240+     * Each iteration of CoinGrinder starts by selecting the `next_utxo` and evaluating the current selection. We
241+     * use three state transactions to progress from the current selection to the next promising selection:

249+     *                                 Evaluation: EXPLORE, next_utxo: 8
250+     *                                 Next Selection: {0, 5, 7, 8}
251+     *
252+     * - SHIFT to omission branch: Adding more UTXOs to the current selection cannot produce a solution that is better
253+     *                             than the current best, e.g. the max weight is exceeded or the current selection has
254+     *                             exceeded reached the target.

251+     *
252+     * - SHIFT to omission branch: Adding more UTXOs to the current selection cannot produce a solution that is better
253+     *                             than the current best, e.g. the max weight is exceeded or the current selection has
254+     *                             exceeded reached the target.
255+     *                             We designate our `next_utxo` the one after the tail of our current selection, then
256+     *                             deselected the tail of our current selection.

83+    std::vector<COutput> utxo_pool;
84+
85+    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
86+
87+    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
88+    CoinSelectionParams coin_params{fast_random_context};

169+    }
170+    size_t num_utxos = utxo_pool.size();
171+    assert(num_utxos <= max_utxos);
172+
173+    std::vector<OutputGroup> group_pos;
174+    GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);

173+    std::vector<OutputGroup> group_pos;
174+    GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
175+    size_t num_groups = group_pos.size();
176+    assert(num_groups <= num_utxos);
177+
178+    // Run coinselection algorithms

174+    GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
175+    size_t num_groups = group_pos.size();
176+    assert(num_groups <= num_utxos);
177+
178+    // Run coinselection algorithms
179+    CAmount change_target{CHANGE_LOWER + coin_params.m_change_fee}; // In order to ensure that it’s comparable to SRD, we must use the same change_target

175+    size_t num_groups = group_pos.size();
176+    assert(num_groups <= num_utxos);
177+
178+    // Run coinselection algorithms
179+    CAmount change_target{CHANGE_LOWER + coin_params.m_change_fee}; // In order to ensure that it’s comparable to SRD, we must use the same change_target
180+    auto result_cg = CoinGrinder(group_pos, target, change_target, MAX_STANDARD_TX_WEIGHT);

207+
208+    // Check that there are sufficient funds
209+    CAmount total_available = 0;
210+    for (const OutputGroup& utxo : utxo_pool) {
211+        // Assert UTXOs with negative effective value have been filtered
212+        assert(utxo.GetSelectionAmount() > 0);

338@@ -338,17 +339,33 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c
339             should_shift  = true;
340         }
341 
342-        if (should_shift) {
343+        while (!is_done && should_shift) {

313+                best_selection_weight = curr_weight;
314+                best_selection_amount = curr_amount;
315+            }
316+        }
317+
318+        if (curr_try >= TOTAL_TRIES) {

327+        }
328+
329+        if (should_cut) {
330+            // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can
331+            // find any solutions. Redirect to exploring Omission branch of the penultimate selected UTXO (i.e. deselect
332+            // last selected UTXO, then SHIFT)

337+
338+        if (should_shift) {
339+            // Set `next_utxo` to one after last selected, then deselect last selected UTXO
340+            if (curr_selection.empty()) {
341+                // Exhausted search space before running into attempt limit
342+                result.SetSelectionsEvaluated(curr_try);

708@@ -709,6 +709,13 @@ util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, co
709         results.push_back(*knapsack_result);
710     } else append_error(knapsack_result);
711 
712+    if (coin_selection_params.m_effective_feerate > CFeeRate{3 * coin_selection_params.m_long_term_feerate}) { // Minimize input set for feerates of at least 3×LTFRE (default: 30 ṩ/vB+)
713+        if (auto cg_result{CoinGrinder(groups.positive_group, nTargetValue, coin_selection_params.m_min_change_target, max_inputs_weight)}) {
714+            cg_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
715+            results.push_back(*cg_result);
716+        } else append_error(cg_result);

140+    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
141+
142+    FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
143+    CoinSelectionParams coin_params{fast_random_context};
144+    coin_params.m_subtract_fee_outputs = false;
145+    coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};

387+            }
388+            next_utxo = curr_selection.back() + 1;
389+            deselect_last();
390+            should_shift  = false;
391+
392+            // After SHIFTing to an omission branch, the `next_utxo` might have the same value and same weight as the

1195+            add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true, 148);
1196+            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68);
1197+            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68);
1198+            return available_coins;
1199+        });
1200+        expected_result.Clear();

1257+            for (int j = 0; j < 100; ++j) {
1258+                add_coin(available_coins, wallet, CAmount(5 * COIN), CFeeRate(5000), 144, false, 0, true, 400);
1259+            }
1260+            return available_coins;
1261+        });
1262+        expected_result.Clear();

213-    for (const OutputGroup& utxo : utxo_pool) {
214-        // Assert UTXOs with non-positive effective value have been filtered
215-        Assume(utxo.GetSelectionAmount() > 0);
216-        total_available += utxo.GetSelectionAmount();
217+    size_t i = utxo_pool.size();
218+    while (i > 0) {

1287+                // make a 100 unique coins only differing by one sat
1288+                add_coin(available_coins, wallet, CAmount(0.01 * COIN + j), CFeeRate(5000), 144, false, 0, true, 110);
1289+            }
1290+            return available_coins;
1291+        });
1292+        expected_result.Clear();

223+
224+    // Calculate lookahead values, min_tail_weights, and check that there are sufficient funds
225+    CAmount total_available = 0;
226+    int min_group_weight = std::numeric_limits<int>::max();
227+    for (size_t i = 0; i < utxo_pool.size(); ++i) {
228+        size_t index = utxo_pool.size() - 1 - i; // Loop over every element in reverse order

219+ *
220+ *     {} {A} {AB} {ABC} {ABCD} {ABC_} {AB_} {AB_D} {AB__} {A_} {A_C} {A_CD} {A_C_} {A__} {A__D} {A___} {_} {_B} {_BC}
221+ *     {_BCD} {_BC_} {_B_} {_B_D} {_B__} {__} {__C} {__CD} {__C} {___} {___D} {____}
222+ *
223+ * As powersets grow exponentially with the set size, walking the entire tree would quickly get computationally
224+ * infeasible with growing UTXO pools. We can represent the current state of the search with constant data thanks to

229+ * visiting {A} and exploring the inclusion branch {AB} and its descendants, the candidate input set in the omission
230+ * branch {A_} is equivalent to the parent {A} in effective value and weight. While CoinGrinder does need to visit the
231+ * descendants of the omission branch {A_}, it is unnecessary to evaluate the candidate input set in the omission branch
232+ * itself. By skipping evaluation of all nodes on an omission branch we reduce the visited nodes to 15:
233+ *
234+ *     {} {A} {AB} {ABC} {ABCD} {AB_D} {A_C} {A_CD} {A__D} {_B} {_BC} {_BCD} {_B_D} {__C} {__CD} {__C} {___D} {____}

254+ * If a candidate input set in a node has not selected enough to fund a transaction, we continue directly along the next
255+ * inclusion branch. We call this operation _EXPLORE_. (We go from one inclusion branch to the next inclusion branch:
256+ * {_B} ⇒ {_BC}.)
257+ * Further, any prefix that already has selected sufficient effective value to fund the transaction cannot be improved
258+ * by adding more UTXOs. If for example the candidate input set in {AB} is a valid solution, all potential descendant
259+ * solutions {ABC}, {ABCD}, and {AB_D} must have a higher weight.

286+ *                                                        /                           /             /             /
287+ * D=[4/2]                                           {A__D}                      {_B_D}        {__CD}        {___D}
288+ *
289+ *
290+ * We implement this tree walk in the following algorithm:
291+ * 1. Add `next_utxo`

288+ *
289+ *
290+ * We implement this tree walk in the following algorithm:
291+ * 1. Add `next_utxo`
292+ * 2. Evaluate candidate input set
293+ * 3. Optionally backtrack, and determine `next_utxo`

1110+    // 3) Select coins without surpassing the max weight (some coins surpasses the max allowed weight, some others not)
1111+    // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO
1112+    // 5) Test finding a solution in a UTXO pool with mixed weights
1113+    // 6) Test that the lightest solution among many clones is found
1114+
1115+    FastRandomContext rand;

329@@ -330,6 +330,8 @@ struct SelectionResult
330     bool m_use_effective{false};
331     /** The computed waste */
332     std::optional<CAmount> m_waste;
333+    /** False if algorithm was cut short by hitting limit of attempts and solution is non-optimal */

223+ * As powersets grow exponentially with the set size, walking the entire tree would quickly get computationally
224+ * infeasible with growing UTXO pools. We can represent the current state of the search with constant data thanks to
225+ * visiting the nodes in a deterministic order. We skip visiting as many nodes as possible by recognizing subtrees that
226+ * cannot yield any better solutions.
227+ * CoinGrinder is searching for the input set with lowest weight that can fund a transaction, so for example we can only
228+ * ever find a _better_ candidate input set in a node that adds a UTXO, but never in a node that skips a UTXO. After

147+    coin_params.m_min_change_target = ConsumeMoney(fuzzed_data_provider);
148+
149+    // Create some coins
150+    CAmount max_spendable{0};
151+    int next_locktime{0};
152+    unsigned max_output_groups = 16;

482+            // After SHIFTing to an omission branch, the `next_utxo` might have the same effective value as the UTXO we
483+            // just omitted. Since lower weight is our tiebreaker on UTXOs with equal effective value for sorting, if it
484+            // ties on the effective value, it _must_ have the same weight (i.e. be a "clone" of the prior UTXO) or a
485+            // higher weight. If so, selecting `next_utxo` would produce an equivalent or worse selection as one we
486+            // previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a differing amount.
487+            while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {

1267@@ -1267,6 +1268,32 @@ BOOST_AUTO_TEST_CASE(coin_grinder_tests)
1268         size_t expected_attempts = 42;
1269         BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1270     }
1271+
1272+    {
1273+        // #################################################################################################################

447@@ -448,6 +448,13 @@ util::Result<SelectionResult> CoinGrinder(std::vector<OutputGroup>& utxo_pool, c
448                 best_selection_weight = curr_weight;
449                 best_selection_amount = curr_amount;
450             }
451+        } else if (!best_selection.empty() && curr_weight + min_tail_weight[curr_tail] * ((total_target - curr_amount) / utxo_pool[curr_tail].GetSelectionAmount()) > best_selection_weight) {

261+ * shifts right by one: {AB} ⇒ {A_C}.)
262+ * When we reach a leaf node in the last level of the tree, shifting to the omission branch is not possible. Instead we
263+ * go to the omission branch of the node’s last ancestor on an inclusion branch: from {ABCD}, we go to {AB_D}. From
264+ * {AB_D}, we go to {A_C}. We refer to this operation as a _CUT_. (The ultimate element in
265+ * the input set is deselected, and the penultimate element is shifted right by one: {AB_D} ⇒ {A_C}.)
266+ * If a candidate input set in a node has not selected enough to fund a transaction, we continue directly along the next