rbf_tests.cpp raw
1 // Copyright (c) 2021-present The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 #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, BasicTestingSetup)
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 static CTransactionRef add_descendants(const CTransactionRef& tx, int32_t num_descendants, CTxMemPool& pool)
41 EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs)
42 {
43 AssertLockHeld(::cs_main);
44 AssertLockHeld(pool.cs);
45 TestMemPoolEntryHelper entry;
46 // Assumes this isn't already spent in mempool
47 auto tx_to_spend = tx;
48 for (int32_t i{0}; i < num_descendants; ++i) {
49 auto next_tx = make_tx(/*inputs=*/{tx_to_spend}, /*output_values=*/{(50 - i) * CENT});
50 TryAddToMempool(pool, entry.FromTx(next_tx));
51 BOOST_CHECK(pool.GetIter(next_tx->GetHash()).has_value());
52 tx_to_spend = next_tx;
53 }
54 // Return last created tx
55 return tx_to_spend;
56 }
57
58 BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
59 {
60 CTxMemPool& pool = *Assert(m_node.mempool);
61 LOCK2(::cs_main, pool.cs);
62 TestMemPoolEntryHelper entry;
63
64 const CAmount low_fee{CENT/100};
65 const CAmount normal_fee{CENT/10};
66 const CAmount high_fee{CENT};
67
68 // Create a parent tx1 and child tx2 with normal fees:
69 const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
70 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx1));
71 const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT});
72 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx2));
73
74 // Create a low-feerate parent tx3 and high-feerate child tx4 (cpfp)
75 const auto tx3 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {1099 * CENT});
76 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx3));
77 const auto tx4 = make_tx(/*inputs=*/ {tx3}, /*output_values=*/ {999 * CENT});
78 TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx4));
79
80 // Create a parent tx5 and child tx6 where both have very low fees
81 const auto tx5 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {1099 * CENT});
82 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx5));
83 const auto tx6 = make_tx(/*inputs=*/ {tx5}, /*output_values=*/ {1098 * CENT});
84 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx6));
85 // Make tx6's modified fee much higher than its base fee. This should cause it to pass
86 // the fee-related checks despite being low-feerate.
87 pool.PrioritiseTransaction(tx6->GetHash(), 1 * COIN);
88
89 // Two independent high-feerate transactions, tx7 and tx8
90 const auto tx7 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {999 * CENT});
91 TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx7));
92 const auto tx8 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {999 * CENT});
93 TryAddToMempool(pool, entry.Fee(high_fee).FromTx(tx8));
94
95 // Will make these two parents of single child
96 const auto tx11 = make_tx(/*inputs=*/ {m_coinbase_txns[7]}, /*output_values=*/ {995 * CENT});
97 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx11));
98 const auto tx12 = make_tx(/*inputs=*/ {m_coinbase_txns[8]}, /*output_values=*/ {995 * CENT});
99 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx12));
100
101 // Will make two children of this single parent
102 const auto tx13 = make_tx(/*inputs=*/ {m_coinbase_txns[9]}, /*output_values=*/ {995 * CENT, 995 * CENT});
103 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx13));
104
105 const auto entry1_normal = pool.GetIter(tx1->GetHash()).value();
106 const auto entry2_normal = pool.GetIter(tx2->GetHash()).value();
107 const auto entry3_low = pool.GetIter(tx3->GetHash()).value();
108 const auto entry4_high = pool.GetIter(tx4->GetHash()).value();
109 const auto entry5_low = pool.GetIter(tx5->GetHash()).value();
110 const auto entry6_low_prioritised = pool.GetIter(tx6->GetHash()).value();
111 const auto entry7_high = pool.GetIter(tx7->GetHash()).value();
112 const auto entry8_high = pool.GetIter(tx8->GetHash()).value();
113
114 BOOST_CHECK_EQUAL(entry1_normal->GetFee(), normal_fee);
115 BOOST_CHECK_EQUAL(entry2_normal->GetFee(), normal_fee);
116 BOOST_CHECK_EQUAL(entry3_low->GetFee(), low_fee);
117 BOOST_CHECK_EQUAL(entry4_high->GetFee(), high_fee);
118 BOOST_CHECK_EQUAL(entry5_low->GetFee(), low_fee);
119 BOOST_CHECK_EQUAL(entry6_low_prioritised->GetFee(), low_fee);
120 BOOST_CHECK_EQUAL(entry7_high->GetFee(), high_fee);
121 BOOST_CHECK_EQUAL(entry8_high->GetFee(), high_fee);
122
123 CTxMemPool::setEntries set_12_normal{entry1_normal, entry2_normal};
124 CTxMemPool::setEntries set_34_cpfp{entry3_low, entry4_high};
125 CTxMemPool::setEntries set_56_low{entry5_low, entry6_low_prioritised};
126 CTxMemPool::setEntries set_78_high{entry7_high, entry8_high};
127 CTxMemPool::setEntries all_entries{entry1_normal, entry2_normal, entry3_low, entry4_high,
128 entry5_low, entry6_low_prioritised, entry7_high, entry8_high};
129 CTxMemPool::setEntries empty_set;
130
131 const auto unused_txid = Txid::FromUint256(GetRandHash());
132
133 // Tests for EntriesAndTxidsDisjoint
134 BOOST_CHECK(EntriesAndTxidsDisjoint(empty_set, {tx1->GetHash()}, unused_txid) == std::nullopt);
135 BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx3->GetHash()}, unused_txid) == std::nullopt);
136 BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx2->GetHash()}, unused_txid).has_value());
137 BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx1->GetHash()}, unused_txid).has_value());
138 BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx2->GetHash()}, unused_txid).has_value());
139 // EntriesAndTxidsDisjoint does not calculate descendants of iters_conflicting; it uses whatever
140 // the caller passed in. As such, no error is returned even though entry2_normal is a descendant of tx1.
141 BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx1->GetHash()}, unused_txid) == std::nullopt);
142
143 // Tests for PaysForRBF
144 const CFeeRate incremental_relay_feerate{DEFAULT_INCREMENTAL_RELAY_FEE};
145 const CFeeRate higher_relay_feerate{2 * DEFAULT_INCREMENTAL_RELAY_FEE};
146 // Must pay at least as much as the original.
147 BOOST_CHECK(PaysForRBF(/*original_fees=*/high_fee,
148 /*replacement_fees=*/high_fee,
149 /*replacement_vsize=*/1,
150 /*relay_fee=*/CFeeRate(0),
151 /*txid=*/unused_txid)
152 == std::nullopt);
153 BOOST_CHECK(PaysForRBF(high_fee, high_fee - 1, 1, CFeeRate(0), unused_txid).has_value());
154 BOOST_CHECK(PaysForRBF(high_fee + 1, high_fee, 1, CFeeRate(0), unused_txid).has_value());
155 // Additional fees must cover the replacement's vsize at incremental relay fee
156 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 1, 11, incremental_relay_feerate, unused_txid).has_value());
157 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 1, 10, incremental_relay_feerate, unused_txid) == std::nullopt);
158 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 2, 11, higher_relay_feerate, unused_txid).has_value());
159 BOOST_CHECK(PaysForRBF(high_fee, high_fee + 4, 20, higher_relay_feerate, unused_txid) == std::nullopt);
160 BOOST_CHECK(PaysForRBF(low_fee, high_fee, 99999999, incremental_relay_feerate, unused_txid).has_value());
161 BOOST_CHECK(PaysForRBF(low_fee, high_fee + 99999999, 99999999, incremental_relay_feerate, unused_txid) == std::nullopt);
162 }
163
164 BOOST_FIXTURE_TEST_CASE(rbf_conflicts_calculator, TestChain100Setup)
165 {
166 CTxMemPool& pool = *Assert(m_node.mempool);
167 LOCK2(::cs_main, pool.cs);
168 TestMemPoolEntryHelper entry;
169
170 const CAmount normal_fee{CENT/10};
171
172 // Create two parent transactions with 51 outputs each
173 const int NUM_OUTPUTS = 51;
174 std::vector<CAmount> output_values;
175 output_values.reserve(NUM_OUTPUTS);
176 for (int i = 0; i < NUM_OUTPUTS; ++i) {
177 output_values.push_back(1 * COIN);
178 }
179
180 const auto parent_tx_1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ output_values);
181 const auto parent_tx_2 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ output_values);
182 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(parent_tx_1));
183 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(parent_tx_2));
184
185 std::vector<CTransactionRef> direct_children;
186
187 // Create individual spends of these outputs
188 for (const auto& parent_tx : {parent_tx_1, parent_tx_2}) {
189 for (auto i = 0; i < NUM_OUTPUTS; ++i) {
190 auto pretx = make_tx(/*inputs=*/ {parent_tx}, /*output_values=*/ {995 * CENT});
191 CMutableTransaction tx(*pretx);
192 tx.vin[0].prevout.n = i;
193 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx));
194 BOOST_CHECK(pool.GetIter(tx.GetHash()).has_value());
195 direct_children.push_back(MakeTransactionRef(tx));
196 }
197 }
198
199 // At this point, we should have 2 clusters in the mempool, each with 52
200 // transactions.
201
202 // parent_tx and all children are in one cluster, so we can have as many
203 // conflicts within this cluster as we want without violating the RBF conflicts
204 // limit.
205 const auto parent_entry_1 = pool.GetIter(parent_tx_1->GetHash()).value();
206 const auto parent_entry_2 = pool.GetIter(parent_tx_2->GetHash()).value();
207 const auto conflicting_transaction = make_tx({parent_tx_1, parent_tx_2}, {50 * CENT});
208 CTxMemPool::setEntries all_conflicts, dummy;
209 BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
210 /*pool=*/ pool,
211 /*iters_conflicting=*/ {parent_entry_1, parent_entry_2},
212 /*all_conflicts=*/ all_conflicts) == std::nullopt);
213
214 dummy.clear();
215 // Conflicting directly with all those conflicts doesn't change anything.
216 BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
217 /*pool=*/ pool,
218 /*iters_conflicting=*/ all_conflicts,
219 /*all_conflicts=*/ dummy) == std::nullopt);
220 BOOST_CHECK_EQUAL(all_conflicts.size(), dummy.size());
221 dummy.clear();
222
223 // If we mine the parent_tx's, then the clusters split (102 clusters).
224 pool.removeForBlock({parent_tx_1, parent_tx_2}, /*nBlockHeight=*/ 1);
225
226 // Add some descendants now to each of the direct children (we can do this now that the clusters have split).
227 for (const auto& child : direct_children) {
228 add_descendants(child, 10, pool);
229 }
230
231 // We can conflict with 100 different clusters, even if they have lots of transactions.
232 CTxMemPool::setEntries conflicts;
233 for (auto i = 0; i < 100; ++i) {
234 conflicts.insert(pool.GetIter(direct_children[i]->GetHash()).value());
235 }
236 BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
237 /*pool=*/ pool,
238 /*iters_conflicting=*/ conflicts,
239 /*all_conflicts=*/ dummy) == std::nullopt);
240
241 // Conflicting with 1 more distinct cluster causes failure, however.
242 conflicts.insert(pool.GetIter(direct_children[100]->GetHash()).value());
243 BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicting_transaction.get(),
244 /*pool=*/ pool,
245 /*iters_conflicting=*/ conflicts,
246 /*all_conflicts=*/ dummy).has_value());
247 }
248
249 BOOST_FIXTURE_TEST_CASE(improves_feerate, TestChain100Setup)
250 {
251 CTxMemPool& pool = *Assert(m_node.mempool);
252 LOCK2(::cs_main, pool.cs);
253 TestMemPoolEntryHelper entry;
254
255 const CAmount low_fee{CENT/100};
256 const CAmount normal_fee{CENT/10};
257
258 // low feerate parent with normal feerate child
259 const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0], m_coinbase_txns[1]}, /*output_values=*/ {10 * COIN});
260 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(tx1));
261 const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT});
262 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx2));
263
264 const auto entry1 = pool.GetIter(tx1->GetHash()).value();
265 const auto tx1_fee = entry1->GetModifiedFee();
266 const auto entry2 = pool.GetIter(tx2->GetHash()).value();
267 const auto tx2_fee = entry2->GetModifiedFee();
268
269 // conflicting transactions
270 const auto tx1_conflict = make_tx(/*inputs=*/ {m_coinbase_txns[0], m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN});
271 const auto tx3 = make_tx(/*inputs=*/ {tx1_conflict}, /*output_values=*/ {995 * CENT});
272 auto entry3 = entry.FromTx(tx3);
273
274 // Now test ImprovesFeerateDiagram with various levels of "package rbf" feerates
275
276 // It doesn't improve itself
277 auto changeset = pool.GetChangeSet();
278 changeset->StageRemoval(entry1);
279 changeset->StageRemoval(entry2);
280 changeset->StageAddition(tx1_conflict, tx1_fee, 0, 1, 0, false, 4, LockPoints());
281 changeset->StageAddition(tx3, tx2_fee, 0, 1, 0, false, 4, LockPoints());
282 const auto res1 = ImprovesFeerateDiagram(*changeset);
283 BOOST_CHECK(res1.has_value());
284 BOOST_CHECK(res1.value().first == DiagramCheckError::FAILURE);
285 BOOST_CHECK(res1.value().second == "insufficient feerate: does not improve feerate diagram");
286
287 // With one more satoshi it does
288 changeset.reset();
289 changeset = pool.GetChangeSet();
290 changeset->StageRemoval(entry1);
291 changeset->StageRemoval(entry2);
292 changeset->StageAddition(tx1_conflict, tx1_fee+1, 0, 1, 0, false, 4, LockPoints());
293 changeset->StageAddition(tx3, tx2_fee, 0, 1, 0, false, 4, LockPoints());
294 BOOST_CHECK(ImprovesFeerateDiagram(*changeset) == std::nullopt);
295
296 changeset.reset();
297 // With prioritisation of in-mempool conflicts, it affects the results of the comparison using the same args as just above
298 pool.PrioritiseTransaction(entry1->GetSharedTx()->GetHash(), /*nFeeDelta=*/1);
299 changeset = pool.GetChangeSet();
300 changeset->StageRemoval(entry1);
301 changeset->StageRemoval(entry2);
302 changeset->StageAddition(tx1_conflict, tx1_fee+1, 0, 1, 0, false, 4, LockPoints());
303 changeset->StageAddition(tx3, tx2_fee, 0, 1, 0, false, 4, LockPoints());
304 const auto res2 = ImprovesFeerateDiagram(*changeset);
305 BOOST_CHECK(res2.has_value());
306 BOOST_CHECK(res2.value().first == DiagramCheckError::FAILURE);
307 BOOST_CHECK(res2.value().second == "insufficient feerate: does not improve feerate diagram");
308 changeset.reset();
309
310 pool.PrioritiseTransaction(entry1->GetSharedTx()->GetHash(), /*nFeeDelta=*/-1);
311
312 // With fewer vbytes it does
313 CMutableTransaction tx4{entry3.GetTx()};
314 tx4.vin[0].scriptWitness = CScriptWitness(); // Clear out the witness, to reduce size
315 auto entry4 = entry.FromTx(MakeTransactionRef(tx4));
316 changeset = pool.GetChangeSet();
317 changeset->StageRemoval(entry1);
318 changeset->StageRemoval(entry2);
319 changeset->StageAddition(tx1_conflict, tx1_fee, 0, 1, 0, false, 4, LockPoints());
320 changeset->StageAddition(entry4.GetSharedTx(), tx2_fee, 0, 1, 0, false, 4, LockPoints());
321 BOOST_CHECK(ImprovesFeerateDiagram(*changeset) == std::nullopt);
322 changeset.reset();
323
324 // Adding a grandchild makes the cluster size 3, which is also calculable
325 const auto tx5 = make_tx(/*inputs=*/ {tx2}, /*output_values=*/ {995 * CENT});
326 TryAddToMempool(pool, entry.Fee(normal_fee).FromTx(tx5));
327 const auto entry5 = pool.GetIter(tx5->GetHash()).value();
328
329 changeset = pool.GetChangeSet();
330 changeset->StageRemoval(entry1);
331 changeset->StageRemoval(entry2);
332 changeset->StageRemoval(entry5);
333 changeset->StageAddition(tx1_conflict, tx1_fee, 0, 1, 0, false, 4, LockPoints());
334 changeset->StageAddition(entry4.GetSharedTx(), tx2_fee + entry5->GetModifiedFee() + 1, 0, 1, 0, false, 4, LockPoints());
335 const auto res3 = ImprovesFeerateDiagram(*changeset);
336 BOOST_CHECK(res3 == std::nullopt);
337 }
338
339 BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup)
340 {
341 CTxMemPool& pool = *Assert(m_node.mempool);
342 LOCK2(::cs_main, pool.cs);
343 TestMemPoolEntryHelper entry;
344
345 const CAmount low_fee{CENT/100};
346 const CAmount high_fee{CENT};
347
348 // low -> high -> medium fee transactions that would result in two chunks together since they
349 // are all same size
350 const auto low_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
351 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(low_tx));
352
353 const auto entry_low = pool.GetIter(low_tx->GetHash()).value();
354 const auto low_size = entry_low->GetAdjustedWeight();
355
356 const auto replacement_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {9 * COIN});
357 auto entry_replacement = entry.FromTx(replacement_tx);
358
359 // Replacement of size 1
360 {
361 auto changeset = pool.GetChangeSet();
362 changeset->StageRemoval(entry_low);
363 changeset->StageAddition(replacement_tx, 0, 0, 1, 0, false, 4, LockPoints());
364 const auto replace_one{changeset->CalculateChunksForRBF()};
365 BOOST_CHECK(replace_one.has_value());
366 std::vector<FeeFrac> expected_old_chunks{{low_fee, low_size}};
367 BOOST_CHECK(replace_one->first == expected_old_chunks);
368 std::vector<FeeFrac> expected_new_chunks{{0, entry_replacement.GetAdjustedWeight()}};
369 BOOST_CHECK(replace_one->second == expected_new_chunks);
370 }
371
372 // Non-zero replacement fee/size
373 {
374 auto changeset = pool.GetChangeSet();
375 changeset->StageRemoval(entry_low);
376 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints());
377 const auto replace_one_fee{changeset->CalculateChunksForRBF()};
378 BOOST_CHECK(replace_one_fee.has_value());
379 std::vector<FeeFrac> expected_old_diagram{{low_fee, low_size}};
380 BOOST_CHECK(replace_one_fee->first == expected_old_diagram);
381 std::vector<FeeFrac> expected_new_diagram{{high_fee, entry_replacement.GetAdjustedWeight()}};
382 BOOST_CHECK(replace_one_fee->second == expected_new_diagram);
383 }
384
385 // Add a second transaction to the cluster that will make a single chunk, to be evicted in the RBF
386 const auto high_tx = make_tx(/*inputs=*/ {low_tx}, /*output_values=*/ {995 * CENT});
387 TryAddToMempool(pool, entry.Fee(high_fee).FromTx(high_tx));
388 const auto entry_high = pool.GetIter(high_tx->GetHash()).value();
389 const auto high_size = entry_high->GetAdjustedWeight();
390
391 {
392 auto changeset = pool.GetChangeSet();
393 changeset->StageRemoval(entry_low);
394 changeset->StageRemoval(entry_high);
395 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints());
396 const auto replace_single_chunk{changeset->CalculateChunksForRBF()};
397 BOOST_CHECK(replace_single_chunk.has_value());
398 std::vector<FeeFrac> expected_old_chunks{{low_fee + high_fee, low_size + high_size}};
399 BOOST_CHECK(replace_single_chunk->first == expected_old_chunks);
400 std::vector<FeeFrac> expected_new_chunks{{high_fee, entry_replacement.GetAdjustedWeight()}};
401 BOOST_CHECK(replace_single_chunk->second == expected_new_chunks);
402 }
403
404 // Conflict with the 2nd tx, resulting in new diagram with three entries
405 {
406 auto changeset = pool.GetChangeSet();
407 changeset->StageRemoval(entry_high);
408 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints());
409 const auto replace_cpfp_child{changeset->CalculateChunksForRBF()};
410 BOOST_CHECK(replace_cpfp_child.has_value());
411 std::vector<FeeFrac> expected_old_chunks{{low_fee + high_fee, low_size + high_size}};
412 BOOST_CHECK(replace_cpfp_child->first == expected_old_chunks);
413 std::vector<FeeFrac> expected_new_chunks{{high_fee, entry_replacement.GetAdjustedWeight()}, {low_fee, low_size}};
414 BOOST_CHECK(replace_cpfp_child->second == expected_new_chunks);
415 }
416
417 // Make a size 2 cluster that is itself two chunks; evict both txns
418 const auto high_tx_2 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {10 * COIN});
419 TryAddToMempool(pool, entry.Fee(high_fee).FromTx(high_tx_2));
420 const auto entry_high_2 = pool.GetIter(high_tx_2->GetHash()).value();
421 const auto high_size_2 = entry_high_2->GetAdjustedWeight();
422
423 const auto low_tx_2 = make_tx(/*inputs=*/ {high_tx_2}, /*output_values=*/ {9 * COIN});
424 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(low_tx_2));
425 const auto entry_low_2 = pool.GetIter(low_tx_2->GetHash()).value();
426 const auto low_size_2 = entry_low_2->GetAdjustedWeight();
427
428 {
429 auto changeset = pool.GetChangeSet();
430 changeset->StageRemoval(entry_high_2);
431 changeset->StageRemoval(entry_low_2);
432 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints());
433 const auto replace_two_chunks_single_cluster{changeset->CalculateChunksForRBF()};
434 BOOST_CHECK(replace_two_chunks_single_cluster.has_value());
435 std::vector<FeeFrac> expected_old_chunks{{high_fee, high_size_2}, {low_fee, low_size_2}};
436 BOOST_CHECK(replace_two_chunks_single_cluster->first == expected_old_chunks);
437 std::vector<FeeFrac> expected_new_chunks{{high_fee, low_size_2}};
438 BOOST_CHECK(replace_two_chunks_single_cluster->second == expected_new_chunks);
439 }
440
441 // You can have more than two direct conflicts
442 const auto conflict_1 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN});
443 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_1));
444 const auto conflict_1_entry = pool.GetIter(conflict_1->GetHash()).value();
445
446 const auto conflict_2 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {10 * COIN});
447 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_2));
448 const auto conflict_2_entry = pool.GetIter(conflict_2->GetHash()).value();
449
450 const auto conflict_3 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {10 * COIN});
451 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_3));
452 const auto conflict_3_entry = pool.GetIter(conflict_3->GetHash()).value();
453
454 {
455 auto changeset = pool.GetChangeSet();
456 changeset->StageRemoval(conflict_1_entry);
457 changeset->StageRemoval(conflict_2_entry);
458 changeset->StageRemoval(conflict_3_entry);
459 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints());
460 const auto replace_multiple_clusters{changeset->CalculateChunksForRBF()};
461 BOOST_CHECK(replace_multiple_clusters.has_value());
462 BOOST_CHECK(replace_multiple_clusters->first.size() == 3);
463 BOOST_CHECK(replace_multiple_clusters->second.size() == 1);
464 }
465
466 // Add a child transaction to conflict_1 and make it cluster size 2, two chunks due to same feerate
467 const auto conflict_1_child = make_tx(/*inputs=*/{conflict_1}, /*output_values=*/ {995 * CENT});
468 TryAddToMempool(pool, entry.Fee(low_fee).FromTx(conflict_1_child));
469 const auto conflict_1_child_entry = pool.GetIter(conflict_1_child->GetHash()).value();
470
471 {
472 auto changeset = pool.GetChangeSet();
473 changeset->StageRemoval(conflict_1_entry);
474 changeset->StageRemoval(conflict_2_entry);
475 changeset->StageRemoval(conflict_3_entry);
476 changeset->StageRemoval(conflict_1_child_entry);
477 changeset->StageAddition(replacement_tx, high_fee, 0, 1, 0, false, 4, LockPoints());
478 const auto replace_multiple_clusters_2{changeset->CalculateChunksForRBF()};
479
480 BOOST_CHECK(replace_multiple_clusters_2.has_value());
481 BOOST_CHECK(replace_multiple_clusters_2->first.size() == 4);
482 BOOST_CHECK(replace_multiple_clusters_2->second.size() == 1);
483 }
484 }
485
486 BOOST_AUTO_TEST_CASE(feerate_chunks_utilities)
487 {
488 // Sanity check the correctness of the feerate chunks comparison.
489
490 // A strictly better case.
491 std::vector<FeeFrac> old_chunks{{{950, 300}, {100, 100}}};
492 std::vector<FeeFrac> new_chunks{{{1000, 300}, {50, 100}}};
493
494 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks)));
495 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks)));
496
497 // Incomparable diagrams
498 old_chunks = {{950, 300}, {100, 100}};
499 new_chunks = {{1000, 300}, {0, 100}};
500
501 BOOST_CHECK(CompareChunks(old_chunks, new_chunks) == std::partial_ordering::unordered);
502 BOOST_CHECK(CompareChunks(new_chunks, old_chunks) == std::partial_ordering::unordered);
503
504 // Strictly better but smaller size.
505 old_chunks = {{950, 300}, {100, 100}};
506 new_chunks = {{1100, 300}};
507
508 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks)));
509 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks)));
510
511 // New diagram is strictly better due to the first chunk, even though
512 // second chunk contributes no fees
513 old_chunks = {{950, 300}, {100, 100}};
514 new_chunks = {{1100, 100}, {0, 100}};
515
516 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks)));
517 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks)));
518
519 // Feerate of first new chunk is better with, but second chunk is worse
520 old_chunks = {{950, 300}, {100, 100}};
521 new_chunks = {{750, 100}, {249, 250}, {151, 650}};
522
523 BOOST_CHECK(CompareChunks(old_chunks, new_chunks) == std::partial_ordering::unordered);
524 BOOST_CHECK(CompareChunks(new_chunks, old_chunks) == std::partial_ordering::unordered);
525
526 // If we make the second chunk slightly better, the new diagram now wins.
527 old_chunks = {{950, 300}, {100, 100}};
528 new_chunks = {{750, 100}, {250, 250}, {150, 150}};
529
530 BOOST_CHECK(std::is_lt(CompareChunks(old_chunks, new_chunks)));
531 BOOST_CHECK(std::is_gt(CompareChunks(new_chunks, old_chunks)));
532
533 // Identical diagrams, cannot be strictly better
534 old_chunks = {{950, 300}, {100, 100}};
535 new_chunks = {{950, 300}, {100, 100}};
536
537 BOOST_CHECK(std::is_eq(CompareChunks(old_chunks, new_chunks)));
538 BOOST_CHECK(std::is_eq(CompareChunks(new_chunks, old_chunks)));
539
540 // Same aggregate fee, but different total size (trigger single tail fee check step)
541 old_chunks = {{950, 300}, {100, 99}};
542 new_chunks = {{950, 300}, {100, 100}};
543
544 // No change in evaluation when tail check needed.
545 BOOST_CHECK(std::is_gt(CompareChunks(old_chunks, new_chunks)));
546 BOOST_CHECK(std::is_lt(CompareChunks(new_chunks, old_chunks)));
547
548 // Trigger multiple tail fee check steps
549 old_chunks = {{950, 300}, {100, 99}};
550 new_chunks = {{950, 300}, {100, 100}, {0, 1}, {0, 1}};
551
552 BOOST_CHECK(std::is_gt(CompareChunks(old_chunks, new_chunks)));
553 BOOST_CHECK(std::is_lt(CompareChunks(new_chunks, old_chunks)));
554
555 // Multiple tail fee check steps, unordered result
556 new_chunks = {{950, 300}, {100, 100}, {0, 1}, {0, 1}, {1, 1}};
557 BOOST_CHECK(CompareChunks(old_chunks, new_chunks) == std::partial_ordering::unordered);
558 BOOST_CHECK(CompareChunks(new_chunks, old_chunks) == std::partial_ordering::unordered);
559 }
560
561 BOOST_AUTO_TEST_SUITE_END()
562