1 // Copyright (c) 2011-2020 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 
DoubleEquals(double a,double b,double epsilon)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 }
BOOST_FIXTURE_TEST_SUITE(blockchain_tests,BasicTestingSetup)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 
55 BOOST_AUTO_TEST_CASE(SimpleRoundTripTest)
56 {
BOOST_AUTO_TEST_CASE(get_difficulty_for_low_target)57     CTxMemPool pool;
58     TestMemPoolEntryHelper entry;
59     CBlock block(BuildBlockTestCase());
60 
61     LOCK2(cs_main, pool.cs);
BOOST_AUTO_TEST_CASE(get_difficulty_for_mid_target)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     {
BOOST_AUTO_TEST_CASE(get_difficulty_for_high_target)67         CBlockHeaderAndShortTxIDs shortIDs(block, true);
68 
69         CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
70         stream << shortIDs;
71 
BOOST_AUTO_TEST_CASE(get_difficulty_for_very_high_target)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 
119     explicit TestHeaderAndShortIDs(const CBlockHeaderAndShortTxIDs& orig) {
120         CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
121         stream << orig;
122         stream >> *this;
123     }
124     explicit TestHeaderAndShortIDs(const CBlock& block) :
125         TestHeaderAndShortIDs(CBlockHeaderAndShortTxIDs(block, true)) {}
126 
127     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     SERIALIZE_METHODS(TestHeaderAndShortIDs, obj) { READWRITE(obj.header, obj.nonce, Using<VectorFormatter<CustomUintFormatter<CBlockHeaderAndShortTxIDs::SHORTTXIDS_LENGTH>>>(obj.shorttxids), obj.prefilledtxn); }
136 };
137 
138 BOOST_AUTO_TEST_CASE(NonCoinbasePreforwardRTTest)
139 {
140     CTxMemPool pool;
141     TestMemPoolEntryHelper entry;
142     CBlock block(BuildBlockTestCase());
143 
144     LOCK2(cs_main, pool.cs);
145     pool.addUnchecked(entry.FromTx(block.vtx[2]));
146     BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2]->GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 0);
147 
148     uint256 txhash;
149 
150     // Test with pre-forwarding tx 1, but not coinbase
151     {
152         TestHeaderAndShortIDs shortIDs(block);
153         shortIDs.prefilledtxn.resize(1);
154         shortIDs.prefilledtxn[0] = {1, block.vtx[1]};
155         shortIDs.shorttxids.resize(2);
156         shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[0]->GetHash());
157         shortIDs.shorttxids[1] = shortIDs.GetShortID(block.vtx[2]->GetHash());
158 
159         CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
160         stream << shortIDs;
161 
162         CBlockHeaderAndShortTxIDs shortIDs2;
163         stream >> shortIDs2;
164 
165         PartiallyDownloadedBlock partialBlock(&pool);
166         BOOST_CHECK(partialBlock.InitData(shortIDs2, extra_txn) == READ_STATUS_OK);
167         BOOST_CHECK(!partialBlock.IsTxAvailable(0));
168         BOOST_CHECK( partialBlock.IsTxAvailable(1));
169         BOOST_CHECK( partialBlock.IsTxAvailable(2));
170 
171         BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2]->GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1); // +1 because of partialBlock
172 
173         CBlock block2;
174         {
175             PartiallyDownloadedBlock tmp = partialBlock;
176             BOOST_CHECK(partialBlock.FillBlock(block2, {}) == READ_STATUS_INVALID); // No transactions
177             partialBlock = tmp;
178         }
179 
180         // Wrong transaction
181         {
182             PartiallyDownloadedBlock tmp = partialBlock;
183             partialBlock.FillBlock(block2, {block.vtx[1]}); // Current implementation doesn't check txn here, but don't require that
184             partialBlock = tmp;
185         }
186         BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2]->GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 2); // +2 because of partialBlock and block2
187         bool mutated;
188         BOOST_CHECK(block.hashMerkleRoot != BlockMerkleRoot(block2, &mutated));
189 
190         CBlock block3;
191         PartiallyDownloadedBlock partialBlockCopy = partialBlock;
192         BOOST_CHECK(partialBlock.FillBlock(block3, {block.vtx[0]}) == READ_STATUS_OK);
193         BOOST_CHECK_EQUAL(block.GetHash().ToString(), block3.GetHash().ToString());
194         BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block3, &mutated).ToString());
195         BOOST_CHECK(!mutated);
196 
197         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
198 
199         txhash = block.vtx[2]->GetHash();
200         block.vtx.clear();
201         block2.vtx.clear();
202         block3.vtx.clear();
203         BOOST_CHECK_EQUAL(pool.mapTx.find(txhash)->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1 - 1); // + 1 because of partialBlock; -1 because of block.
204     }
205     BOOST_CHECK_EQUAL(pool.mapTx.find(txhash)->GetSharedTx().use_count(), SHARED_TX_OFFSET - 1); // -1 because of block
206 }
207 
208 BOOST_AUTO_TEST_CASE(SufficientPreforwardRTTest)
209 {
210     CTxMemPool pool;
211     TestMemPoolEntryHelper entry;
212     CBlock block(BuildBlockTestCase());
213 
214     LOCK2(cs_main, pool.cs);
215     pool.addUnchecked(entry.FromTx(block.vtx[1]));
216     BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[1]->GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 0);
217 
218     uint256 txhash;
219 
220     // Test with pre-forwarding coinbase + tx 2 with tx 1 in mempool
221     {
222         TestHeaderAndShortIDs shortIDs(block);
223         shortIDs.prefilledtxn.resize(2);
224         shortIDs.prefilledtxn[0] = {0, block.vtx[0]};
225         shortIDs.prefilledtxn[1] = {1, block.vtx[2]}; // id == 1 as it is 1 after index 1
226         shortIDs.shorttxids.resize(1);
227         shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[1]->GetHash());
228 
229         CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
230         stream << shortIDs;
231 
232         CBlockHeaderAndShortTxIDs shortIDs2;
233         stream >> shortIDs2;
234 
235         PartiallyDownloadedBlock partialBlock(&pool);
236         BOOST_CHECK(partialBlock.InitData(shortIDs2, extra_txn) == READ_STATUS_OK);
237         BOOST_CHECK( partialBlock.IsTxAvailable(0));
238         BOOST_CHECK( partialBlock.IsTxAvailable(1));
239         BOOST_CHECK( partialBlock.IsTxAvailable(2));
240 
241         BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[1]->GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1);
242 
243         CBlock block2;
244         PartiallyDownloadedBlock partialBlockCopy = partialBlock;
245         BOOST_CHECK(partialBlock.FillBlock(block2, {}) == READ_STATUS_OK);
246         BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString());
247         bool mutated;
248         BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString());
249         BOOST_CHECK(!mutated);
250 
251         txhash = block.vtx[1]->GetHash();
252         block.vtx.clear();
253         block2.vtx.clear();
254         BOOST_CHECK_EQUAL(pool.mapTx.find(txhash)->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1 - 1); // + 1 because of partialBlock; -1 because of block.
255     }
256     BOOST_CHECK_EQUAL(pool.mapTx.find(txhash)->GetSharedTx().use_count(), SHARED_TX_OFFSET - 1); // -1 because of block
257 }
258 
259 BOOST_AUTO_TEST_CASE(EmptyBlockRoundTripTest)
260 {
261     CTxMemPool pool;
262     CMutableTransaction coinbase;
263     coinbase.vin.resize(1);
264     coinbase.vin[0].scriptSig.resize(10);
265     coinbase.vout.resize(1);
266     coinbase.vout[0].nValue = 42;
267 
268     CBlock block;
269     block.vtx.resize(1);
270     block.vtx[0] = MakeTransactionRef(std::move(coinbase));
271     block.nVersion = 42;
272     block.hashPrevBlock = InsecureRand256();
273     block.nBits = 0x207fffff;
274 
275     bool mutated;
276     block.hashMerkleRoot = BlockMerkleRoot(block, &mutated);
277     assert(!mutated);
278     while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce;
279 
280     // Test simple header round-trip with only coinbase
281     {
282         CBlockHeaderAndShortTxIDs shortIDs(block, false);
283 
284         CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
285         stream << shortIDs;
286 
287         CBlockHeaderAndShortTxIDs shortIDs2;
288         stream >> shortIDs2;
289 
290         PartiallyDownloadedBlock partialBlock(&pool);
291         BOOST_CHECK(partialBlock.InitData(shortIDs2, extra_txn) == READ_STATUS_OK);
292         BOOST_CHECK(partialBlock.IsTxAvailable(0));
293 
294         CBlock block2;
295         std::vector<CTransactionRef> vtx_missing;
296         BOOST_CHECK(partialBlock.FillBlock(block2, vtx_missing) == READ_STATUS_OK);
297         BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString());
298         BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString());
299         BOOST_CHECK(!mutated);
300     }
301 }
302 
303 BOOST_AUTO_TEST_CASE(TransactionsRequestSerializationTest) {
304     BlockTransactionsRequest req1;
305     req1.blockhash = InsecureRand256();
306     req1.indexes.resize(4);
307     req1.indexes[0] = 0;
308     req1.indexes[1] = 1;
309     req1.indexes[2] = 3;
310     req1.indexes[3] = 4;
311 
312     CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
313     stream << req1;
314 
315     BlockTransactionsRequest req2;
316     stream >> req2;
317 
318     BOOST_CHECK_EQUAL(req1.blockhash.ToString(), req2.blockhash.ToString());
319     BOOST_CHECK_EQUAL(req1.indexes.size(), req2.indexes.size());
320     BOOST_CHECK_EQUAL(req1.indexes[0], req2.indexes[0]);
321     BOOST_CHECK_EQUAL(req1.indexes[1], req2.indexes[1]);
322     BOOST_CHECK_EQUAL(req1.indexes[2], req2.indexes[2]);
323     BOOST_CHECK_EQUAL(req1.indexes[3], req2.indexes[3]);
324 }
325 
326 BOOST_AUTO_TEST_CASE(TransactionsRequestDeserializationMaxTest) {
327     // Check that the highest legal index is decoded correctly
328     BlockTransactionsRequest req0;
329     req0.blockhash = InsecureRand256();
330     req0.indexes.resize(1);
331     req0.indexes[0] = 0xffff;
332     CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
333     stream << req0;
334 
335     BlockTransactionsRequest req1;
336     stream >> req1;
337     BOOST_CHECK_EQUAL(req0.indexes.size(), req1.indexes.size());
338     BOOST_CHECK_EQUAL(req0.indexes[0], req1.indexes[0]);
339 }
340 
341 BOOST_AUTO_TEST_CASE(TransactionsRequestDeserializationOverflowTest) {
342     // Any set of index deltas that starts with N values that sum to (0x10000 - N)
343     // causes the edge-case overflow that was originally not checked for. Such
344     // a request cannot be created by serializing a real BlockTransactionsRequest
345     // due to the overflow, so here we'll serialize from raw deltas.
346     BlockTransactionsRequest req0;
347     req0.blockhash = InsecureRand256();
348     req0.indexes.resize(3);
349     req0.indexes[0] = 0x7000;
350     req0.indexes[1] = 0x10000 - 0x7000 - 2;
351     req0.indexes[2] = 0;
352     CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
353     stream << req0.blockhash;
354     WriteCompactSize(stream, req0.indexes.size());
355     WriteCompactSize(stream, req0.indexes[0]);
356     WriteCompactSize(stream, req0.indexes[1]);
357     WriteCompactSize(stream, req0.indexes[2]);
358 
359     BlockTransactionsRequest req1;
360     try {
361         stream >> req1;
362         // before patch: deserialize above succeeds and this check fails, demonstrating the overflow
363         BOOST_CHECK(req1.indexes[1] < req1.indexes[2]);
364         // this shouldn't be reachable before or after patch
365         BOOST_CHECK(0);
366     } catch(std::ios_base::failure &) {
367         // deserialize should fail
368         BOOST_CHECK(true); // Needed to suppress "Test case [...] did not check any assertions"
369     }
370 }
371 
372 BOOST_AUTO_TEST_SUITE_END()
373