Merge bitcoin/bitcoin#30000: p2p: index TxOrphanage by wtxid, allow entries with same txid

0fb17bf61a40b73a2b81a18e70b3de180c917f22 [log] updates in TxOrphanage (glozow)
b16da7eda76944719713be68b61f03d4acdd3e16 [functional test] attackers sending mutated orphans (glozow)
6675f6428d653bf7a53537bd773114f4fb5ba53f [unit test] TxOrphanage handling of same-txid-different-witness txns (glozow)
8923edfc1f12ebc6a074651c084ba7d249074799 [p2p] allow entries with the same txid in TxOrphanage (glozow)
c31f148166f01a9167d82501a77823785d28a841 [refactor] TxOrphanage::EraseTx by wtxid (glozow)
efcc5930175f31b685adb4627a038d9f0848eb1f [refactor] TxOrphanage::HaveTx only by wtxid (glozow)
7e475b9648bbee04f5825b922ba0399373eaa5a9 [p2p] don't query orphanage by txid (glozow)

Pull request description:

  Part of #27463 in the "make orphan handling more robust" section.

  Currently the main map in `TxOrphanage` is indexed by txid; we do not allow 2 transactions with the same txid into TxOrphanage. This means that if we receive a transaction and want to store it in orphanage, we'll fail to do so if a same-txid-different-witness version of the tx already exists in the orphanage. The existing orphanage entry can stay until it expires 20 minutes later, or until we find that it is invalid.

  This means an attacker can try to block/delay us accepting an orphan transaction by sending a mutated version of the child ahead of time. See included test.

  Prior to #28970, we don't rely on the orphanage for anything and it would be relatively difficult to guess what transaction will go to a node's orphanage. After the parent(s) are accepted, if anybody sends us the correct transaction, we'll end up accepting it. However, this is a bit more painful for 1p1c: it's easier for an attacker to tell when a tx is going to hit a node's orphanage, and we need to store the correct orphan + receive the parent before we'll consider the package. If we start out with a bad orphan, we can't evict it until we receive the parent + try the 1p1c, and then we'll need to download the real child, put it in orphanage, download the parent again, and then retry 1p1c.

