mempool_tests.cpp
1 // Copyright (c) 2011-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 <common/system.h> 6 #include <policy/policy.h> 7 #include <test/util/time.h> 8 #include <test/util/txmempool.h> 9 #include <txmempool.h> 10 #include <util/time.h> 11 12 #include <test/util/setup_common.h> 13 14 #include <boost/test/unit_test.hpp> 15 #include <vector> 16 17 BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup) 18 19 static constexpr auto REMOVAL_REASON_DUMMY = MemPoolRemovalReason::REPLACED; 20 21 class MemPoolTest final : public CTxMemPool 22 { 23 public: 24 using CTxMemPool::GetMinFee; 25 }; 26 27 BOOST_AUTO_TEST_CASE(MempoolRemoveTest) 28 { 29 // Test CTxMemPool::remove functionality 30 31 TestMemPoolEntryHelper entry; 32 // Parent transaction with three children, 33 // and three grand-children: 34 CMutableTransaction txParent; 35 txParent.vin.resize(1); 36 txParent.vin[0].scriptSig = CScript() << OP_11; 37 txParent.vout.resize(3); 38 for (int i = 0; i < 3; i++) 39 { 40 txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 41 txParent.vout[i].nValue = 33000LL; 42 } 43 CMutableTransaction txChild[3]; 44 for (int i = 0; i < 3; i++) 45 { 46 txChild[i].vin.resize(1); 47 txChild[i].vin[0].scriptSig = CScript() << OP_11; 48 txChild[i].vin[0].prevout.hash = txParent.GetHash(); 49 txChild[i].vin[0].prevout.n = i; 50 txChild[i].vout.resize(1); 51 txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 52 txChild[i].vout[0].nValue = 11000LL; 53 } 54 CMutableTransaction txGrandChild[3]; 55 for (int i = 0; i < 3; i++) 56 { 57 txGrandChild[i].vin.resize(1); 58 txGrandChild[i].vin[0].scriptSig = CScript() << OP_11; 59 txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash(); 60 txGrandChild[i].vin[0].prevout.n = 0; 61 txGrandChild[i].vout.resize(1); 62 txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 63 txGrandChild[i].vout[0].nValue = 11000LL; 64 } 65 66 67 CTxMemPool& testPool = *Assert(m_node.mempool); 68 LOCK2(::cs_main, testPool.cs); 69 70 // Nothing in pool, remove should do nothing: 71 unsigned int poolSize = testPool.size(); 72 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY); 73 BOOST_CHECK_EQUAL(testPool.size(), poolSize); 74 75 // Just the parent: 76 TryAddToMempool(testPool, entry.FromTx(txParent)); 77 poolSize = testPool.size(); 78 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY); 79 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1); 80 81 // Parent, children, grandchildren: 82 TryAddToMempool(testPool, entry.FromTx(txParent)); 83 for (int i = 0; i < 3; i++) 84 { 85 TryAddToMempool(testPool, entry.FromTx(txChild[i])); 86 TryAddToMempool(testPool, entry.FromTx(txGrandChild[i])); 87 } 88 // Remove Child[0], GrandChild[0] should be removed: 89 poolSize = testPool.size(); 90 testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY); 91 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2); 92 // ... make sure grandchild and child are gone: 93 poolSize = testPool.size(); 94 testPool.removeRecursive(CTransaction(txGrandChild[0]), REMOVAL_REASON_DUMMY); 95 BOOST_CHECK_EQUAL(testPool.size(), poolSize); 96 poolSize = testPool.size(); 97 testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY); 98 BOOST_CHECK_EQUAL(testPool.size(), poolSize); 99 // Remove parent, all children/grandchildren should go: 100 poolSize = testPool.size(); 101 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY); 102 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5); 103 BOOST_CHECK_EQUAL(testPool.size(), 0U); 104 105 // Add children and grandchildren, but NOT the parent (simulate the parent being in a block) 106 for (int i = 0; i < 3; i++) 107 { 108 TryAddToMempool(testPool, entry.FromTx(txChild[i])); 109 TryAddToMempool(testPool, entry.FromTx(txGrandChild[i])); 110 } 111 // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be 112 // put into the mempool (maybe because it is non-standard): 113 poolSize = testPool.size(); 114 testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY); 115 BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6); 116 BOOST_CHECK_EQUAL(testPool.size(), 0U); 117 } 118 119 BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest) 120 { 121 auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool)); 122 LOCK2(cs_main, pool.cs); 123 TestMemPoolEntryHelper entry; 124 125 CMutableTransaction tx1 = CMutableTransaction(); 126 tx1.vin.resize(1); 127 tx1.vin[0].scriptSig = CScript() << OP_1; 128 tx1.vout.resize(1); 129 tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL; 130 tx1.vout[0].nValue = 10 * COIN; 131 TryAddToMempool(pool, entry.Fee(1000LL).FromTx(tx1)); 132 133 CMutableTransaction tx2 = CMutableTransaction(); 134 tx2.vin.resize(1); 135 tx2.vin[0].scriptSig = CScript() << OP_2; 136 tx2.vout.resize(1); 137 tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL; 138 tx2.vout[0].nValue = 10 * COIN; 139 TryAddToMempool(pool, entry.Fee(500LL).FromTx(tx2)); 140 141 pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing 142 BOOST_CHECK(pool.exists(tx1.GetHash())); 143 BOOST_CHECK(pool.exists(tx2.GetHash())); 144 145 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction 146 BOOST_CHECK(pool.exists(tx1.GetHash())); 147 BOOST_CHECK(!pool.exists(tx2.GetHash())); 148 149 TryAddToMempool(pool, entry.FromTx(tx2)); 150 CMutableTransaction tx3 = CMutableTransaction(); 151 tx3.vin.resize(1); 152 tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0); 153 tx3.vin[0].scriptSig = CScript() << OP_2; 154 tx3.vout.resize(1); 155 tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL; 156 tx3.vout[0].nValue = 10 * COIN; 157 TryAddToMempool(pool, entry.Fee(2000LL).FromTx(tx3)); 158 159 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP) 160 BOOST_CHECK(!pool.exists(tx1.GetHash())); 161 BOOST_CHECK(pool.exists(tx2.GetHash())); 162 BOOST_CHECK(pool.exists(tx3.GetHash())); 163 164 pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits 165 BOOST_CHECK(!pool.exists(tx1.GetHash())); 166 BOOST_CHECK(!pool.exists(tx2.GetHash())); 167 BOOST_CHECK(!pool.exists(tx3.GetHash())); 168 169 CFeeRate maxFeeRateRemoved(2500, GetVirtualTransactionSize(CTransaction(tx3)) + GetVirtualTransactionSize(CTransaction(tx2))); 170 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE); 171 172 CMutableTransaction tx4 = CMutableTransaction(); 173 tx4.vin.resize(2); 174 tx4.vin[0].prevout.SetNull(); 175 tx4.vin[0].scriptSig = CScript() << OP_4; 176 tx4.vin[1].prevout.SetNull(); 177 tx4.vin[1].scriptSig = CScript() << OP_4; 178 tx4.vout.resize(2); 179 tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL; 180 tx4.vout[0].nValue = 10 * COIN; 181 tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL; 182 tx4.vout[1].nValue = 10 * COIN; 183 184 CMutableTransaction tx5 = CMutableTransaction(); 185 tx5.vin.resize(2); 186 tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0); 187 tx5.vin[0].scriptSig = CScript() << OP_4; 188 tx5.vin[1].prevout.SetNull(); 189 tx5.vin[1].scriptSig = CScript() << OP_5; 190 tx5.vout.resize(2); 191 tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL; 192 tx5.vout[0].nValue = 10 * COIN; 193 tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL; 194 tx5.vout[1].nValue = 10 * COIN; 195 196 CMutableTransaction tx6 = CMutableTransaction(); 197 tx6.vin.resize(2); 198 tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1); 199 tx6.vin[0].scriptSig = CScript() << OP_4; 200 tx6.vin[1].prevout.SetNull(); 201 tx6.vin[1].scriptSig = CScript() << OP_6; 202 tx6.vout.resize(2); 203 tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL; 204 tx6.vout[0].nValue = 10 * COIN; 205 tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL; 206 tx6.vout[1].nValue = 10 * COIN; 207 208 CMutableTransaction tx7 = CMutableTransaction(); 209 tx7.vin.resize(2); 210 tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0); 211 tx7.vin[0].scriptSig = CScript() << OP_5; 212 tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0); 213 tx7.vin[1].scriptSig = CScript() << OP_6; 214 tx7.vout.resize(2); 215 tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL; 216 tx7.vout[0].nValue = 10 * COIN; 217 tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL; 218 tx7.vout[1].nValue = 10 * COIN; 219 220 TryAddToMempool(pool, entry.Fee(700LL).FromTx(tx4)); 221 auto usage_with_tx4_only = pool.DynamicMemoryUsage(); 222 TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5)); 223 TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6)); 224 TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7)); 225 226 // From the topology above, tx7 must be sorted last, so it should 227 // definitely evicted first if we must trim. tx4 should definitely remain 228 // in the mempool since it has a higher feerate than its descendants and 229 // should be in its own chunk. 230 pool.TrimToSize(pool.DynamicMemoryUsage() - 1); 231 BOOST_CHECK(pool.exists(tx4.GetHash())); 232 BOOST_CHECK(!pool.exists(tx7.GetHash())); 233 234 // Tx5 and Tx6 may be removed as well because they're in the same chunk as 235 // tx7, but this behavior need not be guaranteed. 236 237 if (!pool.exists(tx5.GetHash())) 238 TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5)); 239 if (!pool.exists(tx6.GetHash())) 240 TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6)); 241 TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7)); 242 243 // If we trim sufficiently, everything but tx4 should be removed. 244 pool.TrimToSize(usage_with_tx4_only + 1); 245 BOOST_CHECK(pool.exists(tx4.GetHash())); 246 BOOST_CHECK(!pool.exists(tx5.GetHash())); 247 BOOST_CHECK(!pool.exists(tx6.GetHash())); 248 BOOST_CHECK(!pool.exists(tx7.GetHash())); 249 250 TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5)); 251 TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6)); 252 TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7)); 253 254 std::vector<CTransactionRef> vtx; 255 NodeClockContext clock_ctx{42s}; 256 constexpr std::chrono::seconds HALFLIFE{CTxMemPool::ROLLING_FEE_HALFLIFE}; 257 clock_ctx += HALFLIFE; 258 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE); 259 // ... we should keep the same min fee until we get a block 260 pool.removeForBlock(vtx, 1); 261 clock_ctx += HALFLIFE; 262 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/2.0)); 263 // ... then feerate should drop 1/2 each halflife 264 265 clock_ctx += HALFLIFE / 2; 266 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/4.0)); 267 // ... with a 1/2 halflife when mempool is < 1/2 its target size 268 269 clock_ctx += HALFLIFE / 4; 270 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/8.0)); 271 // ... with a 1/4 halflife when mempool is < 1/4 its target size 272 273 clock_ctx += 5 * HALFLIFE; 274 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), DEFAULT_INCREMENTAL_RELAY_FEE); 275 // ... but feerate should never drop below DEFAULT_INCREMENTAL_RELAY_FEE 276 277 clock_ctx += HALFLIFE; 278 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0); 279 // ... unless it has gone all the way to 0 (after getting past DEFAULT_INCREMENTAL_RELAY_FEE/2) 280 } 281 282 inline CTransactionRef make_tx(std::vector<CAmount>&& output_values, std::vector<CTransactionRef>&& inputs=std::vector<CTransactionRef>(), std::vector<uint32_t>&& input_indices=std::vector<uint32_t>()) 283 { 284 CMutableTransaction tx = CMutableTransaction(); 285 tx.vin.resize(inputs.size()); 286 tx.vout.resize(output_values.size()); 287 for (size_t i = 0; i < inputs.size(); ++i) { 288 tx.vin[i].prevout.hash = inputs[i]->GetHash(); 289 tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0; 290 } 291 for (size_t i = 0; i < output_values.size(); ++i) { 292 tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 293 tx.vout[i].nValue = output_values[i]; 294 } 295 return MakeTransactionRef(tx); 296 } 297 298 299 BOOST_AUTO_TEST_CASE(MempoolAncestryTests) 300 { 301 size_t ancestors, clustersize; 302 303 CTxMemPool& pool = *Assert(m_node.mempool); 304 LOCK2(cs_main, pool.cs); 305 TestMemPoolEntryHelper entry; 306 307 /* Base transaction */ 308 // 309 // [tx1] 310 // 311 CTransactionRef tx1 = make_tx(/*output_values=*/{10 * COIN}); 312 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx1)); 313 314 // Ancestors / clustersize should be 1 / 1 (itself / itself) 315 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize); 316 BOOST_CHECK_EQUAL(ancestors, 1ULL); 317 BOOST_CHECK_EQUAL(clustersize, 1ULL); 318 319 /* Child transaction */ 320 // 321 // [tx1].0 <- [tx2] 322 // 323 CTransactionRef tx2 = make_tx(/*output_values=*/{495 * CENT, 5 * COIN}, /*inputs=*/{tx1}); 324 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx2)); 325 326 // Ancestors / clustersize should be: 327 // transaction ancestors clustersize 328 // ============ =========== =========== 329 // tx1 1 (tx1) 2 (tx1,2) 330 // tx2 2 (tx1,2) 2 (tx1,2) 331 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize); 332 BOOST_CHECK_EQUAL(ancestors, 1ULL); 333 BOOST_CHECK_EQUAL(clustersize, 2ULL); 334 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize); 335 BOOST_CHECK_EQUAL(ancestors, 2ULL); 336 BOOST_CHECK_EQUAL(clustersize, 2ULL); 337 338 /* Grand-child 1 */ 339 // 340 // [tx1].0 <- [tx2].0 <- [tx3] 341 // 342 CTransactionRef tx3 = make_tx(/*output_values=*/{290 * CENT, 200 * CENT}, /*inputs=*/{tx2}); 343 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx3)); 344 345 // Ancestors / clustersize should be: 346 // transaction ancestors clustersize 347 // ============ =========== =========== 348 // tx1 1 (tx1) 3 (tx1,2,3) 349 // tx2 2 (tx1,2) 3 (tx1,2,3) 350 // tx3 3 (tx1,2,3) 3 (tx1,2,3) 351 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize); 352 BOOST_CHECK_EQUAL(ancestors, 1ULL); 353 BOOST_CHECK_EQUAL(clustersize, 3ULL); 354 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize); 355 BOOST_CHECK_EQUAL(ancestors, 2ULL); 356 BOOST_CHECK_EQUAL(clustersize, 3ULL); 357 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize); 358 BOOST_CHECK_EQUAL(ancestors, 3ULL); 359 BOOST_CHECK_EQUAL(clustersize, 3ULL); 360 361 /* Grand-child 2 */ 362 // 363 // [tx1].0 <- [tx2].0 <- [tx3] 364 // | 365 // \---1 <- [tx4] 366 // 367 CTransactionRef tx4 = make_tx(/*output_values=*/{290 * CENT, 250 * CENT}, /*inputs=*/{tx2}, /*input_indices=*/{1}); 368 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx4)); 369 370 // Ancestors / clustersize should be: 371 // transaction ancestors clustersize 372 // ============ =========== =========== 373 // tx1 1 (tx1) 4 (tx1,2,3,4) 374 // tx2 2 (tx1,2) 4 (tx1,2,3,4) 375 // tx3 3 (tx1,2,3) 4 (tx1,2,3,4) 376 // tx4 3 (tx1,2,4) 4 (tx1,2,3,4) 377 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize); 378 BOOST_CHECK_EQUAL(ancestors, 1ULL); 379 BOOST_CHECK_EQUAL(clustersize, 4ULL); 380 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize); 381 BOOST_CHECK_EQUAL(ancestors, 2ULL); 382 BOOST_CHECK_EQUAL(clustersize, 4ULL); 383 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize); 384 BOOST_CHECK_EQUAL(ancestors, 3ULL); 385 BOOST_CHECK_EQUAL(clustersize, 4ULL); 386 pool.GetTransactionAncestry(tx4->GetHash(), ancestors, clustersize); 387 BOOST_CHECK_EQUAL(ancestors, 3ULL); 388 BOOST_CHECK_EQUAL(clustersize, 4ULL); 389 390 /* Make an alternate branch that is longer and connect it to tx3 */ 391 // 392 // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0 393 // | 394 // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/ 395 // | 396 // \---1 <- [tx4] 397 // 398 CTransactionRef ty1, ty2, ty3, ty4, ty5; 399 CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5}; 400 CAmount v = 5 * COIN; 401 for (uint64_t i = 0; i < 5; i++) { 402 CTransactionRef& tyi = *ty[i]; 403 tyi = make_tx(/*output_values=*/{v}, /*inputs=*/i > 0 ? std::vector<CTransactionRef>{*ty[i - 1]} : std::vector<CTransactionRef>{}); 404 v -= 50 * CENT; 405 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tyi)); 406 pool.GetTransactionAncestry(tyi->GetHash(), ancestors, clustersize); 407 BOOST_CHECK_EQUAL(ancestors, i+1); 408 BOOST_CHECK_EQUAL(clustersize, i+1); 409 } 410 CTransactionRef ty6 = make_tx(/*output_values=*/{5 * COIN}, /*inputs=*/{tx3, ty5}); 411 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(ty6)); 412 413 // Ancestors / clustersize should be: 414 // transaction ancestors clustersize 415 // ============ =================== =========== 416 // tx1 1 (tx1) 10 (tx1-5, ty1-5) 417 // tx2 2 (tx1,2) 10 418 // tx3 3 (tx1,2,3) 10 419 // tx4 3 (tx1,2,4) 10 420 // ty1 1 (ty1) 10 421 // ty2 2 (ty1,2) 10 422 // ty3 3 (ty1,2,3) 10 423 // ty4 4 (y1234) 10 424 // ty5 5 (y12345) 10 425 // ty6 9 (tx123, ty123456) 10 426 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize); 427 BOOST_CHECK_EQUAL(ancestors, 1ULL); 428 BOOST_CHECK_EQUAL(clustersize, 10ULL); 429 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize); 430 BOOST_CHECK_EQUAL(ancestors, 2ULL); 431 BOOST_CHECK_EQUAL(clustersize, 10ULL); 432 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize); 433 BOOST_CHECK_EQUAL(ancestors, 3ULL); 434 BOOST_CHECK_EQUAL(clustersize, 10ULL); 435 pool.GetTransactionAncestry(tx4->GetHash(), ancestors, clustersize); 436 BOOST_CHECK_EQUAL(ancestors, 3ULL); 437 BOOST_CHECK_EQUAL(clustersize, 10ULL); 438 pool.GetTransactionAncestry(ty1->GetHash(), ancestors, clustersize); 439 BOOST_CHECK_EQUAL(ancestors, 1ULL); 440 BOOST_CHECK_EQUAL(clustersize, 10ULL); 441 pool.GetTransactionAncestry(ty2->GetHash(), ancestors, clustersize); 442 BOOST_CHECK_EQUAL(ancestors, 2ULL); 443 BOOST_CHECK_EQUAL(clustersize, 10ULL); 444 pool.GetTransactionAncestry(ty3->GetHash(), ancestors, clustersize); 445 BOOST_CHECK_EQUAL(ancestors, 3ULL); 446 BOOST_CHECK_EQUAL(clustersize, 10ULL); 447 pool.GetTransactionAncestry(ty4->GetHash(), ancestors, clustersize); 448 BOOST_CHECK_EQUAL(ancestors, 4ULL); 449 BOOST_CHECK_EQUAL(clustersize, 10ULL); 450 pool.GetTransactionAncestry(ty5->GetHash(), ancestors, clustersize); 451 BOOST_CHECK_EQUAL(ancestors, 5ULL); 452 BOOST_CHECK_EQUAL(clustersize, 10ULL); 453 pool.GetTransactionAncestry(ty6->GetHash(), ancestors, clustersize); 454 BOOST_CHECK_EQUAL(ancestors, 9ULL); 455 BOOST_CHECK_EQUAL(clustersize, 10ULL); 456 } 457 458 BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond) 459 { 460 size_t ancestors, descendants; 461 462 CTxMemPool& pool = *Assert(m_node.mempool); 463 LOCK2(::cs_main, pool.cs); 464 TestMemPoolEntryHelper entry; 465 466 /* Ancestors represented more than once ("diamond") */ 467 // 468 // [ta].0 <- [tb].0 -----<------- [td].0 469 // | | 470 // \---1 <- [tc].0 --<--/ 471 // 472 CTransactionRef ta, tb, tc, td; 473 ta = make_tx(/*output_values=*/{10 * COIN}); 474 tb = make_tx(/*output_values=*/{5 * COIN, 3 * COIN}, /*inputs=*/ {ta}); 475 tc = make_tx(/*output_values=*/{2 * COIN}, /*inputs=*/{tb}, /*input_indices=*/{1}); 476 td = make_tx(/*output_values=*/{6 * COIN}, /*inputs=*/{tb, tc}, /*input_indices=*/{0, 0}); 477 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(ta)); 478 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tb)); 479 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tc)); 480 TryAddToMempool(pool, entry.Fee(10000LL).FromTx(td)); 481 482 // Ancestors / descendants should be: 483 // transaction ancestors descendants 484 // ============ =================== =========== 485 // ta 1 (ta 4 (ta,tb,tc,td) 486 // tb 2 (ta,tb) 4 (ta,tb,tc,td) 487 // tc 3 (ta,tb,tc) 4 (ta,tb,tc,td) 488 // td 4 (ta,tb,tc,td) 4 (ta,tb,tc,td) 489 pool.GetTransactionAncestry(ta->GetHash(), ancestors, descendants); 490 BOOST_CHECK_EQUAL(ancestors, 1ULL); 491 BOOST_CHECK_EQUAL(descendants, 4ULL); 492 pool.GetTransactionAncestry(tb->GetHash(), ancestors, descendants); 493 BOOST_CHECK_EQUAL(ancestors, 2ULL); 494 BOOST_CHECK_EQUAL(descendants, 4ULL); 495 pool.GetTransactionAncestry(tc->GetHash(), ancestors, descendants); 496 BOOST_CHECK_EQUAL(ancestors, 3ULL); 497 BOOST_CHECK_EQUAL(descendants, 4ULL); 498 pool.GetTransactionAncestry(td->GetHash(), ancestors, descendants); 499 BOOST_CHECK_EQUAL(ancestors, 4ULL); 500 BOOST_CHECK_EQUAL(descendants, 4ULL); 501 } 502 503 BOOST_AUTO_TEST_SUITE_END()