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