ACKs for top commit:
  AngusP:
    ACK 0fb17bf61a40b73a2b81a18e70b3de180c917f22
  itornaza:
    trACK 0fb17bf61a40b73a2b81a18e70b3de180c917f22
  instagibbs:
    ACK 0fb17bf61a40b73a2b81a18e70b3de180c917f22
  theStack:
    ACK 0fb17bf61a40b73a2b81a18e70b3de180c917f22
  sr-gi:
    crACK [0fb17bf](https://github.com/bitcoin/bitcoin/pull/30000/commits/0fb17bf61a40b73a2b81a18e70b3de180c917f22)
  stickies-v:
    ACK 0fb17bf61a40b73a2b81a18e70b3de180c917f22

Tree-SHA512: edcbac7287c628bc27036920c2d4e4f63ec65087fbac1de9319c4f541515d669fc4e5fdc30c8b9a248b720da42b89153d388e91c7bf5caf4bc5b3b931ded1f59

2 files changed, 176 insertions, 4 deletions

diff --git a/test/functional/p2p_invalid_tx.py b/test/functional/p2p_invalid_tx.py
index ae9dc816ab..0ae05d4b0b 100755
--- a/test/functional/p2p_invalid_tx.py
+++ b/test/functional/p2p_invalid_tx.py
@@ -165,7 +165,7 @@ class InvalidTxRequestTest(BitcoinTestFramework):
             node.p2ps[0].send_txs_and_test([rejected_parent], node, success=False)
 
         self.log.info('Test that a peer disconnection causes erase its transactions from the orphan pool')
-        with node.assert_debug_log(['Erased 100 orphan tx from peer=25']):
+        with node.assert_debug_log(['Erased 100 orphan transaction(s) from peer=25']):
             self.reconnect_p2p(num_connections=1)
 
         self.log.info('Test that a transaction in the orphan pool is included in a new tip block causes erase this transaction from the orphan pool')
@@ -190,7 +190,7 @@ class InvalidTxRequestTest(BitcoinTestFramework):
         block_A.solve()
 
         self.log.info('Send the block that includes the previous orphan ... ')
-        with node.assert_debug_log(["Erased 1 orphan tx included or conflicted by block"]):
+        with node.assert_debug_log(["Erased 1 orphan transaction(s) included or conflicted by block"]):
             node.p2ps[0].send_blocks_and_test([block_A], node, success=True)
 
         self.log.info('Test that a transaction in the orphan pool conflicts with a new tip block causes erase this transaction from the orphan pool')
@@ -219,7 +219,7 @@ class InvalidTxRequestTest(BitcoinTestFramework):
         block_B.solve()
 
         self.log.info('Send the block that includes a transaction which conflicts with the previous orphan ... ')
-        with node.assert_debug_log(["Erased 1 orphan tx included or conflicted by block"]):
+        with node.assert_debug_log(["Erased 1 orphan transaction(s) included or conflicted by block"]):
             node.p2ps[0].send_blocks_and_test([block_B], node, success=True)
 
 
diff --git a/test/functional/p2p_orphan_handling.py b/test/functional/p2p_orphan_handling.py
index 6166c62aa2..f525d87cca 100755
--- a/test/functional/p2p_orphan_handling.py
+++ b/test/functional/p2p_orphan_handling.py
@@ -7,6 +7,7 @@ import time
 
 from test_framework.messages import (
     CInv,
+    CTxInWitness,
     MSG_TX,
     MSG_WITNESS_TX,
     MSG_WTX,
@@ -21,6 +22,7 @@ from test_framework.p2p import (
     NONPREF_PEER_TX_DELAY,
     OVERLOADED_PEER_TX_DELAY,
     p2p_lock,
+    P2PInterface,
     P2PTxInvStore,
     TXID_RELAY_DELAY,
 )
@@ -127,6 +129,22 @@ class OrphanHandlingTest(BitcoinTestFramework):
         peer.wait_for_getdata([wtxid])
         peer.send_and_ping(msg_tx(tx))
 
+    def create_malleated_version(self, tx):
+        """
+        Create a malleated version of the tx where the witness is replaced with garbage data.
+        Returns a CTransaction object.
+        """
+        tx_bad_wit = tx_from_hex(tx["hex"])
+        tx_bad_wit.wit.vtxinwit = [CTxInWitness()]
+        # Add garbage data to witness 0. We cannot simply strip the witness, as the node would
+        # classify it as a transaction in which the witness was missing rather than wrong.
+        tx_bad_wit.wit.vtxinwit[0].scriptWitness.stack = [b'garbage']
+
+        assert_equal(tx["txid"], tx_bad_wit.rehash())
+        assert tx["wtxid"] != tx_bad_wit.getwtxid()
+
+        return tx_bad_wit
+
     @cleanup
     def test_arrival_timing_orphan(self):
         self.log.info("Test missing parents that arrive during delay are not requested")
@@ -284,8 +302,8 @@ class OrphanHandlingTest(BitcoinTestFramework):
         # doesn't give up on the orphan. Once all of the missing parents are received, it should be
         # submitted to mempool.
         peer.send_message(msg_notfound(vec=[CInv(MSG_WITNESS_TX, int(txid_conf_old, 16))]))
+        # Sync with ping to ensure orphans are reconsidered
         peer.send_and_ping(msg_tx(missing_tx["tx"]))
-        peer.sync_with_ping()
         assert_equal(node.getmempoolentry(orphan["txid"])["ancestorcount"], 3)
 
     @cleanup
@@ -394,10 +412,161 @@ class OrphanHandlingTest(BitcoinTestFramework):
         peer2.assert_never_requested(child["tx"].getwtxid())
 
         # The child should never be requested, even if announced again with potentially different witness.
+        # Sync with ping to ensure orphans are reconsidered
         peer3.send_and_ping(msg_inv([CInv(t=MSG_TX, h=int(child["txid"], 16))]))
         self.nodes[0].bumpmocktime(TXREQUEST_TIME_SKIP)
         peer3.assert_never_requested(child["txid"])
 
+    @cleanup
+    def test_same_txid_orphan(self):
+        self.log.info("Check what happens when orphan with same txid is already in orphanage")
+        node = self.nodes[0]
+
+        tx_parent = self.wallet.create_self_transfer()
+
+        # Create the real child
+        tx_child = self.wallet.create_self_transfer(utxo_to_spend=tx_parent["new_utxo"])
+
+        # Create a fake version of the child
+        tx_orphan_bad_wit = self.create_malleated_version(tx_child)
+
+        bad_peer = node.add_p2p_connection(P2PInterface())
+        honest_peer = node.add_p2p_connection(P2PInterface())
+
+        # 1. Fake orphan is received first. It is missing an input.
+        bad_peer.send_and_ping(msg_tx(tx_orphan_bad_wit))
+
+        # 2. Node requests the missing parent by txid.
+        parent_txid_int = int(tx_parent["txid"], 16)
+        node.bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY)
+        bad_peer.wait_for_getdata([parent_txid_int])
+
+        # 3. Honest peer relays the real child, which is also missing parents and should be placed
+        # in the orphanage.
+        with node.assert_debug_log(["missingorspent", "stored orphan tx"]):
+            honest_peer.send_and_ping(msg_tx(tx_child["tx"]))
+
+        # Time out the previous request for the parent (node will not request the same transaction
+        # from multiple nodes at the same time)
+        node.bumpmocktime(GETDATA_TX_INTERVAL)
+
+        # 4. The parent is requested. Honest peer sends it.
+        honest_peer.wait_for_getdata([parent_txid_int])
+        # Sync with ping to ensure orphans are reconsidered
+        honest_peer.send_and_ping(msg_tx(tx_parent["tx"]))
+
+        # 5. After parent is accepted, orphans should be reconsidered.
+        # The real child should be accepted and the fake one rejected.
+        node_mempool = node.getrawmempool()
+        assert tx_parent["txid"] in node_mempool
+        assert tx_child["txid"] in node_mempool
+        assert_equal(node.getmempoolentry(tx_child["txid"])["wtxid"], tx_child["wtxid"])
+
+    @cleanup
+    def test_same_txid_orphan_of_orphan(self):
+        self.log.info("Check what happens when orphan's parent with same txid is already in orphanage")
+        node = self.nodes[0]
+
+        tx_grandparent = self.wallet.create_self_transfer()
+
+        # Create middle tx (both parent and child) which will be in orphanage.
+        tx_middle = self.wallet.create_self_transfer(utxo_to_spend=tx_grandparent["new_utxo"])
+
+        # Create a fake version of the middle tx
+        tx_orphan_bad_wit = self.create_malleated_version(tx_middle)
+
+        # Create grandchild spending from tx_middle (and spending from tx_orphan_bad_wit since they
+        # have the same txid).
+        tx_grandchild = self.wallet.create_self_transfer(utxo_to_spend=tx_middle["new_utxo"])
+
+        bad_peer = node.add_p2p_connection(P2PInterface())
+        honest_peer = node.add_p2p_connection(P2PInterface())
+
+        # 1. Fake orphan is received first. It is missing an input.
+        bad_peer.send_and_ping(msg_tx(tx_orphan_bad_wit))
+
+        # 2. Node requests missing tx_grandparent by txid.
+        grandparent_txid_int = int(tx_grandparent["txid"], 16)
+        node.bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY)
+        bad_peer.wait_for_getdata([grandparent_txid_int])
+
+        # 3. Honest peer relays the grandchild, which is missing a parent. The parent by txid already
+        # exists in orphanage, but should be re-requested because the node shouldn't assume that the
+        # witness data is the same. In this case, a same-txid-different-witness transaction exists!
+        with node.assert_debug_log(["stored orphan tx"]):
+            honest_peer.send_and_ping(msg_tx(tx_grandchild["tx"]))
+        middle_txid_int = int(tx_middle["txid"], 16)
+        node.bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY)
+        honest_peer.wait_for_getdata([middle_txid_int])
+
+        # 4. Honest peer relays the real child, which is also missing parents and should be placed
+        # in the orphanage.
+        with node.assert_debug_log(["stored orphan tx"]):
+            honest_peer.send_and_ping(msg_tx(tx_middle["tx"]))
+        assert_equal(len(node.getrawmempool()), 0)
+
+        # 5. Honest peer sends tx_grandparent
+        honest_peer.send_and_ping(msg_tx(tx_grandparent["tx"]))
+
+        # 6. After parent is accepted, orphans should be reconsidered.
+        # The real child should be accepted and the fake one rejected.
+        node_mempool = node.getrawmempool()
+        assert tx_grandparent["txid"] in node_mempool
+        assert tx_middle["txid"] in node_mempool
+        assert tx_grandchild["txid"] in node_mempool
+        assert_equal(node.getmempoolentry(tx_middle["txid"])["wtxid"], tx_middle["wtxid"])
+
+    @cleanup
+    def test_orphan_txid_inv(self):
+        self.log.info("Check node does not ignore announcement with same txid as tx in orphanage")
+        node = self.nodes[0]
+
+        tx_parent = self.wallet.create_self_transfer()
+
+        # Create the real child and fake version
+        tx_child = self.wallet.create_self_transfer(utxo_to_spend=tx_parent["new_utxo"])
+        tx_orphan_bad_wit = self.create_malleated_version(tx_child)
+
+        bad_peer = node.add_p2p_connection(PeerTxRelayer())
+        # Must not send wtxidrelay because otherwise the inv(TX) will be ignored later
+        honest_peer = node.add_p2p_connection(P2PInterface(wtxidrelay=False))
+
+        # 1. Fake orphan is received first. It is missing an input.
+        bad_peer.send_and_ping(msg_tx(tx_orphan_bad_wit))
+
+        # 2. Node requests the missing parent by txid.
+        parent_txid_int = int(tx_parent["txid"], 16)
+        node.bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY)
+        bad_peer.wait_for_getdata([parent_txid_int])
+
+        # 3. Honest peer announces the real child, by txid (this isn't common but the node should
+        # still keep track of it).
+        child_txid_int = int(tx_child["txid"], 16)
+        honest_peer.send_and_ping(msg_inv([CInv(t=MSG_TX, h=child_txid_int)]))
+
+        # 4. The child is requested. Honest peer sends it.
+        node.bumpmocktime(TXREQUEST_TIME_SKIP)
+        honest_peer.wait_for_getdata([child_txid_int])
+        with node.assert_debug_log(["stored orphan tx"]):
+            honest_peer.send_and_ping(msg_tx(tx_child["tx"]))
+
+        # 5. After first parent request times out, the node sends another one for the missing parent
+        # of the real orphan child.
+        node.bumpmocktime(GETDATA_TX_INTERVAL)
+        honest_peer.wait_for_getdata([parent_txid_int])
+        honest_peer.send_and_ping(msg_tx(tx_parent["tx"]))
+
+        # 6. After parent is accepted, orphans should be reconsidered.
+        # The real child should be accepted and the fake one rejected. This may happen in either
+        # order since the message-processing is randomized. If tx_orphan_bad_wit is validated first,
+        # its consensus error leads to disconnection of bad_peer. If tx_child is validated first,
+        # tx_orphan_bad_wit is rejected for txn-same-nonwitness-data-in-mempool (no punishment).
+        node_mempool = node.getrawmempool()
+        assert tx_parent["txid"] in node_mempool
+        assert tx_child["txid"] in node_mempool
+        assert_equal(node.getmempoolentry(tx_child["txid"])["wtxid"], tx_child["wtxid"])
+
+
     def run_test(self):
         self.nodes[0].setmocktime(int(time.time()))
         self.wallet_nonsegwit = MiniWallet(self.nodes[0], mode=MiniWalletMode.RAW_P2PK)
@@ -410,6 +579,9 @@ class OrphanHandlingTest(BitcoinTestFramework):
         self.test_orphans_overlapping_parents()
         self.test_orphan_of_orphan()
         self.test_orphan_inherit_rejection()
+        self.test_same_txid_orphan()
+        self.test_same_txid_orphan_of_orphan()
+        self.test_orphan_txid_inv()
 
 
 if __name__ == '__main__':