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 namespace { 17 18 /** The number used as acceptable_cost argument in these tests. High enough that everything 19 * should be optimal, always. */ 20 constexpr uint64_t HIGH_ACCEPTABLE_COST = 100'000'000; 21 22 std::strong_ordering PointerComparator(const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept 23 { 24 return (&a) <=> (&b); 25 } 26 27 } // namespace 28 29 BOOST_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 92 BOOST_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 151 BOOST_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)); 251 const auto total_tx_count = graph->GetTransactionCount(TxGraph::Level::TOP); 252 BOOST_CHECK(total_tx_count == top_refs.size() + bottom_refs.size()); 253 BOOST_CHECK(total_tx_count == NUM_TOTAL_TX); 254 255 // Call Trim() to remove transactions and bring the cluster back within limits. 256 auto removed_refs = graph->Trim(); 257 BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP)); 258 BOOST_CHECK(removed_refs.size() == total_tx_count - graph->GetTransactionCount(TxGraph::Level::TOP)); 259 graph->SanityCheck(); 260 261 // At least 99% of chains must survive. 262 BOOST_CHECK(graph->GetTransactionCount(TxGraph::Level::TOP) >= (NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN * 99) / 100); 263 } 264 265 BOOST_AUTO_TEST_CASE(txgraph_trim_big_singletons) 266 { 267 // Mempool consists of 100 singleton clusters; there are no dependencies. Some are oversized. Trim() should remove all of the oversized ones. 268 static constexpr int MAX_CLUSTER_COUNT = 64; 269 static constexpr int32_t MAX_CLUSTER_SIZE = 100'000; 270 static constexpr int NUM_TOTAL_TX = 100; 271 272 // Create a new graph for the test. 273 auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE, HIGH_ACCEPTABLE_COST, PointerComparator); 274 275 // Add all transactions and store their Refs. 276 std::vector<TxGraph::Ref> refs; 277 refs.reserve(NUM_TOTAL_TX); 278 279 // Add all transactions. They are in individual clusters. 280 for (unsigned int i = 0; i < NUM_TOTAL_TX; ++i) { 281 // The 88th transaction is oversized. 282 // Every 20th transaction is oversized. 283 const FeePerWeight feerate{500 + i, (i == 88 || i % 20 == 0) ? MAX_CLUSTER_SIZE + 1 : 100}; 284 graph->AddTransaction(refs.emplace_back(), feerate); 285 } 286 graph->SanityCheck(); 287 288 // Check that the graph is now oversized. This also forces the graph to 289 // group clusters and compute the oversized status. 290 BOOST_CHECK(graph->IsOversized(TxGraph::Level::TOP)); 291 292 // Call Trim() to remove transactions and bring the cluster back within limits. 293 auto removed_refs = graph->Trim(); 294 graph->SanityCheck(); 295 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), NUM_TOTAL_TX - 6); 296 BOOST_CHECK(!graph->IsOversized(TxGraph::Level::TOP)); 297 298 // Check that all the oversized transactions were removed. 299 for (unsigned int i = 0; i < refs.size(); ++i) { 300 BOOST_CHECK_EQUAL(graph->Exists(refs[i], TxGraph::Level::TOP), i != 88 && i % 20 != 0); 301 } 302 } 303 304 BOOST_AUTO_TEST_CASE(txgraph_chunk_chain) 305 { 306 // Create a new graph for the test. 307 auto graph = MakeTxGraph(50, 1000, HIGH_ACCEPTABLE_COST, PointerComparator); 308 309 auto block_builder_checker = [&graph](std::vector<std::vector<TxGraph::Ref*>> expected_chunks) { 310 std::vector<std::vector<TxGraph::Ref*>> chunks; 311 auto builder = graph->GetBlockBuilder(); 312 FeePerWeight last_chunk_feerate; 313 while (auto chunk = builder->GetCurrentChunk()) { 314 FeePerWeight sum; 315 for (TxGraph::Ref* ref : chunk->first) { 316 // The reported chunk feerate must match the chunk feerate obtained by asking 317 // it for each of the chunk's transactions individually. 318 BOOST_CHECK(graph->GetMainChunkFeerate(*ref) == chunk->second); 319 // Verify the chunk feerate matches the sum of the reported individual feerates. 320 sum += graph->GetIndividualFeerate(*ref); 321 } 322 BOOST_CHECK(sum == chunk->second); 323 chunks.push_back(std::move(chunk->first)); 324 last_chunk_feerate = chunk->second; 325 builder->Include(); 326 } 327 328 BOOST_CHECK(chunks == expected_chunks); 329 auto& last_chunk = chunks.back(); 330 // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse. 331 std::reverse(last_chunk.begin(), last_chunk.end()); 332 auto [worst_chunk, worst_chunk_feerate] = graph->GetWorstMainChunk(); 333 BOOST_CHECK(last_chunk == worst_chunk); 334 BOOST_CHECK(last_chunk_feerate == worst_chunk_feerate); 335 }; 336 337 std::vector<TxGraph::Ref> refs; 338 refs.reserve(4); 339 340 FeePerWeight feerateA{2, 10}; 341 FeePerWeight feerateB{1, 10}; 342 FeePerWeight feerateC{2, 10}; 343 FeePerWeight feerateD{4, 10}; 344 345 // everytime adding a transaction, test the chunk status 346 // [A] 347 graph->AddTransaction(refs.emplace_back(), feerateA); 348 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1); 349 block_builder_checker({{&refs[0]}}); 350 // [A, B] 351 graph->AddTransaction(refs.emplace_back(), feerateB); 352 graph->AddDependency(/*parent=*/refs[0], /*child=*/refs[1]); 353 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 2); 354 block_builder_checker({{&refs[0]}, {&refs[1]}}); 355 356 // [A, BC] 357 graph->AddTransaction(refs.emplace_back(), feerateC); 358 graph->AddDependency(/*parent=*/refs[1], /*child=*/refs[2]); 359 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 3); 360 block_builder_checker({{&refs[0]}, {&refs[1], &refs[2]}}); 361 362 // [ABCD] 363 graph->AddTransaction(refs.emplace_back(), feerateD); 364 graph->AddDependency(/*parent=*/refs[2], /*child=*/refs[3]); 365 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 4); 366 block_builder_checker({{&refs[0], &refs[1], &refs[2], &refs[3]}}); 367 368 graph->SanityCheck(); 369 370 // D->C->A 371 graph->RemoveTransaction(refs[1]); 372 // txgraph is not responsible for removing the descendants or ancestors 373 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 3); 374 // only A remains there 375 graph->RemoveTransaction(refs[2]); 376 graph->RemoveTransaction(refs[3]); 377 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1); 378 block_builder_checker({{&refs[0]}}); 379 } 380 381 BOOST_AUTO_TEST_CASE(txgraph_staging) 382 { 383 /* Create a new graph for the test. 384 * The parameters are max_cluster_count, max_cluster_size, acceptable_iters 385 */ 386 auto graph = MakeTxGraph(10, 1000, HIGH_ACCEPTABLE_COST, PointerComparator); 387 388 std::vector<TxGraph::Ref> refs; 389 refs.reserve(2); 390 391 FeePerWeight feerateA{2, 10}; 392 FeePerWeight feerateB{1, 10}; 393 394 // everytime adding a transaction, test the chunk status 395 // [A] 396 graph->AddTransaction(refs.emplace_back(), feerateA); 397 BOOST_CHECK_EQUAL(graph->HaveStaging(), false); 398 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1); 399 400 graph->StartStaging(); 401 BOOST_CHECK_EQUAL(graph->HaveStaging(), true); 402 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1); 403 404 // [A, B] 405 graph->AddTransaction(refs.emplace_back(), feerateB); 406 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 1); 407 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 2); 408 BOOST_CHECK_EQUAL(graph->Exists(refs[0], TxGraph::Level::TOP), true); 409 BOOST_CHECK_EQUAL(graph->Exists(refs[1], TxGraph::Level::TOP), true); 410 411 graph->AddDependency(/*parent=*/refs[0], /*child=*/refs[1]); 412 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 1); 413 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 2); 414 415 graph->CommitStaging(); 416 BOOST_CHECK_EQUAL(graph->HaveStaging(), false); 417 418 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 2); 419 420 graph->StartStaging(); 421 422 // [A] 423 graph->RemoveTransaction(refs[1]); 424 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 2); 425 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::TOP), 1); 426 427 graph->CommitStaging(); 428 429 BOOST_CHECK_EQUAL(graph->GetTransactionCount(TxGraph::Level::MAIN), 1); 430 431 graph->SanityCheck(); 432 } 433 434 BOOST_AUTO_TEST_SUITE_END()