diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -544,6 +544,7 @@
 	addrdb.cpp
 	addrman.cpp
 	avalanche/avalanche.cpp
+	avalanche/compactproofs.cpp
 	avalanche/delegation.cpp
 	avalanche/delegationbuilder.cpp
 	avalanche/peermanager.cpp
diff --git a/src/avalanche/compactproofs.h b/src/avalanche/compactproofs.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/compactproofs.h
@@ -0,0 +1,106 @@
+// Copyright (c) 2022 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_AVALANCHE_COMPACTPROOFS_H
+#define BITCOIN_AVALANCHE_COMPACTPROOFS_H
+
+#include <avalanche/proof.h>
+#include <avalanche/proofradixtreeadapter.h>
+
+#include <radix.h>
+#include <random.h>
+#include <serialize.h>
+
+#include <cstdint>
+#include <ios>
+#include <limits>
+#include <utility>
+#include <vector>
+
+namespace avalanche {
+
+namespace {
+    struct TestCompactProofs;
+}
+
+struct ProofId;
+
+struct PrefilledProof {
+    // Used as an offset since last prefilled proof in CompactProofs
+    uint32_t index;
+    avalanche::ProofRef proof;
+
+    class Formatter : public DifferenceFormatter {
+    public:
+        template <typename Stream> void Ser(Stream &s, PrefilledProof pp) {
+            DifferenceFormatter::Ser(s, pp.index);
+            s << pp.proof;
+        }
+
+        template <typename Stream> void Unser(Stream &s, PrefilledProof &pp) {
+            DifferenceFormatter::Unser(s, pp.index);
+            s >> pp.proof;
+        }
+    };
+};
+
+class CompactProofs {
+private:
+    uint64_t shortproofidk0, shortproofidk1;
+    std::vector<uint64_t> shortproofids;
+    std::vector<PrefilledProof> prefilledProofs;
+
+public:
+    static constexpr int SHORTPROOFIDS_LENGTH = 6;
+
+    CompactProofs()
+        : shortproofidk0(GetRand(std::numeric_limits<uint64_t>::max())),
+          shortproofidk1(GetRand(std::numeric_limits<uint64_t>::max())) {}
+    CompactProofs(const RadixTree<const Proof, ProofRadixTreeAdapter> &proofs);
+
+    uint64_t getShortID(const ProofId &proofid) const;
+
+    size_t size() const {
+        return shortproofids.size() + prefilledProofs.size();
+    }
+    std::pair<uint64_t, uint64_t> getKeys() const {
+        return std::make_pair(shortproofidk0, shortproofidk1);
+    }
+
+    SERIALIZE_METHODS(CompactProofs, obj) {
+        READWRITE(
+            obj.shortproofidk0, obj.shortproofidk1,
+            Using<VectorFormatter<CustomUintFormatter<SHORTPROOFIDS_LENGTH>>>(
+                obj.shortproofids),
+            Using<VectorFormatter<PrefilledProof::Formatter>>(
+                obj.prefilledProofs));
+
+        if (ser_action.ForRead() && obj.prefilledProofs.size() > 0) {
+            // Thanks to the DifferenceFormatter, the index values in the
+            // deserialized prefilled proofs are absolute and sorted, so the
+            // last vector item has the highest index value.
+            uint64_t highestPrefilledIndex = obj.prefilledProofs.back().index;
+
+            // Make sure the indexes do not overflow 32 bits.
+            if (highestPrefilledIndex + obj.shortproofids.size() >
+                std::numeric_limits<uint32_t>::max()) {
+                throw std::ios_base::failure("indexes overflowed 32 bits");
+            }
+
+            // Make sure the indexes are contiguous. E.g. if there is no shortid
+            // but 2 prefilled proofs with absolute indexes 0 and 2, then the
+            // proof at index 1 cannot be recovered.
+            if (highestPrefilledIndex >= obj.size()) {
+                throw std::ios_base::failure("non contiguous indexes");
+            }
+        }
+    }
+
+private:
+    friend struct ::avalanche::TestCompactProofs;
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_COMPACTPROOFS_H
diff --git a/src/avalanche/compactproofs.cpp b/src/avalanche/compactproofs.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/compactproofs.cpp
@@ -0,0 +1,28 @@
+// Copyright (c) 2022 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <avalanche/compactproofs.h>
+
+#include <avalanche/proofid.h>
+#include <crypto/siphash.h>
+
+namespace avalanche {
+
+CompactProofs::CompactProofs(
+    const RadixTree<const Proof, ProofRadixTreeAdapter> &proofs)
+    : CompactProofs() {
+    proofs.forEachLeaf([&](auto pLeaf) {
+        shortproofids.push_back(getShortID(pLeaf->getId()));
+        return true;
+    });
+}
+
+uint64_t CompactProofs::getShortID(const ProofId &proofid) const {
+    static_assert(SHORTPROOFIDS_LENGTH == 6,
+                  "shortproofids calculation assumes 6-byte shortproofids");
+    return SipHashUint256(shortproofidk0, shortproofidk1, proofid) &
+           0xffffffffffffL;
+}
+
+} // namespace avalanche
diff --git a/src/avalanche/test/CMakeLists.txt b/src/avalanche/test/CMakeLists.txt
--- a/src/avalanche/test/CMakeLists.txt
+++ b/src/avalanche/test/CMakeLists.txt
@@ -13,6 +13,7 @@
 	util.cpp
 
 	TESTS
+		compactproofs_tests.cpp
 		delegation_tests.cpp
 		init_tests.cpp
 		peermanager_tests.cpp
diff --git a/src/avalanche/test/compactproofs_tests.cpp b/src/avalanche/test/compactproofs_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/test/compactproofs_tests.cpp
@@ -0,0 +1,318 @@
+// Copyright (c) 2022 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <avalanche/compactproofs.h>
+
+#include <avalanche/test/util.h>
+#include <streams.h>
+
+#include <test/util/setup_common.h>
+
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+namespace avalanche {
+namespace {
+    struct TestCompactProofs {
+        static std::vector<uint64_t> getShortProofIds(const CompactProofs &cp) {
+            return cp.shortproofids;
+        }
+
+        static std::vector<PrefilledProof>
+        getPrefilledProofs(const CompactProofs &cp) {
+            return cp.prefilledProofs;
+        }
+
+        static void addPrefilledProof(CompactProofs &cp, uint32_t index,
+                                      const ProofRef &proof) {
+            PrefilledProof pp{index, proof};
+            cp.prefilledProofs.push_back(std::move(pp));
+        }
+    };
+} // namespace
+} // namespace avalanche
+
+using namespace avalanche;
+
+// TestingSetup is required for buildRandomProof()
+BOOST_FIXTURE_TEST_SUITE(compactproofs_tests, TestingSetup)
+
+BOOST_AUTO_TEST_CASE(compactproofs_roundtrip) {
+    {
+        CompactProofs cpw;
+        BOOST_CHECK_EQUAL(cpw.size(), 0);
+
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        BOOST_CHECK_NO_THROW(ss << cpw);
+
+        CompactProofs cpr;
+        BOOST_CHECK_NO_THROW(ss >> cpr);
+
+        BOOST_CHECK_EQUAL(cpr.size(), 0);
+        BOOST_CHECK_EQUAL(cpr.getKeys().first, cpw.getKeys().first);
+        BOOST_CHECK_EQUAL(cpr.getKeys().second, cpw.getKeys().second);
+    }
+
+    {
+        // Check index boundaries
+        CompactProofs cp;
+
+        TestCompactProofs::addPrefilledProof(
+            cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE));
+        TestCompactProofs::addPrefilledProof(
+            cp, std::numeric_limits<uint32_t>::max(),
+            buildRandomProof(MIN_VALID_PROOF_SCORE));
+
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        BOOST_CHECK_NO_THROW(ss << cp);
+
+        auto prefilledProofs = TestCompactProofs::getPrefilledProofs(cp);
+        BOOST_CHECK_EQUAL(prefilledProofs.size(), 2);
+
+        BOOST_CHECK_EQUAL(prefilledProofs[0].index, 0);
+        BOOST_CHECK_EQUAL(prefilledProofs[1].index,
+                          std::numeric_limits<uint32_t>::max());
+    }
+
+    auto checkCompactProof = [&](size_t numofProof,
+                                 size_t numofPrefilledProof) {
+        RadixTree<const Proof, ProofRadixTreeAdapter> proofs;
+        for (size_t i = 0; i < numofProof; i++) {
+            BOOST_CHECK(proofs.insert(buildRandomProof(MIN_VALID_PROOF_SCORE)));
+        }
+
+        CompactProofs cpw(proofs);
+        BOOST_CHECK_EQUAL(cpw.size(), numofProof);
+
+        uint32_t prefilledProofIndex = 0;
+        for (size_t i = 0; i < numofPrefilledProof; i++) {
+            TestCompactProofs::addPrefilledProof(
+                cpw, prefilledProofIndex++,
+                buildRandomProof(
+                    GetRand(std::numeric_limits<uint32_t>::max())));
+        }
+        auto prefilledProofs = TestCompactProofs::getPrefilledProofs(cpw);
+        BOOST_CHECK_EQUAL(prefilledProofs.size(), numofPrefilledProof);
+
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        BOOST_CHECK_NO_THROW(ss << cpw);
+
+        CompactProofs cpr;
+        BOOST_CHECK_NO_THROW(ss >> cpr);
+
+        BOOST_CHECK_EQUAL(cpr.size(), numofProof + numofPrefilledProof);
+        BOOST_CHECK_EQUAL(cpr.getKeys().first, cpw.getKeys().first);
+        BOOST_CHECK_EQUAL(cpr.getKeys().second, cpw.getKeys().second);
+
+        auto comparePrefilledProof = [](const PrefilledProof &lhs,
+                                        const PrefilledProof &rhs) {
+            return lhs.index == rhs.index &&
+                   lhs.proof->getId() == rhs.proof->getId() &&
+                   lhs.proof->getSignature() == rhs.proof->getSignature();
+        };
+
+        auto prefilledProofsCpr = TestCompactProofs::getPrefilledProofs(cpr);
+        BOOST_CHECK(std::equal(prefilledProofsCpr.begin(),
+                               prefilledProofsCpr.end(),
+                               prefilledProofs.begin(), comparePrefilledProof));
+
+        auto shortIds = TestCompactProofs::getShortProofIds(cpr);
+        size_t index = 0;
+        proofs.forEachLeaf([&](auto pLeaf) {
+            const ProofId &proofid = pLeaf->getId();
+            BOOST_CHECK_EQUAL(cpr.getShortID(proofid), cpw.getShortID(proofid));
+            BOOST_CHECK_EQUAL(cpr.getShortID(proofid), shortIds[index]);
+            ++index;
+
+            return true;
+        });
+    };
+
+    // No proof at all
+    checkCompactProof(0, 0);
+
+    // No prefilled proofs
+    checkCompactProof(1000, 0);
+
+    // Only prefilled proofs
+    checkCompactProof(0, 1000);
+
+    // Mixed case
+    checkCompactProof(1000, 1000);
+}
+
+BOOST_AUTO_TEST_CASE(compactproofs_overflow) {
+    {
+        CompactProofs cp;
+
+        TestCompactProofs::addPrefilledProof(
+            cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE));
+        TestCompactProofs::addPrefilledProof(
+            cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE));
+
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure,
+                              HasReason("differential value overflow"));
+    }
+
+    {
+        CompactProofs cp;
+
+        TestCompactProofs::addPrefilledProof(
+            cp, 1, buildRandomProof(MIN_VALID_PROOF_SCORE));
+        TestCompactProofs::addPrefilledProof(
+            cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE));
+
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure,
+                              HasReason("differential value overflow"));
+    }
+
+    {
+        CompactProofs cp;
+
+        TestCompactProofs::addPrefilledProof(
+            cp, std::numeric_limits<uint32_t>::max(),
+            buildRandomProof(MIN_VALID_PROOF_SCORE));
+        TestCompactProofs::addPrefilledProof(
+            cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE));
+
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure,
+                              HasReason("differential value overflow"));
+    }
+
+    {
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        // shortproofidk0, shortproofidk1
+        ss << uint64_t(0) << uint64_t(0);
+        // shortproofids.size()
+        WriteCompactSize(ss, MAX_SIZE + 1);
+
+        CompactProofs cp;
+        BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+                              HasReason("ReadCompactSize(): size too large"));
+    }
+
+    {
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        // shortproofidk0, shortproofidk1
+        ss << uint64_t(0) << uint64_t(0);
+        // shortproofids.size()
+        WriteCompactSize(ss, 0);
+        // prefilledProofs.size()
+        WriteCompactSize(ss, MAX_SIZE + 1);
+
+        CompactProofs cp;
+        BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+                              HasReason("ReadCompactSize(): size too large"));
+    }
+
+    {
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        // shortproofidk0, shortproofidk1
+        ss << uint64_t(0) << uint64_t(0);
+        // shortproofids.size()
+        WriteCompactSize(ss, 0);
+        // prefilledProofs.size()
+        WriteCompactSize(ss, 1);
+        // prefilledProofs[0].index
+        WriteCompactSize(ss, MAX_SIZE + 1);
+        // prefilledProofs[0].proof
+        ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+        CompactProofs cp;
+        BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+                              HasReason("ReadCompactSize(): size too large"));
+    }
+
+    // Compute the number of MAX_SIZE increment we need to cause an overflow
+    const uint64_t overflow =
+        uint64_t(std::numeric_limits<uint32_t>::max()) + 1;
+    // Due to differential encoding, a value of MAX_SIZE bumps the index by
+    // MAX_SIZE + 1
+    BOOST_CHECK_GE(overflow, MAX_SIZE + 1);
+    const uint64_t overflowIter = overflow / (MAX_SIZE + 1);
+
+    // Make sure the iteration fits in an uint32_t and is <= MAX_SIZE
+    BOOST_CHECK_LE(overflowIter, std::numeric_limits<uint32_t>::max());
+    BOOST_CHECK_LE(overflowIter, MAX_SIZE);
+    uint32_t remainder = uint32_t(overflow - ((MAX_SIZE + 1) * overflowIter));
+
+    {
+        CDataStream ss(SER_DISK, PROTOCOL_VERSION);
+        // shortproofidk0, shortproofidk1
+        ss << uint64_t(0) << uint64_t(0);
+        // shortproofids.size()
+        WriteCompactSize(ss, 0);
+        // prefilledProofs.size()
+        WriteCompactSize(ss, overflowIter + 1);
+        for (uint32_t i = 0; i < overflowIter; i++) {
+            // prefilledProofs[i].index
+            WriteCompactSize(ss, MAX_SIZE);
+            // prefilledProofs[i].proof
+            ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+        }
+        // This is the prefilled proof causing the overflow
+        WriteCompactSize(ss, remainder);
+        ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+        CompactProofs cp;
+        BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+                              HasReason("differential value overflow"));
+    }
+
+    {
+        CDataStream ss(SER_DISK, PROTOCOL_VERSION);
+        // shortproofidk0, shortproofidk1
+        ss << uint64_t(0) << uint64_t(0);
+        // shortproofids.size()
+        WriteCompactSize(ss, 1);
+        // shortproofids[0]
+        CustomUintFormatter<CompactProofs::SHORTPROOFIDS_LENGTH>().Ser(ss, 0u);
+        // prefilledProofs.size()
+        WriteCompactSize(ss, overflowIter + 1);
+        for (uint32_t i = 0; i < overflowIter; i++) {
+            // prefilledProofs[i].index
+            WriteCompactSize(ss, MAX_SIZE);
+            // prefilledProofs[i].proof
+            ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+        }
+        // This prefilled proof isn't enough to cause the overflow alone, but it
+        // overflows due to the extra shortid.
+        WriteCompactSize(ss, remainder - 1);
+        ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+        CompactProofs cp;
+        // ss >> cp;
+        BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+                              HasReason("indexes overflowed 32 bits"));
+    }
+
+    {
+        CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+        // shortproofidk0, shortproofidk1
+        ss << uint64_t(0) << uint64_t(0);
+        // shortproofids.size()
+        WriteCompactSize(ss, 0);
+        // prefilledProofs.size()
+        WriteCompactSize(ss, 2);
+        // prefilledProofs[0].index
+        WriteCompactSize(ss, 0);
+        // prefilledProofs[0].proof
+        ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+        // prefilledProofs[1].index = 1 is differentially encoded, which means
+        // it has an absolute index of 2. This leaves no proof at index 1.
+        WriteCompactSize(ss, 1);
+        // prefilledProofs[1].proof
+        ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+        CompactProofs cp;
+        BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+                              HasReason("non contiguous indexes"));
+    }
+}
+
+BOOST_AUTO_TEST_SUITE_END()