How a wallet chooses which coins to spend

751            nTotalLower += group.GetSelectionAmount();
752        } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
753            lowest_larger = group;
754        }
755    }
756
757    if (nTotalLower == nTargetValue) {
758        for (const auto& group : applicable_groups) {
759            result.AddInput(group);
760        }
761        if (result.GetWeight() <= max_selection_weight) return result;
762        else max_weight_exceeded = true;
763
764        // Try something else
765        result.Clear();
766    }
767
768    if (nTotalLower < nTargetValue) {
769        if (!lowest_larger) {
770            if (max_weight_exceeded) return ErrorMaxWeightExceeded();
771            return util::Error();
772        }
773        result.AddInput(*lowest_larger);
774        return result;
775    }
776
777    // Solve subset sum by stochastic approximation
778    std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
779    std::vector<char> vfBest;
780    CAmount nBest;
781
782    ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest, max_selection_weight);
783    if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
784        ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest, max_selection_weight);
785    }
786
787    // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
788    //                                   or the next bigger coin is closer), return the bigger coin
789    if (lowest_larger &&
790        ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
791        result.AddInput(*lowest_larger);
792    } else {
793        for (unsigned int i = 0; i < applicable_groups.size(); i++) {
794            if (vfBest[i]) {
795                result.AddInput(applicable_groups[i]);
796            }
797        }
798
799        // If the result exceeds the maximum allowed size, return closest UTXO above the target
800        if (result.GetWeight() > max_selection_weight) {
801            // No coin above target, nothing to do.
802            if (!lowest_larger) return ErrorMaxWeightExceeded();
803
804            // Return closest UTXO above target
805            result.Clear();
806            result.AddInput(*lowest_larger);
807        }
808
809        if (util::log::ShouldDebugLog(BCLog::SELECTCOINS)) {
810            std::string log_message{"Coin selection best subset: "};
811            for (unsigned int i = 0; i < applicable_groups.size(); i++) {
812                if (vfBest[i]) {
813                    log_message += strprintf("%s ", FormatMoney(applicable_groups[i].m_value));
814                }
815            }
816            LogDebug(BCLog::SELECTCOINS, "%stotal %s\n", log_message, FormatMoney(nBest));
817        }
818    }
819    Assume(result.GetWeight() <= max_selection_weight);
820    return result;
821}
822
823/******************************************************************************
824
825 OutputGroup
826
827 ******************************************************************************/
828
829void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t cluster_count) {
830    m_outputs.push_back(output);
831    auto& coin = *m_outputs.back();
832
833    fee += coin.GetFee();
834
835    coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
836    long_term_fee += coin.long_term_fee;
837
838    effective_value += coin.GetEffectiveValue();
839
840    m_from_me &= coin.from_me;
841    m_value += coin.txout.nValue;
842    m_depth = std::min(m_depth, coin.depth);
843    // ancestors here express the number of ancestors the new coin will end up having, which is
844    // the sum, rather than the max; this will overestimate in the cases where multiple inputs
845    // have common ancestors
846    m_ancestors += ancestors;
847    // This is the maximum cluster count among all outputs. If these outputs are from distinct clusters but spent in the
848    // same transaction, their clusters will be merged, potentially exceeding the mempool's max cluster count.
849    m_max_cluster_count = std::max(m_max_cluster_count, cluster_count);
850
851    if (output->input_bytes > 0) {
852        m_weight += output->input_bytes * WITNESS_SCALE_FACTOR;
853    }
854}
855
856bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
857{
858    return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
859        && m_ancestors <= eligibility_filter.max_ancestors
860        && m_max_cluster_count <= eligibility_filter.max_cluster_count;
861}
862
863CAmount OutputGroup::GetSelectionAmount() const
864{
865    return m_subtract_fee_outputs ? m_value : effective_value;
866}
867
868void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool insert_positive, bool insert_mixed)
869{
870    if (group.m_outputs.empty()) return;
871
872    Groups& groups = groups_by_type[type];
873    if (insert_positive && group.GetSelectionAmount() > 0) {
874        groups.positive_group.emplace_back(group);
875        all_groups.positive_group.emplace_back(group);
876    }
877    if (insert_mixed) {
878        groups.mixed_group.emplace_back(group);
879        all_groups.mixed_group.emplace_back(group);
880    }
881}
882
883CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
884{
885    if (payment_value <= CHANGE_LOWER / 2) {
886        return change_fee + CHANGE_LOWER;
887    } else {
888        // random value between 50ksat and min (payment_value * 2, 1milsat)
889        const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
890        return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
891    }
892}
893
894void SelectionResult::SetBumpFeeDiscount(const CAmount discount)
895{
896    // Overlapping ancestry can only lower the fees, not increase them
897    assert (discount >= 0);
898    bump_fee_group_discount = discount;
899}
900
901void SelectionResult::RecalculateWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
902{
903    // This function should not be called with empty inputs as that would mean the selection failed
904    assert(!m_selected_inputs.empty());
905
906    // Always consider the cost of spending an input now vs in the future.
907    CAmount waste = 0;
908    for (const auto& coin_ptr : m_selected_inputs) {
909        const COutput& coin = *coin_ptr;
910        waste += coin.GetFee() - coin.long_term_fee;
911    }
912    // Bump fee of whole selection may diverge from sum of individual bump fees
913    waste -= bump_fee_group_discount;
914
915    if (GetChange(min_viable_change, change_fee)) {
916        // if we have a minimum viable amount after deducting fees, account for
917        // cost of creating and spending change
918        waste += change_cost;
919    } else {
920        // When we are not making change (GetChange(…) == 0), consider the excess we are throwing away to fees
921        CAmount selected_effective_value = m_use_effective ? GetSelectedEffectiveValue() : GetSelectedValue();
922        assert(selected_effective_value >= m_target);
923        waste += selected_effective_value - m_target;
924    }
925
926    m_waste = waste;
927}
928
929void SelectionResult::SetAlgoCompleted(bool algo_completed)
930{
931    m_algo_completed = algo_completed;
932}
933
934bool SelectionResult::GetAlgoCompleted() const
935{
936    return m_algo_completed;
937}
938
939void SelectionResult::SetSelectionsEvaluated(size_t attempts)
940{
941    m_selections_evaluated = attempts;
942}
943
944size_t SelectionResult::GetSelectionsEvaluated() const
945{
946    return m_selections_evaluated;
947}
948
949CAmount SelectionResult::GetWaste() const
950{
951    return *Assert(m_waste);
952}
953
954CAmount SelectionResult::GetSelectedValue() const
955{
956    return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->txout.nValue; });
957}
958
959CAmount SelectionResult::GetSelectedEffectiveValue() const
960{
961    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;
962}
963
964CAmount SelectionResult::GetTotalBumpFees() const
965{
966    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;
967}
968
969void SelectionResult::Clear()
970{
971    m_selected_inputs.clear();
972    m_waste.reset();
973    m_weight = 0;
974}
975
976void SelectionResult::AddInput(const OutputGroup& group)
977{
978    // As it can fail, combine inputs first
979    InsertInputs(group.m_outputs);
980    m_use_effective = !group.m_subtract_fee_outputs;
981
982    m_weight += group.m_weight;
983}
984
985void SelectionResult::AddInputs(const OutputSet& inputs, bool subtract_fee_outputs)
986{
987    // As it can fail, combine inputs first
988    InsertInputs(inputs);
989    m_use_effective = !subtract_fee_outputs;
990
991    m_weight += std::accumulate(inputs.cbegin(), inputs.cend(), 0, [](int sum, const auto& coin) {
992        return sum + std::max(coin->input_bytes, 0) * WITNESS_SCALE_FACTOR;
993    });
994}
995
996void SelectionResult::Merge(const SelectionResult& other)
997{
998    // As it can fail, combine inputs first
999    InsertInputs(other.m_selected_inputs);
1000