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