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,20 @@
     ProofPool conflictingProofPool;
     ProofPool orphanProofPool;
 
+public:
+    struct ProofElement {
+        ProofRef proof;
+
+        ProofElement(const ProofRef &proofIn) : proof(proofIn) {}
+
+        Uint256KeyWrapper getId() const { return proof->getId(); }
+
+        IMPLEMENT_RCU_REFCOUNT(uint64_t);
+    };
+
+private:
+    RadixTree<ProofElement> shareableProofs;
+
     using NodeSet = boost::multi_index_container<
         Node,
         bmi::indexed_by<
@@ -356,6 +372,10 @@
     bool isOrphan(const ProofId &proofid) const;
     bool isInConflictingPool(const ProofId &proofid) const;
 
+    RadixTree<ProofElement> getShareableProofsSnapshot() const {
+        return shareableProofs;
+    }
+
 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 =
+        shareableProofs.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 = shareableProofs.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 (shareableProofs.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;
+    shareableProofs.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,122 @@
     checkScores(0, 0);
 }
 
+BOOST_FIXTURE_TEST_CASE(proof_radix_tree, NoCoolDownFixture) {
+    avalanche::PeerManager pm;
+
+    gArgs.ForceSetArg("-enableavalancheproofreplacement", "1");
+
+    struct ProofComparatorById {
+        bool operator()(const ProofRef &lhs, const ProofRef &rhs) const {
+            return lhs->getId() < rhs->getId();
+        };
+    };
+    using ProofSetById = std::set<ProofRef, ProofComparatorById>;
+    // Maintain a list of the expected proofs through this test
+    ProofSetById expectedProofs;
+
+    auto matchExpectedContent = [&](const auto &tree) {
+        bool matchExpectedProofSet = true;
+
+        auto it = expectedProofs.begin();
+        tree.forEachLeaf([&](auto pLeaf) {
+            if (it == expectedProofs.end() || pLeaf->proof != *it++) {
+                matchExpectedProofSet = false;
+            }
+        });
+
+        return matchExpectedProofSet;
+    };
+
+    CKey key = CKey::MakeCompressedKey();
+    const int64_t sequence = 10;
+
+    // Add some initial proofs
+    for (size_t i = 0; i < 10; i++) {
+        auto outpoint = createUtxo(key);
+        auto proof = buildProofWithSequence(key, {{outpoint}}, sequence);
+        BOOST_CHECK(pm.registerProof(proof));
+        expectedProofs.insert(std::move(proof));
+    }
+
+    auto tree = pm.getShareableProofsSnapshot();
+    BOOST_CHECK(matchExpectedContent(tree));
+
+    // Adding more proofs doesn't change the tree...
+    ProofSetById addedProofs;
+    std::vector<COutPoint> outpointsToSpend;
+    for (size_t i = 0; i < 10; i++) {
+        auto outpoint = createUtxo(key);
+        auto proof = buildProofWithSequence(key, {{outpoint}}, sequence);
+        BOOST_CHECK(pm.registerProof(proof));
+        addedProofs.insert(std::move(proof));
+        outpointsToSpend.push_back(std::move(outpoint));
+    }
+
+    BOOST_CHECK(matchExpectedContent(tree));
+
+    // ...until we get a new copy
+    tree = pm.getShareableProofsSnapshot();
+    expectedProofs.insert(addedProofs.begin(), addedProofs.end());
+    BOOST_CHECK(matchExpectedContent(tree));
+
+    // Spend some coins to make the associated proofs invalid
+    {
+        LOCK(cs_main);
+        CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
+        for (const auto &outpoint : outpointsToSpend) {
+            coins.SpendCoin(outpoint);
+        }
+    }
+
+    pm.updatedBlockTip();
+
+    // This doesn't change the tree...
+    BOOST_CHECK(matchExpectedContent(tree));
+
+    // ...until we get a new copy
+    tree = pm.getShareableProofsSnapshot();
+    for (const auto &proof : addedProofs) {
+        BOOST_CHECK_EQUAL(expectedProofs.erase(proof), 1);
+    }
+    BOOST_CHECK(matchExpectedContent(tree));
+
+    // Add some more proof for which we will create conflicts
+    std::vector<ProofRef> conflictingProofs;
+    std::vector<COutPoint> conflictingOutpoints;
+    for (size_t i = 0; i < 10; i++) {
+        auto outpoint = createUtxo(key);
+        auto proof = buildProofWithSequence(key, {{outpoint}}, sequence);
+        BOOST_CHECK(pm.registerProof(proof));
+        conflictingProofs.push_back(std::move(proof));
+        conflictingOutpoints.push_back(std::move(outpoint));
+    }
+
+    tree = pm.getShareableProofsSnapshot();
+    expectedProofs.insert(conflictingProofs.begin(), conflictingProofs.end());
+    BOOST_CHECK(matchExpectedContent(tree));
+
+    // Build a bunch of conflicting proofs, half better, half worst
+    for (size_t i = 0; i < 10; i += 2) {
+        // The worst proof is not added to the expected set
+        BOOST_CHECK(!pm.registerProof(buildProofWithSequence(
+            key, {{conflictingOutpoints[i]}}, sequence - 1)));
+
+        // But the better proof should replace its conflicting one
+        auto replacementProof = buildProofWithSequence(
+            key, {{conflictingOutpoints[i + 1]}}, sequence + 1);
+        BOOST_CHECK(pm.registerProof(replacementProof));
+        BOOST_CHECK_EQUAL(expectedProofs.erase(conflictingProofs[i + 1]), 1);
+        BOOST_CHECK(expectedProofs.insert(replacementProof).second);
+    }
+
+    tree = pm.getShareableProofsSnapshot();
+    BOOST_CHECK(matchExpectedContent(tree));
+
+    // Check for consistency
+    pm.verify();
+
+    gArgs.ClearForcedArg("-enableavalancheproofreplacement");
+}
+
 BOOST_AUTO_TEST_SUITE_END()