block_index_tree.cpp
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 NodeClockContext clock_ctx{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 }