rbf_tests.cpp
1 // Copyright (c) 2021-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 #include <common/system.h> 5 #include <policy/rbf.h> 6 #include <random.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 <optional> 15 #include <vector> 16 17 BOOST_FIXTURE_TEST_SUITE(rbf_tests, TestingSetup) 18 19 static inline CTransactionRef make_tx(const std::vector<CTransactionRef>& inputs, 20 const std::vector<CAmount>& output_values) 21 { 22 CMutableTransaction tx = CMutableTransaction(); 23 tx.vin.resize(inputs.size()); 24 tx.vout.resize(output_values.size()); 25 for (size_t i = 0; i < inputs.size(); ++i) { 26 tx.vin[i].prevout.hash = inputs[i]->GetHash(); 27 tx.vin[i].prevout.n = 0; 28 // Add a witness so wtxid != txid 29 CScriptWitness witness; 30 witness.stack.emplace_back(i + 10); 31 tx.vin[i].scriptWitness = witness; 32 } 33 for (size_t i = 0; i < output_values.size(); ++i) { 34 tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 35 tx.vout[i].nValue = output_values[i]; 36 } 37 return MakeTransactionRef(tx); 38 } 39 40 // Make two child transactions from parent (which must have at least 2 outputs). 41 // Each tx will have the same outputs, using the amounts specified in output_values. 42 static inline std::pair<CTransactionRef, CTransactionRef> make_two_siblings(const CTransactionRef parent, 43 const std::vector<CAmount>& output_values) 44 { 45 assert(parent->vout.size() >= 2); 46 47 // First tx takes first parent output 48 CMutableTransaction tx1 = CMutableTransaction(); 49 tx1.vin.resize(1); 50 tx1.vout.resize(output_values.size()); 51 52 tx1.vin[0].prevout.hash = parent->GetHash(); 53 tx1.vin[0].prevout.n = 0; 54 // Add a witness so wtxid != txid 55 CScriptWitness witness; 56 witness.stack.emplace_back(10); 57 tx1.vin[0].scriptWitness = witness; 58 59 for (size_t i = 0; i < output_values.size(); ++i) { 60 tx1.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL; 61 tx1.vout[i].nValue = output_values[i]; 62 } 63 64 // Second tx takes second parent output 65 CMutableTransaction tx2 = tx1; 66 tx2.vin[0].prevout.n = 1; 67 68 return std::make_pair(MakeTransactionRef(tx1), MakeTransactionRef(tx2)); 69 } 70 71 static CTransactionRef add_descendants(const CTransactionRef& tx, int32_t num_descendants, CTxMemPool& pool) 72 EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs) 73 { 74 AssertLockHeld(::cs_main); 75 AssertLockHeld(pool.cs); 76 TestMemPoolEntryHelper entry; 77 // Assumes this isn't already spent in mempool 78 auto tx_to_spend = tx; 79 for (int32_t i{0}; i < num_descendants; ++i) { 80 auto next_tx = make_tx(/*inputs=*/{tx_to_spend}, /*output_values=*/{(50 - i) * CENT}); 81 AddToMempool(pool, entry.FromTx(next_tx)); 82 tx_to_spend = next_tx; 83 } 84 // Return last created tx 85 return tx_to_spend; 86 } 87 88 static CTransactionRef add_descendant_to_parents(const std::vector<CTransactionRef>& parents, CTxMemPool& pool) 89 EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs) 90 { 91 AssertLockHeld(::cs_main); 92 AssertLockHeld(pool.cs); 93 TestMemPoolEntryHelper entry; 94 // Assumes this isn't already spent in mempool 95 auto child_tx = make_tx(/*inputs=*/parents, /*output_values=*/{50 * CENT}); 96 AddToMempool(pool, entry.FromTx(child_tx)); 97 // Return last created tx 98 return child_tx; 99 } 100 101 // Makes two children for a single parent 102 static std::pair<CTransactionRef, CTransactionRef> add_children_to_parent(const CTransactionRef parent, CTxMemPool& pool) 103 EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs) 104 { 105 AssertLockHeld(::cs_main); 106 AssertLockHeld(pool.cs); 107 TestMemPoolEntryHelper entry; 108 // Assumes this isn't already spent in mempool 109 auto children_tx = make_two_siblings(/*parent=*/parent, /*output_values=*/{50 * CENT}); 110 AddToMempool(pool, entry.FromTx(children_tx.first)); 111 AddToMempool(pool, entry.FromTx(children_tx.second)); 112 return children_tx; 113 } 114 115 BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup) 116 { 117 CTxMemPool& pool = *Assert(m_node.mempool); 118 LOCK2(::cs_main, pool.cs); 119 TestMemPoolEntryHelper entry; 120 121 const CAmount low_fee{CENT/100}; 122 const CAmount normal_fee{CENT/10}; 123 const CAmount high_fee{CENT}; 124 125 // Create a parent tx1 and child tx2 with normal fees: 126 const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN}); 127 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx1)); 128 const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT}); 129 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx2)); 130 131 // Create a low-feerate parent tx3 and high-feerate child tx4 (cpfp) 132 const auto tx3 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {1099 * CENT}); 133 AddToMempool(pool, entry.Fee(low_fee).FromTx(tx3)); 134 const auto tx4 = make_tx(/*inputs=*/ {tx3}, /*output_values=*/ {999 * CENT}); 135 AddToMempool(pool, entry.Fee(high_fee).FromTx(tx4)); 136 137 // Create a parent tx5 and child tx6 where both have very low fees 138 const auto tx5 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {1099 * CENT}); 139 AddToMempool(pool, entry.Fee(low_fee).FromTx(tx5)); 140 const auto tx6 = make_tx(/*inputs=*/ {tx5}, /*output_values=*/ {1098 * CENT}); 141 AddToMempool(pool, entry.Fee(low_fee).FromTx(tx6)); 142 // Make tx6's modified fee much higher than its base fee. This should cause it to pass 143 // the fee-related checks despite being low-feerate. 144 pool.PrioritiseTransaction(tx6->GetHash(), 1 * COIN); 145 146 // Two independent high-feerate transactions, tx7 and tx8 147 const auto tx7 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {999 * CENT}); 148 AddToMempool(pool, entry.Fee(high_fee).FromTx(tx7)); 149 const auto tx8 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {999 * CENT}); 150 AddToMempool(pool, entry.Fee(high_fee).FromTx(tx8)); 151 152 // Normal txs, will chain txns right before CheckConflictTopology test 153 const auto tx9 = make_tx(/*inputs=*/ {m_coinbase_txns[5]}, /*output_values=*/ {995 * CENT}); 154 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx9)); 155 const auto tx10 = make_tx(/*inputs=*/ {m_coinbase_txns[6]}, /*output_values=*/ {995 * CENT}); 156 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx10)); 157 158 // Will make these two parents of single child 159 const auto tx11 = make_tx(/*inputs=*/ {m_coinbase_txns[7]}, /*output_values=*/ {995 * CENT}); 160 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx11)); 161 const auto tx12 = make_tx(/*inputs=*/ {m_coinbase_txns[8]}, /*output_values=*/ {995 * CENT}); 162 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx12)); 163 164 // Will make two children of this single parent 165 const auto tx13 = make_tx(/*inputs=*/ {m_coinbase_txns[9]}, /*output_values=*/ {995 * CENT, 995 * CENT}); 166 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx13)); 167 168 const auto entry1_normal = pool.GetIter(tx1->GetHash()).value(); 169 const auto entry2_normal = pool.GetIter(tx2->GetHash()).value(); 170 const auto entry3_low = pool.GetIter(tx3->GetHash()).value(); 171 const auto entry4_high = pool.GetIter(tx4->GetHash()).value(); 172 const auto entry5_low = pool.GetIter(tx5->GetHash()).value(); 173 const auto entry6_low_prioritised = pool.GetIter(tx6->GetHash()).value(); 174 const auto entry7_high = pool.GetIter(tx7->GetHash()).value(); 175 const auto entry8_high = pool.GetIter(tx8->GetHash()).value(); 176 const auto entry9_unchained = pool.GetIter(tx9->GetHash()).value(); 177 const auto entry10_unchained = pool.GetIter(tx10->GetHash()).value(); 178 const auto entry11_unchained = pool.GetIter(tx11->GetHash()).value(); 179 const auto entry12_unchained = pool.GetIter(tx12->GetHash()).value(); 180 const auto entry13_unchained = pool.GetIter(tx13->GetHash()).value(); 181 182 BOOST_CHECK_EQUAL(entry1_normal->GetFee(), normal_fee); 183 BOOST_CHECK_EQUAL(entry2_normal->GetFee(), normal_fee); 184 BOOST_CHECK_EQUAL(entry3_low->GetFee(), low_fee); 185 BOOST_CHECK_EQUAL(entry4_high->GetFee(), high_fee); 186 BOOST_CHECK_EQUAL(entry5_low->GetFee(), low_fee); 187 BOOST_CHECK_EQUAL(entry6_low_prioritised->GetFee(), low_fee); 188 BOOST_CHECK_EQUAL(entry7_high->GetFee(), high_fee); 189 BOOST_CHECK_EQUAL(entry8_high->GetFee(), high_fee); 190 191 CTxMemPool::setEntries set_12_normal{entry1_normal, entry2_normal}; 192 CTxMemPool::setEntries set_34_cpfp{entry3_low, entry4_high}; 193 CTxMemPool::setEntries set_56_low{entry5_low, entry6_low_prioritised}; 194 CTxMemPool::setEntries set_78_high{entry7_high, entry8_high}; 195 CTxMemPool::setEntries all_entries{entry1_normal, entry2_normal, entry3_low, entry4_high, 196 entry5_low, entry6_low_prioritised, entry7_high, entry8_high}; 197 CTxMemPool::setEntries empty_set; 198 199 const auto unused_txid{GetRandHash()}; 200 201 // Tests for PaysMoreThanConflicts 202 // These tests use feerate, not absolute fee. 203 BOOST_CHECK(PaysMoreThanConflicts(/*iters_conflicting=*/set_12_normal, 204 /*replacement_feerate=*/CFeeRate(entry1_normal->GetModifiedFee() + 1, entry1_normal->GetTxSize() + 2), 205 /*txid=*/unused_txid).has_value()); 206 // Replacement must be strictly greater than the originals. 207 BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1_normal->GetModifiedFee(), entry1_normal->GetTxSize()), unused_txid).has_value()); 208 BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1_normal->GetModifiedFee() + 1, entry1_normal->GetTxSize()), unused_txid) == std::nullopt); 209 // These tests use modified fees (including prioritisation), not base fees. 210 BOOST_CHECK(PaysMoreThanConflicts({entry5_low}, CFeeRate(entry5_low->GetModifiedFee() + 1, entry5_low->GetTxSize()), unused_txid) == std::nullopt); 211 BOOST_CHECK(PaysMoreThanConflicts({entry6_low_prioritised}, CFeeRate(entry6_low_prioritised->GetFee() + 1, entry6_low_prioritised->GetTxSize()), unused_txid).has_value()); 212 BOOST_CHECK(PaysMoreThanConflicts({entry6_low_prioritised}, CFeeRate(entry6_low_prioritised->GetModifiedFee() + 1, entry6_low_prioritised->GetTxSize()), unused_txid) == std::nullopt); 213 // PaysMoreThanConflicts checks individual feerate, not ancestor feerate. This test compares 214 // replacement_feerate and entry4_high's feerate, which are the same. The replacement_feerate is 215 // considered too low even though entry4_high has a low ancestor feerate. 216 BOOST_CHECK(PaysMoreThanConflicts(set_34_cpfp, CFeeRate(entry4_high->GetModifiedFee(), entry4_high->GetTxSize()), unused_txid).has_value()); 217 218 // Tests for EntriesAndTxidsDisjoint 219 BOOST_CHECK(EntriesAndTxidsDisjoint(empty_set, {tx1->GetHash()}, unused_txid) == std::nullopt); 220 BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx3->GetHash()}, unused_txid) == std::nullopt); 221 BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx2->GetHash()}, unused_txid).has_value()); 222 BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx1->GetHash()}, unused_txid).has_value()); 223 BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx2->GetHash()}, unused_txid).has_value()); 224 // EntriesAndTxidsDisjoint does not calculate descendants of iters_conflicting; it uses whatever 225 // the caller passed in. As such, no error is returned even though entry2_normal is a descendant of tx1. 226 BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx1->GetHash()}, unused_txid) == std::nullopt); 227 228 // Tests for PaysForRBF 229 const CFeeRate incremental_relay_feerate{DEFAULT_INCREMENTAL_RELAY_FEE}; 230 const CFeeRate higher_relay_feerate{2 * DEFAULT_INCREMENTAL_RELAY_FEE}; 231 // Must pay at least as much as the original. 232 BOOST_CHECK(PaysForRBF(/*original_fees=*/high_fee, 233 /*replacement_fees=*/high_fee, 234 /*replacement_vsize=*/1, 235 /*relay_fee=*/CFeeRate(0), 236 /*txid=*/unused_txid) 237 == std::nullopt); 238 BOOST_CHECK(PaysForRBF(high_fee, high_fee - 1, 1, CFeeRate(0), unused_txid).has_value()); 239 BOOST_CHECK(PaysForRBF(high_fee + 1, high_fee, 1, CFeeRate(0), unused_txid).has_value()); 240 // Additional fees must cover the replacement's vsize at incremental relay fee 241 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 1, 2, incremental_relay_feerate, unused_txid).has_value()); 242 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 2, 2, incremental_relay_feerate, unused_txid) == std::nullopt); 243 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 2, 2, higher_relay_feerate, unused_txid).has_value()); 244 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 4, 2, higher_relay_feerate, unused_txid) == std::nullopt); 245 BOOST_CHECK(PaysForRBF(low_fee, high_fee, 99999999, incremental_relay_feerate, unused_txid).has_value()); 246 BOOST_CHECK(PaysForRBF(low_fee, high_fee + 99999999, 99999999, incremental_relay_feerate, unused_txid) == std::nullopt); 247 248 // Tests for GetEntriesForConflicts 249 CTxMemPool::setEntries all_parents{entry1_normal, entry3_low, entry5_low, entry7_high, entry8_high}; 250 CTxMemPool::setEntries all_children{entry2_normal, entry4_high, entry6_low_prioritised}; 251 const std::vector<CTransactionRef> parent_inputs({m_coinbase_txns[0], m_coinbase_txns[1], m_coinbase_txns[2], 252 m_coinbase_txns[3], m_coinbase_txns[4]}); 253 const auto conflicts_with_parents = make_tx(parent_inputs, {50 * CENT}); 254 CTxMemPool::setEntries all_conflicts; 255 BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicts_with_parents.get(), 256 /*pool=*/ pool, 257 /*iters_conflicting=*/ all_parents, 258 /*all_conflicts=*/ all_conflicts) == std::nullopt); 259 BOOST_CHECK(all_conflicts == all_entries); 260 auto conflicts_size = all_conflicts.size(); 261 all_conflicts.clear(); 262 263 add_descendants(tx2, 23, pool); 264 BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt); 265 conflicts_size += 23; 266 BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size); 267 all_conflicts.clear(); 268 269 add_descendants(tx4, 23, pool); 270 BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt); 271 conflicts_size += 23; 272 BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size); 273 all_conflicts.clear(); 274 275 add_descendants(tx6, 23, pool); 276 BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt); 277 conflicts_size += 23; 278 BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size); 279 all_conflicts.clear(); 280 281 add_descendants(tx7, 23, pool); 282 BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt); 283 conflicts_size += 23; 284 BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size); 285 BOOST_CHECK_EQUAL(all_conflicts.size(), 100); 286 all_conflicts.clear(); 287 288 // Exceeds maximum number of conflicts. 289 add_descendants(tx8, 1, pool); 290 BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts).has_value()); 291 292 // Tests for HasNoNewUnconfirmed 293 const auto spends_unconfirmed = make_tx({tx1}, {36 * CENT}); 294 for (const auto& input : spends_unconfirmed->vin) { 295 // Spends unconfirmed inputs. 296 BOOST_CHECK(pool.exists(GenTxid::Txid(input.prevout.hash))); 297 } 298 BOOST_CHECK(HasNoNewUnconfirmed(/*tx=*/ *spends_unconfirmed.get(), 299 /*pool=*/ pool, 300 /*iters_conflicting=*/ all_entries) == std::nullopt); 301 BOOST_CHECK(HasNoNewUnconfirmed(*spends_unconfirmed.get(), pool, {entry2_normal}) == std::nullopt); 302 BOOST_CHECK(HasNoNewUnconfirmed(*spends_unconfirmed.get(), pool, empty_set).has_value()); 303 304 const auto spends_new_unconfirmed = make_tx({tx1, tx8}, {36 * CENT}); 305 BOOST_CHECK(HasNoNewUnconfirmed(*spends_new_unconfirmed.get(), pool, {entry2_normal}).has_value()); 306 BOOST_CHECK(HasNoNewUnconfirmed(*spends_new_unconfirmed.get(), pool, all_entries).has_value()); 307 308 const auto spends_conflicting_confirmed = make_tx({m_coinbase_txns[0], m_coinbase_txns[1]}, {45 * CENT}); 309 BOOST_CHECK(HasNoNewUnconfirmed(*spends_conflicting_confirmed.get(), pool, {entry1_normal, entry3_low}) == std::nullopt); 310 311 // Tests for CheckConflictTopology 312 313 // Tx4 has 23 descendants 314 BOOST_CHECK_EQUAL(pool.CheckConflictTopology(set_34_cpfp).value(), strprintf("%s has 23 descendants, max 1 allowed", entry4_high->GetSharedTx()->GetHash().ToString())); 315 316 // No descendants yet 317 BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained}) == std::nullopt); 318 319 // Add 1 descendant, still ok 320 add_descendants(tx9, 1, pool); 321 BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained}) == std::nullopt); 322 323 // N direct conflicts; ok 324 BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}) == std::nullopt); 325 326 // Add 1 descendant, still ok, even if it's considered a direct conflict as well 327 const auto child_tx = add_descendants(tx10, 1, pool); 328 const auto entry10_child = pool.GetIter(child_tx->GetHash()).value(); 329 BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}) == std::nullopt); 330 BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained, entry10_child}) == std::nullopt); 331 332 // One more, size 3 cluster too much 333 const auto grand_child_tx = add_descendants(child_tx, 1, pool); 334 const auto entry10_grand_child = pool.GetIter(grand_child_tx->GetHash()).value(); 335 BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}).value(), strprintf("%s has 2 descendants, max 1 allowed", entry10_unchained->GetSharedTx()->GetHash().ToString())); 336 // even if direct conflict is descendent itself 337 BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry9_unchained, entry10_grand_child, entry11_unchained}).value(), strprintf("%s has 2 ancestors, max 1 allowed", entry10_grand_child->GetSharedTx()->GetHash().ToString())); 338 339 // Make a single child from two singleton parents 340 const auto two_parent_child_tx = add_descendant_to_parents({tx11, tx12}, pool); 341 const auto entry_two_parent_child = pool.GetIter(two_parent_child_tx->GetHash()).value(); 342 BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry11_unchained}).value(), strprintf("%s is not the only parent of child %s", entry11_unchained->GetSharedTx()->GetHash().ToString(), entry_two_parent_child->GetSharedTx()->GetHash().ToString())); 343 BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry12_unchained}).value(), strprintf("%s is not the only parent of child %s", entry12_unchained->GetSharedTx()->GetHash().ToString(), entry_two_parent_child->GetSharedTx()->GetHash().ToString())); 344 BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry_two_parent_child}).value(), strprintf("%s has 2 ancestors, max 1 allowed", entry_two_parent_child->GetSharedTx()->GetHash().ToString())); 345 346 // Single parent with two children, we will conflict with the siblings directly only 347 const auto two_siblings = add_children_to_parent(tx13, pool); 348 const auto entry_sibling_1 = pool.GetIter(two_siblings.first->GetHash()).value(); 349 const auto entry_sibling_2 = pool.GetIter(two_siblings.second->GetHash()).value(); 350 BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry_sibling_1}).value(), strprintf("%s is not the only child of parent %s", entry_sibling_1->GetSharedTx()->GetHash().ToString(), entry13_unchained->GetSharedTx()->GetHash().ToString())); 351 BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry_sibling_2}).value(), strprintf("%s is not the only child of parent %s", entry_sibling_2->GetSharedTx()->GetHash().ToString(), entry13_unchained->GetSharedTx()->GetHash().ToString())); 352 353 } 354 355 BOOST_FIXTURE_TEST_CASE(improves_feerate, TestChain100Setup) 356 { 357 CTxMemPool& pool = *Assert(m_node.mempool); 358 LOCK2(::cs_main, pool.cs); 359 TestMemPoolEntryHelper entry; 360 361 const CAmount low_fee{CENT/100}; 362 const CAmount normal_fee{CENT/10}; 363 364 // low feerate parent with normal feerate child 365 const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0], m_coinbase_txns[1]}, /*output_values=*/ {10 * COIN}); 366 AddToMempool(pool, entry.Fee(low_fee).FromTx(tx1)); 367 const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT}); 368 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx2)); 369 370 const auto entry1 = pool.GetIter(tx1->GetHash()).value(); 371 const auto tx1_fee = entry1->GetModifiedFee(); 372 const auto entry2 = pool.GetIter(tx2->GetHash()).value(); 373 const auto tx2_fee = entry2->GetModifiedFee(); 374 375 // conflicting transactions 376 const auto tx1_conflict = make_tx(/*inputs=*/ {m_coinbase_txns[0], m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN}); 377 const auto tx3 = make_tx(/*inputs=*/ {tx1_conflict}, /*output_values=*/ {995 * CENT}); 378 auto entry3 = entry.FromTx(tx3); 379 380 // Now test ImprovesFeerateDiagram with various levels of "package rbf" feerates 381 382 // It doesn't improve itself 383 auto changeset = pool.GetChangeSet(); 384 changeset->StageRemoval(entry1); 385 changeset->StageRemoval(entry2); 386 changeset->StageAddition(tx1_conflict, tx1_fee, 0, 1, 0, false, 4, LockPoints()); 387 changeset->StageAddition(tx3, tx2_fee, 0, 1, 0, false, 4, LockPoints()); 388 const auto res1 = ImprovesFeerateDiagram(*changeset); 389 BOOST_CHECK(res1.has_value()); 390 BOOST_CHECK(res1.value().first == DiagramCheckError::FAILURE); 391 BOOST_CHECK(res1.value().second == "insufficient feerate: does not improve feerate diagram"); 392 393 // With one more satoshi it does 394 changeset.reset(); 395 changeset = pool.GetChangeSet(); 396 changeset->StageRemoval(entry1); 397 changeset->StageRemoval(entry2); 398 changeset->StageAddition(tx1_conflict, tx1_fee+1, 0, 1, 0, false, 4, LockPoints()); 399 changeset->StageAddition(tx3, tx2_fee, 0, 1, 0, false, 4, LockPoints()); 400 BOOST_CHECK(ImprovesFeerateDiagram(*changeset) == std::nullopt); 401 402 changeset.reset(); 403 // With prioritisation of in-mempool conflicts, it affects the results of the comparison using the same args as just above 404 pool.PrioritiseTransaction(entry1->GetSharedTx()->GetHash(), /*nFeeDelta=*/1); 405 changeset = pool.GetChangeSet(); 406 changeset->StageRemoval(entry1); 407 changeset->StageRemoval(entry2); 408 changeset->StageAddition(tx1_conflict, tx1_fee+1, 0, 1, 0, false, 4, LockPoints()); 409 changeset->StageAddition(tx3, tx2_fee, 0, 1, 0, false, 4, LockPoints()); 410 const auto res2 = ImprovesFeerateDiagram(*changeset); 411 BOOST_CHECK(res2.has_value()); 412 BOOST_CHECK(res2.value().first == DiagramCheckError::FAILURE); 413 BOOST_CHECK(res2.value().second == "insufficient feerate: does not improve feerate diagram"); 414 changeset.reset(); 415 416 pool.PrioritiseTransaction(entry1->GetSharedTx()->GetHash(), /*nFeeDelta=*/-1); 417 418 // With fewer vbytes it does 419 CMutableTransaction tx4{entry3.GetTx()}; 420 tx4.vin[0].scriptWitness = CScriptWitness(); // Clear out the witness, to reduce size 421 auto entry4 = entry.FromTx(MakeTransactionRef(tx4)); 422 changeset = pool.GetChangeSet(); 423 changeset->StageRemoval(entry1); 424 changeset->StageRemoval(entry2); 425 changeset->StageAddition(tx1_conflict, tx1_fee, 0, 1, 0, false, 4, LockPoints()); 426 changeset->StageAddition(entry4.GetSharedTx(), tx2_fee, 0, 1, 0, false, 4, LockPoints()); 427 BOOST_CHECK(ImprovesFeerateDiagram(*changeset) == std::nullopt); 428 changeset.reset(); 429 430 // Adding a grandchild makes the cluster size 3, which is uncalculable 431 const auto tx5 = make_tx(/*inputs=*/ {tx2}, /*output_values=*/ {995 * CENT}); 432 AddToMempool(pool, entry.Fee(normal_fee).FromTx(tx5)); 433 const auto entry5 = pool.GetIter(tx5->GetHash()).value(); 434 435 changeset = pool.GetChangeSet(); 436 changeset->StageRemoval(entry1); 437 changeset->StageRemoval(entry2); 438 changeset->StageRemoval(entry5); 439 changeset->StageAddition(tx1_conflict, tx1_fee, 0, 1, 0, false, 4, LockPoints()); 440 changeset->StageAddition(entry4.GetSharedTx(), tx2_fee + entry5->GetModifiedFee() + 1, 0, 1, 0, false, 4, LockPoints()); 441 const auto res3 = ImprovesFeerateDiagram(*changeset); 442 BOOST_CHECK(res3.has_value()); 443 BOOST_CHECK(res3.value().first == DiagramCheckError::UNCALCULABLE); 444 BOOST_CHECK(res3.value().second == strprintf("%s has 2 ancestors, max 1 allowed", tx5->GetHash().GetHex())); 445 } 446 447 BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) 448 { 449 CTxMemPool& pool = *Assert(m_node.mempool); 450 LOCK2(::cs_main, pool.cs); 451 TestMemPoolEntryHelper entry; 452 453 const CAmount low_fee{CENT/100}; 454 const CAmount normal_fee{CENT/10}; 455 const CAmount high_fee{CENT}; 456 457 // low -> high -> medium fee transactions that would result in two chunks together since they 458 // are all same size 459 const auto low_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN}); 460 AddToMempool(pool, entry.Fee(low_fee).FromTx(low_tx)); 461 462 const auto entry_low = pool.GetIter(low_tx->GetHash()).value(); 463 const auto low_size = entry_low->GetTxSize(); 464 465 const auto replacement_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {9 * COIN}); 466 auto entry_replacement = entry.FromTx(replacement_tx); 467 468 // Replacement of size 1 469 { 470 auto changeset = pool.GetChangeSet(); 471 changeset->StageRemoval(entry_low); 472 changeset->StageAddition(replacement_tx, 0, 0, 1, 0, false, 4, LockPoints()); 473 const auto replace_one{changeset->CalculateChunksForRBF()}; 474 BOOST_CHECK(replace_one.has_value()); 475 std::vector<FeeFrac> expected_old_chunks{{low_fee, low_size}}; 476 BOOST_CHECK(replace_one->first == expected_old_chunks); 477 std::vector<FeeFrac> expected_new_chunks{{0, int32_t(entry_replacement.GetTxSize())}}; 478 BOOST_CHECK(replace_one->second == expected_new_chunks); 479 } 480 481 // Non-zero replacement fee/size 482 { 483 auto changeset = pool.GetChangeSet(); 484 changeset->StageRemoval(entry_low); 485 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 486 const auto replace_one_fee{changeset->CalculateChunksForRBF()}; 487 BOOST_CHECK(replace_one_fee.has_value()); 488 std::vector<FeeFrac> expected_old_diagram{{low_fee, low_size}}; 489 BOOST_CHECK(replace_one_fee->first == expected_old_diagram); 490 std::vector<FeeFrac> expected_new_diagram{{high_fee, low_size}}; 491 BOOST_CHECK(replace_one_fee->second == expected_new_diagram); 492 } 493 494 // Add a second transaction to the cluster that will make a single chunk, to be evicted in the RBF 495 const auto high_tx = make_tx(/*inputs=*/ {low_tx}, /*output_values=*/ {995 * CENT}); 496 AddToMempool(pool, entry.Fee(high_fee).FromTx(high_tx)); 497 const auto entry_high = pool.GetIter(high_tx->GetHash()).value(); 498 const auto high_size = entry_high->GetTxSize(); 499 500 { 501 auto changeset = pool.GetChangeSet(); 502 changeset->StageRemoval(entry_low); 503 changeset->StageRemoval(entry_high); 504 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 505 const auto replace_single_chunk{changeset->CalculateChunksForRBF()}; 506 BOOST_CHECK(replace_single_chunk.has_value()); 507 std::vector<FeeFrac> expected_old_chunks{{low_fee + high_fee, low_size + high_size}}; 508 BOOST_CHECK(replace_single_chunk->first == expected_old_chunks); 509 std::vector<FeeFrac> expected_new_chunks{{high_fee, low_size}}; 510 BOOST_CHECK(replace_single_chunk->second == expected_new_chunks); 511 } 512 513 // Conflict with the 2nd tx, resulting in new diagram with three entries 514 { 515 auto changeset = pool.GetChangeSet(); 516 changeset->StageRemoval(entry_high); 517 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 518 const auto replace_cpfp_child{changeset->CalculateChunksForRBF()}; 519 BOOST_CHECK(replace_cpfp_child.has_value()); 520 std::vector<FeeFrac> expected_old_chunks{{low_fee + high_fee, low_size + high_size}}; 521 BOOST_CHECK(replace_cpfp_child->first == expected_old_chunks); 522 std::vector<FeeFrac> expected_new_chunks{{high_fee, low_size}, {low_fee, low_size}}; 523 BOOST_CHECK(replace_cpfp_child->second == expected_new_chunks); 524 } 525 526 // third transaction causes the topology check to fail 527 const auto normal_tx = make_tx(/*inputs=*/ {high_tx}, /*output_values=*/ {995 * CENT}); 528 AddToMempool(pool, entry.Fee(normal_fee).FromTx(normal_tx)); 529 const auto entry_normal = pool.GetIter(normal_tx->GetHash()).value(); 530 531 { 532 auto changeset = pool.GetChangeSet(); 533 changeset->StageRemoval(entry_low); 534 changeset->StageRemoval(entry_high); 535 changeset->StageRemoval(entry_normal); 536 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 537 const auto replace_too_large{changeset->CalculateChunksForRBF()}; 538 BOOST_CHECK(!replace_too_large.has_value()); 539 BOOST_CHECK_EQUAL(util::ErrorString(replace_too_large).original, strprintf("%s has 2 ancestors, max 1 allowed", normal_tx->GetHash().GetHex())); 540 } 541 542 // Make a size 2 cluster that is itself two chunks; evict both txns 543 const auto high_tx_2 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {10 * COIN}); 544 AddToMempool(pool, entry.Fee(high_fee).FromTx(high_tx_2)); 545 const auto entry_high_2 = pool.GetIter(high_tx_2->GetHash()).value(); 546 const auto high_size_2 = entry_high_2->GetTxSize(); 547 548 const auto low_tx_2 = make_tx(/*inputs=*/ {high_tx_2}, /*output_values=*/ {9 * COIN}); 549 AddToMempool(pool, entry.Fee(low_fee).FromTx(low_tx_2)); 550 const auto entry_low_2 = pool.GetIter(low_tx_2->GetHash()).value(); 551 const auto low_size_2 = entry_low_2->GetTxSize(); 552 553 { 554 auto changeset = pool.GetChangeSet(); 555 changeset->StageRemoval(entry_high_2); 556 changeset->StageRemoval(entry_low_2); 557 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 558 const auto replace_two_chunks_single_cluster{changeset->CalculateChunksForRBF()}; 559 BOOST_CHECK(replace_two_chunks_single_cluster.has_value()); 560 std::vector<FeeFrac> expected_old_chunks{{high_fee, high_size_2}, {low_fee, low_size_2}}; 561 BOOST_CHECK(replace_two_chunks_single_cluster->first == expected_old_chunks); 562 std::vector<FeeFrac> expected_new_chunks{{high_fee, low_size_2}}; 563 BOOST_CHECK(replace_two_chunks_single_cluster->second == expected_new_chunks); 564 } 565 566 // You can have more than two direct conflicts if the there are multiple affected clusters, all of size 2 or less 567 const auto conflict_1 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN}); 568 AddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_1)); 569 const auto conflict_1_entry = pool.GetIter(conflict_1->GetHash()).value(); 570 571 const auto conflict_2 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {10 * COIN}); 572 AddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_2)); 573 const auto conflict_2_entry = pool.GetIter(conflict_2->GetHash()).value(); 574 575 const auto conflict_3 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {10 * COIN}); 576 AddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_3)); 577 const auto conflict_3_entry = pool.GetIter(conflict_3->GetHash()).value(); 578 579 { 580 auto changeset = pool.GetChangeSet(); 581 changeset->StageRemoval(conflict_1_entry); 582 changeset->StageRemoval(conflict_2_entry); 583 changeset->StageRemoval(conflict_3_entry); 584 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 585 const auto replace_multiple_clusters{changeset->CalculateChunksForRBF()}; 586 BOOST_CHECK(replace_multiple_clusters.has_value()); 587 BOOST_CHECK(replace_multiple_clusters->first.size() == 3); 588 BOOST_CHECK(replace_multiple_clusters->second.size() == 1); 589 } 590 591 // Add a child transaction to conflict_1 and make it cluster size 2, two chunks due to same feerate 592 const auto conflict_1_child = make_tx(/*inputs=*/{conflict_1}, /*output_values=*/ {995 * CENT}); 593 AddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_1_child)); 594 const auto conflict_1_child_entry = pool.GetIter(conflict_1_child->GetHash()).value(); 595 596 { 597 auto changeset = pool.GetChangeSet(); 598 changeset->StageRemoval(conflict_1_entry); 599 changeset->StageRemoval(conflict_2_entry); 600 changeset->StageRemoval(conflict_3_entry); 601 changeset->StageRemoval(conflict_1_child_entry); 602 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 603 const auto replace_multiple_clusters_2{changeset->CalculateChunksForRBF()}; 604 605 BOOST_CHECK(replace_multiple_clusters_2.has_value()); 606 BOOST_CHECK(replace_multiple_clusters_2->first.size() == 4); 607 BOOST_CHECK(replace_multiple_clusters_2->second.size() == 1); 608 } 609 610 // Add another descendant to conflict_1, making the cluster size > 2 should fail at this point. 611 const auto conflict_1_grand_child = make_tx(/*inputs=*/{conflict_1_child}, /*output_values=*/ {995 * CENT}); 612 AddToMempool(pool, entry.Fee(high_fee).FromTx(conflict_1_grand_child)); 613 const auto conflict_1_grand_child_entry = pool.GetIter(conflict_1_child->GetHash()).value(); 614 615 { 616 auto changeset = pool.GetChangeSet(); 617 changeset->StageRemoval(conflict_1_entry); 618 changeset->StageRemoval(conflict_2_entry); 619 changeset->StageRemoval(conflict_3_entry); 620 changeset->StageRemoval(conflict_1_child_entry); 621 changeset->StageRemoval(conflict_1_grand_child_entry); 622 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints()); 623 const auto replace_cluster_size_3{changeset->CalculateChunksForRBF()}; 624 625 BOOST_CHECK(!replace_cluster_size_3.has_value()); 626 BOOST_CHECK_EQUAL(util::ErrorString(replace_cluster_size_3).original, strprintf("%s has both ancestor and descendant, exceeding cluster limit of 2", conflict_1_child->GetHash().GetHex())); 627 } 628 } 629 630 BOOST_AUTO_TEST_CASE(feerate_chunks_utilities) 631 { 632 // Sanity check the correctness of the feerate chunks comparison. 633 634 // A strictly better case. 635 std::vector<FeeFrac> old_chunks{{{950, 300}, {100, 100}}}; 636 std::vector<FeeFrac> new_chunks{{{1000, 300}, {50, 100}}}; 637 638 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks))); 639 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks))); 640 641 // Incomparable diagrams 642 old_chunks = {{950, 300}, {100, 100}}; 643 new_chunks = {{1000, 300}, {0, 100}}; 644 645 BOOST_CHECK(CompareChunks(old_chunks, new_chunks) == std::partial_ordering::unordered); 646 BOOST_CHECK(CompareChunks(new_chunks, old_chunks) == std::partial_ordering::unordered); 647 648 // Strictly better but smaller size. 649 old_chunks = {{950, 300}, {100, 100}}; 650 new_chunks = {{1100, 300}}; 651 652 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks))); 653 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks))); 654 655 // New diagram is strictly better due to the first chunk, even though 656 // second chunk contributes no fees 657 old_chunks = {{950, 300}, {100, 100}}; 658 new_chunks = {{1100, 100}, {0, 100}}; 659 660 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks))); 661 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks))); 662 663 // Feerate of first new chunk is better with, but second chunk is worse 664 old_chunks = {{950, 300}, {100, 100}}; 665 new_chunks = {{750, 100}, {249, 250}, {151, 650}}; 666 667 BOOST_CHECK(CompareChunks(old_chunks, new_chunks) == std::partial_ordering::unordered); 668 BOOST_CHECK(CompareChunks(new_chunks, old_chunks) == std::partial_ordering::unordered); 669 670 // If we make the second chunk slightly better, the new diagram now wins. 671 old_chunks = {{950, 300}, {100, 100}}; 672 new_chunks = {{750, 100}, {250, 250}, {150, 150}}; 673 674 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks))); 675 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks))); 676 677 // Identical diagrams, cannot be strictly better 678 old_chunks = {{950, 300}, {100, 100}}; 679 new_chunks = {{950, 300}, {100, 100}}; 680 681 BOOST_CHECK(std::is_eq(CompareChunks(old_chunks, new_chunks))); 682 BOOST_CHECK(std::is_eq(CompareChunks(new_chunks, old_chunks))); 683 684 // Same aggregate fee, but different total size (trigger single tail fee check step) 685 old_chunks = {{950, 300}, {100, 99}}; 686 new_chunks = {{950, 300}, {100, 100}}; 687 688 // No change in evaluation when tail check needed. 689 BOOST_CHECK(std::is_gt(CompareChunks(old_chunks, new_chunks))); 690 BOOST_CHECK(std::is_lt(CompareChunks(new_chunks, old_chunks))); 691 692 // Trigger multiple tail fee check steps 693 old_chunks = {{950, 300}, {100, 99}}; 694 new_chunks = {{950, 300}, {100, 100}, {0, 1}, {0, 1}}; 695 696 BOOST_CHECK(std::is_gt(CompareChunks(old_chunks, new_chunks))); 697 BOOST_CHECK(std::is_lt(CompareChunks(new_chunks, old_chunks))); 698 699 // Multiple tail fee check steps, unordered result 700 new_chunks = {{950, 300}, {100, 100}, {0, 1}, {0, 1}, {1, 1}}; 701 BOOST_CHECK(CompareChunks(old_chunks, new_chunks) == std::partial_ordering::unordered); 702 BOOST_CHECK(CompareChunks(new_chunks, old_chunks) == std::partial_ordering::unordered); 703 } 704 705 BOOST_AUTO_TEST_SUITE_END()