Building a wallet payment

751    }
752
753    // Deduct change weight because remaining Coin Selection algorithms can create change output
754    int change_outputs_weight = coin_selection_params.change_output_size * WITNESS_SCALE_FACTOR;
755    max_selection_weight -= change_outputs_weight;
756    if (max_selection_weight < 0 && results.empty()) {
757        return util::Error{_("Maximum transaction weight is too low, can not accommodate change output")};
758    }
759
760    // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here.
761    if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast, max_selection_weight)}) {
762        results.push_back(*knapsack_result);
763    } else append_error(std::move(knapsack_result));
764
765    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+)
766        if (auto cg_result{CoinGrinder(groups.positive_group, nTargetValue, coin_selection_params.m_min_change_target, max_selection_weight)}) {
767            cg_result->RecalculateWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
768            results.push_back(*cg_result);
769        } else {
770            append_error(std::move(cg_result));
771        }
772    }
773
774    if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.m_change_fee, coin_selection_params.rng_fast, max_selection_weight)}) {
775        results.push_back(*srd_result);
776    } else append_error(std::move(srd_result));
777
778    if (results.empty()) {
779        // No solution found, retrieve the first explicit error (if any).
780        // future: add 'severity level' to errors so the worst one can be retrieved instead of the first one.
781        return errors.empty() ? util::Error() : std::move(errors.front());
782    }
783
784    // If the chosen input set has unconfirmed inputs, check for synergies from overlapping ancestry
785    for (auto& result : results) {
786        std::vector<COutPoint> outpoints;
787        OutputSet coins = result.GetInputSet();
788        CAmount summed_bump_fees = 0;
789        for (auto& coin : coins) {
790            if (coin->depth > 0) continue; // Bump fees only exist for unconfirmed inputs
791            outpoints.push_back(coin->outpoint);
792            summed_bump_fees += coin->ancestor_bump_fees;
793        }
794        std::optional<CAmount> combined_bump_fee = chain.calculateCombinedBumpFee(outpoints, coin_selection_params.m_effective_feerate);
795        if (!combined_bump_fee.has_value()) {
796            return util::Error{_("Failed to calculate bump fees, because unconfirmed UTXOs depend on an enormous cluster of unconfirmed transactions.")};
797        }
798        CAmount bump_fee_overestimate = summed_bump_fees - combined_bump_fee.value();
799        // Avoid negative discount if mempool changed between the two bump fee snapshots.
800        if (bump_fee_overestimate > 0) {
801            result.SetBumpFeeDiscount(bump_fee_overestimate);
802        }
803        result.RecalculateWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
804    }
805
806    // Choose the result with the least waste
807    // If the waste is the same, choose the one which spends more inputs.
808    return *std::min_element(results.begin(), results.end());
809}
810
811util::Result<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const CoinsResult& pre_set_inputs,
812                                          const CAmount& nTargetValue, const CCoinControl& coin_control,
813                                          const CoinSelectionParams& coin_selection_params)
814{
815    // Deduct preset inputs amount from the search target
816    CAmount selection_target = nTargetValue - pre_set_inputs.GetAppropriateTotal(coin_selection_params.m_subtract_fee_outputs).value_or(0);
817
818    // Return if automatic coin selection is disabled, and we don't cover the selection target
819    if (!coin_control.m_allow_other_inputs && selection_target > 0) {
820        return util::Error{_("The preselected coins total amount does not cover the transaction target. "
821                             "Please allow other inputs to be automatically selected or include more coins manually")};
822    }
823
824    OutputSet preset_coin_set;
825    for (const auto& output: pre_set_inputs.All()) {
826        preset_coin_set.insert(std::make_shared<COutput>(output));
827    }
828
829    // Return if we can cover the target only with the preset inputs
830    if (selection_target <= 0) {
831        SelectionResult result(nTargetValue, SelectionAlgorithm::MANUAL);
832        result.AddInputs(preset_coin_set, coin_selection_params.m_subtract_fee_outputs);
833        result.RecalculateWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
834        return result;
835    }
836
837    // Return early if we cannot cover the target with the wallet's UTXO.
838    // We use the total effective value if we are not subtracting fee from outputs and 'available_coins' contains the data.
839    CAmount available_coins_total_amount = available_coins.GetAppropriateTotal(coin_selection_params.m_subtract_fee_outputs).value_or(0);
840    if (selection_target > available_coins_total_amount) {
841        return util::Error(); // Insufficient funds
842    }
843
844    // Start wallet Coin Selection procedure
845    auto op_selection_result = AutomaticCoinSelection(wallet, available_coins, selection_target, coin_selection_params);
846    if (!op_selection_result) return op_selection_result;
847
848    // If needed, add preset inputs to the automatic coin selection result
849    if (!pre_set_inputs.coins.empty()) {
850        auto preset_total = pre_set_inputs.GetAppropriateTotal(coin_selection_params.m_subtract_fee_outputs);
851        assert(preset_total.has_value());
852        SelectionResult preselected(preset_total.value(), SelectionAlgorithm::MANUAL);
853        preselected.AddInputs(preset_coin_set, coin_selection_params.m_subtract_fee_outputs);
854        op_selection_result->Merge(preselected);
855        op_selection_result->RecalculateWaste(coin_selection_params.min_viable_change,
856                                                coin_selection_params.m_cost_of_change,
857                                                coin_selection_params.m_change_fee);
858
859        // Verify we haven't exceeded the maximum allowed weight
860        int max_inputs_weight = coin_selection_params.m_max_tx_weight.value_or(MAX_STANDARD_TX_WEIGHT) - (coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR);
861        if (op_selection_result->GetWeight() > max_inputs_weight) {
862            return util::Error{_("The combination of the pre-selected inputs and the wallet automatic inputs selection exceeds the transaction maximum weight. "
863                                 "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")};
864        }
865    }
866    return op_selection_result;
867}
868
869util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, CoinsResult& available_coins, const CAmount& value_to_select, const CoinSelectionParams& coin_selection_params)
870{
871    // Try to enforce a mixture of cluster limits and ancestor/descendant limits on transactions we create by limiting
872    // the ancestors and the maximum cluster count of any UTXO we use. We use the ancestor/descendant limits, which are
873    // lower than the cluster limits, to avoid exceeding any ancestor/descendant limits of legacy nodes. This filter is safe
874    // because a transaction's ancestor or descendant count cannot be larger than its cluster count.
875    // TODO: these limits can be relaxed in the future, and we can replace the ancestor filter with a cluster equivalent.
876    unsigned int limit_ancestor_count = 0;
877    unsigned int limit_descendant_count = 0;
878    wallet.chain().getPackageLimits(limit_ancestor_count, limit_descendant_count);
879    const size_t max_ancestors = (size_t)std::max<int64_t>(1, limit_ancestor_count);
880    const size_t max_cluster_count = (size_t)std::max<int64_t>(1, limit_descendant_count);
881    const bool fRejectLongChains = gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS);
882
883    // Cases where we have 101+ outputs all pointing to the same destination may result in
884    // privacy leaks as they will potentially be deterministically sorted. We solve that by
885    // explicitly shuffling the outputs before processing
886    if (coin_selection_params.m_avoid_partial_spends && available_coins.Size() > OUTPUT_GROUP_MAX_ENTRIES) {
887        available_coins.Shuffle(coin_selection_params.rng_fast);
888    }
889
890    // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
891    // transaction at a target feerate. If an attempt fails, more attempts may be made using a more
892    // permissive CoinEligibilityFilter.
893    {
894        // Place coins eligibility filters on a scope increasing order.
895        std::vector<SelectionFilter> ordered_filters{
896                // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
897                // confirmations on outputs received from other wallets and only spend confirmed change.
898                {CoinEligibilityFilter(1, 6, 0), /*allow_mixed_output_types=*/false},
899                {CoinEligibilityFilter(1, 1, 0)},
900        };
901        // Fall back to using zero confirmation change (but with as few ancestors in the mempool as
902        // possible) if we cannot fund the transaction otherwise.
903        if (wallet.m_spend_zero_conf_change) {
904            ordered_filters.push_back({CoinEligibilityFilter(0, 1, 2)});
905            ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::min(size_t{4}, max_ancestors/3), std::min(size_t{4}, max_cluster_count/3))});
906            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors/2, max_cluster_count/2)});
907            // If partial groups are allowed, relax the requirement of spending OutputGroups (groups
908            // of UTXOs sent to the same address, which are obviously controlled by a single wallet)
909            // in their entirety.
910            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors-1, max_cluster_count-1, /*include_partial=*/true)});
911            // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
912            // received from other wallets.
913            if (coin_selection_params.m_include_unsafe_inputs) {
914                ordered_filters.push_back({CoinEligibilityFilter(/*conf_mine=*/0, /*conf_theirs=*/0, max_ancestors-1, max_cluster_count-1, /*include_partial=*/true)});
915            }
916            // Try with unlimited ancestors/clusters. The transaction will still need to meet
917            // local mempool policy (i.e. cluster limits) to be accepted to mempool and broadcasted, and
918            // limits of other nodes (e.g. ancestor/descendant limits) to propagate, but OutputGroups
919            // use heuristics that may overestimate.
920            if (!fRejectLongChains) {
921                ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(),
922                                                                   std::numeric_limits<uint64_t>::max(),
923                                                                   /*include_partial=*/true)});
924            }
925        }
926
927        // Group outputs and map them by coin eligibility filter
928        std::vector<OutputGroup> discarded_groups;
929        FilteredOutputGroups filtered_groups = GroupOutputs(wallet, available_coins, coin_selection_params, ordered_filters, discarded_groups);
930
931        // Check if we still have enough balance after applying filters (some coins might be discarded)
932        CAmount total_discarded = 0;
933        CAmount total_unconf_long_chain = 0;
934        for (const auto& group : discarded_groups) {
935            total_discarded += group.GetSelectionAmount();
936            if (group.m_ancestors >= max_ancestors || group.m_max_cluster_count >= max_cluster_count) total_unconf_long_chain += group.GetSelectionAmount();
937        }
938
939        if (CAmount total_amount = available_coins.GetTotalAmount() - total_discarded; total_amount < value_to_select) {
940            // Special case, too-long-mempool cluster.
941            if (total_amount + total_unconf_long_chain > value_to_select) {
942                return util::Error{_("Unconfirmed UTXOs are available, but spending them creates a chain of transactions that will be rejected by the mempool")};
943            }
944            return util::Error{}; // General "Insufficient Funds"
945        }
946
947        // Walk-through the filters until the solution gets found.
948        // If no solution is found, return the first detailed error (if any).
949        // future: add "error level" so the worst one can be picked instead.
950        std::vector<util::Result<SelectionResult>> res_detailed_errors;
951        CoinSelectionParams updated_selection_params = coin_selection_params;
952        for (const auto& select_filter : ordered_filters) {
953            auto it = filtered_groups.find(select_filter.filter);
954            if (it == filtered_groups.end()) continue;
955            if (updated_selection_params.m_version == TRUC_VERSION && (select_filter.filter.conf_mine == 0 || select_filter.filter.conf_theirs == 0)) {
956                if (updated_selection_params.m_max_tx_weight > (TRUC_CHILD_MAX_WEIGHT)) {
957                    updated_selection_params.m_max_tx_weight = TRUC_CHILD_MAX_WEIGHT;
958                }
959            }
960            if (auto res{AttemptSelection(wallet.chain(), value_to_select, it->second,
961                                          updated_selection_params, select_filter.allow_mixed_output_types)}) {
962                return res; // result found
963            } else {
964                // If any specific error message appears here, then something particularly wrong might have happened.
965                // Save the error and continue the selection process. So if no solutions gets found, we can return
966                // the detailed error to the upper layers.
967                if (HasErrorMsg(res)) res_detailed_errors.emplace_back(std::move(res));
968            }
969        }
970
971        // Return right away if we have a detailed error
972        if (!res_detailed_errors.empty()) return std::move(res_detailed_errors.front());
973
974
975        // General "Insufficient Funds"
976        return util::Error{};
977    }
978}
979
980static bool IsCurrentForAntiFeeSniping(interfaces::Chain& chain, const uint256& block_hash)
981{
982    if (chain.isInitialBlockDownload()) {
983        return false;
984    }
985    constexpr int64_t MAX_ANTI_FEE_SNIPING_TIP_AGE = 8 * 60 * 60; // in seconds
986    int64_t block_time;
987    CHECK_NONFATAL(chain.findBlock(block_hash, FoundBlock().time(block_time)));
988    if (block_time < (GetTime() - MAX_ANTI_FEE_SNIPING_TIP_AGE)) {
989        return false;
990    }
991    return true;
992}
993
994void DiscourageFeeSniping(CMutableTransaction& tx, FastRandomContext& rng_fast,
995                                 interfaces::Chain& chain, const uint256& block_hash, int block_height)
996{
997    // All inputs must be added by now
998    assert(!tx.vin.empty());
999    // Discourage fee sniping.
1000    //