Branch data Line data Source code
1 : : // Copyright (c) 2011-2022 The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <common/system.h>
6 : : #include <policy/policy.h>
7 : : #include <test/util/txmempool.h>
8 : : #include <txmempool.h>
9 : : #include <util/time.h>
10 : :
11 : : #include <test/util/setup_common.h>
12 : :
13 : : #include <boost/test/unit_test.hpp>
14 : : #include <vector>
15 : :
16 : 0 : BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
17 : 0 :
18 : 0 : static constexpr auto REMOVAL_REASON_DUMMY = MemPoolRemovalReason::REPLACED;
19 : :
20 : : class MemPoolTest final : public CTxMemPool
21 : : {
22 : : public:
23 : : using CTxMemPool::GetMinFee;
24 : : };
25 : :
26 : 0 : BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
27 : : {
28 : : // Test CTxMemPool::remove functionality
29 : :
30 : 0 : TestMemPoolEntryHelper entry;
31 : : // Parent transaction with three children,
32 : : // and three grand-children:
33 : 0 : CMutableTransaction txParent;
34 : 0 : txParent.vin.resize(1);
35 : 0 : txParent.vin[0].scriptSig = CScript() << OP_11;
36 : 0 : txParent.vout.resize(3);
37 : 0 : for (int i = 0; i < 3; i++)
38 : : {
39 : 0 : txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
40 : 0 : txParent.vout[i].nValue = 33000LL;
41 : 0 : }
42 : 0 : CMutableTransaction txChild[3];
43 : 0 : for (int i = 0; i < 3; i++)
44 : : {
45 : 0 : txChild[i].vin.resize(1);
46 : 0 : txChild[i].vin[0].scriptSig = CScript() << OP_11;
47 : 0 : txChild[i].vin[0].prevout.hash = txParent.GetHash();
48 : 0 : txChild[i].vin[0].prevout.n = i;
49 : 0 : txChild[i].vout.resize(1);
50 : 0 : txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
51 : 0 : txChild[i].vout[0].nValue = 11000LL;
52 : 0 : }
53 : 0 : CMutableTransaction txGrandChild[3];
54 : 0 : for (int i = 0; i < 3; i++)
55 : : {
56 : 0 : txGrandChild[i].vin.resize(1);
57 : 0 : txGrandChild[i].vin[0].scriptSig = CScript() << OP_11;
58 : 0 : txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash();
59 : 0 : txGrandChild[i].vin[0].prevout.n = 0;
60 : 0 : txGrandChild[i].vout.resize(1);
61 : 0 : txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
62 : 0 : txGrandChild[i].vout[0].nValue = 11000LL;
63 : 0 : }
64 : :
65 : :
66 : 0 : CTxMemPool& testPool = *Assert(m_node.mempool);
67 : 0 : LOCK2(::cs_main, testPool.cs);
68 : :
69 : : // Nothing in pool, remove should do nothing:
70 : 0 : unsigned int poolSize = testPool.size();
71 : 0 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
72 : 0 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
73 : :
74 : 0 : // Just the parent:
75 : 0 : testPool.addUnchecked(entry.FromTx(txParent));
76 : 0 : poolSize = testPool.size();
77 : 0 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
78 : 0 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1);
79 : :
80 : : // Parent, children, grandchildren:
81 : 0 : testPool.addUnchecked(entry.FromTx(txParent));
82 : 0 : for (int i = 0; i < 3; i++)
83 : : {
84 : 0 : testPool.addUnchecked(entry.FromTx(txChild[i]));
85 : 0 : testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
86 : 0 : }
87 : : // Remove Child[0], GrandChild[0] should be removed:
88 : 0 : poolSize = testPool.size();
89 : 0 : testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
90 : 0 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2);
91 : : // ... make sure grandchild and child are gone:
92 : 0 : poolSize = testPool.size();
93 : 0 : testPool.removeRecursive(CTransaction(txGrandChild[0]), REMOVAL_REASON_DUMMY);
94 : 0 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
95 : 0 : poolSize = testPool.size();
96 : 0 : testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
97 : 0 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
98 : : // Remove parent, all children/grandchildren should go:
99 : 0 : poolSize = testPool.size();
100 : 0 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
101 : 0 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5);
102 : 0 : BOOST_CHECK_EQUAL(testPool.size(), 0U);
103 : :
104 : : // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
105 : 0 : for (int i = 0; i < 3; i++)
106 : : {
107 : 0 : testPool.addUnchecked(entry.FromTx(txChild[i]));
108 : 0 : testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
109 : 0 : }
110 : : // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
111 : : // put into the mempool (maybe because it is non-standard):
112 : 0 : poolSize = testPool.size();
113 : 0 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
114 : 0 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6);
115 : 0 : BOOST_CHECK_EQUAL(testPool.size(), 0U);
116 : 0 : }
117 : :
118 : : template <typename name>
119 : 0 : static void CheckSort(CTxMemPool& pool, std::vector<std::string>& sortedOrder) EXCLUSIVE_LOCKS_REQUIRED(pool.cs)
120 : : {
121 : 0 : BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
122 : 0 : typename CTxMemPool::indexed_transaction_set::index<name>::type::iterator it = pool.mapTx.get<name>().begin();
123 : 0 : int count = 0;
124 : 0 : for (; it != pool.mapTx.get<name>().end(); ++it, ++count) {
125 : 0 : BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
126 : 0 : }
127 : 0 : }
128 : :
129 : 0 : BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
130 : : {
131 : 0 : CTxMemPool& pool = *Assert(m_node.mempool);
132 : 0 : LOCK2(cs_main, pool.cs);
133 : 0 : TestMemPoolEntryHelper entry;
134 : :
135 : : /* 3rd highest fee */
136 : 0 : CMutableTransaction tx1 = CMutableTransaction();
137 : 0 : tx1.vout.resize(1);
138 : 0 : tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
139 : 0 : tx1.vout[0].nValue = 10 * COIN;
140 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
141 : :
142 : : /* highest fee */
143 : 0 : CMutableTransaction tx2 = CMutableTransaction();
144 : 0 : tx2.vout.resize(1);
145 : 0 : tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
146 : 0 : tx2.vout[0].nValue = 2 * COIN;
147 : 0 : pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
148 : :
149 : : /* lowest fee */
150 : 0 : CMutableTransaction tx3 = CMutableTransaction();
151 : 0 : tx3.vout.resize(1);
152 : 0 : tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
153 : 0 : tx3.vout[0].nValue = 5 * COIN;
154 : 0 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
155 : :
156 : : /* 2nd highest fee */
157 : 0 : CMutableTransaction tx4 = CMutableTransaction();
158 : 0 : tx4.vout.resize(1);
159 : 0 : tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
160 : 0 : tx4.vout[0].nValue = 6 * COIN;
161 : 0 : pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
162 : :
163 : : /* equal fee rate to tx1, but newer */
164 : 0 : CMutableTransaction tx5 = CMutableTransaction();
165 : 0 : tx5.vout.resize(1);
166 : 0 : tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
167 : 0 : tx5.vout[0].nValue = 11 * COIN;
168 : 0 : entry.time = NodeSeconds{1s};
169 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
170 : 0 : BOOST_CHECK_EQUAL(pool.size(), 5U);
171 : :
172 : 0 : std::vector<std::string> sortedOrder;
173 : 0 : sortedOrder.resize(5);
174 : 0 : sortedOrder[0] = tx3.GetHash().ToString(); // 0
175 : 0 : sortedOrder[1] = tx5.GetHash().ToString(); // 10000
176 : 0 : sortedOrder[2] = tx1.GetHash().ToString(); // 10000
177 : 0 : sortedOrder[3] = tx4.GetHash().ToString(); // 15000
178 : 0 : sortedOrder[4] = tx2.GetHash().ToString(); // 20000
179 : 0 : CheckSort<descendant_score>(pool, sortedOrder);
180 : :
181 : : /* low fee but with high fee child */
182 : : /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
183 : 0 : CMutableTransaction tx6 = CMutableTransaction();
184 : 0 : tx6.vout.resize(1);
185 : 0 : tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
186 : 0 : tx6.vout[0].nValue = 20 * COIN;
187 : 0 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
188 : 0 : BOOST_CHECK_EQUAL(pool.size(), 6U);
189 : : // Check that at this point, tx6 is sorted low
190 : 0 : sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
191 : 0 : CheckSort<descendant_score>(pool, sortedOrder);
192 : :
193 : 0 : CTxMemPool::setEntries setAncestors;
194 : 0 : setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
195 : 0 : CMutableTransaction tx7 = CMutableTransaction();
196 : 0 : tx7.vin.resize(1);
197 : 0 : tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
198 : 0 : tx7.vin[0].scriptSig = CScript() << OP_11;
199 : 0 : tx7.vout.resize(2);
200 : 0 : tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
201 : 0 : tx7.vout[0].nValue = 10 * COIN;
202 : 0 : tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
203 : 0 : tx7.vout[1].nValue = 1 * COIN;
204 : :
205 : 0 : auto ancestors_calculated{pool.CalculateMemPoolAncestors(entry.Fee(2000000LL).FromTx(tx7), CTxMemPool::Limits::NoLimits())};
206 : 0 : BOOST_REQUIRE(ancestors_calculated.has_value());
207 : 0 : BOOST_CHECK(*ancestors_calculated == setAncestors);
208 : :
209 : 0 : pool.addUnchecked(entry.FromTx(tx7), setAncestors);
210 : 0 : BOOST_CHECK_EQUAL(pool.size(), 7U);
211 : :
212 : : // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
213 : 0 : sortedOrder.erase(sortedOrder.begin());
214 : 0 : sortedOrder.push_back(tx6.GetHash().ToString());
215 : 0 : sortedOrder.push_back(tx7.GetHash().ToString());
216 : 0 : CheckSort<descendant_score>(pool, sortedOrder);
217 : :
218 : : /* low fee child of tx7 */
219 : 0 : CMutableTransaction tx8 = CMutableTransaction();
220 : 0 : tx8.vin.resize(1);
221 : 0 : tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
222 : 0 : tx8.vin[0].scriptSig = CScript() << OP_11;
223 : 0 : tx8.vout.resize(1);
224 : 0 : tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
225 : 0 : tx8.vout[0].nValue = 10 * COIN;
226 : 0 : setAncestors.insert(pool.mapTx.find(tx7.GetHash()));
227 : 0 : pool.addUnchecked(entry.Fee(0LL).Time(NodeSeconds{2s}).FromTx(tx8), setAncestors);
228 : :
229 : : // Now tx8 should be sorted low, but tx6/tx both high
230 : 0 : sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
231 : 0 : CheckSort<descendant_score>(pool, sortedOrder);
232 : :
233 : : /* low fee child of tx7 */
234 : 0 : CMutableTransaction tx9 = CMutableTransaction();
235 : 0 : tx9.vin.resize(1);
236 : 0 : tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1);
237 : 0 : tx9.vin[0].scriptSig = CScript() << OP_11;
238 : 0 : tx9.vout.resize(1);
239 : 0 : tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
240 : 0 : tx9.vout[0].nValue = 1 * COIN;
241 : 0 : pool.addUnchecked(entry.Fee(0LL).Time(NodeSeconds{3s}).FromTx(tx9), setAncestors);
242 : :
243 : : // tx9 should be sorted low
244 : 0 : BOOST_CHECK_EQUAL(pool.size(), 9U);
245 : 0 : sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
246 : 0 : CheckSort<descendant_score>(pool, sortedOrder);
247 : :
248 : 0 : std::vector<std::string> snapshotOrder = sortedOrder;
249 : :
250 : 0 : setAncestors.insert(pool.mapTx.find(tx8.GetHash()));
251 : 0 : setAncestors.insert(pool.mapTx.find(tx9.GetHash()));
252 : : /* tx10 depends on tx8 and tx9 and has a high fee*/
253 : 0 : CMutableTransaction tx10 = CMutableTransaction();
254 : 0 : tx10.vin.resize(2);
255 : 0 : tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0);
256 : 0 : tx10.vin[0].scriptSig = CScript() << OP_11;
257 : 0 : tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0);
258 : 0 : tx10.vin[1].scriptSig = CScript() << OP_11;
259 : 0 : tx10.vout.resize(1);
260 : 0 : tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
261 : 0 : tx10.vout[0].nValue = 10 * COIN;
262 : :
263 : 0 : ancestors_calculated = pool.CalculateMemPoolAncestors(entry.Fee(200000LL).Time(NodeSeconds{4s}).FromTx(tx10), CTxMemPool::Limits::NoLimits());
264 : 0 : BOOST_REQUIRE(ancestors_calculated);
265 : 0 : BOOST_CHECK(*ancestors_calculated == setAncestors);
266 : :
267 : 0 : pool.addUnchecked(entry.FromTx(tx10), setAncestors);
268 : :
269 : : /**
270 : : * tx8 and tx9 should both now be sorted higher
271 : : * Final order after tx10 is added:
272 : : *
273 : : * tx3 = 0 (1)
274 : : * tx5 = 10000 (1)
275 : : * tx1 = 10000 (1)
276 : : * tx4 = 15000 (1)
277 : : * tx2 = 20000 (1)
278 : : * tx9 = 200k (2 txs)
279 : : * tx8 = 200k (2 txs)
280 : : * tx10 = 200k (1 tx)
281 : : * tx6 = 2.2M (5 txs)
282 : : * tx7 = 2.2M (4 txs)
283 : : */
284 : 0 : sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning
285 : 0 : sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
286 : 0 : sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
287 : 0 : sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
288 : 0 : CheckSort<descendant_score>(pool, sortedOrder);
289 : :
290 : : // there should be 10 transactions in the mempool
291 : 0 : BOOST_CHECK_EQUAL(pool.size(), 10U);
292 : :
293 : : // Now try removing tx10 and verify the sort order returns to normal
294 : 0 : pool.removeRecursive(pool.mapTx.find(tx10.GetHash())->GetTx(), REMOVAL_REASON_DUMMY);
295 : 0 : CheckSort<descendant_score>(pool, snapshotOrder);
296 : :
297 : 0 : pool.removeRecursive(pool.mapTx.find(tx9.GetHash())->GetTx(), REMOVAL_REASON_DUMMY);
298 : 0 : pool.removeRecursive(pool.mapTx.find(tx8.GetHash())->GetTx(), REMOVAL_REASON_DUMMY);
299 : 0 : }
300 : :
301 : 0 : BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest)
302 : : {
303 : 0 : CTxMemPool& pool = *Assert(m_node.mempool);
304 : 0 : LOCK2(cs_main, pool.cs);
305 : 0 : TestMemPoolEntryHelper entry;
306 : :
307 : : /* 3rd highest fee */
308 : 0 : CMutableTransaction tx1 = CMutableTransaction();
309 : 0 : tx1.vout.resize(1);
310 : 0 : tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
311 : 0 : tx1.vout[0].nValue = 10 * COIN;
312 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
313 : :
314 : : /* highest fee */
315 : 0 : CMutableTransaction tx2 = CMutableTransaction();
316 : 0 : tx2.vout.resize(1);
317 : 0 : tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
318 : 0 : tx2.vout[0].nValue = 2 * COIN;
319 : 0 : pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
320 : 0 : uint64_t tx2Size = GetVirtualTransactionSize(CTransaction(tx2));
321 : :
322 : : /* lowest fee */
323 : 0 : CMutableTransaction tx3 = CMutableTransaction();
324 : 0 : tx3.vout.resize(1);
325 : 0 : tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
326 : 0 : tx3.vout[0].nValue = 5 * COIN;
327 : 0 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
328 : :
329 : : /* 2nd highest fee */
330 : 0 : CMutableTransaction tx4 = CMutableTransaction();
331 : 0 : tx4.vout.resize(1);
332 : 0 : tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
333 : 0 : tx4.vout[0].nValue = 6 * COIN;
334 : 0 : pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
335 : :
336 : : /* equal fee rate to tx1, but newer */
337 : 0 : CMutableTransaction tx5 = CMutableTransaction();
338 : 0 : tx5.vout.resize(1);
339 : 0 : tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
340 : 0 : tx5.vout[0].nValue = 11 * COIN;
341 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
342 : 0 : BOOST_CHECK_EQUAL(pool.size(), 5U);
343 : :
344 : 0 : std::vector<std::string> sortedOrder;
345 : 0 : sortedOrder.resize(5);
346 : 0 : sortedOrder[0] = tx2.GetHash().ToString(); // 20000
347 : 0 : sortedOrder[1] = tx4.GetHash().ToString(); // 15000
348 : : // tx1 and tx5 are both 10000
349 : : // Ties are broken by hash, not timestamp, so determine which
350 : : // hash comes first.
351 : 0 : if (tx1.GetHash() < tx5.GetHash()) {
352 : 0 : sortedOrder[2] = tx1.GetHash().ToString();
353 : 0 : sortedOrder[3] = tx5.GetHash().ToString();
354 : 0 : } else {
355 : 0 : sortedOrder[2] = tx5.GetHash().ToString();
356 : 0 : sortedOrder[3] = tx1.GetHash().ToString();
357 : : }
358 : 0 : sortedOrder[4] = tx3.GetHash().ToString(); // 0
359 : :
360 : 0 : CheckSort<ancestor_score>(pool, sortedOrder);
361 : :
362 : : /* low fee parent with high fee child */
363 : : /* tx6 (0) -> tx7 (high) */
364 : 0 : CMutableTransaction tx6 = CMutableTransaction();
365 : 0 : tx6.vout.resize(1);
366 : 0 : tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
367 : 0 : tx6.vout[0].nValue = 20 * COIN;
368 : 0 : uint64_t tx6Size = GetVirtualTransactionSize(CTransaction(tx6));
369 : :
370 : 0 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
371 : 0 : BOOST_CHECK_EQUAL(pool.size(), 6U);
372 : : // Ties are broken by hash
373 : 0 : if (tx3.GetHash() < tx6.GetHash())
374 : 0 : sortedOrder.push_back(tx6.GetHash().ToString());
375 : : else
376 : 0 : sortedOrder.insert(sortedOrder.end()-1,tx6.GetHash().ToString());
377 : :
378 : 0 : CheckSort<ancestor_score>(pool, sortedOrder);
379 : :
380 : 0 : CMutableTransaction tx7 = CMutableTransaction();
381 : 0 : tx7.vin.resize(1);
382 : 0 : tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
383 : 0 : tx7.vin[0].scriptSig = CScript() << OP_11;
384 : 0 : tx7.vout.resize(1);
385 : 0 : tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
386 : 0 : tx7.vout[0].nValue = 10 * COIN;
387 : 0 : uint64_t tx7Size = GetVirtualTransactionSize(CTransaction(tx7));
388 : :
389 : : /* set the fee to just below tx2's feerate when including ancestor */
390 : 0 : CAmount fee = (20000/tx2Size)*(tx7Size + tx6Size) - 1;
391 : :
392 : 0 : pool.addUnchecked(entry.Fee(fee).FromTx(tx7));
393 : 0 : BOOST_CHECK_EQUAL(pool.size(), 7U);
394 : 0 : sortedOrder.insert(sortedOrder.begin()+1, tx7.GetHash().ToString());
395 : 0 : CheckSort<ancestor_score>(pool, sortedOrder);
396 : :
397 : : /* after tx6 is mined, tx7 should move up in the sort */
398 : 0 : std::vector<CTransactionRef> vtx;
399 : 0 : vtx.push_back(MakeTransactionRef(tx6));
400 : 0 : pool.removeForBlock(vtx, 1);
401 : :
402 : 0 : sortedOrder.erase(sortedOrder.begin()+1);
403 : : // Ties are broken by hash
404 : 0 : if (tx3.GetHash() < tx6.GetHash())
405 : 0 : sortedOrder.pop_back();
406 : : else
407 : 0 : sortedOrder.erase(sortedOrder.end()-2);
408 : 0 : sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
409 : 0 : CheckSort<ancestor_score>(pool, sortedOrder);
410 : :
411 : : // High-fee parent, low-fee child
412 : : // tx7 -> tx8
413 : 0 : CMutableTransaction tx8 = CMutableTransaction();
414 : 0 : tx8.vin.resize(1);
415 : 0 : tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
416 : 0 : tx8.vin[0].scriptSig = CScript() << OP_11;
417 : 0 : tx8.vout.resize(1);
418 : 0 : tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
419 : 0 : tx8.vout[0].nValue = 10*COIN;
420 : :
421 : : // Check that we sort by min(feerate, ancestor_feerate):
422 : : // set the fee so that the ancestor feerate is above tx1/5,
423 : : // but the transaction's own feerate is lower
424 : 0 : pool.addUnchecked(entry.Fee(5000LL).FromTx(tx8));
425 : 0 : sortedOrder.insert(sortedOrder.end()-1, tx8.GetHash().ToString());
426 : 0 : CheckSort<ancestor_score>(pool, sortedOrder);
427 : 0 : }
428 : :
429 : :
430 : 0 : BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
431 : : {
432 : 0 : auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool));
433 : 0 : LOCK2(cs_main, pool.cs);
434 : 0 : TestMemPoolEntryHelper entry;
435 : :
436 : 0 : CMutableTransaction tx1 = CMutableTransaction();
437 : 0 : tx1.vin.resize(1);
438 : 0 : tx1.vin[0].scriptSig = CScript() << OP_1;
439 : 0 : tx1.vout.resize(1);
440 : 0 : tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
441 : 0 : tx1.vout[0].nValue = 10 * COIN;
442 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
443 : :
444 : 0 : CMutableTransaction tx2 = CMutableTransaction();
445 : 0 : tx2.vin.resize(1);
446 : 0 : tx2.vin[0].scriptSig = CScript() << OP_2;
447 : 0 : tx2.vout.resize(1);
448 : 0 : tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
449 : 0 : tx2.vout[0].nValue = 10 * COIN;
450 : 0 : pool.addUnchecked(entry.Fee(5000LL).FromTx(tx2));
451 : :
452 : 0 : pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
453 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash())));
454 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash())));
455 : :
456 : 0 : pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
457 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash())));
458 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash())));
459 : :
460 : 0 : pool.addUnchecked(entry.FromTx(tx2));
461 : 0 : CMutableTransaction tx3 = CMutableTransaction();
462 : 0 : tx3.vin.resize(1);
463 : 0 : tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
464 : 0 : tx3.vin[0].scriptSig = CScript() << OP_2;
465 : 0 : tx3.vout.resize(1);
466 : 0 : tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
467 : 0 : tx3.vout[0].nValue = 10 * COIN;
468 : 0 : pool.addUnchecked(entry.Fee(20000LL).FromTx(tx3));
469 : :
470 : 0 : pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
471 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash())));
472 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash())));
473 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx3.GetHash())));
474 : :
475 : 0 : pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits
476 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash())));
477 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash())));
478 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx3.GetHash())));
479 : :
480 : 0 : CFeeRate maxFeeRateRemoved(25000, GetVirtualTransactionSize(CTransaction(tx3)) + GetVirtualTransactionSize(CTransaction(tx2)));
481 : 0 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
482 : :
483 : 0 : CMutableTransaction tx4 = CMutableTransaction();
484 : 0 : tx4.vin.resize(2);
485 : 0 : tx4.vin[0].prevout.SetNull();
486 : 0 : tx4.vin[0].scriptSig = CScript() << OP_4;
487 : 0 : tx4.vin[1].prevout.SetNull();
488 : 0 : tx4.vin[1].scriptSig = CScript() << OP_4;
489 : 0 : tx4.vout.resize(2);
490 : 0 : tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
491 : 0 : tx4.vout[0].nValue = 10 * COIN;
492 : 0 : tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
493 : 0 : tx4.vout[1].nValue = 10 * COIN;
494 : :
495 : 0 : CMutableTransaction tx5 = CMutableTransaction();
496 : 0 : tx5.vin.resize(2);
497 : 0 : tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
498 : 0 : tx5.vin[0].scriptSig = CScript() << OP_4;
499 : 0 : tx5.vin[1].prevout.SetNull();
500 : 0 : tx5.vin[1].scriptSig = CScript() << OP_5;
501 : 0 : tx5.vout.resize(2);
502 : 0 : tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
503 : 0 : tx5.vout[0].nValue = 10 * COIN;
504 : 0 : tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
505 : 0 : tx5.vout[1].nValue = 10 * COIN;
506 : :
507 : 0 : CMutableTransaction tx6 = CMutableTransaction();
508 : 0 : tx6.vin.resize(2);
509 : 0 : tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
510 : 0 : tx6.vin[0].scriptSig = CScript() << OP_4;
511 : 0 : tx6.vin[1].prevout.SetNull();
512 : 0 : tx6.vin[1].scriptSig = CScript() << OP_6;
513 : 0 : tx6.vout.resize(2);
514 : 0 : tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
515 : 0 : tx6.vout[0].nValue = 10 * COIN;
516 : 0 : tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
517 : 0 : tx6.vout[1].nValue = 10 * COIN;
518 : :
519 : 0 : CMutableTransaction tx7 = CMutableTransaction();
520 : 0 : tx7.vin.resize(2);
521 : 0 : tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
522 : 0 : tx7.vin[0].scriptSig = CScript() << OP_5;
523 : 0 : tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
524 : 0 : tx7.vin[1].scriptSig = CScript() << OP_6;
525 : 0 : tx7.vout.resize(2);
526 : 0 : tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
527 : 0 : tx7.vout[0].nValue = 10 * COIN;
528 : 0 : tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
529 : 0 : tx7.vout[1].nValue = 10 * COIN;
530 : :
531 : 0 : pool.addUnchecked(entry.Fee(7000LL).FromTx(tx4));
532 : 0 : pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
533 : 0 : pool.addUnchecked(entry.Fee(1100LL).FromTx(tx6));
534 : 0 : pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
535 : :
536 : : // we only require this to remove, at max, 2 txn, because it's not clear what we're really optimizing for aside from that
537 : 0 : pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
538 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash())));
539 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash())));
540 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash())));
541 : :
542 : 0 : if (!pool.exists(GenTxid::Txid(tx5.GetHash())))
543 : 0 : pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
544 : 0 : pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
545 : :
546 : 0 : pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7
547 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash())));
548 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx5.GetHash())));
549 : 0 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash())));
550 : 0 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash())));
551 : :
552 : 0 : pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
553 : 0 : pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
554 : :
555 : 0 : std::vector<CTransactionRef> vtx;
556 : 0 : SetMockTime(42);
557 : 0 : SetMockTime(42 + CTxMemPool::ROLLING_FEE_HALFLIFE);
558 : 0 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
559 : : // ... we should keep the same min fee until we get a block
560 : 0 : pool.removeForBlock(vtx, 1);
561 : 0 : SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE);
562 : 0 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/2.0));
563 : : // ... then feerate should drop 1/2 each halflife
564 : :
565 : 0 : SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2);
566 : 0 : BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/4.0));
567 : : // ... with a 1/2 halflife when mempool is < 1/2 its target size
568 : :
569 : 0 : SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
570 : 0 : BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/8.0));
571 : : // ... with a 1/4 halflife when mempool is < 1/4 its target size
572 : :
573 : 0 : SetMockTime(42 + 7*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
574 : 0 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000);
575 : : // ... but feerate should never drop below 1000
576 : :
577 : 0 : SetMockTime(42 + 8*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
578 : 0 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
579 : : // ... unless it has gone all the way to 0 (after getting past 1000/2)
580 : 0 : }
581 : :
582 : 0 : inline CTransactionRef make_tx(std::vector<CAmount>&& output_values, std::vector<CTransactionRef>&& inputs=std::vector<CTransactionRef>(), std::vector<uint32_t>&& input_indices=std::vector<uint32_t>())
583 : : {
584 : 0 : CMutableTransaction tx = CMutableTransaction();
585 : 0 : tx.vin.resize(inputs.size());
586 : 0 : tx.vout.resize(output_values.size());
587 : 0 : for (size_t i = 0; i < inputs.size(); ++i) {
588 : 0 : tx.vin[i].prevout.hash = inputs[i]->GetHash();
589 : 0 : tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
590 : 0 : }
591 : 0 : for (size_t i = 0; i < output_values.size(); ++i) {
592 : 0 : tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
593 : 0 : tx.vout[i].nValue = output_values[i];
594 : 0 : }
595 : 0 : return MakeTransactionRef(tx);
596 : 0 : }
597 : :
598 : :
599 : 0 : BOOST_AUTO_TEST_CASE(MempoolAncestryTests)
600 : : {
601 : : size_t ancestors, descendants;
602 : :
603 : 0 : CTxMemPool& pool = *Assert(m_node.mempool);
604 : 0 : LOCK2(cs_main, pool.cs);
605 : 0 : TestMemPoolEntryHelper entry;
606 : :
607 : : /* Base transaction */
608 : : //
609 : : // [tx1]
610 : : //
611 : 0 : CTransactionRef tx1 = make_tx(/*output_values=*/{10 * COIN});
612 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
613 : :
614 : : // Ancestors / descendants should be 1 / 1 (itself / itself)
615 : 0 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
616 : 0 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
617 : 0 : BOOST_CHECK_EQUAL(descendants, 1ULL);
618 : :
619 : : /* Child transaction */
620 : : //
621 : : // [tx1].0 <- [tx2]
622 : : //
623 : 0 : CTransactionRef tx2 = make_tx(/*output_values=*/{495 * CENT, 5 * COIN}, /*inputs=*/{tx1});
624 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx2));
625 : :
626 : : // Ancestors / descendants should be:
627 : : // transaction ancestors descendants
628 : : // ============ =========== ===========
629 : : // tx1 1 (tx1) 2 (tx1,2)
630 : : // tx2 2 (tx1,2) 2 (tx1,2)
631 : 0 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
632 : 0 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
633 : 0 : BOOST_CHECK_EQUAL(descendants, 2ULL);
634 : 0 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
635 : 0 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
636 : 0 : BOOST_CHECK_EQUAL(descendants, 2ULL);
637 : :
638 : : /* Grand-child 1 */
639 : : //
640 : : // [tx1].0 <- [tx2].0 <- [tx3]
641 : : //
642 : 0 : CTransactionRef tx3 = make_tx(/*output_values=*/{290 * CENT, 200 * CENT}, /*inputs=*/{tx2});
643 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx3));
644 : :
645 : : // Ancestors / descendants should be:
646 : : // transaction ancestors descendants
647 : : // ============ =========== ===========
648 : : // tx1 1 (tx1) 3 (tx1,2,3)
649 : : // tx2 2 (tx1,2) 3 (tx1,2,3)
650 : : // tx3 3 (tx1,2,3) 3 (tx1,2,3)
651 : 0 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
652 : 0 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
653 : 0 : BOOST_CHECK_EQUAL(descendants, 3ULL);
654 : 0 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
655 : 0 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
656 : 0 : BOOST_CHECK_EQUAL(descendants, 3ULL);
657 : 0 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
658 : 0 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
659 : 0 : BOOST_CHECK_EQUAL(descendants, 3ULL);
660 : :
661 : : /* Grand-child 2 */
662 : : //
663 : : // [tx1].0 <- [tx2].0 <- [tx3]
664 : : // |
665 : : // \---1 <- [tx4]
666 : : //
667 : 0 : CTransactionRef tx4 = make_tx(/*output_values=*/{290 * CENT, 250 * CENT}, /*inputs=*/{tx2}, /*input_indices=*/{1});
668 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx4));
669 : :
670 : : // Ancestors / descendants should be:
671 : : // transaction ancestors descendants
672 : : // ============ =========== ===========
673 : : // tx1 1 (tx1) 4 (tx1,2,3,4)
674 : : // tx2 2 (tx1,2) 4 (tx1,2,3,4)
675 : : // tx3 3 (tx1,2,3) 4 (tx1,2,3,4)
676 : : // tx4 3 (tx1,2,4) 4 (tx1,2,3,4)
677 : 0 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
678 : 0 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
679 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
680 : 0 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
681 : 0 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
682 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
683 : 0 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
684 : 0 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
685 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
686 : 0 : pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
687 : 0 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
688 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
689 : :
690 : : /* Make an alternate branch that is longer and connect it to tx3 */
691 : : //
692 : : // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0
693 : : // |
694 : : // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/
695 : : // |
696 : : // \---1 <- [tx4]
697 : : //
698 : 0 : CTransactionRef ty1, ty2, ty3, ty4, ty5;
699 : 0 : CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5};
700 : 0 : CAmount v = 5 * COIN;
701 : 0 : for (uint64_t i = 0; i < 5; i++) {
702 : 0 : CTransactionRef& tyi = *ty[i];
703 : 0 : tyi = make_tx(/*output_values=*/{v}, /*inputs=*/i > 0 ? std::vector<CTransactionRef>{*ty[i - 1]} : std::vector<CTransactionRef>{});
704 : 0 : v -= 50 * CENT;
705 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tyi));
706 : 0 : pool.GetTransactionAncestry(tyi->GetHash(), ancestors, descendants);
707 : 0 : BOOST_CHECK_EQUAL(ancestors, i+1);
708 : 0 : BOOST_CHECK_EQUAL(descendants, i+1);
709 : 0 : }
710 : 0 : CTransactionRef ty6 = make_tx(/*output_values=*/{5 * COIN}, /*inputs=*/{tx3, ty5});
711 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(ty6));
712 : :
713 : : // Ancestors / descendants should be:
714 : : // transaction ancestors descendants
715 : : // ============ =================== ===========
716 : : // tx1 1 (tx1) 5 (tx1,2,3,4, ty6)
717 : : // tx2 2 (tx1,2) 5 (tx1,2,3,4, ty6)
718 : : // tx3 3 (tx1,2,3) 5 (tx1,2,3,4, ty6)
719 : : // tx4 3 (tx1,2,4) 5 (tx1,2,3,4, ty6)
720 : : // ty1 1 (ty1) 6 (ty1,2,3,4,5,6)
721 : : // ty2 2 (ty1,2) 6 (ty1,2,3,4,5,6)
722 : : // ty3 3 (ty1,2,3) 6 (ty1,2,3,4,5,6)
723 : : // ty4 4 (y1234) 6 (ty1,2,3,4,5,6)
724 : : // ty5 5 (y12345) 6 (ty1,2,3,4,5,6)
725 : : // ty6 9 (tx123, ty123456) 6 (ty1,2,3,4,5,6)
726 : 0 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
727 : 0 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
728 : 0 : BOOST_CHECK_EQUAL(descendants, 5ULL);
729 : 0 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
730 : 0 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
731 : 0 : BOOST_CHECK_EQUAL(descendants, 5ULL);
732 : 0 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
733 : 0 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
734 : 0 : BOOST_CHECK_EQUAL(descendants, 5ULL);
735 : 0 : pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
736 : 0 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
737 : 0 : BOOST_CHECK_EQUAL(descendants, 5ULL);
738 : 0 : pool.GetTransactionAncestry(ty1->GetHash(), ancestors, descendants);
739 : 0 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
740 : 0 : BOOST_CHECK_EQUAL(descendants, 6ULL);
741 : 0 : pool.GetTransactionAncestry(ty2->GetHash(), ancestors, descendants);
742 : 0 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
743 : 0 : BOOST_CHECK_EQUAL(descendants, 6ULL);
744 : 0 : pool.GetTransactionAncestry(ty3->GetHash(), ancestors, descendants);
745 : 0 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
746 : 0 : BOOST_CHECK_EQUAL(descendants, 6ULL);
747 : 0 : pool.GetTransactionAncestry(ty4->GetHash(), ancestors, descendants);
748 : 0 : BOOST_CHECK_EQUAL(ancestors, 4ULL);
749 : 0 : BOOST_CHECK_EQUAL(descendants, 6ULL);
750 : 0 : pool.GetTransactionAncestry(ty5->GetHash(), ancestors, descendants);
751 : 0 : BOOST_CHECK_EQUAL(ancestors, 5ULL);
752 : 0 : BOOST_CHECK_EQUAL(descendants, 6ULL);
753 : 0 : pool.GetTransactionAncestry(ty6->GetHash(), ancestors, descendants);
754 : 0 : BOOST_CHECK_EQUAL(ancestors, 9ULL);
755 : 0 : BOOST_CHECK_EQUAL(descendants, 6ULL);
756 : 0 : }
757 : :
758 : 0 : BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond)
759 : : {
760 : : size_t ancestors, descendants;
761 : :
762 : 0 : CTxMemPool& pool = *Assert(m_node.mempool);
763 : 0 : LOCK2(::cs_main, pool.cs);
764 : 0 : TestMemPoolEntryHelper entry;
765 : :
766 : : /* Ancestors represented more than once ("diamond") */
767 : : //
768 : : // [ta].0 <- [tb].0 -----<------- [td].0
769 : : // | |
770 : : // \---1 <- [tc].0 --<--/
771 : : //
772 : 0 : CTransactionRef ta, tb, tc, td;
773 : 0 : ta = make_tx(/*output_values=*/{10 * COIN});
774 : 0 : tb = make_tx(/*output_values=*/{5 * COIN, 3 * COIN}, /*inputs=*/ {ta});
775 : 0 : tc = make_tx(/*output_values=*/{2 * COIN}, /*inputs=*/{tb}, /*input_indices=*/{1});
776 : 0 : td = make_tx(/*output_values=*/{6 * COIN}, /*inputs=*/{tb, tc}, /*input_indices=*/{0, 0});
777 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(ta));
778 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tb));
779 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tc));
780 : 0 : pool.addUnchecked(entry.Fee(10000LL).FromTx(td));
781 : :
782 : : // Ancestors / descendants should be:
783 : : // transaction ancestors descendants
784 : : // ============ =================== ===========
785 : : // ta 1 (ta 4 (ta,tb,tc,td)
786 : : // tb 2 (ta,tb) 4 (ta,tb,tc,td)
787 : : // tc 3 (ta,tb,tc) 4 (ta,tb,tc,td)
788 : : // td 4 (ta,tb,tc,td) 4 (ta,tb,tc,td)
789 : 0 : pool.GetTransactionAncestry(ta->GetHash(), ancestors, descendants);
790 : 0 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
791 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
792 : 0 : pool.GetTransactionAncestry(tb->GetHash(), ancestors, descendants);
793 : 0 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
794 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
795 : 0 : pool.GetTransactionAncestry(tc->GetHash(), ancestors, descendants);
796 : 0 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
797 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
798 : 0 : pool.GetTransactionAncestry(td->GetHash(), ancestors, descendants);
799 : 0 : BOOST_CHECK_EQUAL(ancestors, 4ULL);
800 : 0 : BOOST_CHECK_EQUAL(descendants, 4ULL);
801 : 0 : }
802 : :
803 : 0 : BOOST_AUTO_TEST_SUITE_END()
|
