diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -127,6 +127,9 @@
 
     NodeSet nodes;
 
+    /** Pool of proofs not associated with any known node */
+    std::map<ProofId, Proof> orphanProofs;
+
     static constexpr int SELECT_PEER_MAX_RETRY = 3;
     static constexpr int SELECT_NODE_MAX_RETRY = 3;
 
@@ -188,6 +191,10 @@
     std::vector<Peer> getPeers() const;
     std::vector<NodeId> getNodeIdsForPeer(PeerId peerId) const;
 
+    const Proof *getProof(const ProofId proofId) const;
+
+    bool addProof(Proof &&proof);
+
 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,38 @@
     return nodeids;
 }
 
+const Proof *PeerManager::getProof(const ProofId proofId) const {
+    auto &peerView = peers.get<proof_index>();
+    auto peerIt = peerView.find(proofId);
+    if (peerIt != peerView.end()) {
+        return &peerIt->proof;
+    }
+
+    auto proofIt = orphanProofs.find(proofId);
+    if (proofIt != orphanProofs.end()) {
+        return &proofIt->second;
+    }
+    return nullptr;
+}
+
+bool PeerManager::addProof(Proof &&proof) {
+    ProofValidationState state;
+    const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
+    bool success = proof.verify(state, coins);
+
+    if (success) {
+        // Good proof, store the proof in a new peer
+        return fetchOrCreatePeer(proof) != peers.end();
+    }
+
+    if (state.GetResult() == ProofValidationResult::MISSING_UTXO) {
+        // Maybe it can become valid later
+        return orphanProofs
+            .insert(std::make_pair(proof.getId(), std::move(proof)))
+            .second;
+    }
+
+    return false;
+}
+
 } // namespace avalanche
diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h
--- a/src/avalanche/processor.h
+++ b/src/avalanche/processor.h
@@ -299,11 +299,17 @@
      * @returns Proof for this node.
      * @throws a std::runtime_error if there is no proof set for this node
      */
-    const Proof getProof() const;
+    const Proof getLocalProof() const;
 
     std::vector<avalanche::Peer> getPeers() const;
     std::vector<NodeId> getNodeIdsForPeer(PeerId peerId) const;
 
+    /** Verify and add a proof. Return true in case of success. */
+    bool addProof(Proof &&proof);
+
+    /** Return a pointer to a proof or nullptr if we don't have it */
+    const Proof *getProof(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
@@ -444,7 +444,7 @@
     return true;
 }
 
-const Proof Processor::getProof() const {
+const Proof Processor::getLocalProof() const {
     if (!peerData) {
         throw std::runtime_error("proof not set");
     }
@@ -621,4 +621,14 @@
     return peerManager->getNodeIdsForPeer(peerId);
 }
 
+const Proof *Processor::getProof(const ProofId proofId) const {
+    LOCK(cs_peerManager);
+    return peerManager->getProof(proofId);
+}
+
+bool Processor::addProof(Proof &&proof) {
+    LOCK(cs_peerManager);
+    return peerManager->addProof(std::move(proof));
+}
+
 } // 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->getProof(proofid) != nullptr;
+        }
         case MSG_BLOCK:
             return LookupBlockIndex(BlockHash(inv.hash)) != nullptr;
     }