diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -127,10 +127,14 @@
 
     NodeSet nodes;
 
+    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,6 +192,9 @@
     std::vector<Peer> getPeers() const;
     std::vector<NodeId> getNodeIdsForPeer(PeerId peerId) const;
 
+    // For testing only
+    void addRecentReject(ProofId proofId);
+
 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
@@ -13,6 +13,10 @@
 
 namespace avalanche {
 
+PeerManager::PeerManager()
+    : recentProofRejects(
+          std::make_unique<CRollingBloomFilter>(120000, 0.000001)) {}
+
 bool PeerManager::addNode(NodeId nodeid, const Proof &proof,
                           const Delegation &delegation) {
     auto it = fetchOrCreatePeer(proof);
@@ -171,6 +175,9 @@
             ProofValidationState state;
             if (!p.proof.verify(state, coins)) {
                 invalidPeers.push_back(p.peerid);
+                if (state.GetResult() != ProofValidationResult::MISSING_UTXO) {
+                    recentProofRejects->insert(p.proof.getId());
+                }
             }
         }
     }
@@ -196,6 +203,10 @@
         }
     }
 
+    if (recentProofRejects->contains(proof.getId())) {
+        return peers.end();
+    }
+
     {
         // Reject invalid proof.
         LOCK(cs_main);
@@ -203,6 +214,9 @@
 
         ProofValidationState state;
         if (!proof.verify(state, coins)) {
+            if (state.GetResult() != ProofValidationResult::MISSING_UTXO) {
+                recentProofRejects->insert(proof.getId());
+            }
             return peers.end();
         }
     }
@@ -456,4 +470,8 @@
     return nodeids;
 }
 
+void PeerManager::addRecentReject(ProofId proofId) {
+    recentProofRejects->insert(proofId);
+}
+
 } // namespace avalanche
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
@@ -436,6 +436,14 @@
     // Mutliple inputs, collision on both inputs.
     BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 0), COutPoint(txid2, 2)}),
                       NO_PEER);
+
+    // Make a new good proof but add it to recentProofRejects to pretend
+    // that we previously found it to be bad.
+    ProofBuilder pb(0, 0, CPubKey());
+    pb.addUTXO(COutPoint(txid1, 5), v, height, false, key);
+    Proof p(pb.build());
+    pm.addRecentReject(p.getId());
+    BOOST_CHECK_EQUAL(pm.getPeerId(p), NO_PEER);
 }
 
 BOOST_AUTO_TEST_SUITE_END()