diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -543,6 +543,7 @@
 	avalanche/processor.cpp
 	avalanche/proof.cpp
 	avalanche/proofbuilder.cpp
+	avalanche/proofpool.cpp
 	banman.cpp
 	blockencodings.cpp
 	blockfilter.cpp
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,65 @@
+// 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 <list>
+#include <map>
+
+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;
+
+typedef std::map<ProofId, Proof> ProofMap;
+
+/**
+ * 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 {
+    ProofMap proofs;
+
+    /**
+     * Queue that remembers the insertion order of proofs into the ProofMap.
+     * We keep this limited to a size of MAX_NUMBER_OF_PROOFS, and pop the
+     * oldest proof when adding a new one after reaching this limit.
+     *
+     * We also need to be able to remove proofs in the middle of the queue,
+     * on demand.
+     */
+    std::list<ProofMap::iterator> insertionQueue;
+
+public:
+    /**
+     * 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(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
+    bool checkInternalConsistency() const;
+    size_t getSize() const;
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_PROOFPOOL_H
diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/proofpool.cpp
@@ -0,0 +1,67 @@
+// 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/proofpool.h>
+
+#include <algorithm>
+
+namespace avalanche {
+
+bool ProofPool::addProof(Proof proof) {
+    auto p = proofs.insert(std::make_pair(proof.getId(), proof));
+
+    if (!p.second) {
+        // We already have it
+        return false;
+    }
+
+    if (proofs.size() > PROOF_POOL_MAX_SIZE) {
+        proofs.erase(insertionQueue.front());
+        insertionQueue.pop_front();
+    }
+
+    insertionQueue.push_back(p.first);
+    return true;
+}
+
+bool ProofPool::removeProof(ProofId proofId) {
+    auto it = proofs.find(proofId);
+    if (it != proofs.end()) {
+        insertionQueue.remove(it);
+        proofs.erase(it);
+        return true;
+    }
+    return false;
+}
+
+const Proof *ProofPool::getProof(ProofId proofId) const {
+    auto it = proofs.find(proofId);
+    if (it == proofs.end()) {
+        return nullptr;
+    }
+    return &it->second;
+}
+
+bool ProofPool::checkInternalConsistency() const {
+    // container sizes must be identical
+    if (proofs.size() != insertionQueue.size() ||
+        insertionQueue.size() > PROOF_POOL_MAX_SIZE) {
+        return false;
+    }
+
+    // insertionQueue must contain the same elements as proofs
+    for (auto it = proofs.begin(); it != proofs.end(); it++) {
+        if (std::find(insertionQueue.begin(), insertionQueue.end(), it) ==
+            insertionQueue.end()) {
+            return false;
+        }
+    }
+    return true;
+}
+
+size_t ProofPool::getSize() const {
+    return proofs.size();
+}
+
+} // 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
@@ -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,101 @@
+// 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()));
+        }
+
+        BOOST_CHECK(proofPool.checkInternalConsistency());
+    }
+    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);
+    BOOST_CHECK(proofPool.checkInternalConsistency());
+    vProofs.erase(vProofs.begin() + 42);
+
+    // remove a proof at the end
+    BOOST_CHECK(proofPool.removeProof(vProofs.back().getId()));
+    BOOST_CHECK_EQUAL(proofPool.getSize(), --currentPoolSize);
+    BOOST_CHECK(proofPool.checkInternalConsistency());
+    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);
+    BOOST_CHECK(proofPool.checkInternalConsistency());
+
+    // 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);
+    BOOST_CHECK(proofPool.checkInternalConsistency());
+
+    // 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(proofPool.checkInternalConsistency());
+    }
+
+    BOOST_CHECK_EQUAL(proofPool.getSize(), 0);
+}
+
+BOOST_AUTO_TEST_SUITE_END()