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,104 @@
+// 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 {
+
+/**
+ * In a worst case scenario, if all proofs have 1000 utxos, 500 proofs
+ * amounts to about 100 MB of memory.
+ */
+static constexpr size_t PROOF_POOL_MAX_SIZE = 500;
+
+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;
+
+    /**
+     *  Trim the proof pool to given max size.
+     *  It the current size is <= max size this has no effect.
+     *  @param max_size The maximum size of the proof pool
+     *  @return bool True on success
+     */
+    bool trimToSize(size_t max_size) {
+        assert(max_size > 0);
+        auto &proofs_by_sequence = proofs.get<by_sequence>();
+        if (max_size >= proofs_by_sequence.size()) {
+            return true;
+        }
+        proofs_by_sequence.resize(max_size);
+        return proofs_by_sequence.size() <= max_size;
+    }
+
+public:
+    /**
+     * Add a proof to the pool.
+     * The caller is responsible for checking the proof.
+     */
+    bool addProof(const Proof &proof) {
+        return trimToSize(PROOF_POOL_MAX_SIZE - 1) &&
+               proofs.get<by_sequence>().push_front(proof).second;
+    }
+
+    /** Remove a proof from the pool. */
+    bool removeProof(const ProofId &proofId) {
+        return proofs.get<by_proofid>().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(); }
+};
+
+} // 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,94 @@
+// 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()));
+
+    ProofPool proofPool;
+    std::vector<Proof> vProofs;
+
+    for (size_t i = 0; i < PROOF_POOL_MAX_SIZE + 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);
+        BOOST_CHECK_EQUAL(proofPool.getSize(), i < PROOF_POOL_MAX_SIZE
+                                                   ? vProofs.size()
+                                                   : PROOF_POOL_MAX_SIZE);
+
+        Proof oldestProof = i < PROOF_POOL_MAX_SIZE
+                                ? vProofs.front()
+                                : vProofs.at(i - PROOF_POOL_MAX_SIZE + 1);
+        BOOST_CHECK(proofPool.getProof(oldestProof.getId()));
+
+        if (i >= PROOF_POOL_MAX_SIZE) {
+            Proof latestDrop = vProofs.at(i - PROOF_POOL_MAX_SIZE);
+            BOOST_CHECK(!proofPool.getProof(latestDrop.getId()));
+        }
+    }
+    size_t currentPoolSize = PROOF_POOL_MAX_SIZE;
+
+    // remove a proof in the middle
+    BOOST_CHECK(proofPool.removeProof(vProofs.at(42).getId()));
+    BOOST_CHECK_EQUAL(proofPool.getSize(), --currentPoolSize);
+    vProofs.erase(vProofs.begin() + 42);
+
+    // remove a proof at the end
+    BOOST_CHECK(proofPool.removeProof(vProofs.back().getId()));
+    BOOST_CHECK_EQUAL(proofPool.getSize(), --currentPoolSize);
+    vProofs.pop_back();
+
+    // attempt to remove a proof that is longer in the pool
+    BOOST_CHECK(!proofPool.removeProof(vProofs.at(2).getId()));
+    BOOST_CHECK_EQUAL(proofPool.getSize(), 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()));
+    BOOST_CHECK_EQUAL(proofPool.getSize(), currentPoolSize);
+
+    // fail to add a proof that is already in the pool
+    BOOST_CHECK(!proofPool.addProof(vProofs.at(69)));
+    BOOST_CHECK_EQUAL(proofPool.getSize(), currentPoolSize);
+
+    // Remove what's left
+    for (auto it = vProofs.end() - 1; currentPoolSize != 0; it--) {
+        BOOST_CHECK(proofPool.removeProof(it->getId()));
+        BOOST_CHECK_EQUAL(proofPool.getSize(), --currentPoolSize);
+    }
+
+    BOOST_CHECK_EQUAL(proofPool.getSize(), 0);
+}
+
+BOOST_AUTO_TEST_SUITE_END()