diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -539,6 +539,7 @@
 	addrman.cpp
 	avalanche/delegation.cpp
 	avalanche/delegationbuilder.cpp
+	avalanche/orphanproofpool.cpp
 	avalanche/peermanager.cpp
 	avalanche/processor.cpp
 	avalanche/proof.cpp
diff --git a/src/avalanche/orphanproofpool.h b/src/avalanche/orphanproofpool.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/orphanproofpool.h
@@ -0,0 +1,78 @@
+// 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_ORPHANPROOFPOOL_H
+#define BITCOIN_AVALANCHE_ORPHANPROOFPOOL_H
+
+#include <avalanche/proof.h>
+
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/multi_index_container.hpp>
+
+namespace avalanche {
+
+// Extracts a ProofId from a Proof
+struct proofid_extractor {
+    using result_type = ProofId;
+    result_type operator()(const Proof &proof) const { return proof.getId(); }
+};
+
+struct by_sequence {};
+struct by_proofid {};
+
+using ProofContainer = 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>>>;
+
+/**
+ * OrphanProofPool stores orphan proofs waiting for their UTXOs to be
+ * discovered.
+ * The pool has a size limit. When the pool is full, the oldest proof is
+ * removed when a new one is added.
+ */
+class OrphanProofPool {
+    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() noexcept;
+
+public:
+    OrphanProofPool(size_t maxNumberOfStakes)
+        : maxNumberOfStakes(maxNumberOfStakes) {}
+
+    /**
+     * Add a proof to the pool.
+     * The caller is responsible for checking the proof.
+     */
+    bool addProof(Proof proof);
+
+    /** Remove a proof from the pool. */
+    bool removeProof(const ProofId &proofId);
+
+    /**
+     * Get a pointer to a proof by id, or nullptr if the proof is not in the
+     * pool.
+     */
+    const Proof *getProof(ProofId proofId) const;
+
+    // For testing
+    size_t getNProofs() const;
+    size_t getNStakes() const;
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_ORPHANPROOFPOOL_H
diff --git a/src/avalanche/orphanproofpool.cpp b/src/avalanche/orphanproofpool.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/orphanproofpool.cpp
@@ -0,0 +1,52 @@
+// 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/orphanproofpool.h>
+
+namespace avalanche {
+
+void OrphanProofPool::trimToMaximumSize() noexcept {
+    auto &proofs_by_sequence = proofs.get<by_sequence>();
+    auto it = proofs_by_sequence.begin();
+    while (nStakes > maxNumberOfStakes) {
+        nStakes -= it->getStakes().size();
+        it = proofs_by_sequence.erase(it);
+    }
+}
+
+bool OrphanProofPool::addProof(Proof proof) {
+    if (!proofs.push_back(proof).second) {
+        return false;
+    }
+    nStakes += proof.getStakes().size();
+    trimToMaximumSize();
+    return true;
+}
+
+bool OrphanProofPool::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 -= it->getStakes().size();
+    proofs_by_id.erase(it);
+    return true;
+}
+
+const Proof *OrphanProofPool::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;
+}
+
+size_t OrphanProofPool::getNProofs() const {
+    return proofs.size();
+}
+
+size_t OrphanProofPool::getNStakes() const {
+    return nStakes;
+}
+
+} // namespace avalanche
diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -77,13 +77,6 @@
     result_type operator()(const Peer &p) const { return p.proof.getId(); }
 };
 
-class SaltedProofIdHasher : private SaltedUint256Hasher {
-public:
-    SaltedProofIdHasher() : SaltedUint256Hasher() {}
-
-    size_t operator()(const ProofId &proofid) const { return hash(proofid); }
-};
-
 struct next_request_time {};
 
 class PeerManager {
diff --git a/src/avalanche/proofid.h b/src/avalanche/proofid.h
--- a/src/avalanche/proofid.h
+++ b/src/avalanche/proofid.h
@@ -5,6 +5,7 @@
 #ifndef BITCOIN_AVALANCHE_PROOFID_H
 #define BITCOIN_AVALANCHE_PROOFID_H
 
+#include <salteduint256hasher.h>
 #include <uint256.h>
 
 #include <string>
@@ -21,6 +22,13 @@
         return r;
     }
 };
