block_index_tree.cpp raw
1 // Copyright (c) 2020-present 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
6 #include <chain.h>
7 #include <chainparams.h>
8 #include <flatfile.h>
9 #include <primitives/block.h>
10 #include <primitives/transaction.h>
11 #include <test/fuzz/FuzzedDataProvider.h>
12 #include <test/fuzz/fuzz.h>
13 #include <test/fuzz/util.h>
14 #include <test/util/setup_common.h>
15 #include <test/util/time.h>
16 #include <test/util/validation.h>
17 #include <validation.h>
18
19 #include <ranges>
20 #include <vector>
21
22 const TestingSetup* g_setup;
23
24 CBlockHeader ConsumeBlockHeader(FuzzedDataProvider& provider, uint256 prev_hash, int& nonce_counter)
25 {
26 CBlockHeader header;
27 header.nVersion = provider.ConsumeIntegral<decltype(header.nVersion)>();
28 header.hashPrevBlock = prev_hash;
29 header.hashMerkleRoot = uint256{}; // never used
30 header.nTime = provider.ConsumeIntegral<decltype(header.nTime)>();
31 header.nBits = Params().GenesisBlock().nBits; // not fuzzed because not used (validation is mocked).
32 header.nNonce = nonce_counter++; // prevent creating multiple block headers with the same hash
33 return header;
34 }
35
36 void initialize_block_index_tree()
37 {
38 static const auto testing_setup = MakeNoLogFileContext<const TestingSetup>();
39 g_setup = testing_setup.get();
40 }
41
42 FUZZ_TARGET(block_index_tree, .init = initialize_block_index_tree)
43 {
44 FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
45 FakeNodeClock clock{ConsumeTime(fuzzed_data_provider)};
46 auto& chainman = static_cast<TestChainstateManager&>(*g_setup->m_node.chainman);
47 auto& blockman = static_cast<TestBlockManager&>(chainman.m_blockman);
48 CBlockIndex* genesis = chainman.ActiveChainstate().m_chain[0];
49 int nonce_counter = 0;
50 std::vector<CBlockIndex*> blocks;
51 blocks.push_back(genesis);
52 bool abort_run{false};
53
54 std::vector<CBlockIndex*> pruned_blocks;
55
56 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 1000)
57 {
58 if (abort_run) break;
59 CallOneOf(
60 fuzzed_data_provider,
61 [&] {
62 // Receive a header building on an existing valid one. This assumes headers are valid, so PoW is not relevant here.
63 LOCK(cs_main);
64 CBlockIndex* prev_block = PickValue(fuzzed_data_provider, blocks);
65 if (!(prev_block->nStatus & BLOCK_FAILED_VALID)) {
66 CBlockHeader header = ConsumeBlockHeader(fuzzed_data_provider, prev_block->GetBlockHash(), nonce_counter);
67 CBlockIndex* index = blockman.AddToBlockIndex(header, chainman.m_best_header);
68 assert(index->nStatus & BLOCK_VALID_TREE);
69 assert(index->pprev == prev_block);
70 blocks.push_back(index);
71 }
72 },
73 [&] {
74 // Receive a full block (valid or invalid) for an existing header, but don't attempt to connect it yet
75 LOCK(cs_main);
76 CBlockIndex* index = PickValue(fuzzed_data_provider, blocks);
77 // Must be new to us and not known to be invalid (e.g. because of an invalid ancestor).
78 if (index->nTx == 0 && !(index->nStatus & BLOCK_FAILED_VALID)) {
79 if (fuzzed_data_provider.ConsumeBool()) { // Invalid
80 BlockValidationState state;
81 state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, "consensus-invalid");
82 chainman.InvalidBlockFound(index, state);
83 } else {
84 size_t nTx = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 1000);
85 CBlock block; // Dummy block, so that ReceivedBlockTransactions can infer a nTx value.
86 block.vtx = std::vector<CTransactionRef>(nTx);
87 FlatFilePos pos(0, fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 1000));
88 chainman.ReceivedBlockTransactions(block, index, pos);
89 assert(index->nStatus & BLOCK_VALID_TRANSACTIONS);
90 assert(index->nStatus & BLOCK_HAVE_DATA);
91 }
92 }
93 },
94 [&] {
95 // Simplified ActivateBestChain(): Try to move to a chain with more work - with the possibility of finding blocks to be invalid on the way
96 LOCK(cs_main);
97 auto& chain = chainman.ActiveChain();
98 CBlockIndex* old_tip = chain.Tip();
99 assert(old_tip);
100 do {
101 CBlockIndex* best_tip = chainman.FindMostWorkChain();
102 assert(best_tip); // Should at least return current tip
103 if (best_tip == chain.Tip()) break; // Nothing to do
104 // Rewind chain to forking point
105 const CBlockIndex* fork = chain.FindFork(*best_tip);
106 // If we can't go back to the fork point due to pruned data, abort this run. In reality, a pruned node would also currently just crash in this scenario.
107 // This is very unlikely to happen due to the minimum pruning threshold of 550MiB.
108 CBlockIndex* it = chain.Tip();
109 while (it && it->nHeight != fork->nHeight) {
110 if (!(it->nStatus & BLOCK_HAVE_UNDO)) {
111 assert(blockman.m_have_pruned);
112 abort_run = true;
113 return;
114 }
115 it = it->pprev;
116 }
117 chain.SetTip(*chain[fork->nHeight]);
118
119 // Prepare new blocks to connect
120 std::vector<CBlockIndex*> to_connect;
121 it = best_tip;
122 while (it && it->nHeight != fork->nHeight) {
123 to_connect.push_back(it);
124 it = it->pprev;
125 }
126 // Connect blocks, possibly fail
127 for (CBlockIndex* block : to_connect | std::views::reverse) {
128 assert(!(block->nStatus & BLOCK_FAILED_VALID));
129 assert(block->nStatus & BLOCK_HAVE_DATA);
130 if (!block->IsValid(BLOCK_VALID_SCRIPTS)) {
131 if (fuzzed_data_provider.ConsumeBool()) { // Invalid
132 BlockValidationState state;
133 state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, "consensus-invalid");
134 chainman.InvalidBlockFound(block, state);
135 // This results in duplicate calls to InvalidChainFound, but mirrors the behavior in validation
136 chainman.InvalidChainFound(to_connect.front());
137 break;
138 } else {
139 block->RaiseValidity(BLOCK_VALID_SCRIPTS);
140 block->nStatus |= BLOCK_HAVE_UNDO;
141 }
142 }
143 chain.SetTip(*block);
144 chainman.ActiveChainstate().PruneBlockIndexCandidates();
145 // ActivateBestChainStep may release cs_main / not connect all blocks in one go - but only if we have at least as much chain work as we had at the start.
146 if (block->nChainWork > old_tip->nChainWork && fuzzed_data_provider.ConsumeBool()) {
147 break;
148 }
149 }
150 } while (node::CBlockIndexWorkComparator()(chain.Tip(), old_tip));
151 assert(chain.Tip()->nChainWork >= old_tip->nChainWork);
152 },
153 [&] {
154 // Prune chain - dealing with block files is beyond the scope of this test, so just prune random blocks, making no assumptions
155 // about what blocks are pruned together because they are in the same block file.
156 // Also don't prune blocks outside of the chain for now - this would make the fuzzer crash because of the problem described in
157 // https://github.com/bitcoin/bitcoin/issues/31512
158 LOCK(cs_main);
159 auto& chain = chainman.ActiveChain();
160 int prune_height = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, chain.Height());
161 CBlockIndex* prune_block{chain[prune_height]};
162 if (prune_block != chain.Tip() && (prune_block->nStatus & BLOCK_HAVE_DATA)) {
163 blockman.m_have_pruned = true;
164 prune_block->nStatus &= ~BLOCK_HAVE_DATA;
165 prune_block->nStatus &= ~BLOCK_HAVE_UNDO;
166 prune_block->nFile = 0;
167 prune_block->nDataPos = 0;
168 prune_block->nUndoPos = 0;
169 auto range = blockman.m_blocks_unlinked.equal_range(prune_block->pprev);
170 while (range.first != range.second) {
171 std::multimap<CBlockIndex*, CBlockIndex*>::iterator _it = range.first;
172 range.first++;
173 if (_it->second == prune_block) {
174 blockman.m_blocks_unlinked.erase(_it);
175 }
176 }
177 pruned_blocks.push_back(prune_block);
178 }
179 },
180 [&] {
181 // Download a previously pruned block
182 LOCK(cs_main);
183 size_t num_pruned = pruned_blocks.size();
184 if (num_pruned == 0) return;
185 size_t i = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, num_pruned - 1);
186 CBlockIndex* index = pruned_blocks[i];
187 assert(!(index->nStatus & BLOCK_HAVE_DATA));
188 CBlock block;
189 block.vtx = std::vector<CTransactionRef>(index->nTx); // Set the number of tx to the prior value.
190 FlatFilePos pos(0, fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 1000));
191 chainman.ReceivedBlockTransactions(block, index, pos);
192 assert(index->nStatus & BLOCK_VALID_TRANSACTIONS);
193 assert(index->nStatus & BLOCK_HAVE_DATA);
194 pruned_blocks.erase(pruned_blocks.begin() + i);
195 });
196 }
197 if (!abort_run) {
198 chainman.CheckBlockIndex();
199 }
200
201 // clean up global state changed by last iteration and prepare for next iteration
202 {
203 LOCK(cs_main);
204 genesis->nStatus |= BLOCK_HAVE_DATA;
205 genesis->nStatus |= BLOCK_HAVE_UNDO;
206 chainman.m_best_header = genesis;
207 chainman.ResetBestInvalid();
208 chainman.nBlockSequenceId = 2;
209 chainman.ActiveChain().SetTip(*genesis);
210 chainman.ActiveChainstate().setBlockIndexCandidates.clear();
211 chainman.m_cached_is_ibd = true;
212 blockman.m_blocks_unlinked.clear();
213 blockman.m_have_pruned = false;
214 blockman.CleanupForFuzzing();
215 // Delete all blocks but Genesis from block index
216 uint256 genesis_hash = genesis->GetBlockHash();
217 for (auto it = blockman.m_block_index.begin(); it != blockman.m_block_index.end();) {
218 if (it->first != genesis_hash) {
219 it = blockman.m_block_index.erase(it);
220 } else {
221 ++it;
222 }
223 }
224 chainman.ActiveChainstate().TryAddBlockIndexCandidate(genesis);
225 assert(blockman.m_block_index.size() == 1);
226 assert(chainman.ActiveChainstate().setBlockIndexCandidates.size() == 1);
227 assert(chainman.ActiveChain().Height() == 0);
228 }
229 }
230