Merge bitcoin/bitcoin#26152: Bump unconfirmed ancestor transactions to target feerate

f18f9ef4d31c70e2d71ab90a24511692821418c3 Amend bumpfee for inputs with overlapping ancestry (Murch)
2e35e944dab09eff30952233f8dfc0b12c4553d5 Bump unconfirmed parent txs to target feerate (Murch)
3e3e05241128f68cf12f73ee06ff997395643885 coinselection: Move GetSelectionWaste into SelectionResult (Andrew Chow)
c57889da6650715f3e1153b6104bbdae15fcac90 [node] interface to get bump fees (glozow)
c24851be945b2a633ee44ed3c8a501eee5580b62 Make MiniMinerMempoolEntry fields private (Murch)
ac6030e4d8f7d578cd4a8593f41189efca548064 Remove unused imports (Murch)
d2f90c31ef3b8dee5a3e0804ecc62fa1cfec7cd5 Fix calculation of ancestor set feerates in test (Murch)
a1f7d986e0211e54e21a1d4a570e5f15294dca72 Match tx names to index in miniminer overlap test (Murch)

Pull request description:

  Includes some commits to address follow-ups from #27021: https://github.com/bitcoin/bitcoin/pull/27021#issuecomment-1554675156

  Reduces the effective value of unconfirmed UTXOs by the fees necessary to bump their ancestor transactions to the same feerate.

  While the individual UTXOs always account for their full ancestry before coin-selection, we can correct potential overestimates with a second pass where we establish the ancestry and bump fee for the whole input set collectively.

  Fixes #9645
  Fixes #9864
  Fixes #15553

ACKs for top commit:
  S3RK:
    ACK f18f9ef4d31c70e2d71ab90a24511692821418c3
  ismaelsadeeq:
    ACK f18f9ef4d31c70e2d71ab90a24511692821418c3
  achow101:
    ACK f18f9ef4d31c70e2d71ab90a24511692821418c3
  brunoerg:
    crACK f18f9ef4d31c70e2d71ab90a24511692821418c3
  t-bast:
    ACK https://github.com/bitcoin/bitcoin/pull/26152/commits/f18f9ef4d31c70e2d71ab90a24511692821418c3, I reviewed the latest changes and run e2e tests against eclair, everything looks good :+1:

Tree-SHA512: b65180c4243b1f9d13c311ada7a1c9f2f055d530d6c533b78c2068b50b8c29ac1321e89e85675b15515760d4f1b653ebd9da77b37c7be52d9bc565a3538f0aa6

6 files changed, 301 insertions, 134 deletions

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index d6b9b68e1f..391e120932 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -7,6 +7,7 @@
 #include <common/system.h>
 #include <consensus/amount.h>
 #include <consensus/consensus.h>
+#include <interfaces/chain.h>
 #include <logging.h>
 #include <policy/feerate.h>
 #include <util/check.h>
@@ -449,19 +450,19 @@ void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool in
     }
 }
 
-CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
+CAmount SelectionResult::GetSelectionWaste(CAmount change_cost, CAmount target, bool use_effective_value)
 {
     // This function should not be called with empty inputs as that would mean the selection failed
-    assert(!inputs.empty());
+    assert(!m_selected_inputs.empty());
 
     // Always consider the cost of spending an input now vs in the future.
     CAmount waste = 0;
-    CAmount selected_effective_value = 0;
-    for (const auto& coin_ptr : inputs) {
+    for (const auto& coin_ptr : m_selected_inputs) {
         const COutput& coin = *coin_ptr;
         waste += coin.GetFee() - coin.long_term_fee;
-        selected_effective_value += use_effective_value ? coin.GetEffectiveValue() : coin.txout.nValue;
     }
+    // Bump fee of whole selection may diverge from sum of individual bump fees
+    waste -= bump_fee_group_discount;
 
     if (change_cost) {
         // Consider the cost of making change and spending it in the future
@@ -470,6 +471,7 @@ CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmo
         waste += change_cost;
     } else {
         // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
+        CAmount selected_effective_value = use_effective_value ? GetSelectedEffectiveValue() : GetSelectedValue();
         assert(selected_effective_value >= target);
         waste += selected_effective_value - target;
     }
@@ -488,14 +490,22 @@ CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_f
     }
 }
 
