diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/proofpool.h
@@ -0,0 +1,113 @@
+// Copyright (c) 2021 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_PROOFPOOL_H
+#define BITCOIN_AVALANCHE_PROOFPOOL_H
+
+#include <avalanche/proof.h>
+#include <salteduint256hasher.h>
+
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/multi_index_container.hpp>
+
+namespace avalanche {
+
+class SaltedProofIdHasher : private SaltedUint256Hasher {
+public:
+    SaltedProofIdHasher() : SaltedUint256Hasher() {}
+    size_t operator()(const ProofId &proofid) const { return hash(proofid); }
+};
+
+// Extracts a ProofId from a Proof
+struct proofid_extractor {
+    typedef ProofId result_type;
+    result_type operator()(const Proof &proof) const { return proof.getId(); }
+};
+
+struct by_sequence {};
+struct by_proofid {};
+
+typedef boost::multi_index_container<
+    Proof,
+    boost::multi_index::indexed_by<
+        // keep insertion order
+        boost::multi_index::sequenced<boost::multi_index::tag<by_sequence>>,
+        // indexed by proofid
+        boost::multi_index::hashed_unique<boost::multi_index::tag<by_proofid>,
+                                          proofid_extractor,
+                                          SaltedProofIdHasher>>>
+    proofContainer;
+
+/**
+ * ProofPool stores orphan proofs waiting for their UTXOs to be found.
+ *
+ * When the pool is full, the oldest proof is removed before a new one is
+ * added.
+ */
+class ProofPool {
+    proofContainer proofs;
+
+    const size_t maxNumberOfStakes;
+    size_t nStakes = 0;
+
+    /**
+     *  Trim the proof pool to given max size.
+     *  It the current size is <= max size this has no effect.
+     */
+    void trimToMaximumSize() {
+        auto &proofs_by_sequence = proofs.get<by_sequence>();
+
+        while (nStakes > maxNumberOfStakes) {
+            Proof p = proofs_by_sequence.back();
+            nStakes = nStakes - p.getStakes().size();
+            proofs_by_sequence.pop_back();
+        }
+    }
+
+public:
+    ProofPool(size_t maxNumberOfStakes)
+        : maxNumberOfStakes(maxNumberOfStakes) {}
+
+    /**
+     * Add a proof to the pool.
+     * The caller is responsible for checking the proof.
+     */
+    bool addProof(const Proof &proof) {
+        if (proofs.get<by_sequence>().push_front(proof).second) {
+            nStakes = nStakes + proof.getStakes().size();
+            trimToMaximumSize();
+            return true;
+        }
+        return false;
+    }
+
+    /** Remove a proof from the pool. */
+    bool removeProof(const ProofId &proofId) {
+        auto &proofs_by_id = proofs.get<by_proofid>();
+        auto it = proofs_by_id.find(proofId);
+        if (it == proofs_by_id.end()) {
+            return false;
+        }
+        nStakes = nStakes - it->getStakes().size();
+        return proofs_by_id.erase(proofId) == 1;
+    }
+
+    /**
+     * Get a pointer to a proof by id, or nullptr if the proof is not in the
+     * pool.
+     */
+    const Proof *getProof(ProofId proofId) const {
+        auto &proofs_by_proofid = proofs.get<by_proofid>();
+        auto it = proofs_by_proofid.find(proofId);
+        return it == proofs_by_proofid.end() ? nullptr : &*it;
+    }
+
+    // For testing
+    size_t getSize() const { return proofs.get<by_sequence>().size(); }
+    size_t getNStakes() const { return nStakes; }
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_PROOFPOOL_H
\ No newline at end of file
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
@@ -17,6 +17,7 @@
 		peermanager_tests.cpp
 		processor_tests.cpp
 		proof_tests.cpp
+		proofpool_tests.cpp
 )
 
 target_link_libraries(test-avalanche server testutil)
diff --git a/src/avalanche/test/proofpool_tests.cpp b/src/avalanche/test/proofpool_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/test/proofpool_tests.cpp
@@ -0,0 +1,167 @@
+// Copyright (c) 2021 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/proofbuilder.h>
+#include <avalanche/proofpool.h>
+
+#include <script/standard.h>
+#include <validation.h>
+
+#include <test/util/setup_common.h>
+
+#include <boost/test/unit_test.hpp>
+
+using namespace avalanche;
+
+BOOST_FIXTURE_TEST_SUITE(proofpool_tests, TestingSetup)
+
+BOOST_AUTO_TEST_CASE(proofpool_fill) {
+    const Amount v = 5 * COIN;
+    const int height = 1234;
+    CKey key;
+    key.MakeNewKey(true);
+    const CScript script = GetScriptForDestination(PKHash(key.GetPubKey()));
+
+    const size_t maxNStakes = 4 * AVALANCHE_MAX_PROOF_STAKES;
+
+    ProofPool proofPool{maxNStakes};
+    std::vector<Proof> vProofs;
+
+    const auto testSizeSingleStake = [&](const size_t expectedSize) {
+        BOOST_CHECK_EQUAL(proofPool.getSize(), expectedSize);
+        BOOST_CHECK_EQUAL(proofPool.getNStakes(), expectedSize);
+    };
+
+    // Test filling the pool with single stake proofs
+    for (size_t i = 0; i < maxNStakes + 10; i++) {
+        TxId txid(GetRandHash());
+        ProofBuilder pb(0, 0, CPubKey());
+        pb.addUTXO(COutPoint(txid, 0), v, height, false, key);
+
+        Proof p = pb.build();
+        vProofs.push_back(p);
+        BOOST_CHECK(proofPool.addProof(p));
+
+        BOOST_CHECK(proofPool.getProof(p.getId()));
+
+        BOOST_CHECK_EQUAL(vProofs.size(), i + 1);
+
+        size_t proofPoolSize = i < maxNStakes ? vProofs.size() : maxNStakes;
+        testSizeSingleStake(proofPoolSize);
+
+        Proof oldestProof =
+            i < maxNStakes ? vProofs.front() : vProofs.at(i - maxNStakes + 1);
+        BOOST_CHECK(proofPool.getProof(oldestProof.getId()));
+
+        if (i >= maxNStakes) {
+            Proof latestDrop = vProofs.at(i - maxNStakes);
+            BOOST_CHECK(!proofPool.getProof(latestDrop.getId()));
+        }
+    }
+    size_t currentPoolSize = maxNStakes;
+
+    // remove a proof in the middle
+    BOOST_CHECK(proofPool.removeProof(vProofs.at(42).getId()));
+    testSizeSingleStake(--currentPoolSize);
+    vProofs.erase(vProofs.begin() + 42);
+
+    // remove a proof at the end
+    BOOST_CHECK(proofPool.removeProof(vProofs.back().getId()));
+    testSizeSingleStake(--currentPoolSize);
+    vProofs.pop_back();
+
+    // fail to remove a proof that is longer in the pool
+    BOOST_CHECK(!proofPool.removeProof(vProofs.at(2).getId()));
+    testSizeSingleStake(currentPoolSize);
+
+    // fail to remove a proof that was never in the pool
+    {
+        TxId txid(GetRandHash());
+        ProofBuilder pb(0, 0, CPubKey());
+        pb.addUTXO(COutPoint(txid, 0), v, height, false, key);
+        Proof p = pb.build();
+
+        BOOST_CHECK(!proofPool.getProof(p.getId()));
+        BOOST_CHECK(!proofPool.removeProof(p.getId()));
+        testSizeSingleStake(currentPoolSize);
+    }
+
+    // fail to add a proof that is already in the pool
+    BOOST_CHECK(!proofPool.addProof(vProofs.at(69)));
+    testSizeSingleStake(currentPoolSize);
+
+    // Remove what's left
+    for (auto it = vProofs.end() - 1; currentPoolSize != 0; it--) {
+        BOOST_CHECK(proofPool.removeProof(it->getId()));
+        testSizeSingleStake(--currentPoolSize);
+    }
+
+    testSizeSingleStake(0);
+    vProofs.clear();
+
+    // Now try with proofs using the maximum number of stakes allowed
+    const auto testSizeMultiStakes = [&](const size_t expectedNProofs) {
+        BOOST_CHECK_EQUAL(proofPool.getSize(), expectedNProofs);
+        BOOST_CHECK_EQUAL(proofPool.getNStakes(),
+                          expectedNProofs * AVALANCHE_MAX_PROOF_STAKES);
+    };
+
+    size_t maxNProofs = maxNStakes / AVALANCHE_MAX_PROOF_STAKES;
+    for (size_t i = 0; i < maxNProofs + 3; i++) {
+        ProofBuilder pb(0, 0, CPubKey());
+        for (size_t j = 0; j < AVALANCHE_MAX_PROOF_STAKES; j++) {
+            TxId txid(GetRandHash());
+            pb.addUTXO(COutPoint(txid, 0), v, height, false, key);
+        }
+
+        Proof p = pb.build();
+        vProofs.push_back(p);
+        BOOST_CHECK(proofPool.addProof(p));
+        BOOST_CHECK(proofPool.getProof(p.getId()));
+
+        BOOST_CHECK_EQUAL(vProofs.size(), i + 1);
+
+        size_t expectedNProofs = i < maxNProofs ? i + 1 : maxNProofs;
+        testSizeMultiStakes(expectedNProofs);
+
+        Proof oldestProof =
+            i < maxNProofs ? vProofs.front() : vProofs.at(i + 1 - maxNProofs);
+        BOOST_CHECK(proofPool.getProof(oldestProof.getId()));
+
+        if (i >= maxNProofs) {
+            Proof latestDrop = vProofs.at(i - maxNProofs);
+            BOOST_CHECK(!proofPool.getProof(latestDrop.getId()));
+        }
+    }
+
+    currentPoolSize = maxNProofs;
+
+    // remove a proof in the middle
+    BOOST_CHECK(proofPool.removeProof(vProofs.at(5).getId()));
+    testSizeMultiStakes(--currentPoolSize);
+    vProofs.erase(vProofs.begin() + 5);
+
+    // remove a proof at the end
+    BOOST_CHECK(proofPool.removeProof(vProofs.back().getId()));
+    testSizeMultiStakes(--currentPoolSize);
+    vProofs.pop_back();
+
+    // fail to remove a proof that is longer in the pool
+    BOOST_CHECK(!proofPool.removeProof(vProofs.at(2).getId()));
+    testSizeMultiStakes(currentPoolSize);
+
+    // fail to add a proof that is already in the pool
+    BOOST_CHECK(!proofPool.addProof(vProofs.at(3)));
+    testSizeMultiStakes(currentPoolSize);
+
+    // Remove what's left
+    for (auto it = vProofs.end() - 1; currentPoolSize != 0; it--) {
+        BOOST_CHECK(proofPool.removeProof(it->getId()));
+        testSizeMultiStakes(--currentPoolSize);
+    }
+
+    testSizeMultiStakes(0);
+}
+
+BOOST_AUTO_TEST_SUITE_END()