+
+class SaltedProofIdHasher : private SaltedUint256Hasher {
+public:
+    SaltedProofIdHasher() : SaltedUint256Hasher() {}
+    size_t operator()(const ProofId &proofid) const { return hash(proofid); }
+};
+
 } // namespace avalanche
 
 #endif // BITCOIN_AVALANCHE_PROOFID_H
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
@@ -14,6 +14,7 @@
 
 	TESTS
 		delegation_tests.cpp
+		orphanproofpool_tests.cpp
 		peermanager_tests.cpp
 		processor_tests.cpp
 		proof_tests.cpp
diff --git a/src/avalanche/test/orphanproofpool_tests.cpp b/src/avalanche/test/orphanproofpool_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/test/orphanproofpool_tests.cpp
@@ -0,0 +1,181 @@
+// 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/orphanproofpool.h>
+#include <avalanche/proofbuilder.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(orphanproofpool_tests, TestingSetup)
+
+/** Make a proof with stakes using random txids */
+Proof makeProof(const size_t nStakes) {
+    const Amount v = 5 * COIN;
+    const int height = 1234;
+    CKey key;
+    key.MakeNewKey(true);
+    const CScript script = GetScriptForDestination(PKHash(key.GetPubKey()));
+    ProofBuilder pb(0, 0, CPubKey());
+    for (size_t i = 0; i < nStakes; i++) {
+        TxId txid(GetRandHash());
+        pb.addUTXO(COutPoint(txid, 0), v, height, false, key);
+    }
+    return pb.build();
+}
+
+/** Check number of proofs and number of stakes in the pool */
+void checkPoolSize(const OrphanProofPool pool, const size_t expectedNProofs,
+                   const size_t stakesPerProof) {
+    BOOST_CHECK_EQUAL(pool.getNProofs(), expectedNProofs);
+    BOOST_CHECK_EQUAL(pool.getNStakes(), expectedNProofs * stakesPerProof);
+}
+
+// Fill the pool with constant size proofs
+BOOST_AUTO_TEST_CASE(proofpool_add) {
+    std::vector<size_t> maxPoolSizes{1000, 1001, 1337};
+    std::vector<size_t> proofSizes{1, 2, 42, AVALANCHE_MAX_PROOF_STAKES - 1,
+                                   AVALANCHE_MAX_PROOF_STAKES};
+    for (size_t proofSize : proofSizes) {
+        for (size_t maxPoolSize : maxPoolSizes) {
+            OrphanProofPool pool{maxPoolSize};
+            std::vector<Proof> vProofs;
+
+            // Fill the pool
+            size_t maxNProofs = maxPoolSize / proofSize;
+            for (size_t i = 0; i < maxNProofs; i++) {
+                Proof p = makeProof(proofSize);
+                vProofs.push_back(p);
+
+                BOOST_CHECK(pool.addProof(p));
+                BOOST_CHECK(pool.getProof(p.getId()));
+                checkPoolSize(pool, i + 1, proofSize);
+
+                // Check that the first proof is still in the pool
+                BOOST_CHECK(pool.getProof(vProofs[0].getId()));
+            }
+
+            // Add 10 more, verify the overflow behavior
+            for (size_t i = 0; i < 10; i++) {
+                Proof p = makeProof(proofSize);
+                vProofs.push_back(p);
+
+                // We can still add new proofs
+                BOOST_CHECK(pool.addProof(p));
+                BOOST_CHECK(pool.getProof(p.getId()));
+
+                // but the number of proofs in the pool no longer increases
+                checkPoolSize(pool, maxNProofs, proofSize);
+
+                // and the oldest proof has been dropped
+                BOOST_CHECK(!pool.getProof(vProofs[i].getId()));
+                BOOST_CHECK(pool.getProof(vProofs[i + 1].getId()));
+            }
+
+            // Fail to add a proof that is already in the pool
+            BOOST_CHECK(!pool.addProof(vProofs.at(10)));
+            checkPoolSize(pool, maxNProofs, proofSize);
+        }
+    }
+}
+
+// Fill the pool with proofs of various sizes
+BOOST_AUTO_TEST_CASE(proofpool_add_variable_size) {
+    const size_t maxPoolSize = 1337;
+    OrphanProofPool pool{maxPoolSize};
+
+    size_t nStakes = 1;
+    size_t proofSize = 1;
+    size_t nProofs = 0;
+
+    // Fill the pool with proofs of various sizes
+    while (nStakes <= maxPoolSize) {
+        nProofs++;
+        Proof p = makeProof(proofSize);
+        BOOST_CHECK(pool.addProof(p));
+        BOOST_CHECK(pool.getProof(p.getId()));
+        BOOST_CHECK_EQUAL(pool.getNStakes(), nStakes);
+        BOOST_CHECK_EQUAL(pool.getNProofs(), nProofs);
+
+        proofSize = (proofSize + 1) % AVALANCHE_MAX_PROOF_STAKES;
+        nStakes += proofSize;
+    }
+
+    // Add 1 more large proof, verify the overflow behavior
+    Proof p = makeProof(999);
+    BOOST_CHECK(pool.addProof(p));
+    BOOST_CHECK(pool.getProof(p.getId()));
+
+    // The number of proofs in the pool no longer increases
+    BOOST_CHECK(pool.getNStakes() <= maxPoolSize);
+    // and quite a few proofs had to be dropped to make room for this one
+    BOOST_CHECK(pool.getNProofs() < nProofs);
+}
+
+BOOST_AUTO_TEST_CASE(proofpool_remove) {
+    OrphanProofPool pool{1337};
+    std::vector<Proof> vProofs;
+    const size_t stakesPerProof = 42;
+
+    // Add a few proofs
+    for (size_t i = 0; i < 10; i++) {
+        Proof p = makeProof(stakesPerProof);
+        vProofs.push_back(p);
+        BOOST_CHECK(pool.addProof(p));
+    }
+
+    // Remove a proof in the middle
+    BOOST_CHECK(pool.removeProof(vProofs.at(5).getId()));
+    checkPoolSize(pool, 9, stakesPerProof);
+    ProofId deletedProofId = vProofs[5].getId();
+    vProofs.erase(vProofs.begin() + 5);
+
+    // Remove a proof at the front
+    BOOST_CHECK(pool.removeProof(vProofs.front().getId()));
+    checkPoolSize(pool, 8, stakesPerProof);
+    vProofs.erase(vProofs.begin());
+
+    // Remove a proof at the back
+    BOOST_CHECK(pool.removeProof(vProofs.back().getId()));
+    checkPoolSize(pool, 7, stakesPerProof);
+    vProofs.erase(vProofs.end());
+
+    // Fail to remove a proof that is longer in the pool
+    BOOST_CHECK(!pool.removeProof(deletedProofId));
+    checkPoolSize(pool, 7, stakesPerProof);
+
+    // Fail to remove a proof that was never in the pool
+    {
+        Proof p = makeProof(stakesPerProof);
+        BOOST_CHECK(!pool.getProof(p.getId()));
+        BOOST_CHECK(!pool.removeProof(p.getId()));
+        checkPoolSize(pool, 7, stakesPerProof);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(small_proofpool) {
+    OrphanProofPool pool{AVALANCHE_MAX_PROOF_STAKES - 1};
+
+    // Add a couple of small proofs
+    BOOST_CHECK(pool.addProof(makeProof(1)));
+    BOOST_CHECK_EQUAL(pool.getNStakes(), 1);
+    BOOST_CHECK_EQUAL(pool.getNProofs(), 1);
+
+    BOOST_CHECK(pool.addProof(makeProof(2)));
+    BOOST_CHECK_EQUAL(pool.getNStakes(), 3);
+    BOOST_CHECK_EQUAL(pool.getNProofs(), 2);
+
+    // Add a proof that is larger than the pool
+    BOOST_CHECK(pool.addProof(makeProof(AVALANCHE_MAX_PROOF_STAKES)));
+    BOOST_CHECK_EQUAL(pool.getNStakes(), 0);
+    BOOST_CHECK_EQUAL(pool.getNProofs(), 0);
+}
+
+BOOST_AUTO_TEST_SUITE_END()