fuzz: Add fuzz target for block index tree and related validation events

mzumsande commented at 5:53 pm on December 18, 2024: contributor

This adds a fuzz target for the block index and various events in validation that interact with it.

It can create arbitrary tree-like structure of block indexes, simulating (so far) the following events:

Adding a header
Receiving the full block (may be valid or not)
ActivateBestChain() - Reorging the chain to a new chain tip (possibly encountering invalid blocks on the way)
Pruning

It might be interesting / possible to extend this to more events, such as dealing with more than one chainstate (assumeutxo).

The test skips all actual validation of header/ block / transaction data by just simulating the outcome, and also doesn’t interact with the data directory. The main goal is to ensure the integrity of the block index tree in all fuzzed constellations, by calling CheckBlockIndex() at the end of each iteration.

Compared to #29158 this approach has a more limited scope (by skipping all actual validation), but it is fast - it doesn’t do a full init sequence on each iteration, but “cleans up” after itself by resetting the global validation state after each iteration. One downside of this approach is that it needs to have public access to a few members / functions in Chainstate(Manager) / BlockManager.

Looking for conceptual feedback for now, so will leave as draft for a bit - this was helpful while working on #31405 and found the problem described in #31512.

DrahtBot commented at 5:53 pm on December 18, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31533.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	ismaelsadeeq, Crypt-iQ

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#32427 ((RFC) kernel: Replace leveldb-based BlockTreeDB with flat-file based store by TheCharlatan)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

LLM Linter (✨ experimental)

Possible typos and grammar issues:

“at least much chain work as we had at the start” -> “at least as much chain work as we had at the start” [missing “as” after “at least”]

drahtbot_id_4_m

DrahtBot added the label Tests on Dec 18, 2024

mzumsande marked this as a draft on Dec 18, 2024

DrahtBot added the label Needs rebase on Jan 22, 2025

mzumsande force-pushed on Jan 23, 2025

DrahtBot removed the label Needs rebase on Jan 23, 2025

in src/test/fuzz/block_index_tree.cpp:59 in 98d68e00c2 outdated

