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