diff --git a/src/Makefile.test.include b/src/Makefile.test.include
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -19,6 +19,7 @@
   test/fuzz/blocktransactions_deserialize \
   test/fuzz/blocktransactionsrequest_deserialize \
   test/fuzz/blockundo_deserialize \
+  test/fuzz/bloom_filter \
   test/fuzz/bloomfilter_deserialize \
   test/fuzz/coins_deserialize \
   test/fuzz/descriptor_parse \
@@ -40,6 +41,7 @@
   test/fuzz/psbt_input_deserialize \
   test/fuzz/psbt_output_deserialize \
   test/fuzz/pub_key_deserialize \
+  test/fuzz/rolling_bloom_filter \
   test/fuzz/script \
   test/fuzz/script_deserialize \
   test/fuzz/script_flags \
@@ -91,6 +93,7 @@
   test/fuzz/fuzz.cpp \
   test/fuzz/fuzz.h \
   test/fuzz/FuzzedDataProvider.h \
+  test/fuzz/util.h \
   test/util/setup_common.cpp \
   test/util/setup_common.h \
   test/util/str.cpp \
@@ -398,6 +401,12 @@
 test_fuzz_inv_deserialize_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
 test_fuzz_inv_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
 
+test_fuzz_bloom_filter_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_bloom_filter_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_bloom_filter_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_bloom_filter_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_bloom_filter_SOURCES = $(FUZZ_SUITE) test/fuzz/bloom_filter.cpp
+
 test_fuzz_bloomfilter_deserialize_SOURCES = $(FUZZ_SUITE) test/fuzz/deserialize.cpp
 test_fuzz_bloomfilter_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DBLOOMFILTER_DESERIALIZE=1
 test_fuzz_bloomfilter_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
@@ -530,6 +539,12 @@
 test_fuzz_pub_key_deserialize_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
 test_fuzz_pub_key_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
 
