Merge bitcoin/bitcoin#23496: fuzz: Add minisketch fuzz test

fa74d4530615cfa02cf32a16fab6b13908266e6f fuzz: Add minisketch fuzz test (MarcoFalke)

Pull request description:

ACKs for top commit:
  mjdietzx:
    re-ACK fa74d45
  sipa:
    utACK fa74d4530615cfa02cf32a16fab6b13908266e6f

Tree-SHA512: 3d30095c85032139c37c7a2811dd417441a5105cb70af8250000d7b56aeda1e8fab5e65e683fb49d513ef40a81da3967a8a9a70caf40f56cef1dd96c6d4a05f6

2 files changed, 66 insertions, 0 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 88a1ef798e..715c5bb11c 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -51,6 +51,7 @@ FUZZ_SUITE_LD_COMMON = \
  $(BOOST_LIBS) \
  $(LIBMEMENV) \
  $(LIBSECP256K1) \
+ $(MINISKETCH_LIBS) \
  $(EVENT_LIBS) \
  $(EVENT_PTHREADS_LIBS)
 
@@ -259,6 +260,7 @@ test_fuzz_fuzz_SOURCES = \
  test/fuzz/locale.cpp \
  test/fuzz/merkleblock.cpp \
  test/fuzz/message.cpp \
+ test/fuzz/minisketch.cpp \
  test/fuzz/muhash.cpp \
  test/fuzz/multiplication_overflow.cpp \
  test/fuzz/net.cpp \
diff --git a/src/test/fuzz/minisketch.cpp b/src/test/fuzz/minisketch.cpp
new file mode 100644
index 0000000000..93954bd3cf
--- /dev/null
+++ b/src/test/fuzz/minisketch.cpp
@@ -0,0 +1,64 @@
+// Copyright (c) 2021 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 <minisketch.h>
+#include <node/minisketchwrapper.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <util/check.h>
+
+#include <map>
+#include <numeric>
+
+FUZZ_TARGET(minisketch)
+{
+    FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
+    const auto capacity{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 200)};
+    Minisketch sketch_a{Assert(MakeMinisketch32(capacity))};
+    Minisketch sketch_b{Assert(MakeMinisketch32(capacity))};
+
+    // Fill two sets and keep the difference in a map
+    std::map<uint32_t, bool> diff;
+    LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
+    {
+        const auto entry{fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, std::numeric_limits<uint32_t>::max() - 1)};
+        const auto KeepDiff{[&] {
+            bool& mut{diff[entry]};
+            mut = !mut;
+        }};
+        CallOneOf(
+            fuzzed_data_provider,
+            [&] {
+                sketch_a.Add(entry);
+                KeepDiff();
+            },
+            [&] {
+                sketch_b.Add(entry);
+                KeepDiff();
+            },
+            [&] {
+                sketch_a.Add(entry);
+                sketch_b.Add(entry);
+            });
+    }
+    const auto num_diff{std::accumulate(diff.begin(), diff.end(), size_t{0}, [](auto n, const auto& e) { return n + e.second; })};
+
+    Minisketch sketch_ar{MakeMinisketch32(capacity)};
+    Minisketch sketch_br{MakeMinisketch32(capacity)};
+    sketch_ar.Deserialize(sketch_a.Serialize());
+    sketch_br.Deserialize(sketch_b.Serialize());
+
+    Minisketch sketch_diff{std::move(fuzzed_data_provider.ConsumeBool() ? sketch_a : sketch_ar)};
+    sketch_diff.Merge(fuzzed_data_provider.ConsumeBool() ? sketch_b : sketch_br);
+
+    if (capacity >= num_diff) {
+        const auto max_elements{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(num_diff, capacity)};
+        const auto dec{*Assert(sketch_diff.Decode(max_elements))};
+        Assert(dec.size() == num_diff);
+        for (auto d : dec) {
+            Assert(diff.at(d));
+        }
+    }
+}