diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -85,6 +85,14 @@
 };
 
 struct next_request_time {};
+struct expiration_time {};
+
+class CompareProofByExpirationTime {
+public:
+    bool operator()(const Proof &a, const Proof &b) const {
+        return a.getExpirationTime() < b.getExpirationTime();
+    }
+};
 
 class PeerManager {
     std::vector<Slot> slots;
@@ -127,6 +135,21 @@
 
     NodeSet nodes;
 
+    using ProofPool = boost::multi_index_container<
+        Proof, boost::multi_index::indexed_by<
+                   // index by proofid
+                   boost::multi_index::hashed_unique<
+                       boost::multi_index::tag<proof_index>, proof_index,
+                       SaltedProofIdHasher>,
+                   // sorted by expiration time
+                   boost::multi_index::ordered_non_unique<
+                       boost::multi_index::tag<expiration_time>,
+                       boost::multi_index::identity<Proof>,
+                       CompareProofByExpirationTime>>>;
+
+    /** Pool of proofs not associated with any known node */
+    ProofPool unassignedProofs;
+
     static constexpr int SELECT_PEER_MAX_RETRY = 3;
     static constexpr int SELECT_NODE_MAX_RETRY = 3;
 
@@ -188,6 +211,9 @@
     std::vector<Peer> getPeers() const;
     std::vector<NodeId> getNodeIdsForPeer(PeerId peerId) const;
 
+    /** Return true if we already have this proof */
+    bool hasProof(const ProofId proofId) const;
+
 private:
     PeerSet::iterator fetchOrCreatePeer(const Proof &proof);
     bool addNodeToPeer(const PeerSet::iterator &it);
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -456,4 +456,14 @@
     return nodeids;
 }
 
+bool PeerManager::hasProof(const ProofId proofId) const {
+    auto &peerView = peers.get<proof_index>();
+    auto peerIt = peerView.find(proofId);
+
+    auto &proofView = unassignedProofs.get<proof_index>();
+    auto proofIt = proofView.find(proofId);
+
+    return (peerIt != peerView.end() || proofIt != proofView.end());
+}
+
 } // namespace avalanche
diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h
--- a/src/avalanche/processor.h
+++ b/src/avalanche/processor.h
@@ -304,6 +304,9 @@
     std::vector<avalanche::Peer> getPeers() const;
     std::vector<NodeId> getNodeIdsForPeer(PeerId peerId) const;
 
+    /** Return true if we already have this proof. */
+    bool hasProof(const ProofId proofId) const;
+
     bool startEventLoop(CScheduler &scheduler);
     bool stopEventLoop();
 
diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp
--- a/src/avalanche/processor.cpp
+++ b/src/avalanche/processor.cpp
@@ -621,4 +621,9 @@
     return peerManager->getNodeIdsForPeer(peerId);
 }
 
+bool Processor::hasProof(const ProofId proofId) const {
+    LOCK(cs_peerManager);
+    return peerManager->hasProof(proofId);
+}
+
 } // namespace avalanche
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -1742,6 +1742,15 @@
 
             return recentRejects->contains(txid) || mempool.exists(txid);
         }
+        case MSG_AVA_PROOF: {
+            if (!gArgs.GetBoolArg("-enableavalanche",
+                                  AVALANCHE_DEFAULT_ENABLED)) {
+                // We are not interested, just say we already got it
+                return true;
+            }
+            const avalanche::ProofId proofid(inv.hash);
+            return g_avalanche->hasProof(proofid);
+        }
         case MSG_BLOCK:
             return LookupBlockIndex(BlockHash(inv.hash)) != nullptr;
     }