p2p_orphan_handling.py
1 #!/usr/bin/env python3 2 # Copyright (c) 2023 The Bitcoin Core developers 3 # Distributed under the MIT software license, see the accompanying 4 # file COPYING or http://www.opensource.org/licenses/mit-license.php. 5 6 import time 7 8 from test_framework.messages import ( 9 CInv, 10 MSG_TX, 11 MSG_WITNESS_TX, 12 MSG_WTX, 13 msg_getdata, 14 msg_inv, 15 msg_notfound, 16 msg_tx, 17 tx_from_hex, 18 ) 19 from test_framework.p2p import ( 20 GETDATA_TX_INTERVAL, 21 NONPREF_PEER_TX_DELAY, 22 OVERLOADED_PEER_TX_DELAY, 23 p2p_lock, 24 P2PTxInvStore, 25 TXID_RELAY_DELAY, 26 ) 27 from test_framework.util import ( 28 assert_equal, 29 ) 30 from test_framework.test_framework import BitcoinTestFramework 31 from test_framework.wallet import ( 32 MiniWallet, 33 MiniWalletMode, 34 ) 35 36 # Time to bump forward (using setmocktime) before waiting for the node to send getdata(tx) in response 37 # to an inv(tx), in seconds. This delay includes all possible delays + 1, so it should only be used 38 # when the value of the delay is not interesting. If we want to test that the node waits x seconds 39 # for one peer and y seconds for another, use specific values instead. 40 TXREQUEST_TIME_SKIP = NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY + OVERLOADED_PEER_TX_DELAY + 1 41 42 def cleanup(func): 43 # Time to fastfoward (using setmocktime) in between subtests to ensure they do not interfere with 44 # one another, in seconds. Equal to 12 hours, which is enough to expire anything that may exist 45 # (though nothing should since state should be cleared) in p2p data structures. 46 LONG_TIME_SKIP = 12 * 60 * 60 47 48 def wrapper(self): 49 try: 50 func(self) 51 finally: 52 # Clear mempool 53 self.generate(self.nodes[0], 1) 54 self.nodes[0].disconnect_p2ps() 55 self.nodes[0].bumpmocktime(LONG_TIME_SKIP) 56 return wrapper 57 58 class PeerTxRelayer(P2PTxInvStore): 59 """A P2PTxInvStore that also remembers all of the getdata and tx messages it receives.""" 60 def __init__(self): 61 super().__init__() 62 self._tx_received = [] 63 self._getdata_received = [] 64 65 @property 66 def tx_received(self): 67 with p2p_lock: 68 return self._tx_received 69 70 @property 71 def getdata_received(self): 72 with p2p_lock: 73 return self._getdata_received 74 75 def on_tx(self, message): 76 self._tx_received.append(message) 77 78 def on_getdata(self, message): 79 self._getdata_received.append(message) 80 81 def wait_for_parent_requests(self, txids): 82 """Wait for requests for missing parents by txid with witness data (MSG_WITNESS_TX or 83 WitnessTx). Requires that the getdata message match these txids exactly; all txids must be 84 requested and no additional requests are allowed.""" 85 def test_function(): 86 last_getdata = self.last_message.get('getdata') 87 if not last_getdata: 88 return False 89 return len(last_getdata.inv) == len(txids) and all([item.type == MSG_WITNESS_TX and item.hash in txids for item in last_getdata.inv]) 90 self.wait_until(test_function, timeout=10) 91 92 def assert_no_immediate_response(self, message): 93 """Check that the node does not immediately respond to this message with any of getdata, 94 inv, tx. The node may respond later. 95 """ 96 prev_lastmessage = self.last_message 97 self.send_and_ping(message) 98 after_lastmessage = self.last_message 99 for msgtype in ["getdata", "inv", "tx"]: 100 if msgtype not in prev_lastmessage: 101 assert msgtype not in after_lastmessage 102 else: 103 assert_equal(prev_lastmessage[msgtype], after_lastmessage[msgtype]) 104 105 def assert_never_requested(self, txhash): 106 """Check that the node has never sent us a getdata for this hash (int type)""" 107 for getdata in self.getdata_received: 108 for request in getdata.inv: 109 assert request.hash != txhash 110 111 class OrphanHandlingTest(BitcoinTestFramework): 112 def set_test_params(self): 113 self.num_nodes = 1 114 self.extra_args = [[]] 115 116 def create_parent_and_child(self): 117 """Create package with 1 parent and 1 child, normal fees (no cpfp).""" 118 parent = self.wallet.create_self_transfer() 119 child = self.wallet.create_self_transfer(utxo_to_spend=parent['new_utxo']) 120 return child["tx"].getwtxid(), child["tx"], parent["tx"] 121 122 def relay_transaction(self, peer, tx): 123 """Relay transaction using MSG_WTX""" 124 wtxid = int(tx.getwtxid(), 16) 125 peer.send_and_ping(msg_inv([CInv(t=MSG_WTX, h=wtxid)])) 126 self.nodes[0].bumpmocktime(TXREQUEST_TIME_SKIP) 127 peer.wait_for_getdata([wtxid]) 128 peer.send_and_ping(msg_tx(tx)) 129 130 @cleanup 131 def test_arrival_timing_orphan(self): 132 self.log.info("Test missing parents that arrive during delay are not requested") 133 node = self.nodes[0] 134 tx_parent_arrives = self.wallet.create_self_transfer() 135 tx_parent_doesnt_arrive = self.wallet.create_self_transfer() 136 # Fake orphan spends nonexistent outputs of the two parents 137 tx_fake_orphan = self.wallet.create_self_transfer_multi(utxos_to_spend=[ 138 {"txid": tx_parent_doesnt_arrive["txid"], "vout": 10, "value": tx_parent_doesnt_arrive["new_utxo"]["value"]}, 139 {"txid": tx_parent_arrives["txid"], "vout": 10, "value": tx_parent_arrives["new_utxo"]["value"]} 140 ]) 141 142 peer_spy = node.add_p2p_connection(PeerTxRelayer()) 143 peer_normal = node.add_p2p_connection(PeerTxRelayer()) 144 # This transaction is an orphan because it is missing inputs. It is a "fake" orphan that the 145 # spy peer has crafted to learn information about tx_parent_arrives even though it isn't 146 # able to spend a real output of it, but it could also just be a normal, real child tx. 147 # The node should not immediately respond with a request for orphan parents. 148 # Also, no request should be sent later because it will be resolved by 149 # the time the request is scheduled to be sent. 150 peer_spy.assert_no_immediate_response(msg_tx(tx_fake_orphan["tx"])) 151 152 # Node receives transaction. It attempts to obfuscate the exact timing at which this 153 # transaction entered its mempool. Send unsolicited because otherwise we need to wait for 154 # request delays. 155 peer_normal.send_and_ping(msg_tx(tx_parent_arrives["tx"])) 156 assert tx_parent_arrives["txid"] in node.getrawmempool() 157 158 # Spy peer should not be able to query the node for the parent yet, since it hasn't been 159 # announced / insufficient time has elapsed. 160 parent_inv = CInv(t=MSG_WTX, h=int(tx_parent_arrives["tx"].getwtxid(), 16)) 161 assert_equal(len(peer_spy.get_invs()), 0) 162 peer_spy.assert_no_immediate_response(msg_getdata([parent_inv])) 163 164 # Request would be scheduled with this delay because it is not a preferred relay peer. 165 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY) 166 peer_spy.assert_never_requested(int(tx_parent_arrives["txid"], 16)) 167 peer_spy.assert_never_requested(int(tx_parent_doesnt_arrive["txid"], 16)) 168 # Request would be scheduled with this delay because it is by txid. 169 self.nodes[0].bumpmocktime(TXID_RELAY_DELAY) 170 peer_spy.wait_for_parent_requests([int(tx_parent_doesnt_arrive["txid"], 16)]) 171 peer_spy.assert_never_requested(int(tx_parent_arrives["txid"], 16)) 172 173 @cleanup 174 def test_orphan_rejected_parents_exceptions(self): 175 node = self.nodes[0] 176 peer1 = node.add_p2p_connection(PeerTxRelayer()) 177 peer2 = node.add_p2p_connection(PeerTxRelayer()) 178 179 self.log.info("Test orphan handling when a nonsegwit parent is known to be invalid") 180 parent_low_fee_nonsegwit = self.wallet_nonsegwit.create_self_transfer(fee_rate=0) 181 assert_equal(parent_low_fee_nonsegwit["txid"], parent_low_fee_nonsegwit["tx"].getwtxid()) 182 parent_other = self.wallet_nonsegwit.create_self_transfer() 183 child_nonsegwit = self.wallet_nonsegwit.create_self_transfer_multi( 184 utxos_to_spend=[parent_other["new_utxo"], parent_low_fee_nonsegwit["new_utxo"]]) 185 186 # Relay the parent. It should be rejected because it pays 0 fees. 187 self.relay_transaction(peer1, parent_low_fee_nonsegwit["tx"]) 188 assert parent_low_fee_nonsegwit["txid"] not in node.getrawmempool() 189 190 # Relay the child. It should not be accepted because it has missing inputs. 191 # Its parent should not be requested because its hash (txid == wtxid) has been added to the rejection filter. 192 with node.assert_debug_log(['not keeping orphan with rejected parents {}'.format(child_nonsegwit["txid"])]): 193 self.relay_transaction(peer2, child_nonsegwit["tx"]) 194 assert child_nonsegwit["txid"] not in node.getrawmempool() 195 196 # No parents are requested. 197 self.nodes[0].bumpmocktime(GETDATA_TX_INTERVAL) 198 peer1.assert_never_requested(int(parent_other["txid"], 16)) 199 peer2.assert_never_requested(int(parent_other["txid"], 16)) 200 peer2.assert_never_requested(int(parent_low_fee_nonsegwit["txid"], 16)) 201 202 self.log.info("Test orphan handling when a segwit parent was invalid but may be retried with another witness") 203 parent_low_fee = self.wallet.create_self_transfer(fee_rate=0) 204 child_low_fee = self.wallet.create_self_transfer(utxo_to_spend=parent_low_fee["new_utxo"]) 205 206 # Relay the low fee parent. It should not be accepted. 207 self.relay_transaction(peer1, parent_low_fee["tx"]) 208 assert parent_low_fee["txid"] not in node.getrawmempool() 209 210 # Relay the child. It should not be accepted because it has missing inputs. 211 self.relay_transaction(peer2, child_low_fee["tx"]) 212 assert child_low_fee["txid"] not in node.getrawmempool() 213 214 # The parent should be requested because even though the txid commits to the fee, it doesn't 215 # commit to the feerate. Delayed because it's by txid and this is not a preferred relay peer. 216 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY) 217 peer2.wait_for_getdata([int(parent_low_fee["tx"].rehash(), 16)]) 218 219 self.log.info("Test orphan handling when a parent was previously downloaded with witness stripped") 220 parent_normal = self.wallet.create_self_transfer() 221 parent1_witness_stripped = tx_from_hex(parent_normal["tx"].serialize_without_witness().hex()) 222 child_invalid_witness = self.wallet.create_self_transfer(utxo_to_spend=parent_normal["new_utxo"]) 223 224 # Relay the parent with witness stripped. It should not be accepted. 225 self.relay_transaction(peer1, parent1_witness_stripped) 226 assert_equal(parent_normal["txid"], parent1_witness_stripped.rehash()) 227 assert parent1_witness_stripped.rehash() not in node.getrawmempool() 228 229 # Relay the child. It should not be accepted because it has missing inputs. 230 self.relay_transaction(peer2, child_invalid_witness["tx"]) 231 assert child_invalid_witness["txid"] not in node.getrawmempool() 232 233 # The parent should be requested since the unstripped wtxid would differ. Delayed because 234 # it's by txid and this is not a preferred relay peer. 235 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY) 236 peer2.wait_for_getdata([int(parent_normal["tx"].rehash(), 16)]) 237 238 # parent_normal can be relayed again even though parent1_witness_stripped was rejected 239 self.relay_transaction(peer1, parent_normal["tx"]) 240 assert_equal(set(node.getrawmempool()), set([parent_normal["txid"], child_invalid_witness["txid"]])) 241 242 @cleanup 243 def test_orphan_multiple_parents(self): 244 node = self.nodes[0] 245 peer = node.add_p2p_connection(PeerTxRelayer()) 246 247 self.log.info("Test orphan parent requests with a mixture of confirmed, in-mempool and missing parents") 248 # This UTXO confirmed a long time ago. 249 utxo_conf_old = self.wallet.send_self_transfer(from_node=node)["new_utxo"] 250 txid_conf_old = utxo_conf_old["txid"] 251 self.generate(self.wallet, 10) 252 253 # Create a fake reorg to trigger BlockDisconnected, which resets the rolling bloom filter. 254 # The alternative is to mine thousands of transactions to push it out of the filter. 255 last_block = node.getbestblockhash() 256 node.invalidateblock(last_block) 257 node.preciousblock(last_block) 258 node.syncwithvalidationinterfacequeue() 259 260 # This UTXO confirmed recently. 261 utxo_conf_recent = self.wallet.send_self_transfer(from_node=node)["new_utxo"] 262 self.generate(node, 1) 263 264 # This UTXO is unconfirmed and in the mempool. 265 assert_equal(len(node.getrawmempool()), 0) 266 mempool_tx = self.wallet.send_self_transfer(from_node=node) 267 utxo_unconf_mempool = mempool_tx["new_utxo"] 268 269 # This UTXO is unconfirmed and missing. 270 missing_tx = self.wallet.create_self_transfer() 271 utxo_unconf_missing = missing_tx["new_utxo"] 272 assert missing_tx["txid"] not in node.getrawmempool() 273 274 orphan = self.wallet.create_self_transfer_multi(utxos_to_spend=[utxo_conf_old, 275 utxo_conf_recent, utxo_unconf_mempool, utxo_unconf_missing]) 276 277 self.relay_transaction(peer, orphan["tx"]) 278 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY) 279 peer.sync_with_ping() 280 assert_equal(len(peer.last_message["getdata"].inv), 2) 281 peer.wait_for_parent_requests([int(txid_conf_old, 16), int(missing_tx["txid"], 16)]) 282 283 # Even though the peer would send a notfound for the "old" confirmed transaction, the node 284 # doesn't give up on the orphan. Once all of the missing parents are received, it should be 285 # submitted to mempool. 286 peer.send_message(msg_notfound(vec=[CInv(MSG_WITNESS_TX, int(txid_conf_old, 16))])) 287 peer.send_and_ping(msg_tx(missing_tx["tx"])) 288 peer.sync_with_ping() 289 assert_equal(node.getmempoolentry(orphan["txid"])["ancestorcount"], 3) 290 291 @cleanup 292 def test_orphans_overlapping_parents(self): 293 node = self.nodes[0] 294 # In the process of relaying inflight_parent_AB 295 peer_txrequest = node.add_p2p_connection(PeerTxRelayer()) 296 # Sends the orphans 297 peer_orphans = node.add_p2p_connection(PeerTxRelayer()) 298 299 confirmed_utxos = [self.wallet_nonsegwit.get_utxo() for _ in range(4)] 300 assert all([utxo["confirmations"] > 0 for utxo in confirmed_utxos]) 301 self.log.info("Test handling of multiple orphans with missing parents that are already being requested") 302 # Parent of child_A only 303 missing_parent_A = self.wallet_nonsegwit.create_self_transfer(utxo_to_spend=confirmed_utxos[0]) 304 # Parents of child_A and child_B 305 missing_parent_AB = self.wallet_nonsegwit.create_self_transfer(utxo_to_spend=confirmed_utxos[1]) 306 inflight_parent_AB = self.wallet_nonsegwit.create_self_transfer(utxo_to_spend=confirmed_utxos[2]) 307 # Parent of child_B only 308 missing_parent_B = self.wallet_nonsegwit.create_self_transfer(utxo_to_spend=confirmed_utxos[3]) 309 child_A = self.wallet_nonsegwit.create_self_transfer_multi( 310 utxos_to_spend=[missing_parent_A["new_utxo"], missing_parent_AB["new_utxo"], inflight_parent_AB["new_utxo"]] 311 ) 312 child_B = self.wallet_nonsegwit.create_self_transfer_multi( 313 utxos_to_spend=[missing_parent_B["new_utxo"], missing_parent_AB["new_utxo"], inflight_parent_AB["new_utxo"]] 314 ) 315 316 # The wtxid and txid need to be the same for the node to recognize that the missing input 317 # and in-flight request for inflight_parent_AB are the same transaction. 318 assert_equal(inflight_parent_AB["txid"], inflight_parent_AB["tx"].getwtxid()) 319 320 # Announce inflight_parent_AB and wait for getdata 321 peer_txrequest.send_and_ping(msg_inv([CInv(t=MSG_WTX, h=int(inflight_parent_AB["tx"].getwtxid(), 16))])) 322 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY) 323 peer_txrequest.wait_for_getdata([int(inflight_parent_AB["tx"].getwtxid(), 16)]) 324 325 self.log.info("Test that the node does not request a parent if it has an in-flight txrequest") 326 # Relay orphan child_A 327 self.relay_transaction(peer_orphans, child_A["tx"]) 328 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY) 329 # There are 3 missing parents. missing_parent_A and missing_parent_AB should be requested. 330 # But inflight_parent_AB should not, because there is already an in-flight request for it. 331 peer_orphans.wait_for_parent_requests([int(missing_parent_A["txid"], 16), int(missing_parent_AB["txid"], 16)]) 332 333 self.log.info("Test that the node does not request a parent if it has an in-flight orphan parent request") 334 # Relay orphan child_B 335 self.relay_transaction(peer_orphans, child_B["tx"]) 336 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY) 337 # Only missing_parent_B should be requested. Not inflight_parent_AB or missing_parent_AB 338 # because they are already being requested from peer_txrequest and peer_orphans respectively. 339 peer_orphans.wait_for_parent_requests([int(missing_parent_B["txid"], 16)]) 340 peer_orphans.assert_never_requested(int(inflight_parent_AB["txid"], 16)) 341 342 @cleanup 343 def test_orphan_of_orphan(self): 344 node = self.nodes[0] 345 peer = node.add_p2p_connection(PeerTxRelayer()) 346 347 self.log.info("Test handling of an orphan with a parent who is another orphan") 348 missing_grandparent = self.wallet_nonsegwit.create_self_transfer() 349 missing_parent_orphan = self.wallet_nonsegwit.create_self_transfer(utxo_to_spend=missing_grandparent["new_utxo"]) 350 missing_parent = self.wallet_nonsegwit.create_self_transfer() 351 orphan = self.wallet_nonsegwit.create_self_transfer_multi(utxos_to_spend=[missing_parent["new_utxo"], missing_parent_orphan["new_utxo"]]) 352 353 # The node should put missing_parent_orphan into the orphanage and request missing_grandparent 354 self.relay_transaction(peer, missing_parent_orphan["tx"]) 355 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY) 356 peer.wait_for_parent_requests([int(missing_grandparent["txid"], 16)]) 357 358 # The node should put the orphan into the orphanage and request missing_parent, skipping 359 # missing_parent_orphan because it already has it in the orphanage. 360 self.relay_transaction(peer, orphan["tx"]) 361 self.nodes[0].bumpmocktime(NONPREF_PEER_TX_DELAY + TXID_RELAY_DELAY) 362 peer.wait_for_parent_requests([int(missing_parent["txid"], 16)]) 363 364 @cleanup 365 def test_orphan_inherit_rejection(self): 366 node = self.nodes[0] 367 peer1 = node.add_p2p_connection(PeerTxRelayer()) 368 peer2 = node.add_p2p_connection(PeerTxRelayer()) 369 peer3 = node.add_p2p_connection(PeerTxRelayer()) 370 371 self.log.info("Test that an orphan with rejected parents, along with any descendants, cannot be retried with an alternate witness") 372 parent_low_fee_nonsegwit = self.wallet_nonsegwit.create_self_transfer(fee_rate=0) 373 assert_equal(parent_low_fee_nonsegwit["txid"], parent_low_fee_nonsegwit["tx"].getwtxid()) 374 child = self.wallet.create_self_transfer(utxo_to_spend=parent_low_fee_nonsegwit["new_utxo"]) 375 grandchild = self.wallet.create_self_transfer(utxo_to_spend=child["new_utxo"]) 376 assert child["txid"] != child["tx"].getwtxid() 377 assert grandchild["txid"] != grandchild["tx"].getwtxid() 378 379 # Relay the parent. It should be rejected because it pays 0 fees. 380 self.relay_transaction(peer1, parent_low_fee_nonsegwit["tx"]) 381 382 # Relay the child. It should be rejected for having missing parents, and this rejection is 383 # cached by txid and wtxid. 384 with node.assert_debug_log(['not keeping orphan with rejected parents {}'.format(child["txid"])]): 385 self.relay_transaction(peer1, child["tx"]) 386 assert_equal(0, len(node.getrawmempool())) 387 peer1.assert_never_requested(parent_low_fee_nonsegwit["txid"]) 388 389 # Grandchild should also not be kept in orphanage because its parent has been rejected. 390 with node.assert_debug_log(['not keeping orphan with rejected parents {}'.format(grandchild["txid"])]): 391 self.relay_transaction(peer2, grandchild["tx"]) 392 assert_equal(0, len(node.getrawmempool())) 393 peer2.assert_never_requested(child["txid"]) 394 peer2.assert_never_requested(child["tx"].getwtxid()) 395 396 # The child should never be requested, even if announced again with potentially different witness. 397 peer3.send_and_ping(msg_inv([CInv(t=MSG_TX, h=int(child["txid"], 16))])) 398 self.nodes[0].bumpmocktime(TXREQUEST_TIME_SKIP) 399 peer3.assert_never_requested(child["txid"]) 400 401 def run_test(self): 402 self.nodes[0].setmocktime(int(time.time())) 403 self.wallet_nonsegwit = MiniWallet(self.nodes[0], mode=MiniWalletMode.RAW_P2PK) 404 self.generate(self.wallet_nonsegwit, 10) 405 self.wallet = MiniWallet(self.nodes[0]) 406 self.generate(self.wallet, 160) 407 self.test_arrival_timing_orphan() 408 self.test_orphan_rejected_parents_exceptions() 409 self.test_orphan_multiple_parents() 410 self.test_orphans_overlapping_parents() 411 self.test_orphan_of_orphan() 412 self.test_orphan_inherit_rejection() 413 414 415 if __name__ == '__main__': 416 OrphanHandlingTest().main()