+void SelectionResult::SetBumpFeeDiscount(const CAmount discount)
+{
+    // Overlapping ancestry can only lower the fees, not increase them
+    assert (discount >= 0);
+    bump_fee_group_discount = discount;
+}
+
+
 void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
 {
     const CAmount change = GetChange(min_viable_change, change_fee);
 
     if (change > 0) {
-        m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
+        m_waste = GetSelectionWaste(change_cost, m_target, m_use_effective);
     } else {
-        m_waste = GetSelectionWaste(m_selected_inputs, 0, m_target, m_use_effective);
+        m_waste = GetSelectionWaste(0, m_target, m_use_effective);
     }
 }
 
@@ -511,7 +521,12 @@ CAmount SelectionResult::GetSelectedValue() const
 
 CAmount SelectionResult::GetSelectedEffectiveValue() const
 {
-    return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin->GetEffectiveValue(); });
+    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;
+}
+
+CAmount SelectionResult::GetTotalBumpFees() const
+{
+    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;
 }
 
 void SelectionResult::Clear()
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index afd868fc89..20b2461c04 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -17,6 +17,7 @@
 
 #include <optional>
 
+
 namespace wallet {
 //! lower bound for randomly-chosen target change amount
 static constexpr CAmount CHANGE_LOWER{50000};
@@ -26,10 +27,10 @@ static constexpr CAmount CHANGE_UPPER{1000000};
 /** A UTXO under consideration for use in funding a new transaction. */
 struct COutput {
 private:
-    /** The output's value minus fees required to spend it.*/
+    /** The output's value minus fees required to spend it and bump its unconfirmed ancestors to the target feerate. */
     std::optional<CAmount> effective_value;
 
-    /** The fee required to spend this output at the transaction's target feerate. */
+    /** The fee required to spend this output at the transaction's target feerate and to bump its unconfirmed ancestors to the target feerate. */
     std::optional<CAmount> fee;
 
 public:
@@ -71,6 +72,9 @@ public:
     /** The fee required to spend this output at the consolidation feerate. */
     CAmount long_term_fee{0};
 
+    /** The fee necessary to bump this UTXO's ancestor transactions to the target feerate */
+    CAmount ancestor_bump_fees{0};
+
     COutput(const COutPoint& outpoint, const CTxOut& txout, int depth, int input_bytes, bool spendable, bool solvable, bool safe, int64_t time, bool from_me, const std::optional<CFeeRate> feerate = std::nullopt)
         : outpoint{outpoint},
           txout{txout},
@@ -83,6 +87,7 @@ public:
           from_me{from_me}
     {
         if (feerate) {
+            // base fee without considering potential unconfirmed ancestors
             fee = input_bytes < 0 ? 0 : feerate.value().GetFee(input_bytes);
             effective_value = txout.nValue - fee.value();
         }
@@ -104,6 +109,16 @@ public:
         return outpoint < rhs.outpoint;
     }
 
+    void ApplyBumpFee(CAmount bump_fee)
+    {
+        assert(bump_fee >= 0);
+        ancestor_bump_fees = bump_fee;
+        assert(fee);
+        *fee += bump_fee;
+        // Note: assert(effective_value - bump_fee == nValue - fee.value());
+        effective_value = txout.nValue - fee.value();
+    }
+
     CAmount GetFee() const
     {
         assert(fee.has_value());
@@ -275,26 +290,6 @@ struct OutputGroupTypeMap
 
 typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups;
 
-/** Compute the waste for this result given the cost of change
- * and the opportunity cost of spending these inputs now vs in the future.
- * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
- * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
- * where excess = selected_effective_value - target
- * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
- *
- * Note this function is separate from SelectionResult for the tests.
- *
- * @param[in] inputs The selected inputs
- * @param[in] change_cost The cost of creating change and spending it in the future.
- *                        Only used if there is change, in which case it must be positive.
- *                        Must be 0 if there is no change.
- * @param[in] target The amount targeted by the coin selection algorithm.
- * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false).
- * @return The waste
- */
-[[nodiscard]] CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
-
-
 /** Choose a random change target for each transaction to make it harder to fingerprint the Core
  * wallet based on the change output values of transactions it creates.
  * Change target covers at least change fees and adds a random value on top of it.
@@ -336,6 +331,8 @@ private:
     std::optional<CAmount> m_waste;
     /** Total weight of the selected inputs */
     int m_weight{0};
+    /** How much individual inputs overestimated the bump fees for the shared ancestry */
+    CAmount bump_fee_group_discount{0};
 
     template<typename T>
     void InsertInputs(const T& inputs)
@@ -348,6 +345,22 @@ private:
         }
     }
 
+    /** Compute the waste for this result given the cost of change
+     * and the opportunity cost of spending these inputs now vs in the future.
+     * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
+     * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
+     * where excess = selected_effective_value - target
+     * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
+     *
+     * @param[in] change_cost The cost of creating change and spending it in the future.
+     *                        Only used if there is change, in which case it must be positive.
+     *                        Must be 0 if there is no change.
+     * @param[in] target The amount targeted by the coin selection algorithm.
+     * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false).
+     * @return The waste
+     */
+    [[nodiscard]] CAmount GetSelectionWaste(CAmount change_cost, CAmount target, bool use_effective_value = true);
+
 public:
     explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
         : m_target(target), m_algo(algo) {}
@@ -359,11 +372,16 @@ public:
 
     [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
 
+    [[nodiscard]] CAmount GetTotalBumpFees() const;
+
     void Clear();
 
     void AddInput(const OutputGroup& group);
     void AddInputs(const std::set<std::shared_ptr<COutput>>& inputs, bool subtract_fee_outputs);
 
+    /** How much individual inputs overestimated the bump fees for shared ancestries */
+    void SetBumpFeeDiscount(const CAmount discount);
+
     /** Calculates and stores the waste for this selection via GetSelectionWaste */
     void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee);
     [[nodiscard]] CAmount GetWaste() const;
diff --git a/src/wallet/feebumper.cpp b/src/wallet/feebumper.cpp
index 3720d144eb..f99da926bc 100644
--- a/src/wallet/feebumper.cpp
+++ b/src/wallet/feebumper.cpp
@@ -63,7 +63,7 @@ static feebumper::Result PreconditionChecks(const CWallet& wallet, const CWallet
 }
 
 //! Check if the user provided a valid feeRate
-static feebumper::Result CheckFeeRate(const CWallet& wallet, const CFeeRate& newFeerate, const int64_t maxTxSize, CAmount old_fee, std::vector<bilingual_str>& errors)
+static feebumper::Result CheckFeeRate(const CWallet& wallet, const CMutableTransaction& mtx, const CFeeRate& newFeerate, const int64_t maxTxSize, CAmount old_fee, std::vector<bilingual_str>& errors)
 {
     // check that fee rate is higher than mempool's minimum fee
     // (no point in bumping fee if we know that the new tx won't be accepted to the mempool)
@@ -80,7 +80,17 @@ static feebumper::Result CheckFeeRate(const CWallet& wallet, const CFeeRate& new
         return feebumper::Result::WALLET_ERROR;
     }
 
-    CAmount new_total_fee = newFeerate.GetFee(maxTxSize);
+    std::vector<COutPoint> reused_inputs;
+    reused_inputs.reserve(mtx.vin.size());
+    for (const CTxIn& txin : mtx.vin) {
+        reused_inputs.push_back(txin.prevout);
+    }
+
+    std::optional<CAmount> combined_bump_fee = wallet.chain().CalculateCombinedBumpFee(reused_inputs, newFeerate);
+    if (!combined_bump_fee.has_value()) {
+        errors.push_back(strprintf(Untranslated("Failed to calculate bump fees, because unconfirmed UTXOs depend on enormous cluster of unconfirmed transactions.")));
+    }
+    CAmount new_total_fee = newFeerate.GetFee(maxTxSize) + combined_bump_fee.value();
 
     CFeeRate incrementalRelayFee = std::max(wallet.chain().relayIncrementalFee(), CFeeRate(WALLET_INCREMENTAL_RELAY_FEE));
 
@@ -283,7 +293,7 @@ Result CreateRateBumpTransaction(CWallet& wallet, const uint256& txid, const CCo
         }
         temp_mtx.vout = txouts;
         const int64_t maxTxSize{CalculateMaximumSignedTxSize(CTransaction(temp_mtx), &wallet, &new_coin_control).vsize};
-        Result res = CheckFeeRate(wallet, *new_coin_control.m_feerate, maxTxSize, old_fee, errors);
+        Result res = CheckFeeRate(wallet, temp_mtx, *new_coin_control.m_feerate, maxTxSize, old_fee, errors);
         if (res != Result::OK) {
             return res;
         }
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index fd7f279505..96c9a3dc16 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -259,6 +259,7 @@ util::Result<PreSelectedInputs> FetchSelectedInputs(const CWallet& wallet, const
 {
     PreSelectedInputs result;
     const bool can_grind_r = wallet.CanGrindR();
+    std::map<COutPoint, CAmount> map_of_bump_fees = wallet.chain().CalculateIndividualBumpFees(coin_control.ListSelected(), coin_selection_params.m_effective_feerate);
     for (const COutPoint& outpoint : coin_control.ListSelected()) {
         int input_bytes = -1;
         CTxOut txout;
@@ -294,6 +295,7 @@ util::Result<PreSelectedInputs> FetchSelectedInputs(const CWallet& wallet, const
 
         /* Set some defaults for depth, spendable, solvable, safe, time, and from_me as these don't matter for preset inputs since no selection is being done. */
         COutput output(outpoint, txout, /*depth=*/ 0, input_bytes, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, coin_selection_params.m_effective_feerate);
+        output.ApplyBumpFee(map_of_bump_fees.at(output.outpoint));
         result.Insert(output, coin_selection_params.m_subtract_fee_outputs);
     }
     return result;
@@ -314,6 +316,7 @@ CoinsResult AvailableCoins(const CWallet& wallet,
     const int max_depth = {coinControl ? coinControl->m_max_depth : DEFAULT_MAX_DEPTH};
     const bool only_safe = {coinControl ? !coinControl->m_include_unsafe_inputs : true};
     const bool can_grind_r = wallet.CanGrindR();
+    std::vector<COutPoint> outpoints;
 
     std::set<uint256> trusted_parents;
     for (const auto& entry : wallet.mapWallet)
@@ -433,6 +436,8 @@ CoinsResult AvailableCoins(const CWallet& wallet,
             result.Add(GetOutputType(type, is_from_p2sh),
                        COutput(outpoint, output, nDepth, input_bytes, spendable, solvable, safeTx, wtx.GetTxTime(), tx_from_me, feerate));
 
+            outpoints.push_back(outpoint);
+
             // Checks the sum amount of all UTXO's.
             if (params.min_sum_amount != MAX_MONEY) {
                 if (result.GetTotalAmount() >= params.min_sum_amount) {
@@ -447,6 +452,16 @@ CoinsResult AvailableCoins(const CWallet& wallet,
         }
     }
 
+    if (feerate.has_value()) {
+        std::map<COutPoint, CAmount> map_of_bump_fees = wallet.chain().CalculateIndividualBumpFees(outpoints, feerate.value());
+
+        for (auto& [_, outputs] : result.coins) {
+            for (auto& output : outputs) {
+                output.ApplyBumpFee(map_of_bump_fees.at(output.outpoint));
+            }
+        }
+    }
+
     return result;
 }
 
@@ -628,13 +643,13 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet,
 // Returns true if the result contains an error and the message is not empty
 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
 
-util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, OutputGroupTypeMap& groups,
+util::Result<SelectionResult> AttemptSelection(interfaces::Chain& chain, const CAmount& nTargetValue, OutputGroupTypeMap& groups,
                                const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types)
 {
     // Run coin selection on each OutputType and compute the Waste Metric
     std::vector<SelectionResult> results;
     for (auto& [type, group] : groups.groups_by_type) {
-        auto result{ChooseSelectionResult(nTargetValue, group, coin_selection_params)};
+        auto result{ChooseSelectionResult(chain, nTargetValue, group, coin_selection_params)};
         // If any specific error message appears here, then something particularly wrong happened.
         if (HasErrorMsg(result)) return result; // So let's return the specific error.
         // Append the favorable result.
@@ -648,14 +663,14 @@ util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, Outp
     // over all available coins, which would allow mixing.
     // If TypesCount() <= 1, there is nothing to mix.
     if (allow_mixed_output_types && groups.TypesCount() > 1) {
-        return ChooseSelectionResult(nTargetValue, groups.all_groups, coin_selection_params);
+        return ChooseSelectionResult(chain, nTargetValue, groups.all_groups, coin_selection_params);
     }
     // Either mixing is not allowed and we couldn't find a solution from any single OutputType, or mixing was allowed and we still couldn't
     // find a solution using all available coins
     return util::Error();
 };
 
-util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params)
+util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params)
 {
     // Vector of results. We will choose the best one based on waste.
     std::vector<SelectionResult> results;
@@ -680,12 +695,10 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue,
 
     // 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.
     if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast, max_inputs_weight)}) {
-        knapsack_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
         results.push_back(*knapsack_result);
     } else append_error(knapsack_result);
 
     if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.m_change_fee, coin_selection_params.rng_fast, max_inputs_weight)}) {
-        srd_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
         results.push_back(*srd_result);
     } else append_error(srd_result);
 
@@ -695,6 +708,27 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue,
         return errors.empty() ? util::Error() : errors.front();
     }
 
