Merge bitcoin/bitcoin#35975: wallet: Fix `CWalletTx` malleated transaction metadata sync

### src/bench/wallet_migration.cpp
@@ -14,6 +14,7 @@
 #include <sync.h>
 #include <test/util/setup_common.h>
 #include <tinyformat.h>
+#include <uint256.h>
 #include <util/check.h>
 #include <util/result.h>
 #include <wallet/db.h>
@@ -24,6 +25,7 @@
 #include <wallet/walletdb.h>
 
 #include <algorithm>
+#include <cstdint>
 #include <cstddef>
 #include <memory>
 #include <optional>
@@ -88,7 +90,9 @@ static void WalletMigration(benchmark::Bench& bench)
                 CMutableTransaction mtx;
                 mtx.vout.emplace_back(COIN, GetScriptForDestination(dest));
                 mtx.vout.emplace_back(COIN, scripts_watch_only.at(j % NUM_WATCH_ONLY_ADDR).first);
-                mtx.vin.resize(2);
+                // Use distinct dummy prevouts so all txs don't appear to spend the same null outpoint
+                mtx.vin.emplace_back(COutPoint(Txid::FromUint256(uint256{uint8_t(j + 1)}), 0));
+                mtx.vin.emplace_back(COutPoint(Txid::FromUint256(uint256{uint8_t(j + 1)}), 1));
                 wallet->AddToWallet(MakeTransactionRef(mtx), TxStateInactive{}, /*update_wtx=*/nullptr, /*rescanning_old_block=*/true);
                 batch.WriteKey(pubkey, key.GetPrivKey(), CKeyMetadata());
             }

### src/ipc/test/fuzz/ipc.cpp
@@ -128,7 +128,7 @@ FUZZ_TARGET(ipc, .init = initialize_ipc)
                 const CMutableTransaction mutable_tx = ConsumeTransaction(fuzzed_data_provider, std::nullopt);
                 if (mutable_tx.vin.empty()) return;
                 const CTransactionRef tx = MakeTransactionRef(mutable_tx);
-                assert(*ipc.m_client->passTransaction(tx) == *tx);
+                assert(ipc.m_client->passTransaction(tx)->Equals(*tx));
             });
     }
 }

### src/ipc/test/ipc_tests.cpp
@@ -103,14 +103,14 @@ void IpcPipeTest()
     mtx.vout.emplace_back(COIN, CScript());
     CTransactionRef tx1{MakeTransactionRef(mtx)};
     CTransactionRef tx2{foo->passTransaction(tx1)};
-    BOOST_CHECK(*Assert(tx1) == *Assert(tx2));
+    BOOST_CHECK(Assert(tx1)->Equals(*Assert(tx2)));
 
     std::vector<CTransactionRef> txs1;
     txs1.push_back(tx1);
     txs1.push_back(nullptr);
     std::vector<CTransactionRef> txs2(foo->passTransactions(txs1));
     BOOST_CHECK_EQUAL(txs2.size(), 2);
-    BOOST_CHECK(*Assert(txs1[0]) == *Assert(txs2[0]));
+    BOOST_CHECK(Assert(txs1[0])->Equals(*Assert(txs2[0])));
     BOOST_CHECK(!txs2[1]);
 
     std::vector<char> vec1{'H', 'e', 'l', 'l', 'o'};

### src/primitives/transaction.h
@@ -12,6 +12,7 @@
 #include <script/script.h>
 #include <serialize.h>
 
+#include <algorithm>
 #include <compare>
 #include <cstddef>
 #include <cstdint>
@@ -273,6 +274,11 @@ inline CAmount CalculateOutputValue(const TxType& tx)
     return std::accumulate(tx.vout.cbegin(), tx.vout.cend(), CAmount{0}, [](CAmount sum, const auto& txout) { return sum + txout.nValue; });
 }
 
