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