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()
435