+struct EqualsOptions {
+    bool include_script_sig{true};
+    bool include_witness_data{true};
+};
+
 
 /** The basic transaction that is broadcasted on the network and contained in
  * blocks.  A transaction can contain multiple inputs and outputs.
@@ -343,9 +349,17 @@ class CTransaction
         return (vin.size() == 1 && vin[0].prevout.IsNull());
     }
 
-    friend bool operator==(const CTransaction& a, const CTransaction& b)
+    bool Equals(const CTransaction& other, const EqualsOptions opts = {}) const
     {
-        return a.GetWitnessHash() == b.GetWitnessHash();
+        return nLockTime == other.nLockTime &&
+            version == other.version &&
+            vout == other.vout &&
+            std::ranges::equal(vin, other.vin, [&opts](const CTxIn& self, const CTxIn& other) {
+                return self.prevout == other.prevout &&
+                    self.nSequence == other.nSequence &&
+                    (opts.include_script_sig ? self.scriptSig == other.scriptSig : true) &&
+                    (opts.include_witness_data ? self.scriptWitness.stack == other.scriptWitness.stack : true);
+            });
     }
 
     std::string ToString() const;

### src/rpc/rawtransaction.cpp
@@ -389,7 +389,7 @@ static RPCMethod getrawtransaction()
     }
 
     CTxUndo* undoTX {nullptr};
-    auto it = std::find_if(block.vtx.begin(), block.vtx.end(), [tx](CTransactionRef t){ return *t == *tx; });
+    auto it = std::find_if(block.vtx.begin(), block.vtx.end(), [tx](CTransactionRef t){ return t->Equals(*tx); });
     if (it != block.vtx.end()) {
         // -1 as blockundo does not have coinbase tx
         undoTX = &blockUndo.vtxundo.at(it - block.vtx.begin() - 1);

### src/test/fuzz/primitives_transaction.cpp
@@ -29,6 +29,6 @@ FUZZ_TARGET(primitives_transaction)
     if (mutable_tx_1 && mutable_tx_2) {
         const CTransaction tx_1{*mutable_tx_1};
         const CTransaction tx_2{*mutable_tx_2};
-        assert((tx_1 == tx_2) != (tx_1 != tx_2));
+        (void)tx_1.Equals(tx_2);
     }
 }

### src/test/serialize_tests.cpp
@@ -59,7 +59,7 @@ class CSerializeMethodsTestSingle
                boolval == rhs.boolval &&
                stringval == rhs.stringval &&
                strcmp(charstrval, rhs.charstrval) == 0 &&
-               *txval == *rhs.txval;
+               txval->Equals(*rhs.txval);
     }
 };
 

### src/test/transaction_tests.cpp
@@ -706,7 +706,7 @@ BOOST_AUTO_TEST_CASE(test_witness)
     CheckWithFlag(output1, input1, SCRIPT_VERIFY_NONE, false);
     CreateCreditAndSpend(keystore2, scriptMulti, output2, input2, false);
     CheckWithFlag(output2, input2, SCRIPT_VERIFY_NONE, false);
-    BOOST_CHECK(*output1 == *output2);
+    BOOST_CHECK(output1->Equals(*output2));
     UpdateInput(input1.vin[0], CombineSignatures(input1, input2, output1));
     CheckWithFlag(output1, input1, STANDARD_SCRIPT_VERIFY_FLAGS, true);
 
@@ -717,7 +717,7 @@ BOOST_AUTO_TEST_CASE(test_witness)
     CreateCreditAndSpend(keystore2, GetScriptForDestination(ScriptHash(scriptMulti)), output2, input2, false);
     CheckWithFlag(output2, input2, SCRIPT_VERIFY_NONE, true);
     CheckWithFlag(output2, input2, SCRIPT_VERIFY_P2SH, false);
-    BOOST_CHECK(*output1 == *output2);
+    BOOST_CHECK(output1->Equals(*output2));
     UpdateInput(input1.vin[0], CombineSignatures(input1, input2, output1));
     CheckWithFlag(output1, input1, SCRIPT_VERIFY_P2SH, true);
     CheckWithFlag(output1, input1, STANDARD_SCRIPT_VERIFY_FLAGS, true);
@@ -729,7 +729,7 @@ BOOST_AUTO_TEST_CASE(test_witness)
     CreateCreditAndSpend(keystore2, destination_script_multi, output2, input2, false);
     CheckWithFlag(output2, input2, SCRIPT_VERIFY_NONE, true);
     CheckWithFlag(output2, input2, SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_WITNESS, false);
-    BOOST_CHECK(*output1 == *output2);
+    BOOST_CHECK(output1->Equals(*output2));
     UpdateInput(input1.vin[0], CombineSignatures(input1, input2, output1));
     CheckWithFlag(output1, input1, SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_WITNESS, true);
     CheckWithFlag(output1, input1, STANDARD_SCRIPT_VERIFY_FLAGS, true);
@@ -741,7 +741,7 @@ BOOST_AUTO_TEST_CASE(test_witness)
     CreateCreditAndSpend(keystore2, GetScriptForDestination(ScriptHash(destination_script_multi)), output2, input2, false);
     CheckWithFlag(output2, input2, SCRIPT_VERIFY_P2SH, true);
     CheckWithFlag(output2, input2, SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_WITNESS, false);
-    BOOST_CHECK(*output1 == *output2);
+    BOOST_CHECK(output1->Equals(*output2));
     UpdateInput(input1.vin[0], CombineSignatures(input1, input2, output1));
     CheckWithFlag(output1, input1, SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_WITNESS, true);
     CheckWithFlag(output1, input1, STANDARD_SCRIPT_VERIFY_FLAGS, true);

### src/wallet/transaction.cpp
@@ -11,19 +11,9 @@
 using interfaces::FoundBlock;
 
 namespace wallet {
-bool CWalletTx::IsEquivalentTo(const CWalletTx& _tx) const
+bool CWalletTx::IsMalleation(const CWalletTx& _tx) const
 {
-        CMutableTransaction tx1 {*this->GetTx()};
-        CMutableTransaction tx2 {*_tx.GetTx()};
-        for (auto& txin : tx1.vin) {
-            txin.scriptSig = CScript();
-            txin.scriptWitness.SetNull();
-        }
-        for (auto& txin : tx2.vin) {
-            txin.scriptSig = CScript();
-            txin.scriptWitness.SetNull();
-        }
-        return CTransaction(tx1) == CTransaction(tx2);
+    return GetTx()->Equals(*_tx.GetTx(), {.include_script_sig = false, .include_witness_data = false});
 }
 
 bool CWalletTx::InMempool() const

### src/wallet/transaction.h
@@ -366,8 +366,9 @@ class CWalletTx
         m_cached_from_me = std::nullopt;
     }
 
-    /** True if only scriptSigs are different */
-    bool IsEquivalentTo(const CWalletTx& tx) const;
+    /** True if tx is a malleation of this, i.e. it has the exact same version, locktime,
+     * input order, input outpoints, input sequences, and outputs. Input scriptSigs and input scriptWitnesses may differ. */
+    bool IsMalleation(const CWalletTx& tx) const;
 
     bool InMempool() const;
 

