Merge bitcoin/bitcoin#22253: validation: distinguish between same tx and same-nonwitness-data tx in mempool

b7a8cd9963e810264d3b45d0ad15af863965c47a [test] submit same txid different wtxid as mempool tx (glozow)
fdb48163bfbf34f79dc78ffaa2bbf9e39af96687 [validation] distinguish same txid different wtxid in mempool (glozow)

Pull request description:

  On master, if you submit a transaction with the same txid but different witness to the mempool, it thinks the transactions are the same. Users submitting through `BroadcastTransaction()` (i.e. `sendrawtransaction` or the wallet) don't get notified that there's a different transaction in the mempool, although it doesn't crash. Users submitting through `testmempoolaccept()` will get a "txn-already-in-mempool" error.

  This PR simply distinguishes between `txn-already-in-mempool` and `txn-same-nonwitness-data-in-mempool`, without handling them differently: `sendrawtransaction` still will not throw, but `testmempoolaccept` will give you a different error.

  I believe the intention of #19645 is to allow full swaps of transactions that have different witnesses but identical nonwitness data. Returning a different error message + adding a test was suggested: https://github.com/bitcoin/bitcoin/pull/19645#issuecomment-705109193 so this is that PR.

ACKs for top commit:
  naumenkogs:
    ACK b7a8cd9963e810264d3b45d0ad15af863965c47a
  jnewbery:
    Code review ACK b7a8cd9963e810264d3b45d0ad15af863965c47a
  theStack:
    Code-review ACK b7a8cd9963e810264d3b45d0ad15af863965c47a
  darosior:
    re-utACK b7a8cd9963e810264d3b45d0ad15af863965c47a

Tree-SHA512: 9c6591edaf8727ba5b4675977adb8cbdef7288584003b6cd659828032dc92d2ae915800a8ef8b6fdffe112c1b660df72297a3dcf2e2e3e1f959c6cb3678c63ee

3 files changed, 123 insertions, 2 deletions

diff --git a/src/validation.cpp b/src/validation.cpp
index 65d2dfa3b7..c80f015143 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -587,9 +587,13 @@ bool MemPoolAccept::PreChecks(ATMPArgs& args, Workspace& ws)
     if (!CheckFinalTx(m_active_chainstate.m_chain.Tip(), tx, STANDARD_LOCKTIME_VERIFY_FLAGS))
         return state.Invalid(TxValidationResult::TX_PREMATURE_SPEND, "non-final");
 
