diff --git a/src/Makefile.am b/src/Makefile.am
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -117,6 +117,7 @@
   avalanche/node.h \
   avalanche/peermanager.h \
   avalanche/processor.h \
+  avalanche/proof.h \
   avalanche/protocol.h \
   banman.h \
   base58.h \
diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -6,8 +6,10 @@
 #define BITCOIN_AVALANCHE_PEERMANAGER_H
 
 #include <avalanche/node.h>
+#include <avalanche/proof.h>
 #include <net.h>
 #include <pubkey.h>
+#include <salteduint256hasher.h>
 
 #include <boost/multi_index/composite_key.hpp>
 #include <boost/multi_index/hashed_index.hpp>
@@ -17,7 +19,6 @@
 
 #include <chrono>
 #include <cstdint>
-#include <unordered_map>
 #include <vector>
 
 namespace avalanche {
@@ -54,8 +55,16 @@
     bool follows(uint64_t slot) const { return getStart() > slot; }
 };
 
+struct proof_index {};
 struct next_request_time {};
 
+class SaltedProofIdHasher : private SaltedUint256Hasher {
+public:
+    SaltedProofIdHasher() : SaltedUint256Hasher() {}
+
+    size_t operator()(const ProofId &proofid) const { return hash(proofid); }
+};
+
 class PeerManager {
     std::vector<Slot> slots;
     uint64_t slotCount = 0;
@@ -66,14 +75,31 @@
      * considered interchangeable parts of the same peer.
      */
     struct Peer {
+        PeerId peerid;
+
         uint32_t score;
         uint32_t index;
 
-        Peer(uint32_t score_, uint32_t index_) : score(score_), index(index_) {}
+        ProofId proofid;
+
+        Peer(PeerId peerid_, uint32_t score_, uint32_t index_, ProofId proofid_)
+            : peerid(peerid_), score(score_), index(index_),
+              proofid(std::move(proofid_)) {}
     };
 
+    using PeerSet = boost::multi_index_container<
+        Peer, boost::multi_index::indexed_by<
+                  // index by peerid
+                  boost::multi_index::hashed_unique<
+                      boost::multi_index::member<Peer, PeerId, &Peer::peerid>>,
+                  // index by proof
+                  boost::multi_index::hashed_unique<
+                      boost::multi_index::tag<proof_index>,
+                      boost::multi_index::member<Peer, ProofId, &Peer::proofid>,
+                      SaltedProofIdHasher>>>;
+
     PeerId nextPeerId = 0;
-    std::unordered_map<PeerId, Peer> peers;
+    PeerSet peers;
 
     using NodeSet = boost::multi_index_container<
         Node,
@@ -100,8 +126,8 @@
      * Peer API.
      */
     PeerId addPeer(uint32_t score) { return addPeer(nextPeerId++, score); }
-    bool removePeer(PeerId p);
-    bool rescorePeer(PeerId p, uint32_t score);
+    bool removePeer(const PeerId peerid);
+    bool rescorePeer(const PeerId peerid, uint32_t score);
 
     /**
      * Node API.
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -11,7 +11,8 @@
 namespace avalanche {
 
 PeerId PeerManager::addPeer(PeerId p, uint32_t score) {
-    auto inserted = peers.emplace(p, Peer(score, uint32_t(slots.size())));
+    auto inserted =
+        peers.emplace(p, score, uint32_t(slots.size()), ProofId(GetRandHash()));
     assert(inserted.second);
 
     const uint64_t start = slotCount;
@@ -20,13 +21,13 @@
     return p;
 }
 
-bool PeerManager::removePeer(PeerId p) {
-    auto it = peers.find(p);
+bool PeerManager::removePeer(const PeerId peerid) {
+    auto it = peers.find(peerid);
     if (it == peers.end()) {
         return false;
     }
 
-    size_t i = it->second.index;
+    size_t i = it->index;
     assert(i < slots.size());
 
     if (i + 1 == slots.size()) {
@@ -41,25 +42,25 @@
     // active. This ensure that we don't overquery them in case their are
     // subsequently added to another peer.
     auto &nview = nodes.get<next_request_time>();
-    nview.erase(nview.lower_bound(boost::make_tuple(p, TimePoint())),
-                nview.upper_bound(
-                    boost::make_tuple(p, std::chrono::steady_clock::now())));
+    nview.erase(nview.lower_bound(boost::make_tuple(peerid, TimePoint())),
+                nview.upper_bound(boost::make_tuple(
+                    peerid, std::chrono::steady_clock::now())));
 
     peers.erase(it);
     return true;
 }
 
-bool PeerManager::rescorePeer(PeerId p, uint32_t score) {
-    auto it = peers.find(p);
+bool PeerManager::rescorePeer(const PeerId peerid, uint32_t score) {
+    auto it = peers.find(peerid);
     if (it == peers.end()) {
         return false;
     }
 
-    size_t i = it->second.index;
-    assert(i < slots.size());
-
     // Update the peer's score.
-    it->second.score = score;
+    peers.modify(it, [&](Peer &p) { p.score = score; });
+
+    const size_t i = it->index;
+    assert(i < slots.size());
 
     // Update the slot allocation to reflect the new score.
     const uint64_t start = slots[i].getStart();
@@ -84,9 +85,9 @@
     // So we need to insert a new entry.
     fragmentation += slots[i].getScore();
     slots[i] = slots[i].withPeerId(NO_PEER);
-    it->second.index = uint32_t(slots.size());
+    peers.modify(it, [this](Peer &p) { p.index = uint32_t(slots.size()); });
     const uint64_t newStart = slotCount;
-    slots.emplace_back(newStart, score, p);
+    slots.emplace_back(newStart, score, peerid);
     slotCount = newStart + score;
 
     return true;
@@ -181,14 +182,11 @@
 
     uint64_t prevStop = 0;
     uint32_t i = 0;
-    for (auto &pair : peers) {
-        PeerId pid = pair.first;
-        Peer &p = pair.second;
-
-        slots[i] = Slot(prevStop, p.score, pid);
+    for (auto it = peers.begin(); it != peers.end(); it++) {
+        slots[i] = Slot(prevStop, it->score, it->peerid);
         prevStop = slots[i].getStop();
 
-        p.index = i++;
+        peers.modify(it, [&](Peer &p) { p.index = i++; });
     }
 
     const uint64_t saved = slotCount - prevStop;
@@ -217,23 +215,19 @@
 
         // We have a live slot, verify index.
         auto it = peers.find(s.getPeerId());
-        if (it == peers.end() || it->second.index != i) {
+        if (it == peers.end() || it->index != i) {
             return false;
         }
     }
 
-    for (const auto &pair : peers) {
-        auto p = pair.first;
-        auto i = pair.second.index;
-        auto s = pair.second.score;
-
+    for (const auto &p : peers) {
         // The index must point to a slot refering to this peer.
-        if (i >= slots.size() || slots[i].getPeerId() != p) {
+        if (p.index >= slots.size() || slots[p.index].getPeerId() != p.peerid) {
             return false;
         }
 
         // If the score do not match, same thing.
-        if (slots[i].getScore() != s) {
+        if (slots[p.index].getScore() != p.score) {
             return false;
         }
     }
diff --git a/src/avalanche/proof.h b/src/avalanche/proof.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/proof.h
@@ -0,0 +1,19 @@
+// Copyright (c) 2018-2019 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_AVALANCHE_PROOF_H
+#define BITCOIN_AVALANCHE_PROOF_H
+
+#include <uint256.h>
+
+namespace avalanche {
+
+struct ProofId : public uint256 {
+    explicit ProofId() : uint256() {}
+    explicit ProofId(const uint256 &b) : uint256(b) {}
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_PROOF_H