mempool_tests.cpp
1 // Copyright (c) 2011-2022 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 AddToMempool(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 AddToMempool(testPool, entry.FromTx(txParent)); 82 for (int i = 0; i < 3; i++) 83 { 84 AddToMempool(testPool, entry.FromTx(txChild[i])); 85 AddToMempool(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 AddToMempool(testPool, entry.FromTx(txChild[i])); 108 AddToMempool(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 template <typename name> 119 static void CheckSort(CTxMemPool& pool, std::vector<std::string>& sortedOrder) EXCLUSIVE_LOCKS_REQUIRED(pool.cs) 120 { 121 BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size()); 122 typename CTxMemPool::indexed_transaction_set::index<name>::type::iterator it = pool.mapTx.get<name>().begin(); 123 int count = 0; 124 for (; it != pool.mapTx.get<name>().end(); ++it, ++count) { 125 BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]); 126 } 127 } 128 129 BOOST_AUTO_TEST_CASE(MempoolIndexingTest) 130 { 131 CTxMemPool& pool = *Assert(m_node.mempool); 132 LOCK2(cs_main, pool.cs); 133 TestMemPoolEntryHelper entry; 134 135 /* 3rd highest fee */ 136 CMutableTransaction tx1 = CMutableTransaction(); 137 tx1.vout.resize(1); 138 tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 139 tx1.vout[0].nValue = 10 * COIN; 140 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx1)); 141 142 /* highest fee */ 143 CMutableTransaction tx2 = CMutableTransaction(); 144 tx2.vout.resize(1); 145 tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 146 tx2.vout[0].nValue = 2 * COIN; 147 AddToMempool(pool, entry.Fee(20000LL).FromTx(tx2)); 148 149 /* lowest fee */ 150 CMutableTransaction tx3 = CMutableTransaction(); 151 tx3.vout.resize(1); 152 tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 153 tx3.vout[0].nValue = 5 * COIN; 154 AddToMempool(pool, entry.Fee(0LL).FromTx(tx3)); 155 156 /* 2nd highest fee */ 157 CMutableTransaction tx4 = CMutableTransaction(); 158 tx4.vout.resize(1); 159 tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 160 tx4.vout[0].nValue = 6 * COIN; 161 AddToMempool(pool, entry.Fee(15000LL).FromTx(tx4)); 162 163 /* equal fee rate to tx1, but newer */ 164 CMutableTransaction tx5 = CMutableTransaction(); 165 tx5.vout.resize(1); 166 tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 167 tx5.vout[0].nValue = 11 * COIN; 168 entry.time = NodeSeconds{1s}; 169 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx5)); 170 BOOST_CHECK_EQUAL(pool.size(), 5U); 171 172 std::vector<std::string> sortedOrder; 173 sortedOrder.resize(5); 174 sortedOrder[0] = tx3.GetHash().ToString(); // 0 175 sortedOrder[1] = tx5.GetHash().ToString(); // 10000 176 sortedOrder[2] = tx1.GetHash().ToString(); // 10000 177 sortedOrder[3] = tx4.GetHash().ToString(); // 15000 178 sortedOrder[4] = tx2.GetHash().ToString(); // 20000 179 CheckSort<descendant_score>(pool, sortedOrder); 180 181 /* low fee but with high fee child */ 182 /* tx6 -> tx7 -> tx8, tx9 -> tx10 */ 183 CMutableTransaction tx6 = CMutableTransaction(); 184 tx6.vout.resize(1); 185 tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 186 tx6.vout[0].nValue = 20 * COIN; 187 AddToMempool(pool, entry.Fee(0LL).FromTx(tx6)); 188 BOOST_CHECK_EQUAL(pool.size(), 6U); 189 // Check that at this point, tx6 is sorted low 190 sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString()); 191 CheckSort<descendant_score>(pool, sortedOrder); 192 193 CTxMemPool::setEntries setAncestors; 194 setAncestors.insert(pool.GetIter(tx6.GetHash()).value()); 195 CMutableTransaction tx7 = CMutableTransaction(); 196 tx7.vin.resize(1); 197 tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0); 198 tx7.vin[0].scriptSig = CScript() << OP_11; 199 tx7.vout.resize(2); 200 tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 201 tx7.vout[0].nValue = 10 * COIN; 202 tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 203 tx7.vout[1].nValue = 1 * COIN; 204 205 { 206 auto ancestors_calculated{pool.CalculateMemPoolAncestors(entry.Fee(2000000LL).FromTx(tx7), CTxMemPool::Limits::NoLimits())}; 207 BOOST_REQUIRE(ancestors_calculated.has_value()); 208 BOOST_CHECK(*ancestors_calculated == setAncestors); 209 } 210 211 AddToMempool(pool, entry.FromTx(tx7)); 212 BOOST_CHECK_EQUAL(pool.size(), 7U); 213 214 // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ... 215 sortedOrder.erase(sortedOrder.begin()); 216 sortedOrder.push_back(tx6.GetHash().ToString()); 217 sortedOrder.push_back(tx7.GetHash().ToString()); 218 CheckSort<descendant_score>(pool, sortedOrder); 219 220 /* low fee child of tx7 */ 221 CMutableTransaction tx8 = CMutableTransaction(); 222 tx8.vin.resize(1); 223 tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0); 224 tx8.vin[0].scriptSig = CScript() << OP_11; 225 tx8.vout.resize(1); 226 tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 227 tx8.vout[0].nValue = 10 * COIN; 228 setAncestors.insert(pool.GetIter(tx7.GetHash()).value()); 229 AddToMempool(pool, entry.Fee(0LL).Time(NodeSeconds{2s}).FromTx(tx8)); 230 231 // Now tx8 should be sorted low, but tx6/tx both high 232 sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString()); 233 CheckSort<descendant_score>(pool, sortedOrder); 234 235 /* low fee child of tx7 */ 236 CMutableTransaction tx9 = CMutableTransaction(); 237 tx9.vin.resize(1); 238 tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1); 239 tx9.vin[0].scriptSig = CScript() << OP_11; 240 tx9.vout.resize(1); 241 tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 242 tx9.vout[0].nValue = 1 * COIN; 243 AddToMempool(pool, entry.Fee(0LL).Time(NodeSeconds{3s}).FromTx(tx9)); 244 245 // tx9 should be sorted low 246 BOOST_CHECK_EQUAL(pool.size(), 9U); 247 sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString()); 248 CheckSort<descendant_score>(pool, sortedOrder); 249 250 std::vector<std::string> snapshotOrder = sortedOrder; 251 252 setAncestors.insert(pool.GetIter(tx8.GetHash()).value()); 253 setAncestors.insert(pool.GetIter(tx9.GetHash()).value()); 254 /* tx10 depends on tx8 and tx9 and has a high fee*/ 255 CMutableTransaction tx10 = CMutableTransaction(); 256 tx10.vin.resize(2); 257 tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0); 258 tx10.vin[0].scriptSig = CScript() << OP_11; 259 tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0); 260 tx10.vin[1].scriptSig = CScript() << OP_11; 261 tx10.vout.resize(1); 262 tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 263 tx10.vout[0].nValue = 10 * COIN; 264 265 { 266 auto ancestors_calculated{pool.CalculateMemPoolAncestors(entry.Fee(200000LL).Time(NodeSeconds{4s}).FromTx(tx10), CTxMemPool::Limits::NoLimits())}; 267 BOOST_REQUIRE(ancestors_calculated); 268 BOOST_CHECK(*ancestors_calculated == setAncestors); 269 } 270 271 AddToMempool(pool, entry.FromTx(tx10)); 272 273 /** 274 * tx8 and tx9 should both now be sorted higher 275 * Final order after tx10 is added: 276 * 277 * tx3 = 0 (1) 278 * tx5 = 10000 (1) 279 * tx1 = 10000 (1) 280 * tx4 = 15000 (1) 281 * tx2 = 20000 (1) 282 * tx9 = 200k (2 txs) 283 * tx8 = 200k (2 txs) 284 * tx10 = 200k (1 tx) 285 * tx6 = 2.2M (5 txs) 286 * tx7 = 2.2M (4 txs) 287 */ 288 sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning 289 sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString()); 290 sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString()); 291 sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6 292 CheckSort<descendant_score>(pool, sortedOrder); 293 294 // there should be 10 transactions in the mempool 295 BOOST_CHECK_EQUAL(pool.size(), 10U); 296 297 // Now try removing tx10 and verify the sort order returns to normal 298 pool.removeRecursive(*Assert(pool.get(tx10.GetHash())), REMOVAL_REASON_DUMMY); 299 CheckSort<descendant_score>(pool, snapshotOrder); 300 301 pool.removeRecursive(*Assert(pool.get(tx9.GetHash())), REMOVAL_REASON_DUMMY); 302 pool.removeRecursive(*Assert(pool.get(tx8.GetHash())), REMOVAL_REASON_DUMMY); 303 } 304 305 BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest) 306 { 307 CTxMemPool& pool = *Assert(m_node.mempool); 308 LOCK2(cs_main, pool.cs); 309 TestMemPoolEntryHelper entry; 310 311 /* 3rd highest fee */ 312 CMutableTransaction tx1 = CMutableTransaction(); 313 tx1.vout.resize(1); 314 tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 315 tx1.vout[0].nValue = 10 * COIN; 316 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx1)); 317 318 /* highest fee */ 319 CMutableTransaction tx2 = CMutableTransaction(); 320 tx2.vout.resize(1); 321 tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 322 tx2.vout[0].nValue = 2 * COIN; 323 AddToMempool(pool, entry.Fee(20000LL).FromTx(tx2)); 324 uint64_t tx2Size = GetVirtualTransactionSize(CTransaction(tx2)); 325 326 /* lowest fee */ 327 CMutableTransaction tx3 = CMutableTransaction(); 328 tx3.vout.resize(1); 329 tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 330 tx3.vout[0].nValue = 5 * COIN; 331 AddToMempool(pool, entry.Fee(0LL).FromTx(tx3)); 332 333 /* 2nd highest fee */ 334 CMutableTransaction tx4 = CMutableTransaction(); 335 tx4.vout.resize(1); 336 tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 337 tx4.vout[0].nValue = 6 * COIN; 338 AddToMempool(pool, entry.Fee(15000LL).FromTx(tx4)); 339 340 /* equal fee rate to tx1, but newer */ 341 CMutableTransaction tx5 = CMutableTransaction(); 342 tx5.vout.resize(1); 343 tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 344 tx5.vout[0].nValue = 11 * COIN; 345 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx5)); 346 BOOST_CHECK_EQUAL(pool.size(), 5U); 347 348 std::vector<std::string> sortedOrder; 349 sortedOrder.resize(5); 350 sortedOrder[0] = tx2.GetHash().ToString(); // 20000 351 sortedOrder[1] = tx4.GetHash().ToString(); // 15000 352 // tx1 and tx5 are both 10000 353 // Ties are broken by hash, not timestamp, so determine which 354 // hash comes first. 355 if (tx1.GetHash() < tx5.GetHash()) { 356 sortedOrder[2] = tx1.GetHash().ToString(); 357 sortedOrder[3] = tx5.GetHash().ToString(); 358 } else { 359 sortedOrder[2] = tx5.GetHash().ToString(); 360 sortedOrder[3] = tx1.GetHash().ToString(); 361 } 362 sortedOrder[4] = tx3.GetHash().ToString(); // 0 363 364 CheckSort<ancestor_score>(pool, sortedOrder); 365 366 /* low fee parent with high fee child */ 367 /* tx6 (0) -> tx7 (high) */ 368 CMutableTransaction tx6 = CMutableTransaction(); 369 tx6.vout.resize(1); 370 tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 371 tx6.vout[0].nValue = 20 * COIN; 372 uint64_t tx6Size = GetVirtualTransactionSize(CTransaction(tx6)); 373 374 AddToMempool(pool, entry.Fee(0LL).FromTx(tx6)); 375 BOOST_CHECK_EQUAL(pool.size(), 6U); 376 // Ties are broken by hash 377 if (tx3.GetHash() < tx6.GetHash()) 378 sortedOrder.push_back(tx6.GetHash().ToString()); 379 else 380 sortedOrder.insert(sortedOrder.end()-1,tx6.GetHash().ToString()); 381 382 CheckSort<ancestor_score>(pool, sortedOrder); 383 384 CMutableTransaction tx7 = CMutableTransaction(); 385 tx7.vin.resize(1); 386 tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0); 387 tx7.vin[0].scriptSig = CScript() << OP_11; 388 tx7.vout.resize(1); 389 tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 390 tx7.vout[0].nValue = 10 * COIN; 391 uint64_t tx7Size = GetVirtualTransactionSize(CTransaction(tx7)); 392 393 /* set the fee to just below tx2's feerate when including ancestor */ 394 CAmount fee = (20000/tx2Size)*(tx7Size + tx6Size) - 1; 395 396 AddToMempool(pool, entry.Fee(fee).FromTx(tx7)); 397 BOOST_CHECK_EQUAL(pool.size(), 7U); 398 sortedOrder.insert(sortedOrder.begin()+1, tx7.GetHash().ToString()); 399 CheckSort<ancestor_score>(pool, sortedOrder); 400 401 /* after tx6 is mined, tx7 should move up in the sort */ 402 std::vector<CTransactionRef> vtx; 403 vtx.push_back(MakeTransactionRef(tx6)); 404 pool.removeForBlock(vtx, 1); 405 406 sortedOrder.erase(sortedOrder.begin()+1); 407 // Ties are broken by hash 408 if (tx3.GetHash() < tx6.GetHash()) 409 sortedOrder.pop_back(); 410 else 411 sortedOrder.erase(sortedOrder.end()-2); 412 sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString()); 413 CheckSort<ancestor_score>(pool, sortedOrder); 414 415 // High-fee parent, low-fee child 416 // tx7 -> tx8 417 CMutableTransaction tx8 = CMutableTransaction(); 418 tx8.vin.resize(1); 419 tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0); 420 tx8.vin[0].scriptSig = CScript() << OP_11; 421 tx8.vout.resize(1); 422 tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 423 tx8.vout[0].nValue = 10*COIN; 424 425 // Check that we sort by min(feerate, ancestor_feerate): 426 // set the fee so that the ancestor feerate is above tx1/5, 427 // but the transaction's own feerate is lower 428 AddToMempool(pool, entry.Fee(5000LL).FromTx(tx8)); 429 sortedOrder.insert(sortedOrder.end()-1, tx8.GetHash().ToString()); 430 CheckSort<ancestor_score>(pool, sortedOrder); 431 } 432 433 434 BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest) 435 { 436 auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool)); 437 LOCK2(cs_main, pool.cs); 438 TestMemPoolEntryHelper entry; 439 440 CMutableTransaction tx1 = CMutableTransaction(); 441 tx1.vin.resize(1); 442 tx1.vin[0].scriptSig = CScript() << OP_1; 443 tx1.vout.resize(1); 444 tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL; 445 tx1.vout[0].nValue = 10 * COIN; 446 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx1)); 447 448 CMutableTransaction tx2 = CMutableTransaction(); 449 tx2.vin.resize(1); 450 tx2.vin[0].scriptSig = CScript() << OP_2; 451 tx2.vout.resize(1); 452 tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL; 453 tx2.vout[0].nValue = 10 * COIN; 454 AddToMempool(pool, entry.Fee(5000LL).FromTx(tx2)); 455 456 pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing 457 BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash()))); 458 BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash()))); 459 460 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction 461 BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash()))); 462 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash()))); 463 464 AddToMempool(pool, entry.FromTx(tx2)); 465 CMutableTransaction tx3 = CMutableTransaction(); 466 tx3.vin.resize(1); 467 tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0); 468 tx3.vin[0].scriptSig = CScript() << OP_2; 469 tx3.vout.resize(1); 470 tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL; 471 tx3.vout[0].nValue = 10 * COIN; 472 AddToMempool(pool, entry.Fee(20000LL).FromTx(tx3)); 473 474 pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP) 475 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash()))); 476 BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash()))); 477 BOOST_CHECK(pool.exists(GenTxid::Txid(tx3.GetHash()))); 478 479 pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits 480 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash()))); 481 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash()))); 482 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx3.GetHash()))); 483 484 CFeeRate maxFeeRateRemoved(25000, GetVirtualTransactionSize(CTransaction(tx3)) + GetVirtualTransactionSize(CTransaction(tx2))); 485 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000); 486 487 CMutableTransaction tx4 = CMutableTransaction(); 488 tx4.vin.resize(2); 489 tx4.vin[0].prevout.SetNull(); 490 tx4.vin[0].scriptSig = CScript() << OP_4; 491 tx4.vin[1].prevout.SetNull(); 492 tx4.vin[1].scriptSig = CScript() << OP_4; 493 tx4.vout.resize(2); 494 tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL; 495 tx4.vout[0].nValue = 10 * COIN; 496 tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL; 497 tx4.vout[1].nValue = 10 * COIN; 498 499 CMutableTransaction tx5 = CMutableTransaction(); 500 tx5.vin.resize(2); 501 tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0); 502 tx5.vin[0].scriptSig = CScript() << OP_4; 503 tx5.vin[1].prevout.SetNull(); 504 tx5.vin[1].scriptSig = CScript() << OP_5; 505 tx5.vout.resize(2); 506 tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL; 507 tx5.vout[0].nValue = 10 * COIN; 508 tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL; 509 tx5.vout[1].nValue = 10 * COIN; 510 511 CMutableTransaction tx6 = CMutableTransaction(); 512 tx6.vin.resize(2); 513 tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1); 514 tx6.vin[0].scriptSig = CScript() << OP_4; 515 tx6.vin[1].prevout.SetNull(); 516 tx6.vin[1].scriptSig = CScript() << OP_6; 517 tx6.vout.resize(2); 518 tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL; 519 tx6.vout[0].nValue = 10 * COIN; 520 tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL; 521 tx6.vout[1].nValue = 10 * COIN; 522 523 CMutableTransaction tx7 = CMutableTransaction(); 524 tx7.vin.resize(2); 525 tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0); 526 tx7.vin[0].scriptSig = CScript() << OP_5; 527 tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0); 528 tx7.vin[1].scriptSig = CScript() << OP_6; 529 tx7.vout.resize(2); 530 tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL; 531 tx7.vout[0].nValue = 10 * COIN; 532 tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL; 533 tx7.vout[1].nValue = 10 * COIN; 534 535 AddToMempool(pool, entry.Fee(7000LL).FromTx(tx4)); 536 AddToMempool(pool, entry.Fee(1000LL).FromTx(tx5)); 537 AddToMempool(pool, entry.Fee(1100LL).FromTx(tx6)); 538 AddToMempool(pool, entry.Fee(9000LL).FromTx(tx7)); 539 540 // we only require this to remove, at max, 2 txn, because it's not clear what we're really optimizing for aside from that 541 pool.TrimToSize(pool.DynamicMemoryUsage() - 1); 542 BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash()))); 543 BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash()))); 544 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash()))); 545 546 if (!pool.exists(GenTxid::Txid(tx5.GetHash()))) 547 AddToMempool(pool, entry.Fee(1000LL).FromTx(tx5)); 548 AddToMempool(pool, entry.Fee(9000LL).FromTx(tx7)); 549 550 pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7 551 BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash()))); 552 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx5.GetHash()))); 553 BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash()))); 554 BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash()))); 555 556 AddToMempool(pool, entry.Fee(1000LL).FromTx(tx5)); 557 AddToMempool(pool, entry.Fee(9000LL).FromTx(tx7)); 558 559 std::vector<CTransactionRef> vtx; 560 SetMockTime(42); 561 SetMockTime(42 + CTxMemPool::ROLLING_FEE_HALFLIFE); 562 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000); 563 // ... we should keep the same min fee until we get a block 564 pool.removeForBlock(vtx, 1); 565 SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE); 566 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/2.0)); 567 // ... then feerate should drop 1/2 each halflife 568 569 SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2); 570 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/4.0)); 571 // ... with a 1/2 halflife when mempool is < 1/2 its target size 572 573 SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4); 574 BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/8.0)); 575 // ... with a 1/4 halflife when mempool is < 1/4 its target size 576 577 SetMockTime(42 + 7*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4); 578 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000); 579 // ... but feerate should never drop below 1000 580 581 SetMockTime(42 + 8*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4); 582 BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0); 583 // ... unless it has gone all the way to 0 (after getting past 1000/2) 584 } 585 586 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>()) 587 { 588 CMutableTransaction tx = CMutableTransaction(); 589 tx.vin.resize(inputs.size()); 590 tx.vout.resize(output_values.size()); 591 for (size_t i = 0; i < inputs.size(); ++i) { 592 tx.vin[i].prevout.hash = inputs[i]->GetHash(); 593 tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0; 594 } 595 for (size_t i = 0; i < output_values.size(); ++i) { 596 tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 597 tx.vout[i].nValue = output_values[i]; 598 } 599 return MakeTransactionRef(tx); 600 } 601 602 603 BOOST_AUTO_TEST_CASE(MempoolAncestryTests) 604 { 605 size_t ancestors, descendants; 606 607 CTxMemPool& pool = *Assert(m_node.mempool); 608 LOCK2(cs_main, pool.cs); 609 TestMemPoolEntryHelper entry; 610 611 /* Base transaction */ 612 // 613 // [tx1] 614 // 615 CTransactionRef tx1 = make_tx(/*output_values=*/{10 * COIN}); 616 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx1)); 617 618 // Ancestors / descendants should be 1 / 1 (itself / itself) 619 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants); 620 BOOST_CHECK_EQUAL(ancestors, 1ULL); 621 BOOST_CHECK_EQUAL(descendants, 1ULL); 622 623 /* Child transaction */ 624 // 625 // [tx1].0 <- [tx2] 626 // 627 CTransactionRef tx2 = make_tx(/*output_values=*/{495 * CENT, 5 * COIN}, /*inputs=*/{tx1}); 628 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx2)); 629 630 // Ancestors / descendants should be: 631 // transaction ancestors descendants 632 // ============ =========== =========== 633 // tx1 1 (tx1) 2 (tx1,2) 634 // tx2 2 (tx1,2) 2 (tx1,2) 635 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants); 636 BOOST_CHECK_EQUAL(ancestors, 1ULL); 637 BOOST_CHECK_EQUAL(descendants, 2ULL); 638 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants); 639 BOOST_CHECK_EQUAL(ancestors, 2ULL); 640 BOOST_CHECK_EQUAL(descendants, 2ULL); 641 642 /* Grand-child 1 */ 643 // 644 // [tx1].0 <- [tx2].0 <- [tx3] 645 // 646 CTransactionRef tx3 = make_tx(/*output_values=*/{290 * CENT, 200 * CENT}, /*inputs=*/{tx2}); 647 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx3)); 648 649 // Ancestors / descendants should be: 650 // transaction ancestors descendants 651 // ============ =========== =========== 652 // tx1 1 (tx1) 3 (tx1,2,3) 653 // tx2 2 (tx1,2) 3 (tx1,2,3) 654 // tx3 3 (tx1,2,3) 3 (tx1,2,3) 655 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants); 656 BOOST_CHECK_EQUAL(ancestors, 1ULL); 657 BOOST_CHECK_EQUAL(descendants, 3ULL); 658 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants); 659 BOOST_CHECK_EQUAL(ancestors, 2ULL); 660 BOOST_CHECK_EQUAL(descendants, 3ULL); 661 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants); 662 BOOST_CHECK_EQUAL(ancestors, 3ULL); 663 BOOST_CHECK_EQUAL(descendants, 3ULL); 664 665 /* Grand-child 2 */ 666 // 667 // [tx1].0 <- [tx2].0 <- [tx3] 668 // | 669 // \---1 <- [tx4] 670 // 671 CTransactionRef tx4 = make_tx(/*output_values=*/{290 * CENT, 250 * CENT}, /*inputs=*/{tx2}, /*input_indices=*/{1}); 672 AddToMempool(pool, entry.Fee(10000LL).FromTx(tx4)); 673 674 // Ancestors / descendants should be: 675 // transaction ancestors descendants 676 // ============ =========== =========== 677 // tx1 1 (tx1) 4 (tx1,2,3,4) 678 // tx2 2 (tx1,2) 4 (tx1,2,3,4) 679 // tx3 3 (tx1,2,3) 4 (tx1,2,3,4) 680 // tx4 3 (tx1,2,4) 4 (tx1,2,3,4) 681 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants); 682 BOOST_CHECK_EQUAL(ancestors, 1ULL); 683 BOOST_CHECK_EQUAL(descendants, 4ULL); 684 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants); 685 BOOST_CHECK_EQUAL(ancestors, 2ULL); 686 BOOST_CHECK_EQUAL(descendants, 4ULL); 687 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants); 688 BOOST_CHECK_EQUAL(ancestors, 3ULL); 689 BOOST_CHECK_EQUAL(descendants, 4ULL); 690 pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants); 691 BOOST_CHECK_EQUAL(ancestors, 3ULL); 692 BOOST_CHECK_EQUAL(descendants, 4ULL); 693 694 /* Make an alternate branch that is longer and connect it to tx3 */ 695 // 696 // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0 697 // | 698 // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/ 699 // | 700 // \---1 <- [tx4] 701 // 702 CTransactionRef ty1, ty2, ty3, ty4, ty5; 703 CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5}; 704 CAmount v = 5 * COIN; 705 for (uint64_t i = 0; i < 5; i++) { 706 CTransactionRef& tyi = *ty[i]; 707 tyi = make_tx(/*output_values=*/{v}, /*inputs=*/i > 0 ? std::vector<CTransactionRef>{*ty[i - 1]} : std::vector<CTransactionRef>{}); 708 v -= 50 * CENT; 709 AddToMempool(pool, entry.Fee(10000LL).FromTx(tyi)); 710 pool.GetTransactionAncestry(tyi->GetHash(), ancestors, descendants); 711 BOOST_CHECK_EQUAL(ancestors, i+1); 712 BOOST_CHECK_EQUAL(descendants, i+1); 713 } 714 CTransactionRef ty6 = make_tx(/*output_values=*/{5 * COIN}, /*inputs=*/{tx3, ty5}); 715 AddToMempool(pool, entry.Fee(10000LL).FromTx(ty6)); 716 717 // Ancestors / descendants should be: 718 // transaction ancestors descendants 719 // ============ =================== =========== 720 // tx1 1 (tx1) 5 (tx1,2,3,4, ty6) 721 // tx2 2 (tx1,2) 5 (tx1,2,3,4, ty6) 722 // tx3 3 (tx1,2,3) 5 (tx1,2,3,4, ty6) 723 // tx4 3 (tx1,2,4) 5 (tx1,2,3,4, ty6) 724 // ty1 1 (ty1) 6 (ty1,2,3,4,5,6) 725 // ty2 2 (ty1,2) 6 (ty1,2,3,4,5,6) 726 // ty3 3 (ty1,2,3) 6 (ty1,2,3,4,5,6) 727 // ty4 4 (y1234) 6 (ty1,2,3,4,5,6) 728 // ty5 5 (y12345) 6 (ty1,2,3,4,5,6) 729 // ty6 9 (tx123, ty123456) 6 (ty1,2,3,4,5,6) 730 pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants); 731 BOOST_CHECK_EQUAL(ancestors, 1ULL); 732 BOOST_CHECK_EQUAL(descendants, 5ULL); 733 pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants); 734 BOOST_CHECK_EQUAL(ancestors, 2ULL); 735 BOOST_CHECK_EQUAL(descendants, 5ULL); 736 pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants); 737 BOOST_CHECK_EQUAL(ancestors, 3ULL); 738 BOOST_CHECK_EQUAL(descendants, 5ULL); 739 pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants); 740 BOOST_CHECK_EQUAL(ancestors, 3ULL); 741 BOOST_CHECK_EQUAL(descendants, 5ULL); 742 pool.GetTransactionAncestry(ty1->GetHash(), ancestors, descendants); 743 BOOST_CHECK_EQUAL(ancestors, 1ULL); 744 BOOST_CHECK_EQUAL(descendants, 6ULL); 745 pool.GetTransactionAncestry(ty2->GetHash(), ancestors, descendants); 746 BOOST_CHECK_EQUAL(ancestors, 2ULL); 747 BOOST_CHECK_EQUAL(descendants, 6ULL); 748 pool.GetTransactionAncestry(ty3->GetHash(), ancestors, descendants); 749 BOOST_CHECK_EQUAL(ancestors, 3ULL); 750 BOOST_CHECK_EQUAL(descendants, 6ULL); 751 pool.GetTransactionAncestry(ty4->GetHash(), ancestors, descendants); 752 BOOST_CHECK_EQUAL(ancestors, 4ULL); 753 BOOST_CHECK_EQUAL(descendants, 6ULL); 754 pool.GetTransactionAncestry(ty5->GetHash(), ancestors, descendants); 755 BOOST_CHECK_EQUAL(ancestors, 5ULL); 756 BOOST_CHECK_EQUAL(descendants, 6ULL); 757 pool.GetTransactionAncestry(ty6->GetHash(), ancestors, descendants); 758 BOOST_CHECK_EQUAL(ancestors, 9ULL); 759 BOOST_CHECK_EQUAL(descendants, 6ULL); 760 } 761 762 BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond) 763 { 764 size_t ancestors, descendants; 765 766 CTxMemPool& pool = *Assert(m_node.mempool); 767 LOCK2(::cs_main, pool.cs); 768 TestMemPoolEntryHelper entry; 769 770 /* Ancestors represented more than once ("diamond") */ 771 // 772 // [ta].0 <- [tb].0 -----<------- [td].0 773 // | | 774 // \---1 <- [tc].0 --<--/ 775 // 776 CTransactionRef ta, tb, tc, td; 777 ta = make_tx(/*output_values=*/{10 * COIN}); 778 tb = make_tx(/*output_values=*/{5 * COIN, 3 * COIN}, /*inputs=*/ {ta}); 779 tc = make_tx(/*output_values=*/{2 * COIN}, /*inputs=*/{tb}, /*input_indices=*/{1}); 780 td = make_tx(/*output_values=*/{6 * COIN}, /*inputs=*/{tb, tc}, /*input_indices=*/{0, 0}); 781 AddToMempool(pool, entry.Fee(10000LL).FromTx(ta)); 782 AddToMempool(pool, entry.Fee(10000LL).FromTx(tb)); 783 AddToMempool(pool, entry.Fee(10000LL).FromTx(tc)); 784 AddToMempool(pool, entry.Fee(10000LL).FromTx(td)); 785 786 // Ancestors / descendants should be: 787 // transaction ancestors descendants 788 // ============ =================== =========== 789 // ta 1 (ta 4 (ta,tb,tc,td) 790 // tb 2 (ta,tb) 4 (ta,tb,tc,td) 791 // tc 3 (ta,tb,tc) 4 (ta,tb,tc,td) 792 // td 4 (ta,tb,tc,td) 4 (ta,tb,tc,td) 793 pool.GetTransactionAncestry(ta->GetHash(), ancestors, descendants); 794 BOOST_CHECK_EQUAL(ancestors, 1ULL); 795 BOOST_CHECK_EQUAL(descendants, 4ULL); 796 pool.GetTransactionAncestry(tb->GetHash(), ancestors, descendants); 797 BOOST_CHECK_EQUAL(ancestors, 2ULL); 798 BOOST_CHECK_EQUAL(descendants, 4ULL); 799 pool.GetTransactionAncestry(tc->GetHash(), ancestors, descendants); 800 BOOST_CHECK_EQUAL(ancestors, 3ULL); 801 BOOST_CHECK_EQUAL(descendants, 4ULL); 802 pool.GetTransactionAncestry(td->GetHash(), ancestors, descendants); 803 BOOST_CHECK_EQUAL(ancestors, 4ULL); 804 BOOST_CHECK_EQUAL(descendants, 4ULL); 805 } 806 807 BOOST_AUTO_TEST_SUITE_END()