+    // If the chosen input set has unconfirmed inputs, check for synergies from overlapping ancestry
+    for (auto& result : results) {
+        std::vector<COutPoint> outpoints;
+        std::set<std::shared_ptr<COutput>> coins = result.GetInputSet();
+        CAmount summed_bump_fees = 0;
+        for (auto& coin : coins) {
+            if (coin->depth > 0) continue; // Bump fees only exist for unconfirmed inputs
+            outpoints.push_back(coin->outpoint);
+            summed_bump_fees += coin->ancestor_bump_fees;
+        }
+        std::optional<CAmount> combined_bump_fee = chain.CalculateCombinedBumpFee(outpoints, coin_selection_params.m_effective_feerate);
+        if (!combined_bump_fee.has_value()) {
+            return util::Error{_("Failed to calculate bump fees, because unconfirmed UTXOs depend on enormous cluster of unconfirmed transactions.")};
+        }
+        CAmount bump_fee_overestimate = summed_bump_fees - combined_bump_fee.value();
+        if (bump_fee_overestimate) {
+            result.SetBumpFeeDiscount(bump_fee_overestimate);
+        }
+        result.ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
+    }
+
     // Choose the result with the least waste
     // If the waste is the same, choose the one which spends more inputs.
     return *std::min_element(results.begin(), results.end());
