diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -7,6 +7,7 @@
 
 #include <avalanche/node.h>
 #include <avalanche/proof.h>
+#include <bloom.h>
 #include <coins.h>
 #include <net.h>
 #include <pubkey.h>
@@ -127,10 +128,18 @@
 
     NodeSet nodes;
 
+    /** Pool of proofs using orphan UTXOs as stake */
+    std::map<ProofId, Proof> orphanProofs;
+
+    /** Filter of recently rejected proofs */
+    std::unique_ptr<CRollingBloomFilter> recentProofRejects;
+
     static constexpr int SELECT_PEER_MAX_RETRY = 3;
     static constexpr int SELECT_NODE_MAX_RETRY = 3;
 
 public:
+    PeerManager();
+
     /**
      * Node API.
      */
@@ -188,8 +197,14 @@
     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);
+    PeerSet::iterator fetchOrCreatePeer(const Proof &proof,
+                                        ProofValidationState &state);
     bool addNodeToPeer(const PeerSet::iterator &it);
     bool removeNodeFromPeer(const PeerSet::iterator &it, uint32_t count = 1);
 };
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -13,6 +13,10 @@
 
 namespace avalanche {
 
+PeerManager::PeerManager() {
+    recentProofRejects.reset(new CRollingBloomFilter(120000, 0.000001));
+}
+
 bool PeerManager::addNode(NodeId nodeid, const Proof &proof,
                           const Delegation &delegation) {
     auto it = fetchOrCreatePeer(proof);
@@ -187,6 +191,13 @@
 
 PeerManager::PeerSet::iterator
 PeerManager::fetchOrCreatePeer(const Proof &proof) {
+    ProofValidationState state;
+    return fetchOrCreatePeer(proof, state);
+}
+
+PeerManager::PeerSet::iterator
+PeerManager::fetchOrCreatePeer(const Proof &proof,
+                               ProofValidationState &state) {
     {
         // Check if we already know of that peer.
         auto &pview = peers.get<proof_index>();
@@ -201,7 +212,6 @@
         LOCK(cs_main);
         const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
 
-        ProofValidationState state;
         if (!proof.verify(state, coins)) {
             return peers.end();
         }
@@ -456,4 +466,43 @@
     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) {
+    // skip proof verification if we already did it previously
+    if (recentProofRejects->contains(proof.getId()) ||
+        getProof(proof.getId())) {
+        return false;
+    }
+
+    ProofValidationState state;
+    // Store good proof in a new peer
+    if (fetchOrCreatePeer(proof, state) != peers.end()) {
+        return true;
+    }
+
+    // Keep track of orphan proofs in case they become valid later
+    if (state.GetResult() == ProofValidationResult::MISSING_UTXO) {
+        return orphanProofs
+            .insert(std::make_pair(proof.getId(), std::move(proof)))
+            .second;
+    }
+
+    // Keep track of bad proofs to avoid requesting or relaying them
+    recentProofRejects->insert(proof.getId());
+    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
@@ -303,6 +303,14 @@
     std::vector<avalanche::Peer> getPeers() const;
     std::vector<NodeId> getNodeIdsForPeer(PeerId peerId) const;
 
+    /**
+     * Add a proof and return true if it is verifies successfully.
+     */
+    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
@@ -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;
     }
@@ -2658,7 +2667,8 @@
 bool IsAvalancheMessageType(const std::string &msg_type) {
     return msg_type == NetMsgType::AVAHELLO ||
            msg_type == NetMsgType::AVAPOLL ||
-           msg_type == NetMsgType::AVARESPONSE;
+           msg_type == NetMsgType::AVARESPONSE ||
+           msg_type == NetMsgType::AVAPROOF;
 }
 
 void PeerManager::ProcessMessage(const Config &config, CNode &pfrom,
@@ -3995,6 +4005,20 @@
         verifier >> sig;
     }
 
+    if (msg_type == NetMsgType::AVAPROOF) {
+        // Read the proof.
+        avalanche::Proof proof;
+        vRecv >> proof;
+
+        if (!g_avalanche->addProof(std::move(proof)) &&
+            !g_avalanche->getProof(proof.getId())) {
+            // We didn't add it, and it is not because we already have it.
+            // It must be bad.
+            Misbehaving(pfrom, 100, "invalid-proof");
+        }
+        return;
+    }
+
     if (msg_type == NetMsgType::AVAPOLL) {
         auto now = std::chrono::steady_clock::now();
         int64_t cooldown =