Merge bitcoin/bitcoin#26560: wallet: bugfix, invalid CoinsResult cached total amount

7362f8e5e2497bc1ef27bfa871fc6dd306dd33c3 refactor: make CoinsResult total amounts members private (furszy)
3282fad59908da328f8323e1213344fe58ccf69e wallet: add assert to SelectionResult::Merge for safety (S3RK)
c4e3b7d6a154e82cdb902fd7bcb7b725aebde5ea wallet: SelectCoins, return early if wallet's UTXOs cannot cover the target (furszy)
cac2725fd0f5baeb741dfe079a87332784c2adc7 test: bugfix, coinselector_test, use 'CoinsResult::Erase/Add' instead of direct member access (furszy)
cf793846978a8783c23b66ba6b4f3f30e83ff3eb test: Coin Selection, duplicated preset inputs selection (furszy)
341ba7ffd8cdb56b4cde1f251768c3d2c2a9b4e9 test: wallet, coverage for CoinsResult::Erase function (furszy)
f930aefff9690a1e830d897d0a8c53f4219ae4a8 wallet: bugfix, 'CoinsResult::Erase' is erasing only one output of the set (furszy)

Pull request description:

  This comes with #26559.

  Solving few bugs inside the wallet's transaction creation
  process and adding test coverage for them.
  Plus, making use of the `CoinsResult::total_amount` cached value
  inside the Coin Selection process to return early if we don't have
  enough funds to cover the target amount.

  ### Bugs

  1) The `CoinsResult::Erase` method removes only one
  output from the available coins vector (there is a [loop break](https://github.com/bitcoin/bitcoin/blob/c1061be14a515b0ed4f4d646fcd0378c62e6ded3/src/wallet/spend.cpp#L112)
  that should have never been there) and not all the preset inputs.

     Which on master is not a problem, because since [#25685](https://github.com/bitcoin/bitcoin/pull/25685)
     we are no longer using the method. But, it's a bug on v24
     (check [#26559](https://github.com/bitcoin/bitcoin/pull/26559)).

     This method it's being fixed and not removed because I'm later using it to solve
     another bug inside this PR.

  2) As we update the total cached amount of the `CoinsResult` object inside
     `AvailableCoins` and we don't use such function inside the coin selection
     tests (we manually load up the `CoinsResult` object), there is a discrepancy
     between the outputs that we add/erase and the total amount cached value.

  ### Improvements

  * This makes use of the `CoinsResult` total amount field to early return
    with an "Insufficient funds" error inside Coin Selection if the tx target
    amount is greater than the sum of all the wallet available coins plus the
    preset inputs amounts (we don't need to perform the entire coin selection
    process if we already know that there aren't enough funds inside our wallet).

  ### Test Coverage

  1) Adds test coverage for the duplicated preset input selection bug that we have in v24.
    Where the wallet invalidly selects the preset inputs twice during the Coin Selection
    process. Which ends up with a "good" Coin Selection result that does not cover the
    total tx target amount. Which, alone, crashes the wallet due an insane fee.
    But.. to make it worst, adding the subtract fee from output functionality
    to this mix ends up with the wallet by-passing the "insane" fee assertion,
    decreasing the output amount to fulfill the insane fee, and.. sadly,
    broadcasting the tx to the network.

  2) Adds test coverage for the `CoinsResult::Erase` method.

  ------------------------------------

  TO DO:
  * [ ] Update [#26559 ](https://github.com/bitcoin/bitcoin/pull/26559) description.

ACKs for top commit:
  achow101:
    ACK 7362f8e5e2497bc1ef27bfa871fc6dd306dd33c3
  glozow:
    ACK 7362f8e5e2497bc1ef27bfa871fc6dd306dd33c3, I assume there will be a followup PR to add coin selection sanity checks and we can discuss the best way to do that there.
  josibake:
    ACK [7362f8e](https://github.com/bitcoin/bitcoin/pull/26560/commits/7362f8e5e2497bc1ef27bfa871fc6dd306dd33c3)

Tree-SHA512: 37a6828ea10d8d36c8d5873ceede7c8bef72ae4c34bef21721fa9dad83ad6dba93711c3170a26ab6e05bdbc267bb17433da08ccb83b82956d05fb16090328cba

6 files changed, 136 insertions, 18 deletions

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index a8be6cd83a..b889d31928 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -452,12 +452,16 @@ void SelectionResult::AddInputs(const std::set<COutput>& inputs, bool subtract_f
 
 void SelectionResult::Merge(const SelectionResult& other)
 {
+    // Obtain the expected selected inputs count after the merge (for now, duplicates are not allowed)
+    const size_t expected_count = m_selected_inputs.size() + other.m_selected_inputs.size();
+
     m_target += other.m_target;
     m_use_effective |= other.m_use_effective;
     if (m_algo == SelectionAlgorithm::MANUAL) {
         m_algo = other.m_algo;
     }
     util::insert(m_selected_inputs, other.m_selected_inputs);
+    assert(m_selected_inputs.size() == expected_count);
 }
 
 const std::set<COutput>& SelectionResult::GetInputSet() const
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index b23dd10867..2ab4061a9b 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -110,6 +110,8 @@ public:
         assert(effective_value.has_value());
         return effective_value.value();
     }
+
+    bool HasEffectiveValue() const { return effective_value.has_value(); }
 };
 
 /** Parameters for one iteration of Coin Selection. */
@@ -314,6 +316,12 @@ public:
     void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee);
     [[nodiscard]] CAmount GetWaste() const;
 
+    /**
+     * Combines the @param[in] other selection result into 'this' selection result.
+     *
+     * Important note:
+     * There must be no shared 'COutput' among the two selection results being combined.
+     */
     void Merge(const SelectionResult& other);
 
     /** Get m_selected_inputs */
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 8c0d56a1cb..52d10b74b5 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -102,15 +102,19 @@ void CoinsResult::Clear() {
     coins.clear();
 }
 
-void CoinsResult::Erase(std::set<COutPoint>& preset_coins)
+void CoinsResult::Erase(const std::unordered_set<COutPoint, SaltedOutpointHasher>& coins_to_remove)
 {
-    for (auto& it : coins) {
-        auto& vec = it.second;
-        auto i = std::find_if(vec.begin(), vec.end(), [&](const COutput &c) { return preset_coins.count(c.outpoint);});
-        if (i != vec.end()) {
-            vec.erase(i);
-            break;
-        }
+    for (auto& [type, vec] : coins) {
+        auto remove_it = std::remove_if(vec.begin(), vec.end(), [&](const COutput& coin) {
+            // remove it if it's on the set
+            if (coins_to_remove.count(coin.outpoint) == 0) return false;
+
+            // update cached amounts
+            total_amount -= coin.txout.nValue;
+            if (coin.HasEffectiveValue()) total_effective_amount = *total_effective_amount - coin.GetEffectiveValue();
+            return true;
+        });
+        vec.erase(remove_it, vec.end());
     }
 }
 
@@ -124,6 +128,11 @@ void CoinsResult::Shuffle(FastRandomContext& rng_fast)
 void CoinsResult::Add(OutputType type, const COutput& out)
 {
     coins[type].emplace_back(out);
+    total_amount += out.txout.nValue;
+    if (out.HasEffectiveValue()) {
+        total_effective_amount = total_effective_amount.has_value() ?
+                *total_effective_amount + out.GetEffectiveValue() : out.GetEffectiveValue();
+    }
 }
 
 static OutputType GetOutputType(TxoutType type, bool is_from_p2sh)
@@ -321,11 +330,9 @@ 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));
 
-            // Cache total amount as we go
-            result.total_amount += output.nValue;
             // Checks the sum amount of all UTXO's.
             if (params.min_sum_amount != MAX_MONEY) {
-                if (result.total_amount >= params.min_sum_amount) {
+                if (result.GetTotalAmount() >= params.min_sum_amount) {
                     return result;
                 }
             }
@@ -349,7 +356,7 @@ CoinsResult AvailableCoinsListUnspent(const CWallet& wallet, const CCoinControl*
 CAmount GetAvailableBalance(const CWallet& wallet, const CCoinControl* coinControl)
 {
     LOCK(wallet.cs_wallet);
-    return AvailableCoins(wallet, coinControl).total_amount;
+    return AvailableCoins(wallet, coinControl).GetTotalAmount();
 }
 
 const CTxOut& FindNonChangeParentOutput(const CWallet& wallet, const CTransaction& tx, int output)
@@ -577,6 +584,14 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
         return result;
     }
 
+    // Return early if we cannot cover the target with the wallet's UTXO.
+    // We use the total effective value if we are not subtracting fee from outputs and 'available_coins' contains the data.
+    CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.GetTotalAmount() :
+            (available_coins.GetEffectiveTotalAmount().has_value() ? *available_coins.GetEffectiveTotalAmount() : 0);
+    if (selection_target > available_coins_total_amount) {
+        return std::nullopt; // Insufficient funds
+    }
+
     // Start wallet Coin Selection procedure
     auto op_selection_result = AutomaticCoinSelection(wallet, available_coins, selection_target, coin_control, coin_selection_params);
     if (!op_selection_result) return op_selection_result;
diff --git a/src/wallet/spend.h b/src/wallet/spend.h
index ba2c6638c8..2b861c2361 100644
--- a/src/wallet/spend.h
+++ b/src/wallet/spend.h
@@ -47,12 +47,18 @@ struct CoinsResult {
      * i.e., methods can work with individual OutputType vectors or on the entire object */
     size_t Size() const;
     void Clear();
-    void Erase(std::set<COutPoint>& preset_coins);
+    void Erase(const std::unordered_set<COutPoint, SaltedOutpointHasher>& coins_to_remove);
     void Shuffle(FastRandomContext& rng_fast);
     void Add(OutputType type, const COutput& out);
 
-    /** Sum of all available coins */
+    CAmount GetTotalAmount() { return total_amount; }
+    std::optional<CAmount> GetEffectiveTotalAmount() {return total_effective_amount; }
+
+private:
+    /** Sum of all available coins raw value */
     CAmount total_amount{0};
+    /** Sum of all available coins effective value (each output value minus fees required to spend it) */
+    std::optional<CAmount> total_effective_amount{0};
 };
 
 struct CoinFilterParams {
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index f9c8c8ee9d..c764264cd7 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -83,7 +83,7 @@ static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmoun
     assert(ret.second);
     CWalletTx& wtx = (*ret.first).second;
     const auto& txout = wtx.tx->vout.at(nInput);
-    available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx.GetHash(), nInput), txout, nAge, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate);
+    available_coins.Add(OutputType::BECH32, {COutPoint(wtx.GetHash(), nInput), txout, nAge, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate});
 }
 
 /** Check if SelectionResult a is equivalent to SelectionResult b.
@@ -342,7 +342,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         coin_control.Select(select_coin.outpoint);
         PreSelectedInputs selected_input;
         selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
-        available_coins.coins[OutputType::BECH32].erase(available_coins.coins[OutputType::BECH32].begin());
+        available_coins.Erase({available_coins.coins[OutputType::BECH32].begin()->outpoint});
         coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
         const auto result10 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(result10);
@@ -402,7 +402,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         coin_control.Select(select_coin.outpoint);
         PreSelectedInputs selected_input;
         selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
-        available_coins.coins[OutputType::BECH32].erase(++available_coins.coins[OutputType::BECH32].begin());
+        available_coins.Erase({(++available_coins.coins[OutputType::BECH32].begin())->outpoint});
         const auto result13 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);
         BOOST_CHECK(EquivalentResult(expected_result, *result13));
     }
@@ -974,11 +974,51 @@ BOOST_AUTO_TEST_CASE(SelectCoins_effective_value_test)
     cc.SelectExternal(output.outpoint, output.txout);
 
     const auto preset_inputs = *Assert(FetchSelectedInputs(*wallet, cc, cs_params));
-    available_coins.coins[OutputType::BECH32].erase(available_coins.coins[OutputType::BECH32].begin());
+    available_coins.Erase({available_coins.coins[OutputType::BECH32].begin()->outpoint});
 
     const auto result = SelectCoins(*wallet, available_coins, preset_inputs, target, cc, cs_params);
     BOOST_CHECK(!result);
 }
 
+BOOST_FIXTURE_TEST_CASE(wallet_coinsresult_test, BasicTestingSetup)
+{
+    // Test case to verify CoinsResult object sanity.
+    CoinsResult available_coins;
+    {
+        std::unique_ptr<CWallet> dummyWallet = std::make_unique<CWallet>(m_node.chain.get(), "dummy", m_args, CreateMockWalletDatabase());
+        BOOST_CHECK_EQUAL(dummyWallet->LoadWallet(), DBErrors::LOAD_OK);
+        LOCK(dummyWallet->cs_wallet);
+        dummyWallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
+        dummyWallet->SetupDescriptorScriptPubKeyMans();
+
+        // Add some coins to 'available_coins'
+        for (int i=0; i<10; i++) {
+            add_coin(available_coins, *dummyWallet, 1 * COIN);
+        }
+    }
+
+    {
+        // First test case, check that 'CoinsResult::Erase' function works as expected.
+        // By trying to erase two elements from the 'available_coins' object.
+        std::unordered_set<COutPoint, SaltedOutpointHasher> outs_to_remove;
+        const auto& coins = available_coins.All();
+        for (int i = 0; i < 2; i++) {
+            outs_to_remove.emplace(coins[i].outpoint);
+        }
+        available_coins.Erase(outs_to_remove);
+
+        // Check that the elements were actually removed.
+        const auto& updated_coins = available_coins.All();
+        for (const auto& out: outs_to_remove) {
+            auto it = std::find_if(updated_coins.begin(), updated_coins.end(), [&out](const COutput &coin) {
+                return coin.outpoint == out;
+            });
+            BOOST_CHECK(it == updated_coins.end());
+        }
+        // And verify that no extra element were removed
+        BOOST_CHECK_EQUAL(available_coins.Size(), 8);
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 } // namespace wallet
diff --git a/src/wallet/test/spend_tests.cpp b/src/wallet/test/spend_tests.cpp
index a75b014870..81a8883f85 100644
--- a/src/wallet/test/spend_tests.cpp
+++ b/src/wallet/test/spend_tests.cpp
@@ -112,5 +112,50 @@ BOOST_FIXTURE_TEST_CASE(FillInputToWeightTest, BasicTestingSetup)
     // Note: We don't test the next boundary because of memory allocation constraints.
 }
 
+BOOST_FIXTURE_TEST_CASE(wallet_duplicated_preset_inputs_test, TestChain100Setup)
+{
+    // Verify that the wallet's Coin Selection process does not include pre-selected inputs twice in a transaction.
+
+    // Add 4 spendable UTXO, 50 BTC each, to the wallet (total balance 200 BTC)
+    for (int i = 0; i < 4; i++) CreateAndProcessBlock({}, GetScriptForRawPubKey(coinbaseKey.GetPubKey()));
+    auto wallet = CreateSyncedWallet(*m_node.chain, WITH_LOCK(Assert(m_node.chainman)->GetMutex(), return m_node.chainman->ActiveChain()), m_args, coinbaseKey);
+
+    LOCK(wallet->cs_wallet);
+    auto available_coins = AvailableCoins(*wallet);
+    std::vector<COutput> coins = available_coins.All();
+    // Preselect the first 3 UTXO (150 BTC total)
+    std::set<COutPoint> preset_inputs = {coins[0].outpoint, coins[1].outpoint, coins[2].outpoint};
+
+    // Try to create a tx that spends more than what preset inputs + wallet selected inputs are covering for.
+    // The wallet can cover up to 200 BTC, and the tx target is 299 BTC.
+    std::vector<CRecipient> recipients = {{GetScriptForDestination(*Assert(wallet->GetNewDestination(OutputType::BECH32, "dummy"))),
+                                           /*nAmount=*/299 * COIN, /*fSubtractFeeFromAmount=*/true}};
+    CCoinControl coin_control;
+    coin_control.m_allow_other_inputs = true;
+    for (const auto& outpoint : preset_inputs) {
+        coin_control.Select(outpoint);
+    }
+
+    // Attempt to send 299 BTC from a wallet that only has 200 BTC. The wallet should exclude
+    // the preset inputs from the pool of available coins, realize that there is not enough
+    // money to fund the 299 BTC payment, and fail with "Insufficient funds".
+    //
+    // Even with SFFO, the wallet can only afford to send 200 BTC.
+    // If the wallet does not properly exclude preset inputs from the pool of available coins
+    // prior to coin selection, it may create a transaction that does not fund the full payment
+    // amount or, through SFFO, incorrectly reduce the recipient's amount by the difference
+    // between the original target and the wrongly counted inputs (in this case 99 BTC)
+    // so that the recipient's amount is no longer equal to the user's selected target of 299 BTC.
+
+    // First case, use 'subtract_fee_from_outputs=true'
+    util::Result<CreatedTransactionResult> res_tx = CreateTransaction(*wallet, recipients, /*change_pos*/-1, coin_control);
+    BOOST_CHECK(!res_tx.has_value());
+
+    // Second case, don't use 'subtract_fee_from_outputs'.
+    recipients[0].fSubtractFeeFromAmount = false;
+    res_tx = CreateTransaction(*wallet, recipients, /*change_pos*/-1, coin_control);
+    BOOST_CHECK(!res_tx.has_value());
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 } // namespace wallet