51+        CallOneOf(
52+            fuzzed_data_provider,
53+            [&] {
54+                // Receive a header building on an existing one. This assumes headers are valid, so PoW is not relevant here.
55+                LOCK(cs_main);
56+                CBlockIndex* prev_block = PickValue(fuzzed_data_provider, blocks);

stratospher commented at 4:46 am on February 5, 2025:

98d68e0: shouldn’t we have a blocks.push_back(index) in this block of code?

right now, only genesis block gets inserted into std::vector<CBlockIndex*> blocks and we don’t enter into the interesting test cases.

mzumsande commented at 8:47 pm on February 5, 2025:

Good point - fixed, and also cleared blocks in the end! While working /testing this branch I directly did picked a value from blockman.m_block_index and introduced blocks right before pushing because picking from a std::unordered_map mad runs non-deterministic.

mzumsande force-pushed on Feb 5, 2025

DrahtBot added the label Needs rebase on Feb 5, 2025

mzumsande force-pushed on Feb 6, 2025

DrahtBot removed the label Needs rebase on Feb 6, 2025

in src/test/fuzz/block_index_tree.cpp:98 in 7dd613b268 outdated

90+                CBlockIndex* old_tip = chain.Tip();
91+                assert(old_tip);
92+                do {
93+                    CBlockIndex* best_tip = chainman.ActiveChainstate().FindMostWorkChain();
94+                    assert(best_tip);                   // Should at least return current tip
95+                    if (best_tip == chain.Tip()) break; // Nothing to do

stratospher commented at 7:30 pm on March 3, 2025:

~~looks like we always break here since old_tip, best_tip and chain.Tip() is the genesis block initially.~~ EDIT: oops no problem here, please mark as resolved! best_tip can be block at any height n. I got confused when I saw logs with lots of prune height = 0.

mzumsande force-pushed on Apr 4, 2025

mzumsande force-pushed on Apr 7, 2025

DrahtBot added the label CI failed on May 16, 2025

DrahtBot removed the label CI failed on May 17, 2025

DrahtBot added the label CI failed on Jun 15, 2025

DrahtBot commented at 3:55 pm on June 15, 2025: contributor

🚧 At least one of the CI tasks failed. Task tidy: https://github.com/bitcoin/bitcoin/runs/40120572487 LLM reason (✨ experimental): Missing or undefined member ’m_failed_blocks’ in ‘ChainstateManager’ caused compilation error, leading to CI failure.

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

in src/test/fuzz/block_index_tree.cpp:28 in 9622aab389 outdated

23+    CBlockHeader header;
24+    header.nVersion = provider.ConsumeIntegral<decltype(header.nVersion)>();
25+    header.hashPrevBlock = prev_hash;
26+    header.hashMerkleRoot = uint256{}; // never used
27+    header.nTime = provider.ConsumeIntegral<decltype(header.nTime)>();
28+    header.nBits = Params().GenesisBlock().nBits;

ismaelsadeeq commented at 12:11 pm on June 16, 2025:

Should also indicate why the nBits is static?

mzumsande commented at 9:20 pm on June 16, 2025:

done

in src/test/fuzz/block_index_tree.cpp:57 in 9622aab389 outdated

52+    {
53+        if (abort_run) break;
54+        CallOneOf(
55+            fuzzed_data_provider,
56+            [&] {
57+                // Receive a header building on an existing one. This assumes headers are valid, so PoW is not relevant here.

ismaelsadeeq commented at 12:12 pm on June 16, 2025:

0                // Receive a header building on an existing valid one. This assumes headers are valid, so PoW is not relevant here.

mzumsande commented at 9:20 pm on June 16, 2025:

added

in src/test/fuzz/block_index_tree.cpp:63 in 9622aab389 outdated

58+                LOCK(cs_main);
59+                CBlockIndex* prev_block = PickValue(fuzzed_data_provider, blocks);
60+                if (!(prev_block->nStatus & BLOCK_FAILED_MASK)) {
61+                    CBlockHeader header = ConsumeBlockHeader(fuzzed_data_provider, prev_block->GetBlockHash(), nonce_counter);
62+                    CBlockIndex* index = blockman.AddToBlockIndex(header, chainman.m_best_header);
63+                    assert(index->nStatus & BLOCK_VALID_TREE);

ismaelsadeeq commented at 12:14 pm on June 16, 2025:

Assert that we connect to the picked index?

mzumsande commented at 9:20 pm on June 16, 2025:

good idea, added an assert

in src/test/fuzz/block_index_tree.cpp:148 in 9622aab389 outdated

143+                assert(chain.Tip()->nChainWork >= old_tip->nChainWork);
144+            },
145+            [&] {
146+                // Prune chain - dealing with block files is beyond the scope of this test, so just prune random blocks, making no assumptions what must
147+                // be together in a block file.
148+                // Also don't prune blocks outside of the chain for now - this would make the fuzzer crash because of the problem describted in

ismaelsadeeq commented at 12:25 pm on June 16, 2025:

Maybe lil too early, but a nit when updating.

0                // Also don't prune blocks outside of the chain for now - this would make the fuzzer crash because of the problem described in

mzumsande commented at 9:21 pm on June 16, 2025:

fixed

ismaelsadeeq commented at 12:30 pm on June 16, 2025: member

Concept ACK

Simple implementation, comments below are just a suggestions for minor improvements

fuzz: Add fuzzer for block index

This fuzz target creates arbitrary tree-like structure of indices,
simulating the following events:
- Adding a header to the block tree db
- Receiving the full block (may be valid or not)
- Reorging to a new chain tip (possibly encountering invalid blocks on
  the way)
- pruning
The test skips all actual validation of header/ block / transaction data
by just simulating the outcome, and also doesn't interact with the data directory.

The main goal is to test the integrity of the block index tree in
all fuzzed constellations, by calling CheckBlockIndex()
at the end of each iteration.

3d53859074

mzumsande force-pushed on Jun 16, 2025

mzumsande commented at 9:22 pm on June 16, 2025: contributor

Rebased due to silent conflict with #31405 and to address feedback by @ismaelsadeeq (thanks!). I think I’ll fuzz this for a few more days and take it out of draft then.

in src/test/fuzz/block_index_tree.cpp:138 in 3d53859074

133+                                block->nStatus |= BLOCK_HAVE_UNDO;
134+                            }
135+                        }
136+                        chain.SetTip(*block);
137+                        chainman.ActiveChainstate().PruneBlockIndexCandidates();
138+                        // ABC may release cs_main / not connect all blocks in one go - but only if we have at least much chain work as we had at the start.

DrahtBot commented at 7:29 am on June 17, 2025:

“at least much chain work as we had at the start” -> “at least as much chain work as we had at the start” [missing “as” after “at least”]

Crypt-iQ commented at 3:54 pm on June 17, 2025: contributor

Concept ACK, will test out.

I think both approaches (this PR and the i/o-based #29158) have their merits and could both be merged. I like that this PR focuses on the internal state we want to check. I also like that the other PR does round-trip reads/writes to disk since I think there should be asserts on i/o like this.

DrahtBot removed the label CI failed on Jun 17, 2025

fuzz: Add fuzz target for block index tree and related validation events #31533

Code Coverage & Benchmarks

Reviews

Conflicts

LLM Linter (✨ experimental)