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)
#30214 (refactor: Improve assumeutxo state representation by ryanofsky)

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.

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

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 outdated

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

Crypt-iQ commented at 6:00 pm on June 17, 2025: contributor

Have you seen the below crash before / is it the same root cause as reported in #31512?

 0Running: crash-3b11c210b246fa09b395166b5007c451399115b8
 1Assertion failed: (c->setBlockIndexCandidates.contains(const_cast<CBlockIndex*>(pindex))), function CheckBlockIndex, file validation.cpp, line 5416.
 2==90212== ERROR: libFuzzer: deadly signal
 3    [#0](/bitcoin-bitcoin/0/) 0x10876cd70 in __sanitizer_print_stack_trace+0x28 (libclang_rt.asan_osx_dynamic.dylib:arm64+0x5cd70)
 4    [#1](/bitcoin-bitcoin/1/) 0x105276794 in fuzzer::PrintStackTrace() FuzzerUtil.cpp:210
 5    [#2](/bitcoin-bitcoin/2/) 0x10525c57c in fuzzer::Fuzzer::CrashCallback() FuzzerLoop.cpp:231
 6    [#3](/bitcoin-bitcoin/3/) 0x19b787620 in _sigtramp+0x34 (libsystem_platform.dylib:arm64+0x3620)
 7    [#4](/bitcoin-bitcoin/4/) 0x19b74d888 in pthread_kill+0x124 (libsystem_pthread.dylib:arm64+0x6888)
 8    [#5](/bitcoin-bitcoin/5/) 0x19b656c5c in abort+0x78 (libsystem_c.dylib:arm64+0x78c5c)
 9    [#6](/bitcoin-bitcoin/6/) 0x19b655ee8 in __assert_rtn+0x118 (libsystem_c.dylib:arm64+0x77ee8)
10    [#7](/bitcoin-bitcoin/7/) 0x10506d1e4 in ChainstateManager::CheckBlockIndex() const validation.cpp:5416
11    [#8](/bitcoin-bitcoin/8/) 0x102c40e84 in block_index_tree_fuzz_target(std::__1::span<unsigned char const, 18446744073709551615ul>) block_index_tree.cpp:173
12    [#9](/bitcoin-bitcoin/9/) 0x1035242fc in LLVMFuzzerTestOneInput fuzz.cpp:215
13    [#10](/bitcoin-bitcoin/10/) 0x10525d9a4 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) FuzzerLoop.cpp:614
14    [#11](/bitcoin-bitcoin/11/) 0x10524a6e8 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) FuzzerDriver.cpp:327
15    [#12](/bitcoin-bitcoin/12/) 0x10524f980 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) FuzzerDriver.cpp:862
16    [#13](/bitcoin-bitcoin/13/) 0x10527707c in main FuzzerMain.cpp:20
17    [#14](/bitcoin-bitcoin/14/) 0x19b3aeb48  (<unknown module>)

mzumsande commented at 6:18 pm on June 17, 2025: contributor

Have you seen the below crash before / is it the same root cause as reported in #31512?

no, I haven’t seen it, and it shouldn’t be the same root cause - could you provide me the seed?

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.

ab8bc7a1f8

mzumsande force-pushed on Jun 17, 2025

mzumsande commented at 8:09 pm on June 17, 2025: contributor

Thanks for providing me with the seed! It was a bug in the fuzz test: when we set abort_run (because reorging over pruned blocks also makes real nodes crash), we shouldn’t call CheckBlockIndex in the fuzz test.

There are no known crashes with the current version. The problem of #31512 is being avoided by only allowing to prune blocks inside the chain for now, instead of pruning arbitrary blocks.

in src/test/fuzz/block_index_tree.cpp:7 in ab8bc7a1f8

0@@ -0,0 +1,205 @@
1+// Copyright (c) 2020-2022 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 <chain.h>
6+#include <chainparams.h>
7+#include <cstdint>

maflcko commented at 8:56 am on June 20, 2025:

nit: wrong section?

in src/test/fuzz/block_index_tree.cpp:16 in ab8bc7a1f8

11+#include <test/fuzz/util.h>
12+#include <test/util/setup_common.h>
13+
14+#include <optional>
15+#include <ranges>
16+#include <validation.h>

maflcko commented at 8:56 am on June 20, 2025:

same nit

in src/test/fuzz/block_index_tree.cpp:149 in ab8bc7a1f8

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

Crypt-iQ commented at 2:37 pm on June 23, 2025:

Could there also be a lambda that downloads a previously valid, pruned block that is in the main chain?

mzumsande commented at 5:41 pm on June 23, 2025:

you mean to simulate getblockfrompeer? I think it would be good to try! I thought about it and was a bit concerned it would open a can of worms of issues in CheckBlockIndex(), and I’m doubtful if we want to accomodate CBI too much just for getblockfrompeer - it’s a rather recent and artifical rpc after all which I view as kind of a hack - but maybe these concerns are unfounded because I didn’t try it!

Crypt-iQ commented at 6:39 pm on June 23, 2025:

you mean to simulate getblockfrompeer?

Yup just to see that it’s tolerated properly. I completely agree that getblockfrompeer is kind of a hack.

Crypt-iQ commented at 2:41 pm on June 23, 2025: contributor

It would be nice if we could also test out LoadBlockIndex since it inserts into m_blocks_unlinked for pruned blocks, but I think that will require a bit more mocking and not necessary for this PR.

There is some non-determinism in the fuzz test that I’ll investigate:

 0diff --git a/Users/eugenesiegel/btc/bitcoin-review/build/fuzz_det_cov.show.t0.a.txt b/Users/eugenesiegel/btc/bitcoin-review/build/fuzz_det_cov.show.t0.b.txt
 1index 45c6f3edb4..592f5964eb 100644
 2--- a/Users/eugenesiegel/btc/bitcoin-review/build/fuzz_det_cov.show.t0.a.txt
 3+++ b/Users/eugenesiegel/btc/bitcoin-review/build/fuzz_det_cov.show.t0.b.txt
 4@@ -298059,13 +298059,13 @@
 5  5513|  19.6k|            } else if (pindexPar == best_hdr_chain[nHeight - 1]) {
 6                                  ^15.6k^15.6k
 7   ------------------
 8-  |  Branch (5513:24): [True: 6.04k, False: 9.57k]
 9+  |  Branch (5513:24): [True: 6.03k, False: 9.57k]
10   ------------------
11  5514|       |                // Move to pindex's sibling on the best-chain, if it has one.
12- 5515|  6.04k|                pindex = best_hdr_chain[nHeight];
13+ 5515|  6.03k|                pindex = best_hdr_chain[nHeight];
14  5516|       |                // There will not be a next block if (and only if) parent block is the best header.
15- 5517|  6.04k|                assert((pindex == nullptr) == (pindexPar == best_hdr_chain.Tip()));
16- 5518|  6.04k|                break;
17+ 5517|  6.03k|                assert((pindex == nullptr) == (pindexPar == best_hdr_chain.Tip()));
18+ 5518|  6.03k|                break;
19  5519|  9.57k|            } else {
20  5520|       |                // Move up further.
21  5521|  9.57k|                pindex = pindexPar;
22@@ -299753,10 +299753,10 @@
23                                                                          ^6.06k
24   ------------------
25   |  Branch (6425:13): [True: 6.06k, False: 5.70k]
26-  |  Branch (6425:60): [True: 647, False: 5.41k]
27+  |  Branch (6425:60): [True: 645, False: 5.42k]
28   ------------------
29- 6426|    647|            m_best_header = &entry.second;
30- 6427|    647|        }
31+ 6426|    645|            m_best_header = &entry.second;
32+ 6427|    645|        }
33  6428|  11.7k|    }
34  6429|  1.98k|}
35  6430|       |
36⚠️
37
38The coverage was not deterministic between runs.

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

Code Coverage & Benchmarks

Reviews

Conflicts