@@ -824,7 +858,7 @@ util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, Coin
         for (const auto& select_filter : ordered_filters) {
             auto it = filtered_groups.find(select_filter.filter);
             if (it == filtered_groups.end()) continue;
-            if (auto res{AttemptSelection(value_to_select, it->second,
+            if (auto res{AttemptSelection(wallet.chain(), value_to_select, it->second,
                                           coin_selection_params, select_filter.allow_mixed_output_types)}) {
                 return res; // result found
             } else {
@@ -1120,7 +1154,7 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     if (nBytes == -1) {
         return util::Error{_("Missing solving data for estimating transaction size")};
     }
-    CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
+    CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes) + result.GetTotalBumpFees();
     const CAmount output_value = CalculateOutputValue(txNew);
     Assume(recipients_sum + change_amount == output_value);
     CAmount current_fee = result.GetSelectedValue() - output_value;
diff --git a/src/wallet/spend.h b/src/wallet/spend.h
index cc9ccf3011..407627b5f1 100644
--- a/src/wallet/spend.h
+++ b/src/wallet/spend.h
@@ -123,6 +123,7 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet,
  * the solution (according to the waste metric) will be chosen. If a valid input cannot be found from any
  * single OutputType, fallback to running `ChooseSelectionResult()` over all available coins.
  *
+ * param@[in]  chain                     The chain interface to get information on unconfirmed UTXOs bump fees
  * param@[in]  nTargetValue              The target value
  * param@[in]  groups                    The grouped outputs mapped by coin eligibility filters
  * param@[in]  coin_selection_params     Parameters for the coin selection
@@ -132,7 +133,7 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet,
  *                                                  or (2) an specific error message if there was something particularly wrong (e.g. a selection
  *                                                  result that surpassed the tx max weight size).
  */
-util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, OutputGroupTypeMap& groups,
+util::Result<SelectionResult> AttemptSelection(interfaces::Chain& chain, const CAmount& nTargetValue, OutputGroupTypeMap& groups,
                         const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types);
 
 /**
@@ -140,6 +141,7 @@ util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, Outp
  * Multiple coin selection algorithms will be run and the input set that produces the least waste
  * (according to the waste metric) will be chosen.
  *
+ * param@[in]  chain                     The chain interface to get information on unconfirmed UTXOs bump fees
  * param@[in]  nTargetValue              The target value
  * param@[in]  groups                    The struct containing the outputs grouped by script and divided by (1) positive only outputs and (2) all outputs (positive + negative).
  * param@[in]  coin_selection_params     Parameters for the coin selection
@@ -148,7 +150,7 @@ util::Result<SelectionResult> AttemptSelection(const CAmount& nTargetValue, Outp
  *                                                  or (2) an specific error message if there was something particularly wrong (e.g. a selection
  *                                                  result that surpassed the tx max weight size).
  */
-util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params);
+util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params);
 
 // User manually selected inputs that must be part of the transaction
 struct PreSelectedInputs
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index c8283f453a..9569210ba0 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -58,15 +58,17 @@ static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result)
     result.AddInput(group);
 }
 
