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