diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -11,6 +11,8 @@
 #include <coins.h>
 #include <consensus/validation.h>
 #include <pubkey.h>
+#include <radix.h>
+#include <rcu.h>
 #include <salteduint256hasher.h>
 #include <util/time.h>
 
@@ -155,6 +157,17 @@
     ProofPool conflictingProofPool;
     ProofPool orphanProofPool;
 
+    struct ProofElement {
+        ProofRef proof;
+
+        ProofElement(const ProofRef &proofIn) : proof(proofIn) {}
+
+        Uint256KeyWrapper getId() const { return proof->getId(); }
+
+        IMPLEMENT_RCU_REFCOUNT(uint64_t);
+    };
+    RadixTree<ProofElement> proofRadixTree;
+
     using NodeSet = boost::multi_index_container<
         Node,
         bmi::indexed_by<
@@ -356,6 +369,8 @@
     bool isOrphan(const ProofId &proofid) const;
     bool isInConflictingPool(const ProofId &proofid) const;
 
+    RadixTree<ProofElement> getProofRadixTree() const { return proofRadixTree; }
+
 private:
     template <typename ProofContainer>
     void moveToConflictingPool(const ProofContainer &proofs);
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -313,6 +313,11 @@
     auto inserted = peers.emplace(peerid, proof, nextCooldownTimePoint);
     assert(inserted.second);
 
+    auto insertedRadixTree =
+        proofRadixTree.insert(RCUPtr<ProofElement>::make(proof));
+    assert(insertedRadixTree);
+    RCULock::synchronize();
+
     // Add to our registered score when adding to the peer list
     totalPeersScore += proof->getScore();
 
@@ -503,6 +508,10 @@
     // Release UTXOs attached to this proof.
     validProofPool.removeProof(it->getProofId());
 
+    auto removed = proofRadixTree.remove(Uint256KeyWrapper(it->getProofId()));
+    assert(removed != nullptr);
+    RCULock::synchronize();
+
     m_unbroadcast_proofids.erase(it->getProofId());
 
     // Remove the peer from the PeerSet and remove its score from the registered
@@ -662,6 +671,11 @@
         if (slots[p.index].getScore() != p.getScore()) {
             return false;
         }
+
+        // Check the proof is in the radix tree
+        if (proofRadixTree.get(p.getProofId()) == nullptr) {
+            return false;
+        }
     }
 
     // Check our accumulated scores against our registred and allocated scores
@@ -678,7 +692,15 @@
         return false;
     }
 
-    return true;
+    // Check there is no dangling proof in the radix tree
+    bool danglingProofInRadixTree = false;
+    proofRadixTree.forEachLeaf([&](RCUPtr<ProofElement> pLeaf) {
+        if (!isBoundToPeer(pLeaf->proof->getId())) {
+            danglingProofInRadixTree = true;
+        }
+    });
+
+    return !danglingProofInRadixTree;
 }
 
 PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp
--- a/src/avalanche/test/peermanager_tests.cpp
+++ b/src/avalanche/test/peermanager_tests.cpp
@@ -1626,4 +1626,81 @@
     checkScores(0, 0);
 }
 
+BOOST_FIXTURE_TEST_CASE(proof_radix_tree, NoCoolDownFixture) {
+    avalanche::PeerManager pm;
+
+    gArgs.ForceSetArg("-enableavalancheproofreplacement", "1");
+
+    auto countRadixTreeLeaves = [&](const auto &tree) {
+        size_t count = 0;
+
+        tree.forEachLeaf([&](auto pLeaf) { ++count; });
+
+        return count;
+    };
+
+    CKey key = CKey::MakeCompressedKey();
+    const int64_t sequence = 10;
+
+    std::vector<COutPoint> outpoints;
+    for (size_t i = 0; i < 10; i++) {
+        auto outpoint = createUtxo(key);
+        BOOST_CHECK(pm.registerProof(
+            buildProofWithSequence(key, {{outpoint}}, sequence)));
+        outpoints.push_back(std::move(outpoint));
+    }
+
+    auto tree = pm.getProofRadixTree();
+    BOOST_CHECK_EQUAL(countRadixTreeLeaves(tree), 10);
+
+    // Adding more proofs doesn't change the tree...
+    for (size_t i = 0; i < 10; i++) {
+        auto outpoint = createUtxo(key);
+        BOOST_CHECK(pm.registerProof(
+            buildProofWithSequence(key, {{outpoint}}, sequence)));
+        outpoints.push_back(std::move(outpoint));
+    }
+
+    BOOST_CHECK_EQUAL(countRadixTreeLeaves(tree), 10);
+
+    // ...until we get a new copy
+    tree = pm.getProofRadixTree();
+    BOOST_CHECK_EQUAL(countRadixTreeLeaves(tree), 20);
+
+    // Spend some coin to make the associated proofs invalid
+    {
+        LOCK(cs_main);
+        CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
+        for (size_t i = 0; i < 10; i++) {
+            coins.SpendCoin(outpoints.back());
+            outpoints.pop_back();
+        }
+    }
+
+    pm.updatedBlockTip();
+
+    // This doesn't change the tree...
+    BOOST_CHECK_EQUAL(countRadixTreeLeaves(tree), 20);
+    // ...until we get a new copy
+    tree = pm.getProofRadixTree();
+    BOOST_CHECK_EQUAL(countRadixTreeLeaves(tree), 10);
+
+    // Build a bunch of conflicting proofs, half better, half worst
+    for (size_t i = 0; i < 10; i += 2) {
+        BOOST_CHECK(!pm.registerProof(
+            buildProofWithSequence(key, {{outpoints[i]}}, sequence - 1)));
+        BOOST_CHECK(pm.registerProof(
+            buildProofWithSequence(key, {{outpoints[i + 1]}}, sequence + 1)));
+    }
+
+    // The count is still the same
+    tree = pm.getProofRadixTree();
+    BOOST_CHECK_EQUAL(countRadixTreeLeaves(tree), 10);
+
+    // Check for consistency
+    pm.verify();
+
+    gArgs.ClearForcedArg("-enableavalancheproofreplacement");
+}
+
 BOOST_AUTO_TEST_SUITE_END()