1  #!/usr/bin/env python3
  2  # Copyright (c) 2020-2022 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 math import ceil
 11  import time
 12  
 13  from test_framework.test_framework import BitcoinTestFramework
 14  from test_framework.util import assert_equal
 15  from test_framework.wallet import MiniWallet
 16  
 17  
 18  class MempoolUpdateFromBlockTest(BitcoinTestFramework):
 19      def set_test_params(self):
 20          self.num_nodes = 1
 21          self.extra_args = [['-limitdescendantsize=1000', '-limitancestorsize=1000', '-limitancestorcount=100']]
 22  
 23      def transaction_graph_test(self, size, n_tx_to_mine=None, fee=100_000):
 24          """Create an acyclic tournament (a type of directed graph) of transactions and use it for testing.
 25  
 26          Keyword arguments:
 27          size -- the order N of the tournament which is equal to the number of the created transactions
 28          n_tx_to_mine -- the number of transaction that should be mined into a block
 29  
 30          If all of the N created transactions tx[0]..tx[N-1] reside in the mempool,
 31          the following holds:
 32              the tx[K] transaction:
 33              - has N-K descendants (including this one), and
 34              - has K+1 ancestors (including this one)
 35  
 36          More details: https://en.wikipedia.org/wiki/Tournament_(graph_theory)
 37          """
 38          wallet = MiniWallet(self.nodes[0])
 39          first_block_hash = ''
 40          tx_id = []
 41          tx_size = []
 42          self.log.info('Creating {} transactions...'.format(size))
 43          for i in range(0, size):
 44              self.log.debug('Preparing transaction #{}...'.format(i))
 45              # Prepare inputs.
 46              if i == 0:
 47                  inputs = [wallet.get_utxo()]  # let MiniWallet provide a start UTXO
 48              else:
 49                  inputs = []
 50                  for j, tx in enumerate(tx_id[0:i]):
 51                      # Transaction tx[K] is a child of each of previous transactions tx[0]..tx[K-1] at their output K-1.
 52                      vout = i - j - 1
 53                      inputs.append(wallet.get_utxo(txid=tx_id[j], vout=vout))
 54  
 55              # Prepare outputs.
 56              tx_count = i + 1
 57              if tx_count < size:
 58                  # Transaction tx[K] is an ancestor of each of subsequent transactions tx[K+1]..tx[N-1].
 59                  n_outputs = size - tx_count
 60              else:
 61                  n_outputs = 1
 62  
 63              # Create a new transaction.
 64              new_tx = wallet.send_self_transfer_multi(
 65                  from_node=self.nodes[0],
 66                  utxos_to_spend=inputs,
 67                  num_outputs=n_outputs,
 68                  fee_per_output=ceil(fee / n_outputs)
 69              )
 70              tx_id.append(new_tx['txid'])
 71              tx_size.append(new_tx['tx'].get_vsize())
 72  
 73              if tx_count in n_tx_to_mine:
 74                  # The created transactions are mined into blocks by batches.
 75                  self.log.info('The batch of {} transactions has been accepted into the mempool.'.format(len(self.nodes[0].getrawmempool())))
 76                  block_hash = self.generate(self.nodes[0], 1)[0]
 77                  if not first_block_hash:
 78                      first_block_hash = block_hash
 79                  assert_equal(len(self.nodes[0].getrawmempool()), 0)
 80                  self.log.info('All of the transactions from the current batch have been mined into a block.')
 81              elif tx_count == size:
 82                  # At the end all of the mined blocks are invalidated, and all of the created
 83                  # transactions should be re-added from disconnected blocks to the mempool.
 84                  self.log.info('The last batch of {} transactions has been accepted into the mempool.'.format(len(self.nodes[0].getrawmempool())))
 85                  start = time.time()
 86                  self.nodes[0].invalidateblock(first_block_hash)
 87                  end = time.time()
 88                  assert_equal(len(self.nodes[0].getrawmempool()), size)
 89                  self.log.info('All of the recently mined transactions have been re-added into the mempool in {} seconds.'.format(end - start))
 90  
 91          self.log.info('Checking descendants/ancestors properties of all of the in-mempool transactions...')
 92          for k, tx in enumerate(tx_id):
 93              self.log.debug('Check transaction #{}.'.format(k))
 94              entry = self.nodes[0].getmempoolentry(tx)
 95              assert_equal(entry['descendantcount'], size - k)
 96              assert_equal(entry['descendantsize'], sum(tx_size[k:size]))
 97              assert_equal(entry['ancestorcount'], k + 1)
 98              assert_equal(entry['ancestorsize'], sum(tx_size[0:(k + 1)]))
 99  
100      def run_test(self):
101          # Use batch size limited by DEFAULT_ANCESTOR_LIMIT = 25 to not fire "too many unconfirmed parents" error.
102          self.transaction_graph_test(size=100, n_tx_to_mine=[25, 50, 75])
103  
104  
105  if __name__ == '__main__':
106      MempoolUpdateFromBlockTest().main()