Amend bumpfee for inputs with overlapping ancestry

At the end of coin selection reduce the fees by the difference between
the individual bump fee estimates and the collective bump fee estimate.

8 files changed, 88 insertions, 21 deletions

diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
index 0e110a653a..249b76ee85 100644
--- a/src/bench/coin_selection.cpp
+++ b/src/bench/coin_selection.cpp
@@ -79,7 +79,7 @@ static void CoinSelection(benchmark::Bench& bench)
     };
     auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
     bench.run([&] {
-        auto result = AttemptSelection(1003 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
+        auto result = AttemptSelection(wallet.chain(), 1003 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
         assert(result);
         assert(result->GetSelectedValue() == 1003 * COIN);
         assert(result->GetInputSet().size() == 2);
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 804982695e..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>
@@ -456,12 +457,12 @@ CAmount SelectionResult::GetSelectionWaste(CAmount change_cost, CAmount target,
 
     // 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 : 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 SelectionResult::GetSelectionWaste(CAmount change_cost, CAmount target,
         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,6 +490,14 @@ 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);
@@ -511,13 +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; });
+    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 dd1a7bd66a..20b2461c04 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -331,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)
@@ -377,6 +379,9 @@ public:
     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 e72b412c09..f99da926bc 100644
--- a/src/wallet/feebumper.cpp
+++ b/src/wallet/feebumper.cpp
@@ -86,13 +86,11 @@ static feebumper::Result CheckFeeRate(const CWallet& wallet, const CMutableTrans
         reused_inputs.push_back(txin.prevout);
     }
 
-    std::map<COutPoint, CAmount> bump_fees = wallet.chain().CalculateIndividualBumpFees(reused_inputs, newFeerate);
-    CAmount total_bump_fees = 0;
-    for (auto& [_, bump_fee] : bump_fees) {
-        total_bump_fees += bump_fee;
+    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) + total_bump_fees;
+    CAmount new_total_fee = newFeerate.GetFee(maxTxSize) + combined_bump_fee.value();
 
     CFeeRate incrementalRelayFee = std::max(wallet.chain().relayIncrementalFee(), CFeeRate(WALLET_INCREMENTAL_RELAY_FEE));
 
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index dc2b669140..4606c2b808 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -544,13 +544,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.
@@ -564,14 +564,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;
@@ -596,12 +596,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);
 
@@ -611,6 +609,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());
@@ -740,7 +759,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 {
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 0f344b7c15..9569210ba0 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -977,6 +977,11 @@ BOOST_AUTO_TEST_CASE(bump_fee_test)
         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());
     }
 
     {
@@ -998,6 +1003,11 @@ BOOST_AUTO_TEST_CASE(bump_fee_test)
         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());
     }
 }
 
diff --git a/test/functional/wallet_spend_unconfirmed.py b/test/functional/wallet_spend_unconfirmed.py
index af99ed7f1c..bfcdeaeaa8 100755
--- a/test/functional/wallet_spend_unconfirmed.py
+++ b/test/functional/wallet_spend_unconfirmed.py
@@ -337,6 +337,28 @@ class UnconfirmedInputTest(BitcoinTestFramework):
 
         wallet.unloadwallet()
 
+    # Test that transaction spending two UTXOs with overlapping ancestry does not bump shared ancestors twice
+    def test_target_feerate_unconfirmed_low_overlapping_ancestry(self):
+        self.log.info("Start test where two UTXOs have overlapping ancestry")
+        wallet = self.setup_and_fund_wallet("overlapping_ancestry_wallet")
+
+        parent_txid = wallet.sendtoaddress(address=wallet.getnewaddress(), amount=1, fee_rate=1)
+        two_output_parent_tx = wallet.gettransaction(txid=parent_txid, verbose=True)
+
+        self.assert_undershoots_target(two_output_parent_tx)
+
+        # spend both outputs from parent transaction
+        ancestor_aware_txid = wallet.sendtoaddress(address=self.def_wallet.getnewaddress(), amount=1.5, fee_rate=self.target_fee_rate)
+        ancestor_aware_tx = wallet.gettransaction(txid=ancestor_aware_txid, verbose=True)
+        self.assert_spends_only_parents(ancestor_aware_tx, [parent_txid, parent_txid])
+
+        self.assert_beats_target(ancestor_aware_tx)
+        resulting_ancestry_fee_rate = self.calc_set_fee_rate([two_output_parent_tx, ancestor_aware_tx])
+        assert_greater_than_or_equal(resulting_ancestry_fee_rate, self.target_fee_rate)
+        assert_greater_than_or_equal(self.target_fee_rate*1.01, resulting_ancestry_fee_rate)
+
+        wallet.unloadwallet()
+
     # Test that new transaction ignores sibling transaction with low feerate
     def test_sibling_tx_gets_ignored(self):
         self.log.info("Start test where a low-fee sibling tx gets created and check that bumping ignores it")
@@ -472,6 +494,8 @@ class UnconfirmedInputTest(BitcoinTestFramework):
 
         self.test_rbf_bumping()
 
+        self.test_target_feerate_unconfirmed_low_overlapping_ancestry()
+
         self.test_sibling_tx_gets_ignored()
 
         self.test_sibling_tx_bumps_parent()