-static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fee = 0, CAmount long_term_fee = 0)
+static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result, CAmount fee, CAmount long_term_fee)
 {
     CMutableTransaction tx;
     tx.vout.resize(nInput + 1);
     tx.vout[nInput].nValue = nValue;
     tx.nLockTime = nextLockTime++;        // so all transactions get different hashes
-    COutput coin(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ 148, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fee);
-    coin.long_term_fee = long_term_fee;
-    set.insert(std::make_shared<COutput>(coin));
+    std::shared_ptr<COutput> coin = std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ 148, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fee);
+    OutputGroup group;
+    group.Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0);
+    coin->long_term_fee = long_term_fee; // group.Insert() will modify long_term_fee, so we need to set it afterwards
+    result.AddInput(group);
 }
 
 static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmount& nValue, CFeeRate feerate = CFeeRate(0), int nAge = 6*24, bool fIsFromMe = false, int nInput =0, bool spendable = false, int custom_size = 0)
@@ -827,7 +829,6 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
 
 BOOST_AUTO_TEST_CASE(waste_test)
 {
-    CoinSet selection;
     const CAmount fee{100};
     const CAmount change_cost{125};
     const CAmount fee_diff{40};
@@ -835,92 +836,179 @@ BOOST_AUTO_TEST_CASE(waste_test)
     const CAmount target{2 * COIN};
     const CAmount excess{in_amt - fee * 2 - target};
 
-    // Waste with change is the change cost and difference between fee and long term fee
-    add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
-    const CAmount waste1 = GetSelectionWaste(selection, change_cost, target);
-    BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, waste1);
-    selection.clear();
-
-    // Waste without change is the excess and difference between fee and long term fee
-    add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
-    const CAmount waste_nochange1 = GetSelectionWaste(selection, 0, target);
-    BOOST_CHECK_EQUAL(fee_diff * 2 + excess, waste_nochange1);
-    selection.clear();
-
-    // Waste with change and fee == long term fee is just cost of change
-    add_coin(1 * COIN, 1, selection, fee, fee);
-    add_coin(2 * COIN, 2, selection, fee, fee);
-    BOOST_CHECK_EQUAL(change_cost, GetSelectionWaste(selection, change_cost, target));
-    selection.clear();
-
-    // Waste without change and fee == long term fee is just the excess
-    add_coin(1 * COIN, 1, selection, fee, fee);
-    add_coin(2 * COIN, 2, selection, fee, fee);
-    BOOST_CHECK_EQUAL(excess, GetSelectionWaste(selection, 0, target));
-    selection.clear();
-
-    // Waste will be greater when fee is greater, but long term fee is the same
-    add_coin(1 * COIN, 1, selection, fee * 2, fee - fee_diff);
-    add_coin(2 * COIN, 2, selection, fee * 2, fee - fee_diff);
-    const CAmount waste2 = GetSelectionWaste(selection, change_cost, target);
-    BOOST_CHECK_GT(waste2, waste1);
-    selection.clear();
-
-    // Waste with change is the change cost and difference between fee and long term fee
-    // With long term fee greater than fee, waste should be less than when long term fee is less than fee
-    add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
-    const CAmount waste3 = GetSelectionWaste(selection, change_cost, target);
-    BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, waste3);
-    BOOST_CHECK_LT(waste3, waste1);
-    selection.clear();
-
-    // Waste without change is the excess and difference between fee and long term fee
-    // With long term fee greater than fee, waste should be less than when long term fee is less than fee
-    add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
-    const CAmount waste_nochange2 = GetSelectionWaste(selection, 0, target);
-    BOOST_CHECK_EQUAL(fee_diff * -2 + excess, waste_nochange2);
-    BOOST_CHECK_LT(waste_nochange2, waste_nochange1);
-    selection.clear();
-
-    // No Waste when fee == long_term_fee, no change, and no excess
-    add_coin(1 * COIN, 1, selection, fee, fee);
-    add_coin(2 * COIN, 2, selection, fee, fee);
-    const CAmount exact_target{in_amt - fee * 2};
-    BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/0, exact_target));
-    selection.clear();
-
-    // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess
-    const CAmount new_change_cost{fee_diff * 2};
-    add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
-    BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, new_change_cost, target));
-    selection.clear();
-
-    // No Waste when (fee - long_term_fee) == (-excess), no change cost
-    const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
-    add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
-    BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/ 0, new_target));
-    selection.clear();
-
-    // Negative waste when the long term fee is greater than the current fee and the selected value == target
-    const CAmount exact_target1{3 * COIN - 2 * fee};
-    const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff))
-    add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
-    BOOST_CHECK_EQUAL(target_waste1, GetSelectionWaste(selection, /*change_cost=*/ 0, exact_target1));
-    selection.clear();
-
-    // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee))
-    const CAmount large_fee_diff{90};
-    const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
-    add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff);
-    add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff);
-    BOOST_CHECK_EQUAL(target_waste2, GetSelectionWaste(selection, change_cost, target));
+    // The following tests that the waste is calculated correctly in various scenarios.
+    // ComputeAndSetWaste will first determine the size of the change output. We don't really
+    // care about the change and just want to use the variant that always includes the change_cost,
+    // so min_viable_change and change_fee are set to 0 to ensure that.
+    {
+        // Waste with change is the change cost and difference between fee and long term fee
+        SelectionResult selection1{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection1, fee, fee - fee_diff);
+        add_coin(2 * COIN, 2, selection1, fee, fee - fee_diff);
+        selection1.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, selection1.GetWaste());
+
+        // Waste will be greater when fee is greater, but long term fee is the same
+        SelectionResult selection2{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection2, fee * 2, fee - fee_diff);
+        add_coin(2 * COIN, 2, selection2, fee * 2, fee - fee_diff);
+        selection2.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+        BOOST_CHECK_GT(selection2.GetWaste(), selection1.GetWaste());
+
+        // Waste with change is the change cost and difference between fee and long term fee
+        // With long term fee greater than fee, waste should be less than when long term fee is less than fee
+        SelectionResult selection3{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection3, fee, fee + fee_diff);
+        add_coin(2 * COIN, 2, selection3, fee, fee + fee_diff);
+        selection3.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, selection3.GetWaste());
+        BOOST_CHECK_LT(selection3.GetWaste(), selection1.GetWaste());
+    }
+
+    {
+        // Waste without change is the excess and difference between fee and long term fee
+        SelectionResult selection_nochange1{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection_nochange1, fee, fee - fee_diff);
+        add_coin(2 * COIN, 2, selection_nochange1, fee, fee - fee_diff);
+        selection_nochange1.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(fee_diff * 2 + excess, selection_nochange1.GetWaste());
+
+        // Waste without change is the excess and difference between fee and long term fee
+        // With long term fee greater than fee, waste should be less than when long term fee is less than fee
+        SelectionResult selection_nochange2{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection_nochange2, fee, fee + fee_diff);
+        add_coin(2 * COIN, 2, selection_nochange2, fee, fee + fee_diff);
+        selection_nochange2.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(fee_diff * -2 + excess, selection_nochange2.GetWaste());
+        BOOST_CHECK_LT(selection_nochange2.GetWaste(), selection_nochange1.GetWaste());
+    }
+
+    {
+        // Waste with change and fee == long term fee is just cost of change
+        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection, fee, fee);
+        add_coin(2 * COIN, 2, selection, fee, fee);
+        selection.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(change_cost, selection.GetWaste());
+    }
+
+    {
+        // Waste without change and fee == long term fee is just the excess
+        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection, fee, fee);
+        add_coin(2 * COIN, 2, selection, fee, fee);
+        selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(excess, selection.GetWaste());
+    }
+
+    {
+        // No Waste when fee == long_term_fee, no change, and no excess
+        const CAmount exact_target{in_amt - fee * 2};
+        SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection, fee, fee);
+        add_coin(2 * COIN, 2, selection, fee, fee);
+        selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(0, selection.GetWaste());
+    }
+
+    {
+        // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess
+        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+        const CAmount new_change_cost{fee_diff * 2};
+        add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+        selection.ComputeAndSetWaste(/*min_viable_change=*/0, new_change_cost, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(0, selection.GetWaste());
+    }
+
+    {
+        // No Waste when (fee - long_term_fee) == (-excess), no change cost
+        const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
+        SelectionResult selection{new_target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+        selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(0, selection.GetWaste());
+    }
+
+    {
+        // Negative waste when the long term fee is greater than the current fee and the selected value == target
+        const CAmount exact_target{3 * COIN - 2 * fee};
+        SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL};
+        const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff))
+        add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+        selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(target_waste1, selection.GetWaste());
+    }
+
+    {
+        // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee))
+        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+        const CAmount large_fee_diff{90};
+        const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
+        add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff);
+        add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff);
+        selection.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+        BOOST_CHECK_EQUAL(target_waste2, selection.GetWaste());
+    }
+}
+
+
+BOOST_AUTO_TEST_CASE(bump_fee_test)
+{
+    const CAmount fee{100};
+    const CAmount min_viable_change{200};
+    const CAmount change_cost{125};
+    const CAmount change_fee{35};
+    const CAmount fee_diff{40};
+    const CAmount target{2 * COIN};
+
+    {
+        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff);
+        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+        const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector();
+
+        for (size_t i = 0; i < inputs.size(); ++i) {
+            inputs[i]->ApplyBumpFee(20*(i+1));
+        }
+
+        selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee);
+        CAmount expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60;
+        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
+
+        selection.SetBumpFeeDiscount(30);
+        selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee);
+        expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60 - /*group_discount=*/30;
+        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
+    }
+
+    {
+        // Test with changeless transaction
+        //
+        // Bump fees and excess both contribute fully to the waste score,
+        // therefore, a bump fee group discount will not change the waste
+        // score as long as we do not create change in both instances.
+        CAmount changeless_target = 3 * COIN - 2 * fee - 100;
+        SelectionResult selection{changeless_target, SelectionAlgorithm::MANUAL};
+        add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff);
+        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+        const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector();
+
+        for (size_t i = 0; i < inputs.size(); ++i) {
+            inputs[i]->ApplyBumpFee(20*(i+1));
+        }
+
+        selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee);
+        CAmount expected_waste = fee_diff * -2 + /*bump_fees=*/60 + /*excess = 100 - bump_fees*/40;
+        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
+
+        selection.SetBumpFeeDiscount(30);
+        selection.ComputeAndSetWaste(min_viable_change, change_cost, change_fee);
+        expected_waste = fee_diff * -2 + /*bump_fees=*/60 - /*group_discount=*/30 + /*excess = 100 - bump_fees + group_discount*/70;
+        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
+    }
 }
 
 BOOST_AUTO_TEST_CASE(effective_value_test)