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 <coins.h>
 #include <net.h>
 #include <pubkey.h>
 #include <salteduint256hasher.h>
@@ -104,6 +105,8 @@
     PeerId nextPeerId = 0;
     PeerSet peers;
 
+    std::unordered_map<COutPoint, PeerId, SaltedOutpointHasher> utxos;
+
     using NodeSet = boost::multi_index_container<
         Node,
         boost::multi_index::indexed_by<
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -13,10 +13,13 @@
 namespace avalanche {
 
 PeerId PeerManager::getPeer(const Proof &proof) {
-    auto &pview = peers.get<proof_index>();
-    auto it = pview.find(proof.getId());
-    if (it != pview.end()) {
-        return it->peerid;
+    {
+        // Check if we already know of that peer.
+        auto &pview = peers.get<proof_index>();
+        auto it = pview.find(proof.getId());
+        if (it != pview.end()) {
+            return it->peerid;
+        }
     }
 
     {
@@ -30,8 +33,35 @@
         }
     }
 
-    // We have no peer for this proof, time to create it.
+    // New peer means new peerid!
     const PeerId peerid = nextPeerId++;
+
+    // Attach UTXOs to this proof.
+    std::unordered_set<PeerId> conflicting_peerids;
+    for (const auto &s : proof.getStakes()) {
+        auto p = utxos.emplace(s.getStake().getUTXO(), peerid);
+        if (!p.second) {
+            // We have a collision with an existing proof.
+            conflicting_peerids.insert(p.first->second);
+        }
+    }
+
+    // For now, if there is a conflict, just ceanup the mess.
+    if (conflicting_peerids.size() > 0) {
+        for (const auto &s : proof.getStakes()) {
+            auto it = utxos.find(s.getStake().getUTXO());
+            assert(it != utxos.end());
+
+            // We need to delete that one.
+            if (it->second == peerid) {
+                utxos.erase(it);
+            }
+        }
+
+        return NO_PEER;
+    }
+
+    // We have no peer for this proof, time to create it.
     auto inserted = peers.emplace(peerid, uint32_t(slots.size()), proof);
     assert(inserted.second);
 
@@ -67,6 +97,12 @@
                 nview.upper_bound(boost::make_tuple(
                     peerid, std::chrono::steady_clock::now())));
 
+    // Release UTXOs attached to this proof.
+    for (const auto &s : it->proof.getStakes()) {
+        bool deleted = utxos.erase(s.getStake().getUTXO()) > 0;
+        assert(deleted);
+    }
+
     peers.erase(it);
     return true;
 }
@@ -289,8 +325,6 @@
     for (const auto &pid : invalidPeers) {
         removePeer(pid);
     }
-
-    compact();
 }
 
 } // 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
@@ -3,6 +3,9 @@
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <avalanche/peermanager.h>
+#include <avalanche/proofbuilder.h>
+#include <script/standard.h>
+#include <validation.h>
 
 #include <avalanche/test/util.h>
 
@@ -50,7 +53,7 @@
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 142, 500), 69);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 199, 500), 69);
 
-    // In betwenn
+    // In between
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 200, 500), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 242, 500), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 299, 500), NO_PEER);
@@ -346,4 +349,77 @@
     }
 }
 
+BOOST_AUTO_TEST_CASE(proof_conflict) {
+    CKey key;
+    key.MakeNewKey(true);
+    const CScript script = GetScriptForDestination(PKHash(key.GetPubKey()));
+
+    TxId txid1(GetRandHash());
+    TxId txid2(GetRandHash());
+    BOOST_CHECK(txid1 != txid2);
+
+    const Amount v = 5 * COIN;
+    const int height = 1234;
+
+    {
+        LOCK(cs_main);
+        CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
+
+        for (int i = 0; i < 10; i++) {
+            coins.AddCoin(COutPoint(txid1, i),
+                          Coin(CTxOut(v, script), height, false), false);
+            coins.AddCoin(COutPoint(txid2, i),
+                          Coin(CTxOut(v, script), height, false), false);
+        }
+    }
+
+    PeerManager pm;
+    const auto getPeerId = [&](const std::vector<COutPoint> &outpoints) {
+        ProofBuilder pb(0, 0, CPubKey());
+        for (const auto &o : outpoints) {
+            pb.addUTXO(o, v, height, false, key);
+        }
+
+        return pm.getPeer(pb.build());
+    };
+
+    // Add one peer.
+    const PeerId peer1 = getPeerId({COutPoint(txid1, 0)});
+    BOOST_CHECK(peer1 != NO_PEER);
+
+    // Same proof, same peer.
+    BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 0)}), peer1);
+
+    // Different txid, different proof.
+    const PeerId peer2 = getPeerId({COutPoint(txid2, 0)});
+    BOOST_CHECK(peer2 != NO_PEER && peer2 != peer1);
+
+    // Different index, different proof.
+    const PeerId peer3 = getPeerId({COutPoint(txid1, 1)});
+    BOOST_CHECK(peer3 != NO_PEER && peer3 != peer1);
+
+    // Empty proof, no peer.
+    BOOST_CHECK_EQUAL(getPeerId({}), NO_PEER);
+
+    // Multiple inputs.
+    const PeerId peer4 = getPeerId({COutPoint(txid1, 2), COutPoint(txid2, 2)});
+    BOOST_CHECK(peer4 != NO_PEER && peer4 != peer1);
+
+    // Duplicated input.
+    BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 3), COutPoint(txid1, 3)}),
+                      NO_PEER);
+
+    // Multiple inputs, collision on first input.
+    BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 0), COutPoint(txid2, 4)}),
+                      NO_PEER);
+
+    // Mutliple inputs, collision on second input.
+    BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 4), COutPoint(txid2, 0)}),
+                      NO_PEER);
+
+    // Mutliple inputs, collision on both inputs.
+    BOOST_CHECK_EQUAL(getPeerId({COutPoint(txid1, 0), COutPoint(txid2, 2)}),
+                      NO_PEER);
+}
+
 BOOST_AUTO_TEST_SUITE_END()