-    // is it already in the memory pool?
-    if (m_pool.exists(hash)) {
+    if (m_pool.exists(GenTxid(true, tx.GetWitnessHash()))) {
+        // Exact transaction already exists in the mempool.
         return state.Invalid(TxValidationResult::TX_CONFLICT, "txn-already-in-mempool");
+    } else if (m_pool.exists(GenTxid(false, tx.GetHash()))) {
+        // Transaction with the same non-witness data but different witness (same txid, different
+        // wtxid) already exists in the mempool.
+        return state.Invalid(TxValidationResult::TX_CONFLICT, "txn-same-nonwitness-data-in-mempool");
     }
 
     // Check for conflicts with in-memory transactions
diff --git a/test/functional/mempool_accept_wtxid.py b/test/functional/mempool_accept_wtxid.py
new file mode 100755
index 0000000000..dd1f8997ad
--- /dev/null
+++ b/test/functional/mempool_accept_wtxid.py
@@ -0,0 +1,116 @@
+#!/usr/bin/env python3
+# Copyright (c) 2021 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""
+Test mempool acceptance in case of an already known transaction
+with identical non-witness data different witness.
+"""
+
+from test_framework.messages import (
+    COIN,
+    COutPoint,
+    CTransaction,
+    CTxIn,
+    CTxInWitness,
+    CTxOut,
+    sha256,
+)
+from test_framework.script import (
+    CScript,
+    OP_0,
+    OP_ELSE,
+    OP_ENDIF,
+    OP_EQUAL,
+    OP_HASH160,
+    OP_IF,
+    OP_TRUE,
+    hash160,
+)
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import (
+    assert_equal,
+)
+
+class MempoolWtxidTest(BitcoinTestFramework):
+    def set_test_params(self):
+        self.num_nodes = 1
+        self.setup_clean_chain = True
+
+    def run_test(self):
+        node = self.nodes[0]
+
+        self.log.info('Start with empty mempool and 101 blocks')
+        # The last 100 coinbase transactions are premature
+        blockhash = node.generate(101)[0]
+        txid = node.getblock(blockhash=blockhash, verbosity=2)["tx"][0]["txid"]
+        assert_equal(node.getmempoolinfo()['size'], 0)
+
+        self.log.info("Submit parent with multiple script branches to mempool")
+        hashlock = hash160(b'Preimage')
+        witness_script = CScript([OP_IF, OP_HASH160, hashlock, OP_EQUAL, OP_ELSE, OP_TRUE, OP_ENDIF])
+        witness_program = sha256(witness_script)
+        script_pubkey = CScript([OP_0, witness_program])
+
+        parent = CTransaction()
+        parent.vin.append(CTxIn(COutPoint(int(txid, 16), 0), b""))
+        parent.vout.append(CTxOut(int(9.99998 * COIN), script_pubkey))
+        parent.rehash()
+
+        privkeys = [node.get_deterministic_priv_key().key]
+        raw_parent = node.signrawtransactionwithkey(hexstring=parent.serialize().hex(), privkeys=privkeys)['hex']
+        parent_txid = node.sendrawtransaction(hexstring=raw_parent, maxfeerate=0)
+        node.generate(1)
+
+        # Create a new transaction with witness solving first branch
+        child_witness_script = CScript([OP_TRUE])
+        child_witness_program = sha256(child_witness_script)
+        child_script_pubkey = CScript([OP_0, child_witness_program])
+
+        child_one = CTransaction()
+        child_one.vin.append(CTxIn(COutPoint(int(parent_txid, 16), 0), b""))
+        child_one.vout.append(CTxOut(int(9.99996 * COIN), child_script_pubkey))
+        child_one.wit.vtxinwit.append(CTxInWitness())
+        child_one.wit.vtxinwit[0].scriptWitness.stack = [b'Preimage', b'\x01', witness_script]
+        child_one_wtxid = child_one.getwtxid()
+        child_one_txid = child_one.rehash()
+
+        # Create another identical transaction with witness solving second branch
+        child_two = CTransaction()
+        child_two.vin.append(CTxIn(COutPoint(int(parent_txid, 16), 0), b""))
+        child_two.vout.append(CTxOut(int(9.99996 * COIN), child_script_pubkey))
+        child_two.wit.vtxinwit.append(CTxInWitness())
+        child_two.wit.vtxinwit[0].scriptWitness.stack = [b'', witness_script]
+        child_two_wtxid = child_two.getwtxid()
+        child_two_txid = child_two.rehash()
+
+        assert_equal(child_one_txid, child_two_txid)
+        assert child_one_wtxid != child_two_wtxid
+
+        self.log.info("Submit one child to the mempool")
+        txid_submitted = node.sendrawtransaction(child_one.serialize().hex())
+        assert_equal(node.getrawmempool(True)[txid_submitted]['wtxid'], child_one_wtxid)
+
+        # testmempoolaccept reports the "already in mempool" error
+        assert_equal(node.testmempoolaccept([child_one.serialize().hex()]), [{
+            "txid": child_one_txid,
+            "wtxid": child_one_wtxid,
+            "allowed": False,
+            "reject-reason": "txn-already-in-mempool"
+        }])
+        testres_child_two = node.testmempoolaccept([child_two.serialize().hex()])[0]
+        assert_equal(testres_child_two, {
+            "txid": child_two_txid,
+            "wtxid": child_two_wtxid,
+            "allowed": False,
+            "reject-reason": "txn-same-nonwitness-data-in-mempool"
+        })
+
+        # sendrawtransaction will not throw but quits early when the exact same transaction is already in mempool
+        node.sendrawtransaction(child_one.serialize().hex())
+        # sendrawtransaction will not throw but quits early when a transaction with the same non-witness data is already in mempool
+        node.sendrawtransaction(child_two.serialize().hex())
+
+
+if __name__ == '__main__':
+    MempoolWtxidTest().main()
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index ad1acd2e2f..303742236f 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -279,6 +279,7 @@ BASE_SCRIPTS = [
     'feature_asmap.py',
     'mempool_unbroadcast.py',
     'mempool_compatibility.py',
+    'mempool_accept_wtxid.py',
     'rpc_deriveaddresses.py',
     'rpc_deriveaddresses.py --usecli',
     'p2p_ping.py',