How a wallet chooses which coins to spend

501        curr_amount += utxo.GetSelectionAmount();
502        curr_weight += utxo.m_weight;
503        curr_selection.push_back(next_utxo);
504        ++next_utxo;
505        ++curr_try;
506
507        // EVALUATE current selection: check for solutions and see whether we can CUT or SHIFT before EXPLORING further
508        auto curr_tail = curr_selection.back();
509        if (curr_amount + lookahead[curr_tail] < total_target) {
510            // Insufficient funds with lookahead: CUT
511            should_cut = true;
512        } else if (curr_weight > best_selection_weight) {
513            // best_selection_weight is initialized to max_selection_weight
514            if (curr_weight > max_selection_weight) max_tx_weight_exceeded = true;
515            // Worse weight than best solution. More UTXOs only increase weight:
516            // CUT if last selected group had minimal weight, else SHIFT
517            if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
518                should_cut = true;
519            } else {
520                should_shift  = true;
521            }
522        } else if (curr_amount >= total_target) {
523            // Success, adding more weight cannot be better: SHIFT
524            should_shift  = true;
525            if (curr_weight < best_selection_weight || (curr_weight == best_selection_weight && curr_amount < best_selection_amount)) {
526                // New lowest weight, or same weight with fewer funds tied up
527                best_selection = curr_selection;
528                best_selection_weight = curr_weight;
529                best_selection_amount = curr_amount;
530            }
531        } else if (!best_selection.empty() && curr_weight + int64_t{min_tail_weight[curr_tail]} * ((total_target - curr_amount + utxo_pool[curr_tail].GetSelectionAmount() - 1) / utxo_pool[curr_tail].GetSelectionAmount()) > best_selection_weight) {
532            // Compare minimal tail weight and last selected amount with the amount missing to gauge whether a better weight is still possible.
533            if (utxo_pool[curr_tail].m_weight <= min_tail_weight[curr_tail]) {
534                should_cut = true;
535            } else {
536                should_shift = true;
537            }
538        }
539
540        if (curr_try >= TOTAL_TRIES) {
541            // Solution is not guaranteed to be optimal if `curr_try` hit TOTAL_TRIES
542            result.SetAlgoCompleted(false);
543            break;
544        }
545
546        if (next_utxo == utxo_pool.size()) {
547            // Last added UTXO was end of UTXO pool, nothing left to add on inclusion or omission branch: CUT
548            should_cut = true;
549        }
550
551        if (should_cut) {
552            // Neither adding to the current selection nor exploring the omission branch of the last selected UTXO can
553            // find any solutions. Redirect to exploring the Omission branch of the penultimate selected UTXO (i.e.
554            // set `next_utxo` to one after the penultimate selected, then deselect the last two selected UTXOs)
555            deselect_last();
556            should_shift  = true;
557        }
558
559        while (should_shift) {
560            // Set `next_utxo` to one after last selected, then deselect last selected UTXO
561            if (curr_selection.empty()) {
562                // Exhausted search space before running into attempt limit
563                is_done = true;
564                result.SetAlgoCompleted(true);
565                break;
566            }
567            next_utxo = curr_selection.back() + 1;
568            deselect_last();
569            should_shift  = false;
570
571            // After SHIFTing to an omission branch, the `next_utxo` might have the same effective value as the UTXO we
572            // just omitted. Since lower weight is our tiebreaker on UTXOs with equal effective value for sorting, if it
573            // ties on the effective value, it _must_ have the same weight (i.e. be a "clone" of the prior UTXO) or a
574            // higher weight. If so, selecting `next_utxo` would produce an equivalent or worse selection as one we
575            // previously evaluated. In that case, increment `next_utxo` until we find a UTXO with a differing amount.
576            while (utxo_pool[next_utxo - 1].GetSelectionAmount() == utxo_pool[next_utxo].GetSelectionAmount()) {
577                if (next_utxo >= utxo_pool.size() - 1) {
578                    // Reached end of UTXO pool skipping clones: SHIFT instead
579                    should_shift = true;
580                    break;
581                }
582                // Skip clone: previous UTXO is equivalent and unselected
583                ++next_utxo;
584            }
585        }
586    }
587
588    result.SetSelectionsEvaluated(curr_try);
589
590    if (best_selection.empty()) {
591        return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
592    }
593
594    for (const size_t& i : best_selection) {
595        result.AddInput(utxo_pool[i]);
596    }
597
598    return result;
599}
600
601class MinOutputGroupComparator
602{
603public:
604    int operator() (const OutputGroup& group1, const OutputGroup& group2) const
605    {
606        return descending_effval_weight(group1, group2);
607    }
608};
609
610util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext& rng,
611                                             int max_selection_weight)
612{
613    SelectionResult result(target_value, SelectionAlgorithm::SRD);
614    std::priority_queue<OutputGroup, std::vector<OutputGroup>, MinOutputGroupComparator> heap;
615
616    // Include change for SRD as we want to avoid making really small change if the selection just
617    // barely meets the target. Just use the lower bound change target instead of the randomly
618    // generated one, since SRD will result in a random change amount anyway; avoid making the
619    // target needlessly large.
620    target_value += CHANGE_LOWER + change_fee;
621
622    std::vector<size_t> indexes;
623    indexes.resize(utxo_pool.size());
624    std::iota(indexes.begin(), indexes.end(), 0);
625    std::shuffle(indexes.begin(), indexes.end(), rng);
626
627    CAmount selected_eff_value = 0;
628    int weight = 0;
629    bool max_tx_weight_exceeded = false;
630    for (const size_t i : indexes) {
631        const OutputGroup& group = utxo_pool.at(i);
632        Assume(group.GetSelectionAmount() > 0);
633
634        // Add group to selection
635        heap.push(group);
636        selected_eff_value += group.GetSelectionAmount();
637        weight += group.m_weight;
638
639        // If the selection weight exceeds the maximum allowed size, remove the least valuable inputs until we
640        // are below max weight.
641        if (weight > max_selection_weight) {
642            max_tx_weight_exceeded = true; // mark it in case we don't find any useful result.
643            do {
644                const OutputGroup& to_remove_group = heap.top();
645                selected_eff_value -= to_remove_group.GetSelectionAmount();
646                weight -= to_remove_group.m_weight;
647                heap.pop();
648            } while (!heap.empty() && weight > max_selection_weight);
649        }
650
651        // Now check if we are above the target
652        if (selected_eff_value >= target_value) {
653            // Result found, add it.
654            while (!heap.empty()) {
655                result.AddInput(heap.top());
656                heap.pop();
657            }
658            return result;
659        }
660    }
661    return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();
662}
663
664/** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
665 * target amount; solve subset sum.
666 * @param[in]   groups          OutputGroups to choose from, sorted by value in descending order.
667 * @param[in]   nTotalLower     Total (effective) value of the UTXOs in groups.
668 * @param[in]   nTargetValue    Subset sum target, not including change.
669 * @param[out]  vfBest          Boolean vector representing the subset chosen that is closest to
670 *                              nTargetValue, with indices corresponding to groups. If the ith
671 *                              entry is true, that means the ith group in groups was selected.
672 * @param[out]  nBest           Total amount of subset chosen that is closest to nTargetValue.
673 * @param[in]   max_selection_weight  The maximum allowed weight for a selection result to be valid.
674 * @param[in]   iterations      Maximum number of tries.
675 */
676static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
677                                  const CAmount& nTotalLower, const CAmount& nTargetValue,
678                                  std::vector<char>& vfBest, CAmount& nBest, int max_selection_weight, int iterations = 1000)
679{
680    std::vector<char> vfIncluded;
681
682    // Worst case "best" approximation is just all of the groups.
683    vfBest.assign(groups.size(), true);
684    nBest = nTotalLower;
685
686    for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
687    {
688        vfIncluded.assign(groups.size(), false);
689        CAmount nTotal = 0;
690        int selected_coins_weight{0};
691        bool fReachedTarget = false;
692        for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
693        {
694            for (unsigned int i = 0; i < groups.size(); i++)
695            {
696                //The solver here uses a randomized algorithm,
697                //the randomness serves no real security purpose but is just
698                //needed to prevent degenerate behavior and it is important
699                //that the rng is fast. We do not use a constant random sequence,
700                //because there may be some privacy improvement by making
701                //the selection random.
702                if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
703                {
704                    nTotal += groups[i].GetSelectionAmount();
705                    selected_coins_weight += groups[i].m_weight;
706                    vfIncluded[i] = true;
707                    if (nTotal >= nTargetValue && selected_coins_weight <= max_selection_weight) {
708                        fReachedTarget = true;
709                        // If the total is between nTargetValue and nBest, it's our new best
710                        // approximation.
711                        if (nTotal < nBest)
712                        {
713                            nBest = nTotal;
714                            vfBest = vfIncluded;
715                        }
716                        nTotal -= groups[i].GetSelectionAmount();
717                        selected_coins_weight -= groups[i].m_weight;
718                        vfIncluded[i] = false;
719                    }
720                }
721            }
722        }
723    }
724}
725
726util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
727                                             CAmount change_target, FastRandomContext& rng, int max_selection_weight)
728{
729    SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
730
731    bool max_weight_exceeded{false};
732    // List of values less than target
733    std::optional<OutputGroup> lowest_larger;
734    // Groups with selection amount smaller than the target and any change we might produce.
735    // Don't include groups larger than this, because they will only cause us to overshoot.
736    std::vector<OutputGroup> applicable_groups;
737    CAmount nTotalLower = 0;
738
739    std::shuffle(groups.begin(), groups.end(), rng);
740
741    for (const OutputGroup& group : groups) {
742        if (group.m_weight > max_selection_weight) {
743            max_weight_exceeded = true;
744            continue;
745        }
746        if (group.GetSelectionAmount() == nTargetValue) {
747            result.AddInput(group);
748            return result;
749        } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
750            applicable_groups.push_back(group);