diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -75,10 +75,12 @@
 
     // The network stack uses timestamp in seconds, so we oblige.
     std::chrono::seconds registration_time;
+    std::chrono::seconds nextPossibleConflictTime;
 
     Peer(PeerId peerid_, ProofRef proof_)
         : peerid(peerid_), proof(std::move(proof_)),
-          registration_time(GetTime<std::chrono::seconds>()) {}
+          registration_time(GetTime<std::chrono::seconds>()),
+          nextPossibleConflictTime(registration_time) {}
 
     const ProofId &getProofId() const { return proof->getId(); }
     uint32_t getScore() const { return proof->getScore(); }
@@ -195,6 +197,14 @@
     /**
      * Proof and Peer related API.
      */
+
+    /**
+     * Update the time before which a proof is not allowed to have conflicting
+     * UTXO with this peer's proof.
+     */
+    bool updateNextPossibleConflictTime(PeerId peerid,
+                                        const std::chrono::seconds &nextTime);
+
     bool registerProof(const ProofRef &proof);
     bool exists(const ProofId &proofid) const {
         return getProof(proofid) != nullptr;
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -147,6 +147,23 @@
            state.GetResult() == ProofValidationResult::HEIGHT_MISMATCH;
 }
 
+bool PeerManager::updateNextPossibleConflictTime(
+    PeerId peerid, const std::chrono::seconds &nextTime) {
+    auto it = peers.find(peerid);
+    if (it == peers.end()) {
+        // No such peer
+        return false;
+    }
+
+    // Make sure we don't move the time in the past.
+    peers.modify(it, [&](Peer &p) {
+        p.nextPossibleConflictTime =
+            std::max(p.nextPossibleConflictTime, nextTime);
+    });
+
+    return it->nextPossibleConflictTime == nextTime;
+}
+
 bool PeerManager::registerProof(const ProofRef &proof) {
     assert(proof);
 
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
@@ -1062,4 +1062,37 @@
     BOOST_CHECK(!pm.exists(proofSeq10->getId()));
 }
 
+BOOST_AUTO_TEST_CASE(update_next_conflict_time) {
+    avalanche::PeerManager pm;
+
+    auto now = GetTime<std::chrono::seconds>();
+    SetMockTime(now.count());
+
+    // Updating the time of an unknown peer should fail
+    for (size_t i = 0; i < 10; i++) {
+        BOOST_CHECK(
+            !pm.updateNextPossibleConflictTime(PeerId(GetRandInt(1000)), now));
+    }
+
+    auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+    PeerId peerid = TestPeerManager::registerAndGetPeerId(pm, proof);
+
+    auto checkNextPossibleConflictTime = [&](std::chrono::seconds expected) {
+        BOOST_CHECK(pm.forPeer(proof->getId(), [&](const Peer &p) {
+            return p.nextPossibleConflictTime == expected;
+        }));
+    };
+
+    checkNextPossibleConflictTime(now);
+
+    // Move the time in the past is not possible
+    BOOST_CHECK(!pm.updateNextPossibleConflictTime(
+        peerid, now - std::chrono::seconds{1}));
+    checkNextPossibleConflictTime(now);
+
+    BOOST_CHECK(pm.updateNextPossibleConflictTime(
+        peerid, now + std::chrono::seconds{1}));
+    checkNextPossibleConflictTime(now + std::chrono::seconds{1});
+}
+
 BOOST_AUTO_TEST_SUITE_END()