1 #!/usr/bin/env python3
2 # Copyright (c) 2020-present 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 """Test mempool descendants/ancestors information update.
6 7 Test mempool update of transaction descendants/ancestors information (count, size)
8 when transactions have been re-added from a disconnected block to the mempool.
9 """
10 from decimal import Decimal
11 from math import ceil
12 import time
13 14 from test_framework.blocktools import create_empty_fork
15 from test_framework.test_framework import BitcoinTestFramework
16 from test_framework.util import assert_equal, assert_greater_than_or_equal, assert_raises_rpc_error
17 from test_framework.wallet import MiniWallet
18 from test_framework.mempool_util import DEFAULT_CLUSTER_LIMIT
19 20 MAX_DISCONNECTED_TX_POOL_BYTES = 20_000_000
21 22 class MempoolUpdateFromBlockTest(BitcoinTestFramework):
23 def set_test_params(self):
24 self.num_nodes = 1
25 self.extra_args = [['-limitclustersize=1000']]
26 27 def trigger_reorg(self, fork_blocks):
28 """Trigger reorg of the fork blocks."""
29 for block in fork_blocks:
30 self.nodes[0].submitblock(block.serialize().hex())
31 assert_equal(self.nodes[0].getbestblockhash(), fork_blocks[-1].hash_hex)
32 33 def transaction_graph_test(self, size, *, n_tx_to_mine, fee=100_000):
34 """Create an acyclic tournament (a type of directed graph) of transactions and use it for testing.
35 36 Keyword arguments:
37 size -- the order N of the tournament which is equal to the number of the created transactions
38 n_tx_to_mine -- the number of transactions that should be mined into a block
39 40 If all of the N created transactions tx[0]..tx[N-1] reside in the mempool,
41 the following holds:
42 the tx[K] transaction:
43 - has N-K descendants (including this one), and
44 - has K+1 ancestors (including this one)
45 46 More details: https://en.wikipedia.org/wiki/Tournament_(graph_theory)
47 """
48 wallet = MiniWallet(self.nodes[0])
49 50 # Prep for fork with empty blocks to not use invalidateblock directly
51 # for reorg case. The rpc has different codepath
52 fork_blocks = create_empty_fork(self.nodes[0], fork_length=7)
53 54 tx_id = []
55 tx_size = []
56 self.log.info('Creating {} transactions...'.format(size))
57 for i in range(0, size):
58 self.log.debug('Preparing transaction #{}...'.format(i))
59 # Prepare inputs.
60 if i == 0:
61 inputs = [wallet.get_utxo()] # let MiniWallet provide a start UTXO
62 else:
63 inputs = []
64 for j, tx in enumerate(tx_id[0:i]):
65 # Transaction tx[K] is a child of each of previous transactions tx[0]..tx[K-1] at their output K-1.
66 vout = i - j - 1
67 inputs.append(wallet.get_utxo(txid=tx_id[j], vout=vout))
68 69 # Prepare outputs.
70 tx_count = i + 1
71 if tx_count < size:
72 # Transaction tx[K] is an ancestor of each of subsequent transactions tx[K+1]..tx[N-1].
73 n_outputs = size - tx_count
74 else:
75 n_outputs = 1
76 77 # Create a new transaction.
78 new_tx = wallet.send_self_transfer_multi(
79 from_node=self.nodes[0],
80 utxos_to_spend=inputs,
81 num_outputs=n_outputs,
82 fee_per_output=ceil(fee / n_outputs)
83 )
84 tx_id.append(new_tx['txid'])
85 tx_size.append(new_tx['tx'].get_vsize())
86 87 if tx_count in n_tx_to_mine:
88 # The created transactions are mined into blocks by batches.
89 self.log.info('The batch of {} transactions has been accepted into the mempool.'.format(len(self.nodes[0].getrawmempool())))
90 self.generate(self.nodes[0], 1)[0]
91 assert_equal(len(self.nodes[0].getrawmempool()), 0)
92 self.log.info('All of the transactions from the current batch have been mined into a block.')
93 elif tx_count == size:
94 # At the end the old fork is submitted to cause reorg, and all of the created
95 # transactions should be re-added from disconnected blocks to the mempool.
96 self.log.info('The last batch of {} transactions has been accepted into the mempool.'.format(len(self.nodes[0].getrawmempool())))
97 start = time.time()
98 # Trigger reorg
99 for block in fork_blocks:
100 self.nodes[0].submitblock(block.serialize().hex())
101 end = time.time()
102 assert_equal(len(self.nodes[0].getrawmempool()), size)
103 self.log.info('All of the recently mined transactions have been re-added into the mempool in {} seconds.'.format(end - start))
104 105 self.log.info('Checking descendants/ancestors properties of all of the in-mempool transactions...')
106 for k, tx in enumerate(tx_id):
107 self.log.debug('Check transaction #{}.'.format(k))
108 entry = self.nodes[0].getmempoolentry(tx)
109 assert_equal(entry['descendantcount'], size - k)
110 assert_equal(entry['descendantsize'], sum(tx_size[k:size]))
111 assert_equal(entry['ancestorcount'], k + 1)
112 assert_equal(entry['ancestorsize'], sum(tx_size[0:(k + 1)]))
113 114 self.generate(self.nodes[0], 1)
115 assert_equal(self.nodes[0].getrawmempool(), [])
116 wallet.rescan_utxos()
117 118 def test_max_disconnect_pool_bytes(self):
119 self.log.info('Creating independent transactions to test MAX_DISCONNECTED_TX_POOL_BYTES limit during reorg')
120 121 # Generate coins for the hundreds of transactions we will make
122 parent_target_vsize = 100_000
123 wallet = MiniWallet(self.nodes[0])
124 self.generate(wallet, (MAX_DISCONNECTED_TX_POOL_BYTES // parent_target_vsize) + 100)
125 126 assert_equal(self.nodes[0].getrawmempool(), [])
127 128 # Set up empty fork blocks ahead of time, needs to be longer than full fork made later
129 fork_blocks = create_empty_fork(self.nodes[0], fork_length=60)
130 131 large_std_txs = []
132 # Add children to ensure they're recursively removed if disconnectpool trimming of parent occurs
133 small_child_txs = []
134 aggregate_serialized_size = 0
135 while aggregate_serialized_size < MAX_DISCONNECTED_TX_POOL_BYTES:
136 # Mine parents in FIFO order via fee ordering
137 large_std_txs.append(wallet.create_self_transfer(target_vsize=parent_target_vsize, fee=Decimal("0.00400000") - (Decimal("0.00001000") * len(large_std_txs))))
138 small_child_txs.append(wallet.create_self_transfer(utxo_to_spend=large_std_txs[-1]['new_utxo']))
139 # Slight underestimate of dynamic cost, so we'll be over during reorg
140 aggregate_serialized_size += len(large_std_txs[-1]["tx"].serialize())
141 142 for large_std_tx in large_std_txs:
143 self.nodes[0].sendrawtransaction(large_std_tx["hex"])
144 145 assert_equal(self.nodes[0].getmempoolinfo()["size"], len(large_std_txs))
146 147 # Mine non-empty chain that will be reorged shortly
148 self.generate(self.nodes[0], len(fork_blocks) - 1)
149 assert_equal(self.nodes[0].getrawmempool(), [])
150 151 # Stick children in mempool, evicted with parent potentially
152 for small_child_tx in small_child_txs:
153 self.nodes[0].sendrawtransaction(small_child_tx["hex"])
154 155 assert_equal(self.nodes[0].getmempoolinfo()["size"], len(small_child_txs))
156 157 # Reorg back before the first block in the series, should drop something
158 # but not all, and any time parent is dropped, child is also removed
159 self.trigger_reorg(fork_blocks=fork_blocks)
160 mempool = self.nodes[0].getrawmempool()
161 # At least one parent must be dropped, but more may be dropped,
162 # depending on the dynamic cost overhead.
163 expected_parent_count = len(large_std_txs) - 1
164 assert_greater_than_or_equal(expected_parent_count * 2, len(mempool))
165 expected_parent_count = len(mempool) // 2
166 167 parent_presence = [tx["txid"] in mempool for tx in large_std_txs]
168 169 # The txns at the end of the list, or most recently confirmed, should have been trimmed
170 assert_equal(parent_presence, [tx["txid"] in mempool for tx in small_child_txs])
171 assert_equal(parent_presence, [True] * expected_parent_count + [False] * (len(large_std_txs) - expected_parent_count))
172 173 def test_chainlimits_exceeded(self):
174 self.log.info('Check that too long chains on reorg are handled')
175 176 wallet = MiniWallet(self.nodes[0])
177 self.generate(wallet, 101)
178 179 assert_equal(self.nodes[0].getrawmempool(), [])
180 181 # Prep fork
182 fork_blocks = create_empty_fork(self.nodes[0])
183 184 # Two higher than descendant count
185 chain = wallet.create_self_transfer_chain(chain_length=DEFAULT_CLUSTER_LIMIT + 2)
186 for tx in chain[:-2]:
187 self.nodes[0].sendrawtransaction(tx["hex"])
188 189 assert_raises_rpc_error(-26, "too-large-cluster", self.nodes[0].sendrawtransaction, chain[-2]["hex"])
190 191 # Mine a block with all but last transaction, non-standardly long chain
192 self.generateblock(self.nodes[0], output="raw(42)", transactions=[tx["hex"] for tx in chain[:-1]])
193 assert_equal(self.nodes[0].getrawmempool(), [])
194 195 # Last tx fits now
196 self.nodes[0].sendrawtransaction(chain[-1]["hex"])
197 198 # Finally, reorg to empty chain to kick everything back into mempool
199 # at normal chain limits
200 for block in fork_blocks:
201 self.nodes[0].submitblock(block.serialize().hex())
202 mempool = self.nodes[0].getrawmempool()
203 assert_equal(set(mempool), set([tx["txid"] for tx in chain[:-2]]))
204 205 def run_test(self):
206 # Mine in batches of 25 to test multi-block reorg under chain limits
207 self.transaction_graph_test(size=DEFAULT_CLUSTER_LIMIT, n_tx_to_mine=[25, 50, 75])
208 209 self.test_max_disconnect_pool_bytes()
210 211 self.test_chainlimits_exceeded()
212 213 if __name__ == '__main__':
214 MempoolUpdateFromBlockTest(__file__).main()
215