1 // Copyright (c) 2018-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 <boost/test/unit_test.hpp>
6
7 #include <chainparams.h>
8 #include <consensus/merkle.h>
9 #include <consensus/validation.h>
10 #include <miner.h>
11 #include <pow.h>
12 #include <random.h>
13 #include <script/standard.h>
14 #include <test/util/script.h>
15 #include <test/util/setup_common.h>
16 #include <util/time.h>
17 #include <validation.h>
18 #include <validationinterface.h>
19
20 #include <thread>
21
22 namespace validation_block_tests {
23 struct MinerTestingSetup : public RegTestingSetup {
24 std::shared_ptr<CBlock> Block(const uint256& prev_hash);
25 std::shared_ptr<const CBlock> GoodBlock(const uint256& prev_hash);
26 std::shared_ptr<const CBlock> BadBlock(const uint256& prev_hash);
27 std::shared_ptr<CBlock> FinalizeBlock(std::shared_ptr<CBlock> pblock);
28 void BuildChain(const uint256& root, int height, const unsigned int invalid_rate, const unsigned int branch_rate, const unsigned int max_size, std::vector<std::shared_ptr<const CBlock>>& blocks);
29 };
30 } // namespace validation_block_tests
31
32 BOOST_FIXTURE_TEST_SUITE(validation_block_tests, MinerTestingSetup)
33
34 struct TestSubscriber final : public CValidationInterface {
35 uint256 m_expected_tip;
36
TestSubscriberTestSubscriber37 explicit TestSubscriber(uint256 tip) : m_expected_tip(tip) {}
38
UpdatedBlockTipTestSubscriber39 void UpdatedBlockTip(const CBlockIndex* pindexNew, const CBlockIndex* pindexFork, bool fInitialDownload) override
40 {
41 BOOST_CHECK_EQUAL(m_expected_tip, pindexNew->GetBlockHash());
42 }
43
BlockConnectedTestSubscriber44 void BlockConnected(const std::shared_ptr<const CBlock>& block, const CBlockIndex* pindex) override
45 {
46 BOOST_CHECK_EQUAL(m_expected_tip, block->hashPrevBlock);
47 BOOST_CHECK_EQUAL(m_expected_tip, pindex->pprev->GetBlockHash());
48
49 m_expected_tip = block->GetHash();
50 }
51
BlockDisconnectedTestSubscriber52 void BlockDisconnected(const std::shared_ptr<const CBlock>& block, const CBlockIndex* pindex) override
53 {
54 BOOST_CHECK_EQUAL(m_expected_tip, block->GetHash());
55 BOOST_CHECK_EQUAL(m_expected_tip, pindex->GetBlockHash());
56
57 m_expected_tip = block->hashPrevBlock;
58 }
59 };
60
Block(const uint256 & prev_hash)61 std::shared_ptr<CBlock> MinerTestingSetup::Block(const uint256& prev_hash)
62 {
63 static int i = 0;
64 static uint64_t time = Params().GenesisBlock().nTime;
65
66 auto ptemplate = BlockAssembler(m_node.chainman->ActiveChainstate(), *m_node.mempool, Params()).CreateNewBlock(CScript{} << i++ << OP_TRUE);
67 auto pblock = std::make_shared<CBlock>(ptemplate->block);
68 pblock->hashPrevBlock = prev_hash;
69 pblock->nTime = ++time;
70
71 // Make the coinbase transaction with two outputs:
72 // One zero-value one that has a unique pubkey to make sure that blocks at the same height can have a different hash
73 // Another one that has the coinbase reward in a P2WSH with OP_TRUE as witness program to make it easy to spend
74 CMutableTransaction txCoinbase(*pblock->vtx[0]);
75 txCoinbase.vout.resize(2);
76 txCoinbase.vout[1].scriptPubKey = P2WSH_OP_TRUE;
77 txCoinbase.vout[1].nValue = txCoinbase.vout[0].nValue;
78 txCoinbase.vout[0].nValue = 0;
79 txCoinbase.vin[0].scriptWitness.SetNull();
80 pblock->vtx[0] = MakeTransactionRef(std::move(txCoinbase));
81
82 return pblock;
83 }
84
FinalizeBlock(std::shared_ptr<CBlock> pblock)85 std::shared_ptr<CBlock> MinerTestingSetup::FinalizeBlock(std::shared_ptr<CBlock> pblock)
86 {
87 LOCK(cs_main); // For m_node.chainman->m_blockman.LookupBlockIndex
88 GenerateCoinbaseCommitment(*pblock, m_node.chainman->m_blockman.LookupBlockIndex(pblock->hashPrevBlock), Params().GetConsensus());
89
90 pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
91
92 while (!CheckProofOfWork(pblock->GetHash(), pblock->nBits, Params().GetConsensus())) {
93 ++(pblock->nNonce);
94 }
95
96 return pblock;
97 }
98
99 // construct a valid block
GoodBlock(const uint256 & prev_hash)100 std::shared_ptr<const CBlock> MinerTestingSetup::GoodBlock(const uint256& prev_hash)
101 {
102 return FinalizeBlock(Block(prev_hash));
103 }
104
105 // construct an invalid block (but with a valid header)
BadBlock(const uint256 & prev_hash)106 std::shared_ptr<const CBlock> MinerTestingSetup::BadBlock(const uint256& prev_hash)
107 {
108 auto pblock = Block(prev_hash);
109
110 CMutableTransaction coinbase_spend;
111 coinbase_spend.vin.push_back(CTxIn(COutPoint(pblock->vtx[0]->GetHash(), 0), CScript(), 0));
112 coinbase_spend.vout.push_back(pblock->vtx[0]->vout[0]);
113
114 CTransactionRef tx = MakeTransactionRef(coinbase_spend);
115 pblock->vtx.push_back(tx);
116
117 auto ret = FinalizeBlock(pblock);
118 return ret;
119 }
120
BuildChain(const uint256 & root,int height,const unsigned int invalid_rate,const unsigned int branch_rate,const unsigned int max_size,std::vector<std::shared_ptr<const CBlock>> & blocks)121 void MinerTestingSetup::BuildChain(const uint256& root, int height, const unsigned int invalid_rate, const unsigned int branch_rate, const unsigned int max_size, std::vector<std::shared_ptr<const CBlock>>& blocks)
122 {
123 if (height <= 0 || blocks.size() >= max_size) return;
124
125 bool gen_invalid = InsecureRandRange(100) < invalid_rate;
126 bool gen_fork = InsecureRandRange(100) < branch_rate;
127
128 const std::shared_ptr<const CBlock> pblock = gen_invalid ? BadBlock(root) : GoodBlock(root);
129 blocks.push_back(pblock);
130 if (!gen_invalid) {
131 BuildChain(pblock->GetHash(), height - 1, invalid_rate, branch_rate, max_size, blocks);
132 }
133
134 if (gen_fork) {
135 blocks.push_back(GoodBlock(root));
136 BuildChain(blocks.back()->GetHash(), height - 1, invalid_rate, branch_rate, max_size, blocks);
137 }
138 }
139
BOOST_AUTO_TEST_CASE(processnewblock_signals_ordering)140 BOOST_AUTO_TEST_CASE(processnewblock_signals_ordering)
141 {
142 // build a large-ish chain that's likely to have some forks
143 std::vector<std::shared_ptr<const CBlock>> blocks;
144 while (blocks.size() < 50) {
145 blocks.clear();
146 BuildChain(Params().GenesisBlock().GetHash(), 100, 15, 10, 500, blocks);
147 }
148
149 bool ignored;
150 BlockValidationState state;
151 std::vector<CBlockHeader> headers;
152 std::transform(blocks.begin(), blocks.end(), std::back_inserter(headers), [](std::shared_ptr<const CBlock> b) { return b->GetBlockHeader(); });
153
154 // Process all the headers so we understand the toplogy of the chain
155 BOOST_CHECK(Assert(m_node.chainman)->ProcessNewBlockHeaders(headers, state, Params()));
156
157 // Connect the genesis block and drain any outstanding events
158 BOOST_CHECK(Assert(m_node.chainman)->ProcessNewBlock(Params(), std::make_shared<CBlock>(Params().GenesisBlock()), true, &ignored));
159 SyncWithValidationInterfaceQueue();
160
161 // subscribe to events (this subscriber will validate event ordering)
162 const CBlockIndex* initial_tip = nullptr;
163 {
164 LOCK(cs_main);
165 initial_tip = m_node.chainman->ActiveChain().Tip();
166 }
167 auto sub = std::make_shared<TestSubscriber>(initial_tip->GetBlockHash());
168 RegisterSharedValidationInterface(sub);
169
170 // create a bunch of threads that repeatedly process a block generated above at random
171 // this will create parallelism and randomness inside validation - the ValidationInterface
172 // will subscribe to events generated during block validation and assert on ordering invariance
173 std::vector<std::thread> threads;
174 for (int i = 0; i < 10; i++) {
175 threads.emplace_back([&]() {
176 bool ignored;
177 FastRandomContext insecure;
178 for (int i = 0; i < 1000; i++) {
179 auto block = blocks[insecure.randrange(blocks.size() - 1)];
180 Assert(m_node.chainman)->ProcessNewBlock(Params(), block, true, &ignored);
181 }
182
183 // to make sure that eventually we process the full chain - do it here
184 for (auto block : blocks) {
185 if (block->vtx.size() == 1) {
186 bool processed = Assert(m_node.chainman)->ProcessNewBlock(Params(), block, true, &ignored);
187 assert(processed);
188 }
189 }
190 });
191 }
192
193 for (auto& t : threads) {
194 t.join();
195 }
196 SyncWithValidationInterfaceQueue();
197
198 UnregisterSharedValidationInterface(sub);
199
200 LOCK(cs_main);
201 BOOST_CHECK_EQUAL(sub->m_expected_tip, m_node.chainman->ActiveChain().Tip()->GetBlockHash());
202 }
203
204 /**
205 * Test that mempool updates happen atomically with reorgs.
206 *
207 * This prevents RPC clients, among others, from retrieving immediately-out-of-date mempool data
208 * during large reorgs.
209 *
210 * The test verifies this by creating a chain of `num_txs` blocks, matures their coinbases, and then
211 * submits txns spending from their coinbase to the mempool. A fork chain is then processed,
212 * invalidating the txns and evicting them from the mempool.
213 *
214 * We verify that the mempool updates atomically by polling it continuously
215 * from another thread during the reorg and checking that its size only changes
216 * once. The size changing exactly once indicates that the polling thread's
217 * view of the mempool is either consistent with the chain state before reorg,
218 * or consistent with the chain state after the reorg, and not just consistent
219 * with some intermediate state during the reorg.
220 */
BOOST_AUTO_TEST_CASE(mempool_locks_reorg)221 BOOST_AUTO_TEST_CASE(mempool_locks_reorg)
222 {
223 bool ignored;
224 auto ProcessBlock = [&](std::shared_ptr<const CBlock> block) -> bool {
225 return Assert(m_node.chainman)->ProcessNewBlock(Params(), block, /* fForceProcessing */ true, /* fNewBlock */ &ignored);
226 };
227
228 // Process all mined blocks
229 BOOST_REQUIRE(ProcessBlock(std::make_shared<CBlock>(Params().GenesisBlock())));
230 auto last_mined = GoodBlock(Params().GenesisBlock().GetHash());
231 BOOST_REQUIRE(ProcessBlock(last_mined));
232
233 // Run the test multiple times
234 for (int test_runs = 3; test_runs > 0; --test_runs) {
235 BOOST_CHECK_EQUAL(last_mined->GetHash(), m_node.chainman->ActiveChain().Tip()->GetBlockHash());
236
237 // Later on split from here
238 const uint256 split_hash{last_mined->hashPrevBlock};
239
240 // Create a bunch of transactions to spend the miner rewards of the
241 // most recent blocks
242 std::vector<CTransactionRef> txs;
243 for (int num_txs = 22; num_txs > 0; --num_txs) {
244 CMutableTransaction mtx;
245 mtx.vin.push_back(CTxIn{COutPoint{last_mined->vtx[0]->GetHash(), 1}, CScript{}});
246 mtx.vin[0].scriptWitness.stack.push_back(WITNESS_STACK_ELEM_OP_TRUE);
247 mtx.vout.push_back(last_mined->vtx[0]->vout[1]);
248 mtx.vout[0].nValue -= 1000;
249 txs.push_back(MakeTransactionRef(mtx));
250
251 last_mined = GoodBlock(last_mined->GetHash());
252 BOOST_REQUIRE(ProcessBlock(last_mined));
253 }
254
255 // Mature the inputs of the txs
256 for (int j = COINBASE_MATURITY; j > 0; --j) {
257 last_mined = GoodBlock(last_mined->GetHash());
258 BOOST_REQUIRE(ProcessBlock(last_mined));
259 }
260
261 // Mine a reorg (and hold it back) before adding the txs to the mempool
262 const uint256 tip_init{last_mined->GetHash()};
263
264 std::vector<std::shared_ptr<const CBlock>> reorg;
265 last_mined = GoodBlock(split_hash);
266 reorg.push_back(last_mined);
267 for (size_t j = COINBASE_MATURITY + txs.size() + 1; j > 0; --j) {
268 last_mined = GoodBlock(last_mined->GetHash());
269 reorg.push_back(last_mined);
270 }
271
272 // Add the txs to the tx pool
273 {
274 LOCK(cs_main);
275 for (const auto& tx : txs) {
276 const MempoolAcceptResult result = AcceptToMemoryPool(m_node.chainman->ActiveChainstate(), *m_node.mempool, tx, false /* bypass_limits */);
277 BOOST_REQUIRE(result.m_result_type == MempoolAcceptResult::ResultType::VALID);
278 }
279 }
280
281 // Check that all txs are in the pool
282 {
283 LOCK(m_node.mempool->cs);
284 BOOST_CHECK_EQUAL(m_node.mempool->mapTx.size(), txs.size());
285 }
286
287 // Run a thread that simulates an RPC caller that is polling while
288 // validation is doing a reorg
289 std::thread rpc_thread{[&]() {
290 // This thread is checking that the mempool either contains all of
291 // the transactions invalidated by the reorg, or none of them, and
292 // not some intermediate amount.
293 while (true) {
294 LOCK(m_node.mempool->cs);
295 if (m_node.mempool->mapTx.size() == 0) {
296 // We are done with the reorg
297 break;
298 }
299 // Internally, we might be in the middle of the reorg, but
300 // externally the reorg to the most-proof-of-work chain should
301 // be atomic. So the caller assumes that the returned mempool
302 // is consistent. That is, it has all txs that were there
303 // before the reorg.
304 assert(m_node.mempool->mapTx.size() == txs.size());
305 continue;
306 }
307 LOCK(cs_main);
308 // We are done with the reorg, so the tip must have changed
309 assert(tip_init != m_node.chainman->ActiveChain().Tip()->GetBlockHash());
310 }};
311
312 // Submit the reorg in this thread to invalidate and remove the txs from the tx pool
313 for (const auto& b : reorg) {
314 ProcessBlock(b);
315 }
316 // Check that the reorg was eventually successful
317 BOOST_CHECK_EQUAL(last_mined->GetHash(), m_node.chainman->ActiveChain().Tip()->GetBlockHash());
318
319 // We can join the other thread, which returns when the reorg was successful
320 rpc_thread.join();
321 }
322 }
323
BOOST_AUTO_TEST_CASE(witness_commitment_index)324 BOOST_AUTO_TEST_CASE(witness_commitment_index)
325 {
326 CScript pubKey;
327 pubKey << 1 << OP_TRUE;
328 auto ptemplate = BlockAssembler(m_node.chainman->ActiveChainstate(), *m_node.mempool, Params()).CreateNewBlock(pubKey);
329 CBlock pblock = ptemplate->block;
330
331 CTxOut witness;
332 witness.scriptPubKey.resize(MINIMUM_WITNESS_COMMITMENT);
333 witness.scriptPubKey[0] = OP_RETURN;
334 witness.scriptPubKey[1] = 0x24;
335 witness.scriptPubKey[2] = 0xaa;
336 witness.scriptPubKey[3] = 0x21;
337 witness.scriptPubKey[4] = 0xa9;
338 witness.scriptPubKey[5] = 0xed;
339
340 // A witness larger than the minimum size is still valid
341 CTxOut min_plus_one = witness;
342 min_plus_one.scriptPubKey.resize(MINIMUM_WITNESS_COMMITMENT + 1);
343
344 CTxOut invalid = witness;
345 invalid.scriptPubKey[0] = OP_VERIFY;
346
347 CMutableTransaction txCoinbase(*pblock.vtx[0]);
348 txCoinbase.vout.resize(4);
349 txCoinbase.vout[0] = witness;
350 txCoinbase.vout[1] = witness;
351 txCoinbase.vout[2] = min_plus_one;
352 txCoinbase.vout[3] = invalid;
353 pblock.vtx[0] = MakeTransactionRef(std::move(txCoinbase));
354
355 BOOST_CHECK_EQUAL(GetWitnessCommitmentIndex(pblock), 2);
356 }
357 BOOST_AUTO_TEST_SUITE_END()
358