+test_fuzz_rolling_bloom_filter_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_rolling_bloom_filter_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_rolling_bloom_filter_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_rolling_bloom_filter_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_rolling_bloom_filter_SOURCES = $(FUZZ_SUITE) test/fuzz/rolling_bloom_filter.cpp
+
 test_fuzz_script_deserialize_SOURCES = $(FUZZ_SUITE) test/fuzz/deserialize.cpp
 test_fuzz_script_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DSCRIPT_DESERIALIZE=1
 test_fuzz_script_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
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
@@ -45,6 +45,8 @@
 endfunction()
 
 add_regular_fuzz_targets(
+	bloom_filter
+	rolling_bloom_filter
 	cashaddr
 	descriptor_parse
 	eval_script
diff --git a/src/test/fuzz/bloom_filter.cpp b/src/test/fuzz/bloom_filter.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/fuzz/bloom_filter.cpp
@@ -0,0 +1,88 @@
+// 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 <bloom.h>
+#include <optional.h>
+#include <primitives/transaction.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <uint256.h>
+
+#include <cassert>
+#include <cstdint>
+#include <string>
+#include <vector>
+
+void test_one_input(const std::vector<uint8_t> &buffer) {
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+
+    CBloomFilter bloom_filter{
+        fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, 10000000),
+        1.0 / fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(
+                  1, std::numeric_limits<unsigned int>::max()),
+        fuzzed_data_provider.ConsumeIntegral<unsigned int>(),
+        static_cast<uint8_t>(fuzzed_data_provider.PickValueInArray(
+            {BLOOM_UPDATE_NONE, BLOOM_UPDATE_ALL, BLOOM_UPDATE_P2PUBKEY_ONLY,
+             BLOOM_UPDATE_MASK}))};
+    while (fuzzed_data_provider.remaining_bytes() > 0) {
+        switch (fuzzed_data_provider.ConsumeIntegralInRange(0, 6)) {
+            case 0: {
+                const std::vector<uint8_t> &b =
+                    ConsumeRandomLengthByteVector(fuzzed_data_provider);
+                (void)bloom_filter.contains(b);
+                bloom_filter.insert(b);
+                const bool present = bloom_filter.contains(b);
+                assert(present);
+                break;
+            }
+            case 1: {
+                const Optional<COutPoint> out_point =
+                    ConsumeDeserializable<COutPoint>(fuzzed_data_provider);
+                if (!out_point) {
+                    break;
+                }
+                (void)bloom_filter.contains(*out_point);
+                bloom_filter.insert(*out_point);
+                const bool present = bloom_filter.contains(*out_point);
+                assert(present);
+                break;
+            }
+            case 2: {
+                const Optional<uint256> u256 =
+                    ConsumeDeserializable<uint256>(fuzzed_data_provider);
+                if (!u256) {
+                    break;
+                }
+                (void)bloom_filter.contains(*u256);
+                bloom_filter.insert(*u256);
+                const bool present = bloom_filter.contains(*u256);
+                assert(present);
+                break;
+            }
+            case 3:
+                bloom_filter.clear();
+                break;
+            case 4:
+                bloom_filter.reset(
+                    fuzzed_data_provider.ConsumeIntegral<unsigned int>());
+                break;
+            case 5: {
+                const Optional<CMutableTransaction> mut_tx =
+                    ConsumeDeserializable<CMutableTransaction>(
+                        fuzzed_data_provider);
+                if (!mut_tx) {
+                    break;
+                }
+                const CTransaction tx{*mut_tx};
+                (void)bloom_filter.IsRelevantAndUpdate(tx);
+                break;
+            }
+            case 6:
+                bloom_filter.UpdateEmptyFull();
+                break;
+        }
+        (void)bloom_filter.IsWithinSizeConstraints();
+    }
+}
diff --git a/src/test/fuzz/rolling_bloom_filter.cpp b/src/test/fuzz/rolling_bloom_filter.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/fuzz/rolling_bloom_filter.cpp
@@ -0,0 +1,52 @@
+// 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 <bloom.h>
+#include <optional.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <uint256.h>
+
+#include <cassert>
+#include <cstdint>
+#include <string>
+#include <vector>
+
+void test_one_input(const std::vector<uint8_t> &buffer) {
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+
+    CRollingBloomFilter rolling_bloom_filter{
+        fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(1, 1000),
+        0.999 / fuzzed_data_provider.ConsumeIntegralInRange<unsigned int>(
+                    1, std::numeric_limits<unsigned int>::max())};
+    while (fuzzed_data_provider.remaining_bytes() > 0) {
+        switch (fuzzed_data_provider.ConsumeIntegralInRange(0, 2)) {
+            case 0: {
+                const std::vector<uint8_t> &b =
+                    ConsumeRandomLengthByteVector(fuzzed_data_provider);
+                (void)rolling_bloom_filter.contains(b);
+                rolling_bloom_filter.insert(b);
+                const bool present = rolling_bloom_filter.contains(b);
+                assert(present);
+                break;
+            }
+            case 1: {
+                const Optional<uint256> u256 =
+                    ConsumeDeserializable<uint256>(fuzzed_data_provider);
+                if (!u256) {
+                    break;
+                }
+                (void)rolling_bloom_filter.contains(*u256);
+                rolling_bloom_filter.insert(*u256);
+                const bool present = rolling_bloom_filter.contains(*u256);
+                assert(present);
+                break;
+            }
+            case 2:
+                rolling_bloom_filter.reset();
+                break;
+        }
+    }
+}
diff --git a/src/test/fuzz/util.h b/src/test/fuzz/util.h
new file mode 100644
--- /dev/null
+++ b/src/test/fuzz/util.h
@@ -0,0 +1,43 @@
+// Copyright (c) 2009-2019 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_TEST_FUZZ_UTIL_H
+#define BITCOIN_TEST_FUZZ_UTIL_H
+
+#include <attributes.h>
+#include <optional.h>
+#include <serialize.h>
+#include <streams.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <version.h>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+NODISCARD inline std::vector<uint8_t>
+ConsumeRandomLengthByteVector(FuzzedDataProvider &fuzzed_data_provider,
+                              size_t max_length = 4096) noexcept {
+    const std::string s =
+        fuzzed_data_provider.ConsumeRandomLengthString(max_length);
+    return {s.begin(), s.end()};
+}
+
+template <typename T>
+NODISCARD inline Optional<T>
+ConsumeDeserializable(FuzzedDataProvider &fuzzed_data_provider,
+                      size_t max_length = 4096) noexcept {
+    const std::vector<uint8_t> &buffer =
+        ConsumeRandomLengthByteVector(fuzzed_data_provider, max_length);
+    CDataStream ds{buffer, SER_NETWORK, INIT_PROTO_VERSION};
+    T obj;
+    try {
+        ds >> obj;
+    } catch (const std::ios_base::failure &) {
+        return nullopt;
+    }
+    return obj;
+}
+
+#endif // BITCOIN_TEST_FUZZ_UTIL_H