### src/wallet/wallet.cpp
@@ -732,46 +732,57 @@ void CWallet::Close()
     GetDatabase().Close();
 }
 
-void CWallet::SyncMetaData(std::pair<TxSpends::iterator, TxSpends::iterator> range)
+std::set<CWalletTx*, WalletTxOrderComparator> CWallet::GetMalleatedVariants(const CWalletTx& wtx)
 {
-    // We want all the wallet transactions in range to have the same metadata as
-    // the oldest (smallest nOrderPos).
-    // So: find smallest nOrderPos:
+    AssertLockHeld(cs_wallet);
+    std::set<CWalletTx*, WalletTxOrderComparator> txs;
 
-    int nMinOrderPos = std::numeric_limits<int>::max();
-    const CWalletTx* copyFrom = nullptr;
-    for (TxSpends::iterator it = range.first; it != range.second; ++it) {
-        const CWalletTx* wtx = &mapWallet.at(it->second);
-        if (wtx->nOrderPos < nMinOrderPos) {
-            nMinOrderPos = wtx->nOrderPos;
-            copyFrom = wtx;
-        }
+    // Coinbases cannot be malleated
+    if (wtx.IsCoinBase()) return txs;
+
+    // Only transactions that have non-witness inputs can be malleated
+    if (std::ranges::none_of(wtx.GetTx()->vin, [](const CTxIn& in) { return in.scriptWitness.IsNull(); })) {
+        return txs;
     }
 
-    if (!copyFrom) {
-        return;
+    // All variants spend wtx's first input, so a single lookup finds every candidate
+    bool found_self = false;
+    const auto [begin, end] = mapTxSpends.equal_range(wtx.GetTx()->vin.front().prevout);
+    for (auto it = begin; it != end; ++it) {
+        auto entry = mapWallet.find(it->second);
+        if (!Assume(entry != mapWallet.end())) continue; // sanity-check: mapTxSpends has txs that are in mapWallet
+        const bool is_self = &entry->second == &wtx;
+        found_self |= is_self;
+        if (is_self || wtx.IsMalleation(entry->second)) {
+            Assume(txs.insert(&entry->second).second);
+        }
     }
+    // wtx should always be found as this function is always called after AddToSpends
+    Assert(found_self);
+    return txs;
+}
+
+void CWallet::SyncMalleatedTxMetadata(WalletBatch& batch, const CWalletTx& wtx)
+{
+    const auto txs = GetMalleatedVariants(wtx);
+    if (txs.size() <= 1) return; // no variants, nothing to do
+
+    // First tx is the oldest one (smallest nOrderPos)
+    const CWalletTx* copyFrom = *txs.begin();
+
+    // The metadata that is kept in sync between malleated variants.
+    // nTimeReceived, nOrderPos and cached members are not copied on purpose.
+    const auto metadata = [](auto& tx) {
+        return std::tie(tx.m_from, tx.m_message, tx.m_comment, tx.m_comment_to,
+                        tx.m_replaces_txid, tx.m_replaced_by_txid,
+                        tx.m_messages, tx.m_payment_requests, tx.nTimeSmart);
+    };
 
     // Now copy data from copyFrom to rest:
-    for (TxSpends::iterator it = range.first; it != range.second; ++it)
-    {
-        const Txid& hash = it->second;
-        CWalletTx* copyTo = &mapWallet.at(hash);
-        if (copyFrom == copyTo) continue;
-        assert(copyFrom && "Oldest wallet transaction in range assumed to have been found.");
-        if (!copyFrom->IsEquivalentTo(*copyTo)) continue;
-        copyTo->m_from = copyFrom->m_from;
-        copyTo->m_message = copyFrom->m_message;
-        copyTo->m_comment = copyFrom->m_comment;
-        copyTo->m_comment_to = copyFrom->m_comment_to;
-        copyTo->m_replaces_txid = copyFrom->m_replaces_txid;
-        copyTo->m_replaced_by_txid = copyFrom->m_replaced_by_txid;
-        copyTo->m_messages = copyFrom->m_messages;
-        copyTo->m_payment_requests = copyFrom->m_payment_requests;
-        // nTimeReceived not copied on purpose
-        copyTo->nTimeSmart = copyFrom->nTimeSmart;
-        // nOrderPos not copied on purpose
-        // cached members not copied on purpose
+    for (CWalletTx* copyTo : txs) {
+        if (copyTo == copyFrom) continue;
+        metadata(*copyTo) = metadata(*copyFrom);
+        (void)batch.WriteTxMetadata(*copyTo);
     }
 }
 
@@ -824,10 +835,6 @@ void CWallet::AddToSpends(const COutPoint& outpoint, const Txid& txid)
     mapTxSpends.insert(std::make_pair(outpoint, txid));
 
     UnlockCoin(outpoint);
-
-    std::pair<TxSpends::iterator, TxSpends::iterator> range;
-    range = mapTxSpends.equal_range(outpoint);
-    SyncMetaData(range);
 }
 
 
@@ -1020,6 +1027,17 @@ bool CWallet::MarkReplaced(const Txid& originalHash, const Txid& newHash)
         success = false;
     }
 
+    // The new transaction also replaces any malleated variants of wtx,
+    // so bumpfee refuses to bump them afterwards
+    for (CWalletTx* variant : GetMalleatedVariants(wtx)) {
+        if (variant == &wtx) continue;
+        variant->m_replaced_by_txid = newHash;
+        if (!batch.WriteTxMetadata(*variant)) {
+            WalletLogPrintf("%s: Updating variant tx %s failed\n", __func__, variant->GetHash().ToString());
+            success = false;
+        }
+    }
+
     NotifyTransactionChanged(originalHash, CT_UPDATED);
 
     return success;
@@ -1088,6 +1106,7 @@ CWalletTx* CWallet::AddToWallet(CTransactionRef tx, const TxState& state, const
         wtx.m_it_wtxOrdered = wtxOrdered.insert(std::make_pair(wtx.nOrderPos, &wtx));
         wtx.nTimeSmart = ComputeTimeSmart(wtx, rescanning_old_block);
         AddToSpends(wtx);
+        SyncMalleatedTxMetadata(batch, wtx);
 
         // Update birth time when tx time is older than it.
         MaybeUpdateBirthTime(wtx.GetTxTime());

### src/wallet/wallet.h
@@ -373,7 +373,11 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
     /** Mark a transaction's inputs dirty, thus forcing the outputs to be recomputed */
     void MarkInputsDirty(const CTransactionRef& tx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 
-    void SyncMetaData(std::pair<TxSpends::iterator, TxSpends::iterator>) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
+    /** Collects all wallet txs that differ from wtx only in their scriptSigs (i.e. different tx id malleated variants)
+     *  plus wtx itself. Sorted by the order in which they were inserted in the wallet (CWalletTx::nOrderPos) */
+    std::set<CWalletTx*, WalletTxOrderComparator> GetMalleatedVariants(const CWalletTx& wtx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
+
+    void SyncMalleatedTxMetadata(WalletBatch& batch, const CWalletTx& wtx) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 
     bool SyncTransaction(const CTransactionRef& tx, const SyncTxState& state, bool rescanning_old_block = false) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 

### test/functional/wallet_txn_clone.py
@@ -7,6 +7,8 @@
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import (
     assert_equal,
+    assert_not_equal,
+    assert_raises_rpc_error,
 )
 from test_framework.messages import (
     COIN,
@@ -144,6 +146,109 @@ def run_test(self):
             expected -= 50
         assert_equal(self.nodes[0].getbalance(), expected)
 
+        self.test_malleated_metadata_synced()
+        self.test_malleated_rbf_metadata_synced()
+
+    def malleate_tx(self, wallet, txid):
+        rawtx = wallet.getrawtransaction(txid)
+        tx = tx_from_hex(rawtx)
+        for txin in tx.vin:
+            txin.scriptSig = b""
+        for wit in tx.wit.vtxinwit:
+            wit.scriptWitness.stack.clear()
+        unsigned_tx = tx.serialize_without_witness().hex()
+
+        # malleate the tx by signing with a different sighash
+        malleated_tx = wallet.signrawtransactionwithwallet(hexstring=unsigned_tx, sighashtype="ALL|ANYONECANPAY")["hex"]
+        malleated_txid = wallet.decoderawtransaction(malleated_tx)["txid"]
+        assert_not_equal(malleated_txid, txid)
+        return malleated_tx, malleated_txid
+
+
+    def test_malleated_metadata_synced(self):
+        self.log.info("Test malleated tx has copied user provided metadata")
+        self.nodes[0].createwallet("metadata_clone")
+        wallet = self.nodes[0].get_wallet_rpc("metadata_clone")
+        def_wallet = self.nodes[0].get_wallet_rpc(self.default_wallet_name)
+
+        # Make non-segwit UTXOs that can be malleated. Smaller than the spending amount
+        # to create multiple inputs.
+        for _ in range(6):
+            def_wallet.sendtoaddress(wallet.getnewaddress(address_type="legacy"), 0.5)
+
+        self.generate(self.nodes[0], 1)
+
+        # Bumping either should prevent the other from being bumped as well
+        for bump_malleated in [False, True]:
+            original_txid = wallet.sendtoaddress(def_wallet.getnewaddress(), 0.9, comment="testing", fee_rate=1)
+            malleated_tx, malleated_txid = self.malleate_tx(wallet, original_txid)
+
+            blockhash = self.generateblock(self.nodes[0], def_wallet.getnewaddress(), [malleated_tx])["hash"]
+
+            assert_equal(wallet.gettransaction(malleated_txid)["comment"], "testing")
+
+            # Check synced comment was written to disk
+            wallet.unloadwallet()
+            self.nodes[0].loadwallet("metadata_clone")
+            assert_equal(wallet.gettransaction(malleated_txid)["comment"], "testing")
+
+            # Put the malleated back into the mempol by invalidating the block
+            self.nodes[0].invalidateblock(blockhash)
+
+            if bump_malleated:
+                to_bump = malleated_txid
+                other_bump = original_txid
+            else:
+                to_bump = original_txid
+                other_bump = malleated_txid
+
+            bumped = wallet.bumpfee(to_bump, fee_rate=10)
+
+            def check_metadata():
+                original_txinfo = wallet.gettransaction(original_txid)
+                malleated_txinfo = wallet.gettransaction(malleated_txid)
+                assert_equal(original_txinfo["replaced_by_txid"], bumped["txid"])
+                assert_equal(malleated_txinfo["replaced_by_txid"], bumped["txid"])
+
+                assert_raises_rpc_error(-4, f"Cannot bump transaction {other_bump} which was already bumped by transaction", wallet.bumpfee, other_bump, fee_rate=20)
+
+            check_metadata()
+
+            # Check persistence
+            wallet.unloadwallet()
+            self.nodes[0].loadwallet("metadata_clone")
+
+            check_metadata()
+
+            self.nodes[0].reconsiderblock(blockhash)
+
+    def test_malleated_rbf_metadata_synced(self):
+        self.log.info("Test malleation of a rbf has copied user provided and replacement metadata")
+        self.nodes[0].createwallet("rbf_metadata_clone")
+        wallet = self.nodes[0].get_wallet_rpc("rbf_metadata_clone")
+        def_wallet = self.nodes[0].get_wallet_rpc(self.default_wallet_name)
+
+        def_wallet.sendtoaddress(wallet.getnewaddress(address_type="legacy"), 1)
+
+        self.generate(self.nodes[0], 1)
+
+        orig_txid = wallet.sendtoaddress(def_wallet.getnewaddress(), 0.9999, comment="testing")
+        txid = wallet.bumpfee(orig_txid)["txid"]
+        malleated_tx, malleated_txid = self.malleate_tx(wallet, txid)
+
+        self.generateblock(self.nodes[0], def_wallet.getnewaddress(), [malleated_tx])
+
+        txinfo = wallet.gettransaction(malleated_txid)
+        assert_equal(txinfo["comment"], "testing")
+        assert_equal(txinfo["replaces_txid"], orig_txid)
+
+        # Synced metadata must survive a reload
+        wallet.unloadwallet()
+        self.nodes[0].loadwallet("rbf_metadata_clone")
+        txinfo = wallet.gettransaction(malleated_txid)
+        assert_equal(txinfo["comment"], "testing")
+        assert_equal(txinfo["replaces_txid"], orig_txid)
+
 
 if __name__ == '__main__':
     TxnMallTest(__file__).main()