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 https://opensource.org/license/mit/.
4
5#include <txgraph.h>
6
7#include <random.h>
8
9#include <boost/test/unit_test.hpp>
10
11#include <memory>
12#include <vector>
13
14BOOST_AUTO_TEST_SUITE(txgraph_tests)
15
16namespace {
17
18/** The number used as acceptable_cost argument in these tests. High enough that everything
19 *  should be optimal, always. */
20constexpr uint64_t HIGH_ACCEPTABLE_COST = 100'000'000;
21
22std::strong_ordering PointerComparator(const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept
23{
24    return (&a) <=> (&b);
25}
26
27} // namespace
28
29BOOST_AUTO_TEST_CASE(txgraph_trim_zigzag)
30{
31    // T     T     T     T     T     T     T     T     T     T     T     T     T     T (50 T's)
32    //  \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   /
33    //   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /
34    //    B     B     B     B     B     B     B     B     B     B     B     B     B    (49 B's)
35    //
36    /** The maximum cluster count used in this test. */
37    static constexpr int MAX_CLUSTER_COUNT = 50;
38    /** The number of "bottom" transactions, which are in the mempool already. */
39    static constexpr int NUM_BOTTOM_TX = 49;
40    /** The number of "top" transactions, which come from disconnected blocks. These are re-added
41     *  to the mempool and, while connecting them to the already-in-mempool transactions, we
42     *   discover the resulting cluster is oversized. */
43    static constexpr int NUM_TOP_TX = 50;
44    /** The total number of transactions in the test. */
45    static constexpr int NUM_TOTAL_TX = NUM_BOTTOM_TX + NUM_TOP_TX;
46    static_assert(NUM_TOTAL_TX > MAX_CLUSTER_COUNT);
47    /** Set a very large cluster size limit so that only the count limit is triggered. */
48    static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
49
50    // Create a new graph for the test.
51    auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, HIGH_ACCEPTABLE_COST, PointerComparator);
52
53    // Add all transactions and store their Refs.
54    std::vector<TxGraph::Ref> refs;
55    refs.reserve(NUM_TOTAL_TX);
56    // First all bottom transactions: the i'th bottom transaction is at position i.
57    for (unsigned int i = 0; i < NUM_BOTTOM_TX; ++i) {
58        graph->AddTransaction(refs.emplace_back(), FeePerWeight{200 - i, 100});
59    }
60    // Then all top transactions: the i'th top transaction is at position NUM_BOTTOM_TX + i.
61    for (unsigned int i = 0; i < NUM_TOP_TX; ++i) {
62        graph->AddTransaction(refs.emplace_back(), FeePerWeight{100 - i, 100});
63    }
64
65    // Create the zigzag dependency structure.
66    // Each transaction in the bottom row depends on two adjacent transactions from the top row.
67    graph->SanityCheck();
68    for (unsigned int i = 0; i < NUM_BOTTOM_TX; ++i) {
69        graph->AddDependency(/*parent=*/refs[NUM_BOTTOM_TX + i], /*child=*/refs[i]);
70        graph->AddDependency(/*parent=*/refs[NUM_BOTTOM_TX + i + 1], /*child=*/refs[i]);
71    }
72
73    // Check that the graph is now oversized. This also forces the graph to
74    // group clusters and compute the oversized status.
75    graph->SanityCheck();
76    BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), NUM_TOTAL_TX);
77    BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP));
78
79    // Call Trim() to remove transactions and bring the cluster back within limits.
80    auto removed_refs = graph->Trim();
81    graph->SanityCheck();
82    BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
83
84    // We only need to trim the middle bottom transaction to end up with 2 clusters each within cluster limits.
85    BOOST_CHECK_EQUAL(removed_refs.size(), 1);
86    BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), MAX_CLUSTER_COUNT * 2 - 2);
87    for (unsigned int i = 0; i < refs.size(); ++i) {
88        BOOST_CHECK_EQUAL(graph->Exists(refs[i], TxGraph::Level::TOP), i != (NUM_BOTTOM_TX / 2));
89    }
90}
91
92BOOST_AUTO_TEST_CASE(txgraph_trim_flower)
93{
94    // We will build an oversized flower-shaped graph: all transactions are spent by 1 descendant.
95    //
96    //   T   T   T   T   T   T   T   T (100 T's)
97    //   |   |   |   |   |   |   |   |
98    //   |   |   |   |   |   |   |   |
99    //   \---+---+---+-+-+---+---+---/
100    //                 |
101    //                 B (1 B)
102    //
103    /** The maximum cluster count used in this test. */
104    static constexpr int MAX_CLUSTER_COUNT = 50;
105    /** The number of "top" transactions, which come from disconnected blocks. These are re-added
106     *  to the mempool and, connecting them to the already-in-mempool transactions, we discover the
107     *  resulting cluster is oversized. */
108    static constexpr int NUM_TOP_TX = MAX_CLUSTER_COUNT * 2;
109    /** The total number of transactions in this test. */
110    static constexpr int NUM_TOTAL_TX = NUM_TOP_TX + 1;
111    /** Set a very large cluster size limit so that only the count limit is triggered. */
112    static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
113
114    auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, HIGH_ACCEPTABLE_COST, PointerComparator);
115
116    // Add all transactions and store their Refs.
117    std::vector<TxGraph::Ref> refs;
118    refs.reserve(NUM_TOTAL_TX);
119
120    // Add all transactions. They are in individual clusters.
121    graph->AddTransaction(refs.emplace_back(), {1, 100});
122    for (unsigned int i = 0; i < NUM_TOP_TX; ++i) {
123        graph->AddTransaction(refs.emplace_back(), FeePerWeight{500 + i, 100});
124    }
125    graph->SanityCheck();
126
127    // The 0th transaction spends all the top transactions.
128    for (unsigned int i = 1; i < NUM_TOTAL_TX; ++i) {
129        graph->AddDependency(/*parent=*/refs[i], /*child=*/refs[0]);
130    }
131    graph->SanityCheck();
132
133    // Check that the graph is now oversized. This also forces the graph to
134    // group clusters and compute the oversized status.
135    BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP));
136
137    // Call Trim() to remove transactions and bring the cluster back within limits.
138    auto removed_refs = graph->Trim();
139    graph->SanityCheck();
140    BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
141
142    // Since only the bottom transaction connects these clusters, we only need to remove it.
143    BOOST_CHECK_EQUAL(removed_refs.size(), 1);
144    BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), MAX_CLUSTER_COUNT * 2);
145    BOOST_CHECK(!graph->Exists(refs[0], TxGraph::Level::TOP));
146    for (unsigned int i = 1; i < refs.size(); ++i) {
147        BOOST_CHECK(graph->Exists(refs[i], TxGraph::Level::TOP));
148    }
149}
150
151BOOST_AUTO_TEST_CASE(txgraph_trim_huge)
152{
153    // The from-block transactions consist of 1000 fully linear clusters, each with 64
154    // transactions. The mempool contains 11 transactions that together merge all of these into
155    // a single cluster.
156    //
157    // (1000 chains of 64 transactions, 64000 T's total)
158    //
159    //      T          T          T          T          T          T          T          T
160    //      |          |          |          |          |          |          |          |
161    //      T          T          T          T          T          T          T          T
162    //      |          |          |          |          |          |          |          |
163    //      T          T          T          T          T          T          T          T
164    //      |          |          |          |          |          |          |          |
165    //      T          T          T          T          T          T          T          T
166    //  (64 long)  (64 long)  (64 long)  (64 long)  (64 long)  (64 long)  (64 long)  (64 long)
167    //      |          |          |          |          |          |          |          |
168    //      |          |         / \         |         / \         |          |         /
169    //      \----------+--------/   \--------+--------/   \--------+-----+----+--------/
170    //                 |                     |                           |
171    //                 B                     B                           B
172    //
173    //  (11 B's, each attaching to up to 100 chains of 64 T's)
174    //
175    /** The maximum cluster count used in this test. */
176    static constexpr int MAX_CLUSTER_COUNT = 64;
177    /** The number of "top" (from-block) chains of transactions. */
178    static constexpr int NUM_TOP_CHAINS = 1000;
179    /** The number of transactions per top chain. */
180    static constexpr int NUM_TX_PER_TOP_CHAIN = MAX_CLUSTER_COUNT;
181    /** The (maximum) number of dependencies per bottom transaction. */
182    static constexpr int NUM_DEPS_PER_BOTTOM_TX = 100;
183    /** The number of bottom transactions that are expected to be created. */
184    static constexpr int NUM_BOTTOM_TX = (NUM_TOP_CHAINS - 1 + (NUM_DEPS_PER_BOTTOM_TX - 2)) / (NUM_DEPS_PER_BOTTOM_TX - 1);
185    /** The total number of transactions created in this test. */
186    static constexpr int NUM_TOTAL_TX = NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN + NUM_BOTTOM_TX;
187    /** Set a very large cluster size limit so that only the count limit is triggered. */
188    static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
189
190    /** Refs to all top transactions. */
191    std::vector<TxGraph::Ref> top_refs;
192    /** Refs to all bottom transactions. */
193    std::vector<TxGraph::Ref> bottom_refs;
194    /** Indexes into top_refs for some transaction of each component, in arbitrary order.
195     *  Initially these are the last transactions in each chains, but as bottom transactions are
196     *  added, entries will be removed when they get merged, and randomized. */
197    std::vector<size_t> top_components;
198
199    FastRandomContext rng;
200    auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, HIGH_ACCEPTABLE_COST, PointerComparator);
201
202    // Construct the top chains.
203    for (int chain = 0; chain < NUM_TOP_CHAINS; ++chain) {
204        for (int chaintx = 0; chaintx < NUM_TX_PER_TOP_CHAIN; ++chaintx) {
205            // Use random fees, size 1.
206            int64_t fee = rng.randbits<27>() + 100;
207            FeePerWeight feerate{fee, 1};
208            graph->AddTransaction(top_refs.emplace_back(), feerate);
209            // Add internal dependencies linking the chain transactions together.
210            if (chaintx > 0) {
211                 graph->AddDependency(*(top_refs.rbegin()), *(top_refs.rbegin() + 1));
212            }
213        }
214        // Remember the last transaction in each chain, to attach the bottom transactions to.
215        top_components.push_back(top_refs.size() - 1);
216    }
217    graph->SanityCheck();
218
219    // Not oversized so far (just 1000 clusters of 64).
220    BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP));
221
222    // Construct the bottom transactions, and dependencies to the top chains.
223    while (top_components.size() > 1) {
224        // Construct the transaction.
225        int64_t fee = rng.randbits<27>() + 100;
226        FeePerWeight feerate{fee, 1};
227        TxGraph::Ref bottom_tx;
228        graph->AddTransaction(bottom_tx, feerate);
229        // Determine the number of dependencies this transaction will have.
230        int deps = std::min<int>(NUM_DEPS_PER_BOTTOM_TX, top_components.size());
231        for (int dep = 0; dep < deps; ++dep) {
232            // Pick an transaction in top_components to attach to.
233            auto idx = rng.randrange(top_components.size());
234            // Add dependency.
235            graph->AddDependency(/*parent=*/top_refs[top_components[idx]], /*child=*/bottom_tx);
236            // Unless this is the last dependency being added, remove from top_components, as
237            // the component will be merged with that one.
238            if (dep < deps - 1) {
239                // Move entry top the back.
240                if (idx != top_components.size() - 1) std::swap(top_components.back(), top_components[idx]);
241                // And pop it.
242                top_components.pop_back();
243            }
244        }
245        bottom_refs.push_back(std::move(bottom_tx));
246    }
247    graph->SanityCheck();
248
249    // Now we are oversized (one cluster of 64011).
250    BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP));