blockencodings_tests.cpp raw
1 // Copyright (c) 2011-2022 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #include <blockencodings.h>
6 #include <chainparams.h>
7 #include <consensus/merkle.h>
8 #include <pow.h>
9 #include <streams.h>
10 #include <test/util/random.h>
11 #include <test/util/txmempool.h>
12
13 #include <test/util/setup_common.h>
14
15 #include <boost/test/unit_test.hpp>
16
17 const std::vector<CTransactionRef> empty_extra_txn;
18
19 BOOST_FIXTURE_TEST_SUITE(blockencodings_tests, RegTestingSetup)
20
21 static CMutableTransaction BuildTransactionTestCase() {
22 CMutableTransaction tx;
23 tx.vin.resize(1);
24 tx.vin[0].scriptSig.resize(10);
25 tx.vout.resize(1);
26 tx.vout[0].nValue = 42;
27 return tx;
28 }
29
30 static CBlock BuildBlockTestCase(FastRandomContext& ctx) {
31 CBlock block;
32 CMutableTransaction tx = BuildTransactionTestCase();
33
34 block.vtx.resize(3);
35 block.vtx[0] = MakeTransactionRef(tx);
36 block.nVersion = 42;
37 block.hashPrevBlock = ctx.rand256();
38 block.nBits = 0x207fffff;
39
40 tx.vin[0].prevout.hash = Txid::FromUint256(ctx.rand256());
41 tx.vin[0].prevout.n = 0;
42 block.vtx[1] = MakeTransactionRef(tx);
43
44 tx.vin.resize(10);
45 for (size_t i = 0; i < tx.vin.size(); i++) {
46 tx.vin[i].prevout.hash = Txid::FromUint256(ctx.rand256());
47 tx.vin[i].prevout.n = 0;
48 }
49 block.vtx[2] = MakeTransactionRef(tx);
50
51 bool mutated;
52 block.hashMerkleRoot = BlockMerkleRoot(block, &mutated);
53 assert(!mutated);
54 while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce;
55 return block;
56 }
57
58 // Number of shared use_counts we expect for a tx we haven't touched
59 // (block + mempool entry + mempool txns_randomized + our copy from the GetSharedTx call)
60 constexpr long SHARED_TX_OFFSET{4};
61
62 BOOST_AUTO_TEST_CASE(SimpleRoundTripTest)
63 {
64 CTxMemPool& pool = *Assert(m_node.mempool);
65 TestMemPoolEntryHelper entry;
66 auto rand_ctx(FastRandomContext(uint256{42}));
67 CBlock block(BuildBlockTestCase(rand_ctx));
68
69 LOCK2(cs_main, pool.cs);
70 AddToMempool(pool, entry.FromTx(block.vtx[2]));
71 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 0);
72
73 // Do a simple ShortTxIDs RT
74 {
75 CBlockHeaderAndShortTxIDs shortIDs{block, rand_ctx.rand64()};
76
77 DataStream stream{};
78 stream << shortIDs;
79
80 CBlockHeaderAndShortTxIDs shortIDs2;
81 stream >> shortIDs2;
82
83 PartiallyDownloadedBlock partialBlock(&pool);
84 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK);
85 BOOST_CHECK( partialBlock.IsTxAvailable(0));
86 BOOST_CHECK(!partialBlock.IsTxAvailable(1));
87 BOOST_CHECK( partialBlock.IsTxAvailable(2));
88
89 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 1);
90
91 size_t poolSize = pool.size();
92 pool.removeRecursive(*block.vtx[2], MemPoolRemovalReason::REPLACED);
93 BOOST_CHECK_EQUAL(pool.size(), poolSize - 1);
94
95 CBlock block2;
96 {
97 PartiallyDownloadedBlock tmp = partialBlock;
98 BOOST_CHECK(partialBlock.FillBlock(block2, {}, /*segwit_active=*/true) == READ_STATUS_INVALID); // No transactions
99 partialBlock = tmp;
100 }
101
102 // Wrong transaction
103 {
104 PartiallyDownloadedBlock tmp = partialBlock;
105 partialBlock.FillBlock(block2, {block.vtx[2]}, /*segwit_active=*/true); // Current implementation doesn't check txn here, but don't require that
106 partialBlock = tmp;
107 }
108 bool mutated;
109 BOOST_CHECK(block.hashMerkleRoot != BlockMerkleRoot(block2, &mutated));
110
111 CBlock block3;
112 BOOST_CHECK(partialBlock.FillBlock(block3, {block.vtx[1]}, /*segwit_active=*/true) == READ_STATUS_OK);
113 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block3.GetHash().ToString());
114 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block3, &mutated).ToString());
115 BOOST_CHECK(!mutated);
116 }
117 }
118
119 class TestHeaderAndShortIDs {
120 // Utility to encode custom CBlockHeaderAndShortTxIDs
121 public:
122 CBlockHeader header;
123 uint64_t nonce;
124 std::vector<uint64_t> shorttxids;
125 std::vector<PrefilledTransaction> prefilledtxn;
126
127 explicit TestHeaderAndShortIDs(const CBlockHeaderAndShortTxIDs& orig) {
128 DataStream stream{};
129 stream << orig;
130 stream >> *this;
131 }
132 explicit TestHeaderAndShortIDs(const CBlock& block, FastRandomContext& ctx) :
133 TestHeaderAndShortIDs(CBlockHeaderAndShortTxIDs{block, ctx.rand64()}) {}
134
135 uint64_t GetShortID(const Wtxid& txhash) const {
136 DataStream stream{};
137 stream << *this;
138 CBlockHeaderAndShortTxIDs base;
139 stream >> base;
140 return base.GetShortID(txhash);
141 }
142
143 SERIALIZE_METHODS(TestHeaderAndShortIDs, obj) { READWRITE(obj.header, obj.nonce, Using<VectorFormatter<CustomUintFormatter<CBlockHeaderAndShortTxIDs::SHORTTXIDS_LENGTH>>>(obj.shorttxids), obj.prefilledtxn); }
144 };
145
146 BOOST_AUTO_TEST_CASE(NonCoinbasePreforwardRTTest)
147 {
148 CTxMemPool& pool = *Assert(m_node.mempool);
149 TestMemPoolEntryHelper entry;
150 auto rand_ctx(FastRandomContext(uint256{42}));
151 CBlock block(BuildBlockTestCase(rand_ctx));
152
153 LOCK2(cs_main, pool.cs);
154 AddToMempool(pool, entry.FromTx(block.vtx[2]));
155 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 0);
156
157 uint256 txhash;
158
159 // Test with pre-forwarding tx 1, but not coinbase
160 {
161 TestHeaderAndShortIDs shortIDs(block, rand_ctx);
162 shortIDs.prefilledtxn.resize(1);
163 shortIDs.prefilledtxn[0] = {1, block.vtx[1]};
164 shortIDs.shorttxids.resize(2);
165 shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[0]->GetWitnessHash());
166 shortIDs.shorttxids[1] = shortIDs.GetShortID(block.vtx[2]->GetWitnessHash());
167
168 DataStream stream{};
169 stream << shortIDs;
170
171 CBlockHeaderAndShortTxIDs shortIDs2;
172 stream >> shortIDs2;
173
174 PartiallyDownloadedBlock partialBlock(&pool);
175 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK);
176 BOOST_CHECK(!partialBlock.IsTxAvailable(0));
177 BOOST_CHECK( partialBlock.IsTxAvailable(1));
178 BOOST_CHECK( partialBlock.IsTxAvailable(2));
179
180 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 1); // +1 because of partialBlock
181
182 CBlock block2;
183 {
184 PartiallyDownloadedBlock tmp = partialBlock;
185 BOOST_CHECK(partialBlock.FillBlock(block2, {}, /*segwit_active=*/true) == READ_STATUS_INVALID); // No transactions
186 partialBlock = tmp;
187 }
188
189 // Wrong transaction
190 {
191 PartiallyDownloadedBlock tmp = partialBlock;
192 partialBlock.FillBlock(block2, {block.vtx[1]}, /*segwit_active=*/true); // Current implementation doesn't check txn here, but don't require that
193 partialBlock = tmp;
194 }
195 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 2); // +2 because of partialBlock and block2
196 bool mutated;
197 BOOST_CHECK(block.hashMerkleRoot != BlockMerkleRoot(block2, &mutated));
198
199 CBlock block3;
200 PartiallyDownloadedBlock partialBlockCopy = partialBlock;
201 BOOST_CHECK(partialBlock.FillBlock(block3, {block.vtx[0]}, /*segwit_active=*/true) == READ_STATUS_OK);
202 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block3.GetHash().ToString());
203 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block3, &mutated).ToString());
204 BOOST_CHECK(!mutated);
205
206 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 3); // +2 because of partialBlock and block2 and block3
207
208 txhash = block.vtx[2]->GetHash();
209 block.vtx.clear();
210 block2.vtx.clear();
211 block3.vtx.clear();
212 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET + 1 - 1); // + 1 because of partialBlock; -1 because of block.
213 }
214 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET - 1); // -1 because of block
215 }
216
217 BOOST_AUTO_TEST_CASE(SufficientPreforwardRTTest)
218 {
219 CTxMemPool& pool = *Assert(m_node.mempool);
220 TestMemPoolEntryHelper entry;
221 auto rand_ctx(FastRandomContext(uint256{42}));
222 CBlock block(BuildBlockTestCase(rand_ctx));
223
224 LOCK2(cs_main, pool.cs);
225 AddToMempool(pool, entry.FromTx(block.vtx[1]));
226 BOOST_CHECK_EQUAL(pool.get(block.vtx[1]->GetHash()).use_count(), SHARED_TX_OFFSET + 0);
227
228 uint256 txhash;
229
230 // Test with pre-forwarding coinbase + tx 2 with tx 1 in mempool
231 {
232 TestHeaderAndShortIDs shortIDs(block, rand_ctx);
233 shortIDs.prefilledtxn.resize(2);
234 shortIDs.prefilledtxn[0] = {0, block.vtx[0]};
235 shortIDs.prefilledtxn[1] = {1, block.vtx[2]}; // id == 1 as it is 1 after index 1
236 shortIDs.shorttxids.resize(1);
237 shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[1]->GetWitnessHash());
238
239 DataStream stream{};
240 stream << shortIDs;
241
242 CBlockHeaderAndShortTxIDs shortIDs2;
243 stream >> shortIDs2;
244
245 PartiallyDownloadedBlock partialBlock(&pool);
246 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK);
247 BOOST_CHECK( partialBlock.IsTxAvailable(0));
248 BOOST_CHECK( partialBlock.IsTxAvailable(1));
249 BOOST_CHECK( partialBlock.IsTxAvailable(2));
250
251 BOOST_CHECK_EQUAL(pool.get(block.vtx[1]->GetHash()).use_count(), SHARED_TX_OFFSET + 1);
252
253 CBlock block2;
254 PartiallyDownloadedBlock partialBlockCopy = partialBlock;
255 BOOST_CHECK(partialBlock.FillBlock(block2, {}, /*segwit_active=*/true) == READ_STATUS_OK);
256 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString());
257 bool mutated;
258 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString());
259 BOOST_CHECK(!mutated);
260
261 txhash = block.vtx[1]->GetHash();
262 block.vtx.clear();
263 block2.vtx.clear();
264 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET + 1 - 1); // + 1 because of partialBlock; -1 because of block.
265 }
266 BOOST_CHECK_EQUAL(pool.get(txhash).use_count(), SHARED_TX_OFFSET - 1); // -1 because of block
267 }
268
269 BOOST_AUTO_TEST_CASE(EmptyBlockRoundTripTest)
270 {
271 CTxMemPool& pool = *Assert(m_node.mempool);
272 CMutableTransaction coinbase = BuildTransactionTestCase();
273
274 CBlock block;
275 auto rand_ctx(FastRandomContext(uint256{42}));
276 block.vtx.resize(1);
277 block.vtx[0] = MakeTransactionRef(std::move(coinbase));
278 block.nVersion = 42;
279 block.hashPrevBlock = rand_ctx.rand256();
280 block.nBits = 0x207fffff;
281
282 bool mutated;
283 block.hashMerkleRoot = BlockMerkleRoot(block, &mutated);
284 assert(!mutated);
285 while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce;
286
287 // Test simple header round-trip with only coinbase
288 {
289 CBlockHeaderAndShortTxIDs shortIDs{block, rand_ctx.rand64()};
290
291 DataStream stream{};
292 stream << shortIDs;
293
294 CBlockHeaderAndShortTxIDs shortIDs2;
295 stream >> shortIDs2;
296
297 PartiallyDownloadedBlock partialBlock(&pool);
298 BOOST_CHECK(partialBlock.InitData(shortIDs2, empty_extra_txn) == READ_STATUS_OK);
299 BOOST_CHECK(partialBlock.IsTxAvailable(0));
300
301 CBlock block2;
302 std::vector<CTransactionRef> vtx_missing;
303 BOOST_CHECK(partialBlock.FillBlock(block2, vtx_missing, /*segwit_active=*/true) == READ_STATUS_OK);
304 BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString());
305 BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString());
306 BOOST_CHECK(!mutated);
307 }
308 }
309
310 BOOST_AUTO_TEST_CASE(ReceiveWithExtraTransactions) {
311 CTxMemPool& pool = *Assert(m_node.mempool);
312 TestMemPoolEntryHelper entry;
313 auto rand_ctx(FastRandomContext(uint256{42}));
314
315 CMutableTransaction mtx = BuildTransactionTestCase();
316 mtx.vin[0].prevout.hash = Txid::FromUint256(rand_ctx.rand256());
317 mtx.vin[0].prevout.n = 0;
318 const CTransactionRef non_block_tx = MakeTransactionRef(std::move(mtx));
319
320 CBlock block(BuildBlockTestCase(rand_ctx));
321 std::vector<CTransactionRef> extra_txn;
322 extra_txn.resize(10);
323
324 LOCK2(cs_main, pool.cs);
325 AddToMempool(pool, entry.FromTx(block.vtx[2]));
326 BOOST_CHECK_EQUAL(pool.get(block.vtx[2]->GetHash()).use_count(), SHARED_TX_OFFSET + 0);
327 // Ensure the non_block_tx is actually not in the block
328 for (const auto &block_tx : block.vtx) {
329 BOOST_CHECK_NE(block_tx->GetHash(), non_block_tx->GetHash());
330 }
331 // Ensure block.vtx[1] is not in pool
332 BOOST_CHECK_EQUAL(pool.get(block.vtx[1]->GetHash()), nullptr);
333
334 {
335 const CBlockHeaderAndShortTxIDs cmpctblock{block, rand_ctx.rand64()};
336 PartiallyDownloadedBlock partial_block(&pool);
337 PartiallyDownloadedBlock partial_block_with_extra(&pool);
338
339 BOOST_CHECK(partial_block.InitData(cmpctblock, extra_txn) == READ_STATUS_OK);
340 BOOST_CHECK( partial_block.IsTxAvailable(0));
341 BOOST_CHECK(!partial_block.IsTxAvailable(1));
342 BOOST_CHECK( partial_block.IsTxAvailable(2));
343
344 // Add an unrelated tx to extra_txn:
345 extra_txn[0] = non_block_tx;
346 // and a tx from the block that's not in the mempool:
347 extra_txn[1] = block.vtx[1];
348
349 BOOST_CHECK(partial_block_with_extra.InitData(cmpctblock, extra_txn) == READ_STATUS_OK);
350 BOOST_CHECK(partial_block_with_extra.IsTxAvailable(0));
351 // This transaction is now available via extra_txn:
352 BOOST_CHECK(partial_block_with_extra.IsTxAvailable(1));
353 BOOST_CHECK(partial_block_with_extra.IsTxAvailable(2));
354 }
355 }
356
357 BOOST_AUTO_TEST_CASE(TransactionsRequestSerializationTest) {
358 BlockTransactionsRequest req1;
359 req1.blockhash = m_rng.rand256();
360 req1.indexes.resize(4);
361 req1.indexes[0] = 0;
362 req1.indexes[1] = 1;
363 req1.indexes[2] = 3;
364 req1.indexes[3] = 4;
365
366 DataStream stream{};
367 stream << req1;
368
369 BlockTransactionsRequest req2;
370 stream >> req2;
371
372 BOOST_CHECK_EQUAL(req1.blockhash.ToString(), req2.blockhash.ToString());
373 BOOST_CHECK_EQUAL(req1.indexes.size(), req2.indexes.size());
374 BOOST_CHECK_EQUAL(req1.indexes[0], req2.indexes[0]);
375 BOOST_CHECK_EQUAL(req1.indexes[1], req2.indexes[1]);
376 BOOST_CHECK_EQUAL(req1.indexes[2], req2.indexes[2]);
377 BOOST_CHECK_EQUAL(req1.indexes[3], req2.indexes[3]);
378 }
379
380 BOOST_AUTO_TEST_CASE(TransactionsRequestDeserializationMaxTest) {
381 // Check that the highest legal index is decoded correctly
382 BlockTransactionsRequest req0;
383 req0.blockhash = m_rng.rand256();
384 req0.indexes.resize(1);
385 req0.indexes[0] = 0xffff;
386 DataStream stream{};
387 stream << req0;
388
389 BlockTransactionsRequest req1;
390 stream >> req1;
391 BOOST_CHECK_EQUAL(req0.indexes.size(), req1.indexes.size());
392 BOOST_CHECK_EQUAL(req0.indexes[0], req1.indexes[0]);
393 }
394
395 BOOST_AUTO_TEST_CASE(TransactionsRequestDeserializationOverflowTest) {
396 // Any set of index deltas that starts with N values that sum to (0x10000 - N)
397 // causes the edge-case overflow that was originally not checked for. Such
398 // a request cannot be created by serializing a real BlockTransactionsRequest
399 // due to the overflow, so here we'll serialize from raw deltas.
400 BlockTransactionsRequest req0;
401 req0.blockhash = m_rng.rand256();
402 req0.indexes.resize(3);
403 req0.indexes[0] = 0x7000;
404 req0.indexes[1] = 0x10000 - 0x7000 - 2;
405 req0.indexes[2] = 0;
406 DataStream stream{};
407 stream << req0.blockhash;
408 WriteCompactSize(stream, req0.indexes.size());
409 WriteCompactSize(stream, req0.indexes[0]);
410 WriteCompactSize(stream, req0.indexes[1]);
411 WriteCompactSize(stream, req0.indexes[2]);
412
413 BlockTransactionsRequest req1;
414 try {
415 stream >> req1;
416 // before patch: deserialize above succeeds and this check fails, demonstrating the overflow
417 BOOST_CHECK(req1.indexes[1] < req1.indexes[2]);
418 // this shouldn't be reachable before or after patch
419 BOOST_CHECK(0);
420 } catch(std::ios_base::failure &) {
421 // deserialize should fail
422 BOOST_CHECK(true); // Needed to suppress "Test case [...] did not check any assertions"
423 }
424 }
425
426 BOOST_AUTO_TEST_SUITE_END()
427