diff --git a/src/test/fuzz/CMakeLists.txt b/src/test/fuzz/CMakeLists.txt
--- a/src/test/fuzz/CMakeLists.txt
+++ b/src/test/fuzz/CMakeLists.txt
@@ -82,8 +82,8 @@
 	block_header
 	blockfilter
 	bloom_filter
-	rolling_bloom_filter
 	cashaddr
+	chain
 	descriptor_parse
 	eval_script
 	fee_rate
@@ -104,7 +104,9 @@
 	parse_univalue
 	process_message
 	process_messages
+	protocol
 	psbt
+	rolling_bloom_filter
 	script
 	script_flags
 	script_ops
diff --git a/src/test/fuzz/chain.cpp b/src/test/fuzz/chain.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/fuzz/chain.cpp
@@ -0,0 +1,98 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <chain.h>
+#include <primitives/blockhash.h>
+
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+
+#include <cstdint>
+#include <optional>
+#include <vector>
+
+void test_one_input(const std::vector<uint8_t> &buffer) {
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    std::optional<CDiskBlockIndex> disk_block_index =
+        ConsumeDeserializable<CDiskBlockIndex>(fuzzed_data_provider);
+    if (!disk_block_index) {
+        return;
+    }
+
+    const BlockHash zero{};
+    disk_block_index->phashBlock = &zero;
+    (void)disk_block_index->GetBlockHash();
+    (void)disk_block_index->GetBlockPos();
+    (void)disk_block_index->GetBlockTime();
+    (void)disk_block_index->GetBlockTimeMax();
+    (void)disk_block_index->GetChainSize();
+    (void)disk_block_index->GetChainTxCount();
+    (void)disk_block_index->GetHeaderReceivedTime();
+    (void)disk_block_index->GetMedianTimePast();
+    (void)disk_block_index->GetReceivedTimeDiff();
+    (void)disk_block_index->GetUndoPos();
+    (void)disk_block_index->HaveTxsDownloaded();
+    (void)disk_block_index->IsValid();
+    (void)disk_block_index->ToString();
+    (void)disk_block_index->UpdateChainStats();
+
+    const CBlockHeader block_header = disk_block_index->GetBlockHeader();
+    (void)CDiskBlockIndex{*disk_block_index};
+    (void)disk_block_index->BuildSkip();
+
+    while (fuzzed_data_provider.ConsumeBool()) {
+        const BlockValidity block_validity =
+            fuzzed_data_provider.PickValueInArray({
+                BlockValidity::UNKNOWN,
+                BlockValidity::RESERVED,
+                BlockValidity::TREE,
+                BlockValidity::TRANSACTIONS,
+                BlockValidity::CHAIN,
+                BlockValidity::SCRIPTS,
+            });
+        const BlockStatus base;
+        bool has_data = fuzzed_data_provider.ConsumeBool();
+        bool has_undo = fuzzed_data_provider.ConsumeBool();
+        bool has_failed = fuzzed_data_provider.ConsumeBool();
+        bool has_failed_parent = fuzzed_data_provider.ConsumeBool();
+        bool is_parked = fuzzed_data_provider.ConsumeBool();
+        bool has_parked_parent = fuzzed_data_provider.ConsumeBool();
+        const BlockStatus block_status =
+            base.withValidity(block_validity)
+                .withData(has_data)
+                .withUndo(has_undo)
+                .withFailed(has_failed)
+                .withFailedParent(has_failed_parent)
+                .withParked(is_parked)
+                .withParkedParent(has_parked_parent);
+
+        assert(block_status.hasData() == has_data);
+        assert(block_status.hasUndo() == has_undo);
+        assert(block_status.hasFailed() == has_failed);
+        assert(block_status.hasFailedParent() == has_failed_parent);
+        assert(block_status.isParked() == is_parked);
+        assert(block_status.hasParkedParent() == has_parked_parent);
+
+        assert(block_status.isInvalid() == has_failed || has_failed_parent);
+        const BlockStatus valid_block = block_status.withClearedFailureFlags();
+        assert(!valid_block.isInvalid());
+
+        assert(block_status.isOnParkedChain() == is_parked ||
+               has_parked_parent);
+        const BlockStatus unparked_block =
+            block_status.withClearedParkedFlags();
+        assert(!unparked_block.isOnParkedChain());
+
+        if (!block_status.isValid()) {
+            continue;
+        }
+        (void)disk_block_index->RaiseValidity(block_validity);
+    }
+
+    CBlockIndex block_index{block_header};
+    block_index.phashBlock = &zero;
+    (void)block_index.GetBlockHash();
+    (void)block_index.ToString();
+}
diff --git a/src/test/fuzz/protocol.cpp b/src/test/fuzz/protocol.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/fuzz/protocol.cpp
@@ -0,0 +1,37 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <protocol.h>
+
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+
+#include <cstdint>
+#include <optional>
+#include <stdexcept>
+#include <vector>
+
+void test_one_input(const std::vector<uint8_t> &buffer) {
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const std::optional<CInv> inv =
+        ConsumeDeserializable<CInv>(fuzzed_data_provider);
+    if (!inv) {
+        return;
+    }
+    try {
+        (void)inv->GetCommand();
+    } catch (const std::out_of_range &) {
+    }
+    (void)inv->GetKind();
+    (void)inv->IsSomeBlock();
+    (void)inv->IsTx();
+    (void)inv->ToString();
+    const std::optional<CInv> another_inv =
+        ConsumeDeserializable<CInv>(fuzzed_data_provider);
+    if (!another_inv) {
+        return;
+    }
+    (void)(*inv < *another_inv);
+}