Bitcoin Core  27.99.0
P2P Digital Currency
rbf_tests.cpp
Go to the documentation of this file.
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 {
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)
42 {
44  AssertLockHeld(pool.cs);
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  pool.addUnchecked(entry.FromTx(next_tx));
51  tx_to_spend = next_tx;
52  }
53  // Return last created tx
54  return tx_to_spend;
55 }
56 
57 static CTransactionRef add_descendant_to_parents(const std::vector<CTransactionRef>& parents, CTxMemPool& pool)
59 {
61  AssertLockHeld(pool.cs);
63  // Assumes this isn't already spent in mempool
64  auto child_tx = make_tx(/*inputs=*/parents, /*output_values=*/{50 * CENT});
65  pool.addUnchecked(entry.FromTx(child_tx));
66  // Return last created tx
67  return child_tx;
68 }
69 
71 {
72  CTxMemPool& pool = *Assert(m_node.mempool);
73  LOCK2(::cs_main, pool.cs);
75 
76  const CAmount low_fee{CENT/100};
77  const CAmount normal_fee{CENT/10};
78  const CAmount high_fee{CENT};
79 
80  // Create a parent tx1 and child tx2 with normal fees:
81  const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
82  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx1));
83  const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT});
84  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx2));
85 
86  // Create a low-feerate parent tx3 and high-feerate child tx4 (cpfp)
87  const auto tx3 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {1099 * CENT});
88  pool.addUnchecked(entry.Fee(low_fee).FromTx(tx3));
89  const auto tx4 = make_tx(/*inputs=*/ {tx3}, /*output_values=*/ {999 * CENT});
90  pool.addUnchecked(entry.Fee(high_fee).FromTx(tx4));
91 
92  // Create a parent tx5 and child tx6 where both have very low fees
93  const auto tx5 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {1099 * CENT});
94  pool.addUnchecked(entry.Fee(low_fee).FromTx(tx5));
95  const auto tx6 = make_tx(/*inputs=*/ {tx5}, /*output_values=*/ {1098 * CENT});
96  pool.addUnchecked(entry.Fee(low_fee).FromTx(tx6));
97  // Make tx6's modified fee much higher than its base fee. This should cause it to pass
98  // the fee-related checks despite being low-feerate.
99  pool.PrioritiseTransaction(tx6->GetHash(), 1 * COIN);
100 
101  // Two independent high-feerate transactions, tx7 and tx8
102  const auto tx7 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {999 * CENT});
103  pool.addUnchecked(entry.Fee(high_fee).FromTx(tx7));
104  const auto tx8 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {999 * CENT});
105  pool.addUnchecked(entry.Fee(high_fee).FromTx(tx8));
106 
107  // Normal txs, will chain txns right before CheckConflictTopology test
108  const auto tx9 = make_tx(/*inputs=*/ {m_coinbase_txns[5]}, /*output_values=*/ {995 * CENT});
109  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx9));
110  const auto tx10 = make_tx(/*inputs=*/ {m_coinbase_txns[6]}, /*output_values=*/ {995 * CENT});
111  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx10));
112 
113  // Will make these two parents of single child
114  const auto tx11 = make_tx(/*inputs=*/ {m_coinbase_txns[7]}, /*output_values=*/ {995 * CENT});
115  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx11));
116  const auto tx12 = make_tx(/*inputs=*/ {m_coinbase_txns[8]}, /*output_values=*/ {995 * CENT});
117  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx12));
118 
119  const auto entry1_normal = pool.GetIter(tx1->GetHash()).value();
120  const auto entry2_normal = pool.GetIter(tx2->GetHash()).value();
121  const auto entry3_low = pool.GetIter(tx3->GetHash()).value();
122  const auto entry4_high = pool.GetIter(tx4->GetHash()).value();
123  const auto entry5_low = pool.GetIter(tx5->GetHash()).value();
124  const auto entry6_low_prioritised = pool.GetIter(tx6->GetHash()).value();
125  const auto entry7_high = pool.GetIter(tx7->GetHash()).value();
126  const auto entry8_high = pool.GetIter(tx8->GetHash()).value();
127  const auto entry9_unchained = pool.GetIter(tx9->GetHash()).value();
128  const auto entry10_unchained = pool.GetIter(tx10->GetHash()).value();
129  const auto entry11_unchained = pool.GetIter(tx11->GetHash()).value();
130  const auto entry12_unchained = pool.GetIter(tx12->GetHash()).value();
131 
132  BOOST_CHECK_EQUAL(entry1_normal->GetFee(), normal_fee);
133  BOOST_CHECK_EQUAL(entry2_normal->GetFee(), normal_fee);
134  BOOST_CHECK_EQUAL(entry3_low->GetFee(), low_fee);
135  BOOST_CHECK_EQUAL(entry4_high->GetFee(), high_fee);
136  BOOST_CHECK_EQUAL(entry5_low->GetFee(), low_fee);
137  BOOST_CHECK_EQUAL(entry6_low_prioritised->GetFee(), low_fee);
138  BOOST_CHECK_EQUAL(entry7_high->GetFee(), high_fee);
139  BOOST_CHECK_EQUAL(entry8_high->GetFee(), high_fee);
140 
141  CTxMemPool::setEntries set_12_normal{entry1_normal, entry2_normal};
142  CTxMemPool::setEntries set_34_cpfp{entry3_low, entry4_high};
143  CTxMemPool::setEntries set_56_low{entry5_low, entry6_low_prioritised};
144  CTxMemPool::setEntries set_78_high{entry7_high, entry8_high};
145  CTxMemPool::setEntries all_entries{entry1_normal, entry2_normal, entry3_low, entry4_high,
146  entry5_low, entry6_low_prioritised, entry7_high, entry8_high};
147  CTxMemPool::setEntries empty_set;
148 
149  const auto unused_txid{GetRandHash()};
150 
151  // Tests for PaysMoreThanConflicts
152  // These tests use feerate, not absolute fee.
153  BOOST_CHECK(PaysMoreThanConflicts(/*iters_conflicting=*/set_12_normal,
154  /*replacement_feerate=*/CFeeRate(entry1_normal->GetModifiedFee() + 1, entry1_normal->GetTxSize() + 2),
155  /*txid=*/unused_txid).has_value());
156  // Replacement must be strictly greater than the originals.
157  BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1_normal->GetModifiedFee(), entry1_normal->GetTxSize()), unused_txid).has_value());
158  BOOST_CHECK(PaysMoreThanConflicts(set_12_normal, CFeeRate(entry1_normal->GetModifiedFee() + 1, entry1_normal->GetTxSize()), unused_txid) == std::nullopt);
159  // These tests use modified fees (including prioritisation), not base fees.
160  BOOST_CHECK(PaysMoreThanConflicts({entry5_low}, CFeeRate(entry5_low->GetModifiedFee() + 1, entry5_low->GetTxSize()), unused_txid) == std::nullopt);
161  BOOST_CHECK(PaysMoreThanConflicts({entry6_low_prioritised}, CFeeRate(entry6_low_prioritised->GetFee() + 1, entry6_low_prioritised->GetTxSize()), unused_txid).has_value());
162  BOOST_CHECK(PaysMoreThanConflicts({entry6_low_prioritised}, CFeeRate(entry6_low_prioritised->GetModifiedFee() + 1, entry6_low_prioritised->GetTxSize()), unused_txid) == std::nullopt);
163  // PaysMoreThanConflicts checks individual feerate, not ancestor feerate. This test compares
164  // replacement_feerate and entry4_high's feerate, which are the same. The replacement_feerate is
165  // considered too low even though entry4_high has a low ancestor feerate.
166  BOOST_CHECK(PaysMoreThanConflicts(set_34_cpfp, CFeeRate(entry4_high->GetModifiedFee(), entry4_high->GetTxSize()), unused_txid).has_value());
167 
168  // Tests for EntriesAndTxidsDisjoint
169  BOOST_CHECK(EntriesAndTxidsDisjoint(empty_set, {tx1->GetHash()}, unused_txid) == std::nullopt);
170  BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx3->GetHash()}, unused_txid) == std::nullopt);
171  BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx2->GetHash()}, unused_txid).has_value());
172  BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx1->GetHash()}, unused_txid).has_value());
173  BOOST_CHECK(EntriesAndTxidsDisjoint(set_12_normal, {tx2->GetHash()}, unused_txid).has_value());
174  // EntriesAndTxidsDisjoint does not calculate descendants of iters_conflicting; it uses whatever
175  // the caller passed in. As such, no error is returned even though entry2_normal is a descendant of tx1.
176  BOOST_CHECK(EntriesAndTxidsDisjoint({entry2_normal}, {tx1->GetHash()}, unused_txid) == std::nullopt);
177 
178  // Tests for PaysForRBF
179  const CFeeRate incremental_relay_feerate{DEFAULT_INCREMENTAL_RELAY_FEE};
180  const CFeeRate higher_relay_feerate{2 * DEFAULT_INCREMENTAL_RELAY_FEE};
181  // Must pay at least as much as the original.
182  BOOST_CHECK(PaysForRBF(/*original_fees=*/high_fee,
183  /*replacement_fees=*/high_fee,
184  /*replacement_vsize=*/1,
185  /*relay_fee=*/CFeeRate(0),
186  /*txid=*/unused_txid)
187  == std::nullopt);
188  BOOST_CHECK(PaysForRBF(high_fee, high_fee - 1, 1, CFeeRate(0), unused_txid).has_value());
189  BOOST_CHECK(PaysForRBF(high_fee + 1, high_fee, 1, CFeeRate(0), unused_txid).has_value());
190  // Additional fees must cover the replacement's vsize at incremental relay fee
191  BOOST_CHECK(PaysForRBF(high_fee, high_fee + 1, 2, incremental_relay_feerate, unused_txid).has_value());
192  BOOST_CHECK(PaysForRBF(high_fee, high_fee + 2, 2, incremental_relay_feerate, unused_txid) == std::nullopt);
193  BOOST_CHECK(PaysForRBF(high_fee, high_fee + 2, 2, higher_relay_feerate, unused_txid).has_value());
194  BOOST_CHECK(PaysForRBF(high_fee, high_fee + 4, 2, higher_relay_feerate, unused_txid) == std::nullopt);
195  BOOST_CHECK(PaysForRBF(low_fee, high_fee, 99999999, incremental_relay_feerate, unused_txid).has_value());
196  BOOST_CHECK(PaysForRBF(low_fee, high_fee + 99999999, 99999999, incremental_relay_feerate, unused_txid) == std::nullopt);
197 
198  // Tests for GetEntriesForConflicts
199  CTxMemPool::setEntries all_parents{entry1_normal, entry3_low, entry5_low, entry7_high, entry8_high};
200  CTxMemPool::setEntries all_children{entry2_normal, entry4_high, entry6_low_prioritised};
201  const std::vector<CTransactionRef> parent_inputs({m_coinbase_txns[0], m_coinbase_txns[1], m_coinbase_txns[2],
202  m_coinbase_txns[3], m_coinbase_txns[4]});
203  const auto conflicts_with_parents = make_tx(parent_inputs, {50 * CENT});
204  CTxMemPool::setEntries all_conflicts;
205  BOOST_CHECK(GetEntriesForConflicts(/*tx=*/ *conflicts_with_parents.get(),
206  /*pool=*/ pool,
207  /*iters_conflicting=*/ all_parents,
208  /*all_conflicts=*/ all_conflicts) == std::nullopt);
209  BOOST_CHECK(all_conflicts == all_entries);
210  auto conflicts_size = all_conflicts.size();
211  all_conflicts.clear();
212 
213  add_descendants(tx2, 23, pool);
214  BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt);
215  conflicts_size += 23;
216  BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size);
217  all_conflicts.clear();
218 
219  add_descendants(tx4, 23, pool);
220  BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt);
221  conflicts_size += 23;
222  BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size);
223  all_conflicts.clear();
224 
225  add_descendants(tx6, 23, pool);
226  BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt);
227  conflicts_size += 23;
228  BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size);
229  all_conflicts.clear();
230 
231  add_descendants(tx7, 23, pool);
232  BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts) == std::nullopt);
233  conflicts_size += 23;
234  BOOST_CHECK_EQUAL(all_conflicts.size(), conflicts_size);
235  BOOST_CHECK_EQUAL(all_conflicts.size(), 100);
236  all_conflicts.clear();
237 
238  // Exceeds maximum number of conflicts.
239  add_descendants(tx8, 1, pool);
240  BOOST_CHECK(GetEntriesForConflicts(*conflicts_with_parents.get(), pool, all_parents, all_conflicts).has_value());
241 
242  // Tests for HasNoNewUnconfirmed
243  const auto spends_unconfirmed = make_tx({tx1}, {36 * CENT});
244  for (const auto& input : spends_unconfirmed->vin) {
245  // Spends unconfirmed inputs.
246  BOOST_CHECK(pool.exists(GenTxid::Txid(input.prevout.hash)));
247  }
248  BOOST_CHECK(HasNoNewUnconfirmed(/*tx=*/ *spends_unconfirmed.get(),
249  /*pool=*/ pool,
250  /*iters_conflicting=*/ all_entries) == std::nullopt);
251  BOOST_CHECK(HasNoNewUnconfirmed(*spends_unconfirmed.get(), pool, {entry2_normal}) == std::nullopt);
252  BOOST_CHECK(HasNoNewUnconfirmed(*spends_unconfirmed.get(), pool, empty_set).has_value());
253 
254  const auto spends_new_unconfirmed = make_tx({tx1, tx8}, {36 * CENT});
255  BOOST_CHECK(HasNoNewUnconfirmed(*spends_new_unconfirmed.get(), pool, {entry2_normal}).has_value());
256  BOOST_CHECK(HasNoNewUnconfirmed(*spends_new_unconfirmed.get(), pool, all_entries).has_value());
257 
258  const auto spends_conflicting_confirmed = make_tx({m_coinbase_txns[0], m_coinbase_txns[1]}, {45 * CENT});
259  BOOST_CHECK(HasNoNewUnconfirmed(*spends_conflicting_confirmed.get(), pool, {entry1_normal, entry3_low}) == std::nullopt);
260 
261  // Tests for CheckConflictTopology
262 
263  // Tx4 has 23 descendants
264  BOOST_CHECK(pool.CheckConflictTopology(set_34_cpfp).has_value());
265 
266  // No descendants yet
267  BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained}) == std::nullopt);
268 
269  // Add 1 descendant, still ok
270  add_descendants(tx9, 1, pool);
271  BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained}) == std::nullopt);
272 
273  // N direct conflicts; ok
274  BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}) == std::nullopt);
275 
276  // Add 1 descendant, still ok, even if it's considered a direct conflict as well
277  const auto child_tx = add_descendants(tx10, 1, pool);
278  const auto entry10_child = pool.GetIter(child_tx->GetHash()).value();
279  BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained}) == std::nullopt);
280  BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained, entry10_unchained, entry11_unchained, entry10_child}) == std::nullopt);
281 
282  // One more, size 3 cluster too much
283  const auto grand_child_tx = add_descendants(child_tx, 1, pool);
284  const auto entry10_grand_child = pool.GetIter(grand_child_tx->GetHash()).value();
285  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()));
286  // even if direct conflict is descendent itself
287  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()));
288 
289  // Make a single child from two singleton parents
290  const auto two_parent_child_tx = add_descendant_to_parents({tx11, tx12}, pool);
291  const auto entry_two_parent_child = pool.GetIter(two_parent_child_tx->GetHash()).value();
292  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()));
293  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()));
294  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()));
295 }
296 
298 {
299  CTxMemPool& pool = *Assert(m_node.mempool);
300  LOCK2(::cs_main, pool.cs);
302 
303  const CAmount low_fee{CENT/100};
304  const CAmount normal_fee{CENT/10};
305 
306  // low feerate parent with normal feerate child
307  const auto tx1 = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
308  pool.addUnchecked(entry.Fee(low_fee).FromTx(tx1));
309  const auto tx2 = make_tx(/*inputs=*/ {tx1}, /*output_values=*/ {995 * CENT});
310  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx2));
311 
312  const auto entry1 = pool.GetIter(tx1->GetHash()).value();
313  const auto tx1_fee = entry1->GetModifiedFee();
314  const auto tx1_size = entry1->GetTxSize();
315  const auto entry2 = pool.GetIter(tx2->GetHash()).value();
316  const auto tx2_fee = entry2->GetModifiedFee();
317  const auto tx2_size = entry2->GetTxSize();
318 
319  // Now test ImprovesFeerateDiagram with various levels of "package rbf" feerates
320 
321  // It doesn't improve itself
322  const auto res1 = ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee, tx1_size + tx2_size);
323  BOOST_CHECK(res1.has_value());
324  BOOST_CHECK(res1.value().first == DiagramCheckError::FAILURE);
325  BOOST_CHECK(res1.value().second == "insufficient feerate: does not improve feerate diagram");
326 
327  // With one more satoshi it does
328  BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size) == std::nullopt);
329 
330  // Adding a grandchild makes the cluster size 3, which is uncalculable
331  const auto tx3 = make_tx(/*inputs=*/ {tx2}, /*output_values=*/ {995 * CENT});
332  pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx3));
333  const auto res3 = ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size);
334  BOOST_CHECK(res3.has_value());
335  BOOST_CHECK(res3.value().first == DiagramCheckError::UNCALCULABLE);
336  BOOST_CHECK(res3.value().second == strprintf("%s has 2 descendants, max 1 allowed", tx1->GetHash().GetHex()));
337 
338 }
339 
340 BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup)
341 {
342  CTxMemPool& pool = *Assert(m_node.mempool);
343  LOCK2(::cs_main, pool.cs);
345 
346  const CAmount low_fee{CENT/100};
347  const CAmount normal_fee{CENT/10};
348  const CAmount high_fee{CENT};
349 
350  // low -> high -> medium fee transactions that would result in two chunks together
351  const auto low_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});
352  pool.addUnchecked(entry.Fee(low_fee).FromTx(low_tx));
353 
354  const auto entry_low = pool.GetIter(low_tx->GetHash()).value();
355  const auto low_size = entry_low->GetTxSize();
356 
357  std::vector<FeeFrac> old_diagram, new_diagram;
358 
359  // Replacement of size 1
360  const auto replace_one{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/0, /*replacement_vsize=*/1, {entry_low}, {entry_low})};
361  BOOST_CHECK(replace_one.has_value());
362  old_diagram = replace_one->first;
363  new_diagram = replace_one->second;
364  BOOST_CHECK(old_diagram.size() == 2);
365  BOOST_CHECK(new_diagram.size() == 2);
366  BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
367  BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee, low_size));
368  BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
369  BOOST_CHECK(new_diagram[1] == FeeFrac(0, 1));
370 
371  // Non-zero replacement fee/size
372  const auto replace_one_fee{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low})};
373  BOOST_CHECK(replace_one_fee.has_value());
374  old_diagram = replace_one_fee->first;
375  new_diagram = replace_one_fee->second;
376  BOOST_CHECK(old_diagram.size() == 2);
377  BOOST_CHECK(new_diagram.size() == 2);
378  BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
379  BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee, low_size));
380  BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
381  BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size));
382 
383  // Add a second transaction to the cluster that will make a single chunk, to be evicted in the RBF
384  const auto high_tx = make_tx(/*inputs=*/ {low_tx}, /*output_values=*/ {995 * CENT});
385  pool.addUnchecked(entry.Fee(high_fee).FromTx(high_tx));
386  const auto entry_high = pool.GetIter(high_tx->GetHash()).value();
387  const auto high_size = entry_high->GetTxSize();
388 
389  const auto replace_single_chunk{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low, entry_high})};
390  BOOST_CHECK(replace_single_chunk.has_value());
391  old_diagram = replace_single_chunk->first;
392  new_diagram = replace_single_chunk->second;
393  BOOST_CHECK(old_diagram.size() == 2);
394  BOOST_CHECK(new_diagram.size() == 2);
395  BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
396  BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee + high_fee, low_size + high_size));
397  BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
398  BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size));
399 
400  // Conflict with the 2nd tx, resulting in new diagram with three entries
401  const auto replace_cpfp_child{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high}, {entry_high})};
402  BOOST_CHECK(replace_cpfp_child.has_value());
403  old_diagram = replace_cpfp_child->first;
404  new_diagram = replace_cpfp_child->second;
405  BOOST_CHECK(old_diagram.size() == 2);
406  BOOST_CHECK(new_diagram.size() == 3);
407  BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
408  BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee + high_fee, low_size + high_size));
409  BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
410  BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size));
411  BOOST_CHECK(new_diagram[2] == FeeFrac(low_fee + high_fee, low_size + low_size));
412 
413  // third transaction causes the topology check to fail
414  const auto normal_tx = make_tx(/*inputs=*/ {high_tx}, /*output_values=*/ {995 * CENT});
415  pool.addUnchecked(entry.Fee(normal_fee).FromTx(normal_tx));
416  const auto entry_normal = pool.GetIter(normal_tx->GetHash()).value();
417  const auto normal_size = entry_normal->GetTxSize();
418 
419  const auto replace_too_large{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/normal_fee, /*replacement_vsize=*/normal_size, {entry_low}, {entry_low, entry_high, entry_normal})};
420  BOOST_CHECK(!replace_too_large.has_value());
421  BOOST_CHECK_EQUAL(util::ErrorString(replace_too_large).original, strprintf("%s has 2 descendants, max 1 allowed", low_tx->GetHash().GetHex()));
422  old_diagram.clear();
423  new_diagram.clear();
424 
425  // Make a size 2 cluster that is itself two chunks; evict both txns
426  const auto high_tx_2 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {10 * COIN});
427  pool.addUnchecked(entry.Fee(high_fee).FromTx(high_tx_2));
428  const auto entry_high_2 = pool.GetIter(high_tx_2->GetHash()).value();
429  const auto high_size_2 = entry_high_2->GetTxSize();
430 
431  const auto low_tx_2 = make_tx(/*inputs=*/ {high_tx_2}, /*output_values=*/ {9 * COIN});
432  pool.addUnchecked(entry.Fee(low_fee).FromTx(low_tx_2));
433  const auto entry_low_2 = pool.GetIter(low_tx_2->GetHash()).value();
434  const auto low_size_2 = entry_low_2->GetTxSize();
435 
436  const auto replace_two_chunks_single_cluster{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high_2}, {entry_high_2, entry_low_2})};
437  BOOST_CHECK(replace_two_chunks_single_cluster.has_value());
438  old_diagram = replace_two_chunks_single_cluster->first;
439  new_diagram = replace_two_chunks_single_cluster->second;
440  BOOST_CHECK(old_diagram.size() == 3);
441  BOOST_CHECK(new_diagram.size() == 2);
442  BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0));
443  BOOST_CHECK(old_diagram[1] == FeeFrac(high_fee, high_size_2));
444  BOOST_CHECK(old_diagram[2] == FeeFrac(low_fee + high_fee, low_size_2 + high_size_2));
445  BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0));
446  BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size_2));
447 
448  // You can have more than two direct conflicts if the there are multiple effected clusters, all of size 2 or less
449  const auto conflict_1 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN});
450  pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1));
451  const auto conflict_1_entry = pool.GetIter(conflict_1->GetHash()).value();
452 
453  const auto conflict_2 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {10 * COIN});
454  pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_2));
455  const auto conflict_2_entry = pool.GetIter(conflict_2->GetHash()).value();
456 
457  const auto conflict_3 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {10 * COIN});
458  pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_3));
459  const auto conflict_3_entry = pool.GetIter(conflict_3->GetHash()).value();
460 
461  const auto replace_multiple_clusters{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry})};
462 
463  BOOST_CHECK(replace_multiple_clusters.has_value());
464  old_diagram = replace_multiple_clusters->first;
465  new_diagram = replace_multiple_clusters->second;
466  BOOST_CHECK(old_diagram.size() == 4);
467  BOOST_CHECK(new_diagram.size() == 2);
468 
469  // Add a child transaction to conflict_1 and make it cluster size 2, still one chunk due to same feerate
470  const auto conflict_1_child = make_tx(/*inputs=*/{conflict_1}, /*output_values=*/ {995 * CENT});
471  pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1_child));
472  const auto conflict_1_child_entry = pool.GetIter(conflict_1_child->GetHash()).value();
473 
474  const auto replace_multiple_clusters_2{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry})};
475 
476  BOOST_CHECK(replace_multiple_clusters_2.has_value());
477  old_diagram = replace_multiple_clusters_2->first;
478  new_diagram = replace_multiple_clusters_2->second;
479  BOOST_CHECK(old_diagram.size() == 4);
480  BOOST_CHECK(new_diagram.size() == 2);
481  old_diagram.clear();
482  new_diagram.clear();
483 
484  // Add another descendant to conflict_1, making the cluster size > 2 should fail at this point.
485  const auto conflict_1_grand_child = make_tx(/*inputs=*/{conflict_1_child}, /*output_values=*/ {995 * CENT});
486  pool.addUnchecked(entry.Fee(high_fee).FromTx(conflict_1_grand_child));
487  const auto conflict_1_grand_child_entry = pool.GetIter(conflict_1_child->GetHash()).value();
488 
489  const auto replace_cluster_size_3{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry, conflict_1_grand_child_entry})};
490 
491  BOOST_CHECK(!replace_cluster_size_3.has_value());
492  BOOST_CHECK_EQUAL(util::ErrorString(replace_cluster_size_3).original, strprintf("%s has 2 descendants, max 1 allowed", conflict_1->GetHash().GetHex()));
493  BOOST_CHECK(old_diagram.empty());
494  BOOST_CHECK(new_diagram.empty());
495 }
496 
497 BOOST_AUTO_TEST_CASE(feerate_diagram_utilities)
498 {
499  // Sanity check the correctness of the feerate diagram comparison.
500 
501  // A strictly better case.
502  std::vector<FeeFrac> old_diagram{{FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}};
503  std::vector<FeeFrac> new_diagram{{FeeFrac{0, 0}, FeeFrac{1000, 300}, FeeFrac{1050, 400}}};
504 
505  BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
506 
507  // Incomparable diagrams
508  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
509  new_diagram = {FeeFrac{0, 0}, FeeFrac{1000, 300}, FeeFrac{1000, 400}};
510 
511  BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered);
512 
513  // Strictly better but smaller size.
514  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
515  new_diagram = {FeeFrac{0, 0}, FeeFrac{1100, 300}};
516 
517  BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
518 
519  // New diagram is strictly better due to the first chunk, even though
520  // second chunk contributes no fees
521  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
522  new_diagram = {FeeFrac{0, 0}, FeeFrac{1100, 100}, FeeFrac{1100, 200}};
523 
524  BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
525 
526  // Feerate of first new chunk is better with, but second chunk is worse
527  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
528  new_diagram = {FeeFrac{0, 0}, FeeFrac{750, 100}, FeeFrac{999, 350}, FeeFrac{1150, 1000}};
529 
530  BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered);
531 
532  // If we make the second chunk slightly better, the new diagram now wins.
533  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
534  new_diagram = {FeeFrac{0, 0}, FeeFrac{750, 100}, FeeFrac{1000, 350}, FeeFrac{1150, 500}};
535 
536  BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
537 
538  // Identical diagrams, cannot be strictly better
539  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
540  new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
541 
542  BOOST_CHECK(std::is_eq(CompareFeerateDiagram(old_diagram, new_diagram)));
543 
544  // Same aggregate fee, but different total size (trigger single tail fee check step)
545  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 399}};
546  new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};
547 
548  // No change in evaluation when tail check needed.
549  BOOST_CHECK(std::is_gt(CompareFeerateDiagram(old_diagram, new_diagram)));
550 
551  // Padding works on either argument
552  BOOST_CHECK(std::is_lt(CompareFeerateDiagram(new_diagram, old_diagram)));
553 
554  // Trigger multiple tail fee check steps
555  old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 399}};
556  new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}, FeeFrac{1050, 401}, FeeFrac{1050, 402}};
557 
558  BOOST_CHECK(std::is_gt(CompareFeerateDiagram(old_diagram, new_diagram)));
559  BOOST_CHECK(std::is_lt(CompareFeerateDiagram(new_diagram, old_diagram)));
560 
561  // Multiple tail fee check steps, unordered result
562  new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}, FeeFrac{1050, 401}, FeeFrac{1050, 402}, FeeFrac{1051, 403}};
563  BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered);
564 }
565 
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
static constexpr CAmount COIN
The amount of satoshis in one BTC.
Definition: amount.h:15
node::NodeContext m_node
Definition: bitcoin-gui.cpp:37
#define Assert(val)
Identity function.
Definition: check.h:77
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:414
CTxMemPool stores valid-according-to-the-current-best-chain transactions that may be included in the ...
Definition: txmempool.h:302
void PrioritiseTransaction(const uint256 &hash, const CAmount &nFeeDelta)
Affect CreateNewBlock prioritisation of transactions.
Definition: txmempool.cpp:876
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:390
std::optional< txiter > GetIter(const uint256 &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs)
Returns an iterator to the given hash, if found.
Definition: txmempool.cpp:950
std::set< txiter, CompareIteratorByHash > setEntries
Definition: txmempool.h:396
bool exists(const GenTxid &gtxid) const
Definition: txmempool.h:678
std::optional< std::string > CheckConflictTopology(const setEntries &direct_conflicts)
Definition: txmempool.cpp:1243
util::Result< std::pair< std::vector< FeeFrac >, std::vector< FeeFrac > > > CalculateFeerateDiagramsForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries &direct_conflicts, const setEntries &all_conflicts) EXCLUSIVE_LOCKS_REQUIRED(cs)
Calculate the old and new mempool feerate diagrams relating to the clusters that would be affected by...
Definition: txmempool.cpp:1283
void check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(void addUnchecked(const CTxMemPoolEntry &entry) EXCLUSIVE_LOCKS_REQUIRED(cs
If sanity-checking is turned on, check makes sure the pool is consistent (does not contain two transa...
Definition: txmempool.h:476
static GenTxid Txid(const uint256 &hash)
Definition: transaction.h:434
RecursiveMutex cs_main
Mutex to guard access to validation specific variables, such as reading or changing the chainstate.
Definition: cs_main.cpp:8
BOOST_AUTO_TEST_SUITE_END()
const CAmount high_fee
const CAmount low_fee
bilingual_str ErrorString(const Result< T > &result)
Definition: result.h:81
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
#define BOOST_CHECK(expr)
Definition: object.cpp:17
std::optional< std::string > PaysMoreThanConflicts(const CTxMemPool::setEntries &iters_conflicting, CFeeRate replacement_feerate, const uint256 &txid)
Check that the feerate of the replacement transaction(s) is higher than the feerate of each of the tr...
Definition: rbf.cpp:134
std::optional< std::string > HasNoNewUnconfirmed(const CTransaction &tx, const CTxMemPool &pool, const CTxMemPool::setEntries &iters_conflicting)
The replacement transaction may only include an unconfirmed input if that input was included in one o...
Definition: rbf.cpp:87
std::optional< std::string > PaysForRBF(CAmount original_fees, CAmount replacement_fees, size_t replacement_vsize, CFeeRate relay_fee, const uint256 &txid)
The replacement transaction must pay more fees than the original transactions.
Definition: rbf.cpp:160
std::optional< std::string > EntriesAndTxidsDisjoint(const CTxMemPool::setEntries &ancestors, const std::set< Txid > &direct_conflicts, const uint256 &txid)
Check the intersection between two sets of transactions (a set of mempool entries and a set of txids)...
Definition: rbf.cpp:119
std::optional< std::pair< DiagramCheckError, std::string > > ImprovesFeerateDiagram(CTxMemPool &pool, const CTxMemPool::setEntries &direct_conflicts, const CTxMemPool::setEntries &all_conflicts, CAmount replacement_fees, int64_t replacement_vsize)
The replacement transaction must improve the feerate diagram of the mempool.
Definition: rbf.cpp:187
std::optional< std::string > GetEntriesForConflicts(const CTransaction &tx, CTxMemPool &pool, const CTxMemPool::setEntries &iters_conflicting, CTxMemPool::setEntries &all_conflicts)
Get all descendants of iters_conflicting.
Definition: rbf.cpp:59
@ FAILURE
New diagram wasn't strictly superior
@ UNCALCULABLE
Unable to calculate due to topology or other reason.
static constexpr unsigned int DEFAULT_INCREMENTAL_RELAY_FEE
Default for -incrementalrelayfee, which sets the minimum feerate increase for mempool limiting or rep...
Definition: policy.h:35
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:424
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:423
uint256 GetRandHash() noexcept
Definition: random.cpp:650
BOOST_AUTO_TEST_CASE(feerate_diagram_utilities)
Definition: rbf_tests.cpp:497
static CTransactionRef make_tx(const std::vector< CTransactionRef > &inputs, const std::vector< CAmount > &output_values)
Definition: rbf_tests.cpp:19
static CTransactionRef add_descendants(const CTransactionRef &tx, int32_t num_descendants, CTxMemPool &pool) EXCLUSIVE_LOCKS_REQUIRED(
Definition: rbf_tests.cpp:40
static CTransactionRef add_descendant_to_parents(const std::vector< CTransactionRef > &parents, CTxMemPool &pool) EXCLUSIVE_LOCKS_REQUIRED(
Definition: rbf_tests.cpp:57
BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup)
Definition: rbf_tests.cpp:70
@ OP_EQUAL
Definition: script.h:145
@ OP_11
Definition: script.h:93
static constexpr CAmount CENT
Definition: setup_common.h:47
A mutable version of CTransaction.
Definition: transaction.h:378
std::vector< CTxOut > vout
Definition: transaction.h:380
std::vector< CTxIn > vin
Definition: transaction.h:379
std::vector< std::vector< unsigned char > > stack
Definition: script.h:569
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:39
Testing fixture that pre-creates a 100-block REGTEST-mode block chain.
Definition: setup_common.h:104
Definition: txmempool.h:19
CTxMemPoolEntry FromTx(const CMutableTransaction &tx) const
Definition: txmempool.cpp:32
TestMemPoolEntryHelper & Fee(CAmount _fee)
Definition: txmempool.h:33
Testing setup that configures a complete environment.
Definition: setup_common.h:83
std::unique_ptr< CTxMemPool > mempool
Definition: context.h:58
#define LOCK2(cs1, cs2)
Definition: sync.h:258
#define EXCLUSIVE_LOCKS_REQUIRED(...)
Definition: threadsafety.h:49
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1162
std::partial_ordering CompareFeerateDiagram(Span< const FeeFrac > dia0, Span< const FeeFrac > dia1)
Compares two feerate diagrams.
Definition: feefrac.cpp:22
AssertLockHeld(pool.cs)