Inside Bitcoin

1// Copyright (c) 2023-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <bench/bench.h>
6#include <kernel/disconnected_transactions.h>
7#include <primitives/block.h>
8#include <primitives/transaction.h>
9#include <script/script.h>
10#include <test/util/setup_common.h>
11#include <util/check.h>
12
13#include <algorithm>
14#include <cstddef>
15#include <cstdint>
16#include <iterator>
17#include <vector>
18
19constexpr size_t BLOCK_VTX_COUNT{4000};
20constexpr size_t BLOCK_VTX_COUNT_10PERCENT{400};
21
22using BlockTxns = decltype(CBlock::vtx);
23
24/** Reorg where 1 block is disconnected and 2 blocks are connected. */
25struct ReorgTxns {
26    /** Disconnected block. */
27    BlockTxns disconnected_txns;
28    /** First connected block. */
29    BlockTxns connected_txns_1;
30    /** Second connected block, new chain tip. Has no overlap with disconnected_txns. */
31    BlockTxns connected_txns_2;
32    /** Transactions shared between disconnected_txns and connected_txns_1. */
33    size_t num_shared;
34};
35
36static BlockTxns CreateRandomTransactions(size_t num_txns)
37{
38    // Ensure every transaction has a different txid by having each one spend the previous one.
39    static Txid prevout_hash{};
40
41    BlockTxns txns;
42    txns.reserve(num_txns);
43    // Simplest spk for every tx
44    CScript spk = CScript() << OP_TRUE;
45    for (uint32_t i = 0; i < num_txns; ++i) {
46        CMutableTransaction tx;
47        tx.vin.emplace_back(COutPoint{prevout_hash, 0});
48        tx.vout.emplace_back(CENT, spk);
49        auto ptx{MakeTransactionRef(tx)};
50        txns.emplace_back(ptx);
51        prevout_hash = ptx->GetHash();
52    }
53    return txns;
54}
55
56/** Creates blocks for a Reorg, each with BLOCK_VTX_COUNT transactions. Between the disconnected
57 * block and the first connected block, there will be num_not_shared transactions that are
58 * different, and all other transactions the exact same. The second connected block has all unique
59 * transactions. This is to simulate a reorg in which all but num_not_shared transactions are
60 * confirmed in the new chain. */
61static ReorgTxns CreateBlocks(size_t num_not_shared)
62{
63    auto num_shared{BLOCK_VTX_COUNT - num_not_shared};
64    const auto shared_txns{CreateRandomTransactions(/*num_txns=*/num_shared)};
65
66    // Create different sets of transactions...
67    auto disconnected_block_txns{CreateRandomTransactions(/*num_txns=*/num_not_shared)};
68    std::copy(shared_txns.begin(), shared_txns.end(), std::back_inserter(disconnected_block_txns));
69
70    auto connected_block_txns{CreateRandomTransactions(/*num_txns=*/num_not_shared)};
71    std::copy(shared_txns.begin(), shared_txns.end(), std::back_inserter(connected_block_txns));
72
73    assert(disconnected_block_txns.size() == BLOCK_VTX_COUNT);
74    assert(connected_block_txns.size() == BLOCK_VTX_COUNT);
75
76    return ReorgTxns{/*disconnected_txns=*/disconnected_block_txns,
77                     /*connected_txns_1=*/connected_block_txns,
78                     /*connected_txns_2=*/CreateRandomTransactions(BLOCK_VTX_COUNT),
79                     /*num_shared=*/num_shared};
80}
81
82static void Reorg(const ReorgTxns& reorg)
83{
84    DisconnectedBlockTransactions disconnectpool{MAX_DISCONNECTED_TX_POOL_BYTES};
85    // Disconnect block
86    const auto evicted = disconnectpool.AddTransactionsFromBlock(reorg.disconnected_txns);
87    assert(evicted.empty());
88
89    // Connect first block
90    disconnectpool.removeForBlock(reorg.connected_txns_1);
91    // Connect new tip
92    disconnectpool.removeForBlock(reorg.connected_txns_2);
93
94    // Sanity Check
95    assert(disconnectpool.size() == BLOCK_VTX_COUNT - reorg.num_shared);
96
97    disconnectpool.clear();
98}
99
100/** Add transactions from DisconnectedBlockTransactions, remove all but one (the disconnected
101 * block's coinbase transaction) of them, and then pop from the front until empty. This is a reorg
102 * in which all of the non-coinbase transactions in the disconnected chain also exist in the new
103 * chain. */
104static void AddAndRemoveDisconnectedBlockTransactionsAll(benchmark::Bench& bench)
105{
106    const auto chains{CreateBlocks(/*num_not_shared=*/1)};
107    assert(chains.num_shared == BLOCK_VTX_COUNT - 1);
108
109    bench.minEpochIterations(10).run([&]() {
110        Reorg(chains);
111    });
112}
113
114/** Add transactions from DisconnectedBlockTransactions, remove 90% of them, and then pop from the front until empty. */
115static void AddAndRemoveDisconnectedBlockTransactions90(benchmark::Bench& bench)
116{
117    const auto chains{CreateBlocks(/*num_not_shared=*/BLOCK_VTX_COUNT_10PERCENT)};
118    assert(chains.num_shared == BLOCK_VTX_COUNT - BLOCK_VTX_COUNT_10PERCENT);
119
120    bench.minEpochIterations(10).run([&]() {
121        Reorg(chains);
122    });
123}
124
125/** Add transactions from DisconnectedBlockTransactions, remove 10% of them, and then pop from the front until empty. */
126static void AddAndRemoveDisconnectedBlockTransactions10(benchmark::Bench& bench)
127{
128    const auto chains{CreateBlocks(/*num_not_shared=*/BLOCK_VTX_COUNT - BLOCK_VTX_COUNT_10PERCENT)};
129    assert(chains.num_shared == BLOCK_VTX_COUNT_10PERCENT);
130
131    bench.minEpochIterations(10).run([&]() {
132        Reorg(chains);
133    });
134}
135
136BENCHMARK(AddAndRemoveDisconnectedBlockTransactionsAll);
137BENCHMARK(AddAndRemoveDisconnectedBlockTransactions90);
138BENCHMARK(AddAndRemoveDisconnectedBlockTransactions10);
139