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