diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
index eed4503fa..e09fbfb52 100644
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -1,344 +1,441 @@
 // Copyright (c) 2020 The Bitcoin developers
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <avalanche/peermanager.h>
 
 #include <avalanche/delegation.h>
 #include <avalanche/validation.h>
 #include <random.h>
 #include <validation.h> // For ChainstateActive()
 
 #include <cassert>
 
 namespace avalanche {
 
 bool PeerManager::addNode(NodeId nodeid, const Proof &proof,
                           const Delegation &delegation) {
-    const PeerId peerid = getPeerId(proof);
-    if (peerid == NO_PEER) {
+    auto it = fetchOrCreatePeer(proof);
+    if (it == peers.end()) {
         return false;
     }
 
+    const PeerId peerid = it->peerid;
+
     DelegationState state;
     CPubKey pubkey;
     if (!delegation.verify(state, proof, pubkey)) {
         return false;
     }
 
     auto nit = nodes.find(nodeid);
     if (nit == nodes.end()) {
-        return nodes.emplace(nodeid, peerid, std::move(pubkey)).second;
+        if (!nodes.emplace(nodeid, peerid, std::move(pubkey)).second) {
+            return false;
+        }
+    } else {
+        const PeerId oldpeerid = nit->peerid;
+        if (!nodes.modify(nit, [&](Node &n) {
+                n.peerid = peerid;
+                n.pubkey = std::move(pubkey);
+            })) {
+            return false;
+        }
+
+        // We actually have this node already, we need to update it.
+        bool success = removeNodeFromPeer(peers.find(oldpeerid));
+        assert(success);
+
+        // Make sure it is not invalidated.
+        it = peers.find(peerid);
     }
 
-    // We actually have this node already, we need to update it.
-    return nodes.modify(nit, [&](Node &n) {
-        n.peerid = peerid;
-        n.pubkey = std::move(pubkey);
+    bool success = addNodeToPeer(it);
+    assert(success);
+
+    return true;
+}
+
+bool PeerManager::addNodeToPeer(const PeerSet::iterator &it) {
+    assert(it != peers.end());
+    return peers.modify(it, [&](Peer &p) {
+        if (p.node_count++ > 0) {
+            // We are done.
+            return;
+        }
+
+        // We ned to allocate this peer.
+        p.index = uint32_t(slots.size());
+        const uint32_t score = p.getScore();
+        const uint64_t start = slotCount;
+        slots.emplace_back(start, score, it->peerid);
+        slotCount = start + score;
     });
 }
 
 bool PeerManager::removeNode(NodeId nodeid) {
-    return nodes.erase(nodeid) > 0;
+    auto it = nodes.find(nodeid);
+    if (it == nodes.end()) {
+        return false;
+    }
+
+    const PeerId peerid = it->peerid;
+    nodes.erase(it);
+
+    // Keep the track of the reference count.
+    bool success = removeNodeFromPeer(peers.find(peerid));
+    assert(success);
+
+    return true;
+}
+
+bool PeerManager::removeNodeFromPeer(const PeerSet::iterator &it,
+                                     uint32_t count) {
+    assert(it != peers.end());
+    assert(count <= it->node_count);
+    if (count == 0) {
+        // This is a NOOP.
+        return false;
+    }
+
+    const uint32_t new_count = it->node_count - count;
+    if (!peers.modify(it, [&](Peer &p) { p.node_count = new_count; })) {
+        return false;
+    }
+
+    if (new_count > 0) {
+        // We are done.
+        return true;
+    }
+
+    // There are no more node left, we need to cleanup.
+    const size_t i = it->index;
+    assert(i < slots.size());
+    if (i + 1 == slots.size()) {
+        slots.pop_back();
+        slotCount = slots.empty() ? 0 : slots.back().getStop();
+    } else {
+        fragmentation += slots[i].getScore();
+        slots[i] = slots[i].withPeerId(NO_PEER);
+    }
+
+    return true;
 }
 
 bool PeerManager::forNode(NodeId nodeid,
                           std::function<bool(const Node &n)> func) const {
     auto it = nodes.find(nodeid);
     return it != nodes.end() && func(*it);
 }
 
 bool PeerManager::updateNextRequestTime(NodeId nodeid, TimePoint timeout) {
     auto it = nodes.find(nodeid);
     if (it == nodes.end()) {
         return false;
     }
 
     return nodes.modify(it, [&](Node &n) { n.nextRequestTime = timeout; });
 }
 
 NodeId PeerManager::selectNode() {
     for (int retry = 0; retry < SELECT_NODE_MAX_RETRY; retry++) {
         const PeerId p = selectPeer();
 
         // If we cannot find a peer, it may be due to the fact that it is
         // unlikely due to high fragmentation, so compact and retry.
         if (p == NO_PEER) {
             compact();
             continue;
         }
 
         // See if that peer has an available node.
         auto &nview = nodes.get<next_request_time>();
         auto it = nview.lower_bound(boost::make_tuple(p, TimePoint()));
         if (it != nview.end() && it->peerid == p &&
             it->nextRequestTime <= std::chrono::steady_clock::now()) {
             return it->nodeid;
         }
     }
 
     return NO_NODE;
 }
 
 void PeerManager::updatedBlockTip() {
     std::vector<PeerId> invalidPeers;
 
     {
         LOCK(cs_main);
 
         const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
         for (const auto &p : peers) {
             ProofValidationState state;
             if (!p.proof.verify(state, coins)) {
                 invalidPeers.push_back(p.peerid);
             }
         }
     }
 
     for (const auto &pid : invalidPeers) {
         removePeer(pid);
     }
 }
 
 PeerId PeerManager::getPeerId(const Proof &proof) {
     auto it = fetchOrCreatePeer(proof);
     return it == peers.end() ? NO_PEER : it->peerid;
 }
 
 PeerManager::PeerSet::iterator
 PeerManager::fetchOrCreatePeer(const Proof &proof) {
     {
         // 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 peers.project<0>(it);
         }
     }
 
     {
         // Reject invalid proof.
         LOCK(cs_main);
         const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
 
         ProofValidationState state;
         if (!proof.verify(state, coins)) {
             return peers.end();
         }
     }
 
     // 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 peers.end();
     }
 
     // We have no peer for this proof, time to create it.
-    auto inserted = peers.emplace(peerid, uint32_t(slots.size()), proof);
+    auto inserted = peers.emplace(peerid, proof);
     assert(inserted.second);
 
-    const uint32_t score = proof.getScore();
-    const uint64_t start = slotCount;
-    slots.emplace_back(start, score, peerid);
-    slotCount = start + score;
-
     return inserted.first;
 }
 
 bool PeerManager::removePeer(const PeerId peerid) {
     auto it = peers.find(peerid);
     if (it == peers.end()) {
         return false;
     }
 
-    size_t i = it->index;
-    assert(i < slots.size());
-
-    if (i + 1 == slots.size()) {
-        slots.pop_back();
-        slotCount = slots.empty() ? 0 : slots.back().getStop();
-    } else {
-        fragmentation += slots[i].getScore();
-        slots[i] = slots[i].withPeerId(NO_PEER);
-    }
+    // Remove all nodes from this peer.
+    removeNodeFromPeer(it, it->node_count);
 
     // Remove nodes associated with this peer, unless their timeout is still
-    // active. This ensure that we don't overquery them in case their are
+    // active. This ensure that we don't overquery them in case they are
     // subsequently added to another peer.
     auto &nview = nodes.get<next_request_time>();
     nview.erase(nview.lower_bound(boost::make_tuple(peerid, TimePoint())),
                 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;
 }
 
 PeerId PeerManager::selectPeer() const {
     if (slots.empty() || slotCount == 0) {
         return NO_PEER;
     }
 
     const uint64_t max = slotCount;
     for (int retry = 0; retry < SELECT_PEER_MAX_RETRY; retry++) {
         size_t i = selectPeerImpl(slots, GetRand(max), max);
         if (i != NO_PEER) {
             return i;
         }
     }
 
     return NO_PEER;
 }
 
 uint64_t PeerManager::compact() {
     // There is nothing to compact.
     if (fragmentation == 0) {
         return 0;
     }
 
-    // Shrink the vector to the expected size.
-    while (slots.size() > peers.size()) {
-        slots.pop_back();
-    }
+    std::vector<Slot> newslots;
+    newslots.reserve(peers.size());
 
     uint64_t prevStop = 0;
     uint32_t i = 0;
     for (auto it = peers.begin(); it != peers.end(); it++) {
-        slots[i] = Slot(prevStop, it->getScore(), it->peerid);
-        prevStop = slots[i].getStop();
+        if (it->node_count == 0) {
+            continue;
+        }
 
-        peers.modify(it, [&](Peer &p) { p.index = i++; });
+        newslots.emplace_back(prevStop, it->getScore(), it->peerid);
+        prevStop = slots[i].getStop();
+        if (!peers.modify(it, [&](Peer &p) { p.index = i++; })) {
+            return 0;
+        }
     }
 
+    slots = std::move(newslots);
+
     const uint64_t saved = slotCount - prevStop;
     slotCount = prevStop;
     fragmentation = 0;
 
     return saved;
 }
 
 bool PeerManager::verify() const {
     uint64_t prevStop = 0;
     for (size_t i = 0; i < slots.size(); i++) {
         const Slot &s = slots[i];
 
         // Slots must be in correct order.
         if (s.getStart() < prevStop) {
             return false;
         }
 
         prevStop = s.getStop();
 
         // If this is a dead slot, then nothing more needs to be checked.
         if (s.getPeerId() == NO_PEER) {
             continue;
         }
 
         // We have a live slot, verify index.
         auto it = peers.find(s.getPeerId());
         if (it == peers.end() || it->index != i) {
             return false;
         }
     }
 
     for (const auto &p : peers) {
+        // Count node attached to this peer.
+        const auto count_nodes = [&]() {
+            size_t count = 0;
+            auto &nview = nodes.get<next_request_time>();
+            auto begin =
+                nview.lower_bound(boost::make_tuple(p.peerid, TimePoint()));
+            auto end =
+                nview.upper_bound(boost::make_tuple(p.peerid + 1, TimePoint()));
+
+            for (auto it = begin; it != end; ++it) {
+                count++;
+            }
+
+            return count;
+        };
+
+        if (p.node_count != count_nodes()) {
+            return false;
+        }
+
+        // If there are no nodes attached to this peer, then we are done.
+        if (p.node_count == 0) {
+            continue;
+        }
+
         // The index must point to a slot refering to this peer.
         if (p.index >= slots.size() || slots[p.index].getPeerId() != p.peerid) {
             return false;
         }
 
         // If the score do not match, same thing.
         if (slots[p.index].getScore() != p.getScore()) {
             return false;
         }
     }
 
     return true;
 }
 
 PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
                       const uint64_t max) {
     assert(slot <= max);
 
     size_t begin = 0, end = slots.size();
     uint64_t bottom = 0, top = max;
 
     // Try to find the slot using dichotomic search.
     while ((end - begin) > 8) {
         // The slot we picked in not allocated.
         if (slot < bottom || slot >= top) {
             return NO_PEER;
         }
 
         // Guesstimate the position of the slot.
         size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom));
         assert(begin <= i && i < end);
 
         // We have a match.
         if (slots[i].contains(slot)) {
             return slots[i].getPeerId();
         }
 
         // We undershooted.
         if (slots[i].precedes(slot)) {
             begin = i + 1;
             if (begin >= end) {
                 return NO_PEER;
             }
 
             bottom = slots[begin].getStart();
             continue;
         }
 
         // We overshooted.
         if (slots[i].follows(slot)) {
             end = i;
             top = slots[end].getStart();
             continue;
         }
 
         // We have an unalocated slot.
         return NO_PEER;
     }
 
     // Enough of that nonsense, let fallback to linear search.
     for (size_t i = begin; i < end; i++) {
         // We have a match.
         if (slots[i].contains(slot)) {
             return slots[i].getPeerId();
         }
     }
 
     // We failed to find a slot, retry.
     return NO_PEER;
 }
 
 } // namespace avalanche
diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
index d3b0ca9db..212c7c468 100644
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -1,199 +1,202 @@
 // Copyright (c) 2020 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_PEERMANAGER_H
 #define BITCOIN_AVALANCHE_PEERMANAGER_H
 
 #include <avalanche/node.h>
 #include <avalanche/proof.h>
 #include <coins.h>
 #include <net.h>
 #include <pubkey.h>
 #include <salteduint256hasher.h>
 
 #include <boost/multi_index/composite_key.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/member.hpp>
 #include <boost/multi_index/ordered_index.hpp>
 #include <boost/multi_index_container.hpp>
 
 #include <chrono>
 #include <cstdint>
 #include <vector>
 
 namespace avalanche {
 
 class Delegation;
 
 struct Slot {
 private:
     uint64_t start;
     uint32_t score;
     PeerId peerid;
 
 public:
     Slot(uint64_t startIn, uint32_t scoreIn, PeerId peeridIn)
         : start(startIn), score(scoreIn), peerid(peeridIn) {}
 
     Slot withStart(uint64_t startIn) const {
         return Slot(startIn, score, peerid);
     }
     Slot withScore(uint64_t scoreIn) const {
         return Slot(start, scoreIn, peerid);
     }
     Slot withPeerId(PeerId peeridIn) const {
         return Slot(start, score, peeridIn);
     }
 
     uint64_t getStart() const { return start; }
     uint64_t getStop() const { return start + score; }
     uint32_t getScore() const { return score; }
     PeerId getPeerId() const { return peerid; }
 
     bool contains(uint64_t slot) const {
         return getStart() <= slot && slot < getStop();
     }
     bool precedes(uint64_t slot) const { return slot >= getStop(); }
     bool follows(uint64_t slot) const { return getStart() > slot; }
 };
 
 struct Peer {
     PeerId peerid;
-    uint32_t index;
+    uint32_t index = -1;
+    uint32_t node_count = 0;
 
     Proof proof;
 
-    Peer(PeerId peerid_, uint32_t index_, Proof proof_)
-        : peerid(peerid_), index(index_), proof(std::move(proof_)) {}
+    Peer(PeerId peerid_, Proof proof_)
+        : peerid(peerid_), proof(std::move(proof_)) {}
 
     const ProofId &getProofId() const { return proof.getId(); }
     uint32_t getScore() const { return proof.getScore(); }
 };
 
 struct proof_index {
     using result_type = ProofId;
     result_type operator()(const Peer &p) const { return p.proof.getId(); }
 };
 
 class SaltedProofIdHasher : private SaltedUint256Hasher {
 public:
     SaltedProofIdHasher() : SaltedUint256Hasher() {}
 
     size_t operator()(const ProofId &proofid) const { return hash(proofid); }
 };
 
 struct next_request_time {};
 
 class PeerManager {
     std::vector<Slot> slots;
     uint64_t slotCount = 0;
     uint64_t fragmentation = 0;
 
     /**
      * Several nodes can make an avalanche peer. In this case, all nodes are
      * considered interchangeable parts of the same peer.
      */
     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>, proof_index,
                       SaltedProofIdHasher>>>;
 
     PeerId nextPeerId = 0;
     PeerSet peers;
 
     std::unordered_map<COutPoint, PeerId, SaltedOutpointHasher> utxos;
 
     using NodeSet = boost::multi_index_container<
         Node,
         boost::multi_index::indexed_by<
             // index by nodeid
             boost::multi_index::hashed_unique<
                 boost::multi_index::member<Node, NodeId, &Node::nodeid>>,
             // sorted by peerid/nextRequestTime
             boost::multi_index::ordered_non_unique<
                 boost::multi_index::tag<next_request_time>,
                 boost::multi_index::composite_key<
                     Node,
                     boost::multi_index::member<Node, PeerId, &Node::peerid>,
                     boost::multi_index::member<Node, TimePoint,
                                                &Node::nextRequestTime>>>>>;
 
     NodeSet nodes;
 
     static constexpr int SELECT_PEER_MAX_RETRY = 3;
     static constexpr int SELECT_NODE_MAX_RETRY = 3;
 
 public:
     /**
      * Node API.
      */
     bool addNode(NodeId nodeid, const Proof &proof,
                  const Delegation &delegation);
     bool removeNode(NodeId nodeid);
 
     bool forNode(NodeId nodeid, std::function<bool(const Node &n)> func) const;
     bool updateNextRequestTime(NodeId nodeid, TimePoint timeout);
 
     /**
      * Randomly select a node to poll.
      */
     NodeId selectNode();
 
     /**
      * Update the peer set when a nw block is connected.
      */
     void updatedBlockTip();
 
     /****************************************************
      * Functions which are public for testing purposes. *
      ****************************************************/
     /**
      * Provide the PeerId associated with the given proof. If the peer does not
      * exists, then it is created.
      */
     PeerId getPeerId(const Proof &proof);
 
     /**
      * Remove an existing peer.
      */
     bool removePeer(const PeerId peerid);
 
     /**
      * Randomly select a peer to poll.
      */
     PeerId selectPeer() const;
 
     /**
      * Trigger maintenance of internal datastructures.
      * Returns how much slot space was saved after compaction.
      */
     uint64_t compact();
 
     /**
      * Perform consistency check on internal data structures.
      */
     bool verify() const;
 
     // Accssors.
     uint64_t getSlotCount() const { return slotCount; }
     uint64_t getFragmentation() const { return fragmentation; }
 
 private:
     PeerSet::iterator fetchOrCreatePeer(const Proof &proof);
+    bool addNodeToPeer(const PeerSet::iterator &it);
+    bool removeNodeFromPeer(const PeerSet::iterator &it, uint32_t count = 1);
 };
 
 /**
  * This is an internal method that is exposed for testing purposes.
  */
 PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
                       const uint64_t max);
 
 } // namespace avalanche
 
 #endif // BITCOIN_AVALANCHE_PEERMANAGER_H
diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp
index 8ac7adf56..9ebe1186c 100644
--- a/src/avalanche/test/peermanager_tests.cpp
+++ b/src/avalanche/test/peermanager_tests.cpp
@@ -1,432 +1,441 @@
 // Copyright (c) 2020 The Bitcoin developers
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <avalanche/delegationbuilder.h>
 #include <avalanche/peermanager.h>
 #include <avalanche/proofbuilder.h>
 #include <avalanche/test/util.h>
 #include <script/standard.h>
 #include <validation.h>
 
 #include <test/util/setup_common.h>
 
 #include <boost/test/unit_test.hpp>
 
 using namespace avalanche;
 
 BOOST_FIXTURE_TEST_SUITE(peermanager_tests, TestingSetup)
 
 BOOST_AUTO_TEST_CASE(select_peer_linear) {
     // No peers.
     BOOST_CHECK_EQUAL(selectPeerImpl({}, 0, 0), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl({}, 1, 3), NO_PEER);
 
     // One peer
     const std::vector<Slot> oneslot = {{100, 100, 23}};
 
     // Undershoot
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 0, 300), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 42, 300), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 99, 300), NO_PEER);
 
     // Nailed it
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 100, 300), 23);
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 142, 300), 23);
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 199, 300), 23);
 
     // Overshoot
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 200, 300), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 242, 300), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 299, 300), NO_PEER);
 
     // Two peers
     const std::vector<Slot> twoslots = {{100, 100, 69}, {300, 100, 42}};
 
     // Undershoot
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 0, 500), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 42, 500), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 99, 500), NO_PEER);
 
     // First entry
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 100, 500), 69);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 142, 500), 69);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 199, 500), 69);
 
     // 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);
 
     // Second entry
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 300, 500), 42);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 342, 500), 42);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 399, 500), 42);
 
     // Overshoot
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 400, 500), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 442, 500), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 499, 500), NO_PEER);
 }
 
 BOOST_AUTO_TEST_CASE(select_peer_dichotomic) {
     std::vector<Slot> slots;
 
     // 100 peers of size 1 with 1 empty element apart.
     uint64_t max = 1;
     for (int i = 0; i < 100; i++) {
         slots.emplace_back(max, 1, i);
         max += 2;
     }
 
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 4, max), NO_PEER);
 
     // Check that we get what we expect.
     for (int i = 0; i < 100; i++) {
         BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i, max), NO_PEER);
         BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i + 1, max), i);
     }
 
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, max, max), NO_PEER);
 
     // Update the slots to be heavily skewed toward the last element.
     slots[99] = slots[99].withScore(101);
     max = slots[99].getStop();
     BOOST_CHECK_EQUAL(max, 300);
 
     for (int i = 0; i < 100; i++) {
         BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i, max), NO_PEER);
         BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i + 1, max), i);
     }
 
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 200, max), 99);
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 256, max), 99);
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 299, max), 99);
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 300, max), NO_PEER);
 
     // Update the slots to be heavily skewed toward the first element.
     for (int i = 0; i < 100; i++) {
         slots[i] = slots[i].withStart(slots[i].getStart() + 100);
     }
 
     slots[0] = Slot(1, slots[0].getStop() - 1, slots[0].getPeerId());
     slots[99] = slots[99].withScore(1);
     max = slots[99].getStop();
     BOOST_CHECK_EQUAL(max, 300);
 
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 0, max), NO_PEER);
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 1, max), 0);
     BOOST_CHECK_EQUAL(selectPeerImpl(slots, 42, max), 0);
 
     for (int i = 0; i < 100; i++) {
         BOOST_CHECK_EQUAL(selectPeerImpl(slots, 100 + 2 * i + 1, max), i);
         BOOST_CHECK_EQUAL(selectPeerImpl(slots, 100 + 2 * i + 2, max), NO_PEER);
     }
 }
 
 BOOST_AUTO_TEST_CASE(select_peer_random) {
     for (int c = 0; c < 1000; c++) {
         size_t size = InsecureRandBits(10) + 1;
         std::vector<Slot> slots;
         slots.reserve(size);
 
         uint64_t max = InsecureRandBits(3);
         auto next = [&]() {
             uint64_t r = max;
             max += InsecureRandBits(3);
             return r;
         };
 
         for (size_t i = 0; i < size; i++) {
             const uint64_t start = next();
             const uint32_t score = InsecureRandBits(3);
             max += score;
             slots.emplace_back(start, score, i);
         }
 
         for (int k = 0; k < 100; k++) {
             uint64_t s = max > 0 ? InsecureRandRange(max) : 0;
             auto i = selectPeerImpl(slots, s, max);
             // /!\ Because of the way we construct the vector, the peer id is
             // always the index. This might not be the case in practice.
             BOOST_CHECK(i == NO_PEER || slots[i].contains(s));
         }
     }
 }
 
 BOOST_AUTO_TEST_CASE(peer_probabilities) {
     // No peers.
     PeerManager pm;
     BOOST_CHECK_EQUAL(pm.selectNode(), NO_NODE);
 
     const NodeId node0 = 42, node1 = 69, node2 = 37;
 
     // One peer, we always return it.
     Proof proof0 = buildRandomProof(100);
     Delegation dg0 = DelegationBuilder(proof0).build();
     pm.addNode(node0, proof0, dg0);
     BOOST_CHECK_EQUAL(pm.selectNode(), node0);
 
     // Two peers, verify ratio.
     Proof proof1 = buildRandomProof(200);
     Delegation dg1 = DelegationBuilder(proof1).build();
     pm.addNode(node1, proof1, dg1);
 
     std::unordered_map<PeerId, int> results = {};
     for (int i = 0; i < 10000; i++) {
         size_t n = pm.selectNode();
         BOOST_CHECK(n == node0 || n == node1);
         results[n]++;
     }
 
     BOOST_CHECK(abs(2 * results[0] - results[1]) < 500);
 
     // Three peers, verify ratio.
     Proof proof2 = buildRandomProof(100);
     Delegation dg2 = DelegationBuilder(proof2).build();
     pm.addNode(node2, proof2, dg2);
 
     results.clear();
     for (int i = 0; i < 10000; i++) {
         size_t n = pm.selectNode();
         BOOST_CHECK(n == node0 || n == node1 || n == node2);
         results[n]++;
     }
 
     BOOST_CHECK(abs(results[0] - results[1] + results[2]) < 500);
 }
 
 BOOST_AUTO_TEST_CASE(remove_peer) {
     // No peers.
     PeerManager pm;
     BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER);
 
     // Add 4 peers.
     std::array<PeerId, 8> peerids;
     for (int i = 0; i < 4; i++) {
-        peerids[i] = pm.getPeerId(buildRandomProof(100));
+        Proof p = buildRandomProof(100);
+        peerids[i] = pm.getPeerId(p);
+        BOOST_CHECK(
+            pm.addNode(InsecureRand32(), p, DelegationBuilder(p).build()));
     }
 
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
 
     for (int i = 0; i < 100; i++) {
         PeerId p = pm.selectPeer();
         BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[2] ||
                     p == peerids[3]);
     }
 
     // Remove one peer, it nevers show up now.
     BOOST_CHECK(pm.removePeer(peerids[2]));
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 100);
 
     // Make sure we compact to never get NO_PEER.
     BOOST_CHECK_EQUAL(pm.compact(), 100);
     BOOST_CHECK(pm.verify());
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 300);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
 
     for (int i = 0; i < 100; i++) {
         PeerId p = pm.selectPeer();
         BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[3]);
     }
 
     // Add 4 more peers.
     for (int i = 0; i < 4; i++) {
-        peerids[i + 4] = pm.getPeerId(buildRandomProof(100));
+        Proof p = buildRandomProof(100);
+        peerids[i + 4] = pm.getPeerId(p);
+        BOOST_CHECK(
+            pm.addNode(InsecureRand32(), p, DelegationBuilder(p).build()));
     }
 
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 700);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
 
     BOOST_CHECK(pm.removePeer(peerids[0]));
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 700);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 100);
 
     // Removing the last entry do not increase fragmentation.
     BOOST_CHECK(pm.removePeer(peerids[7]));
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 600);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 100);
 
     // Make sure we compact to never get NO_PEER.
     BOOST_CHECK_EQUAL(pm.compact(), 100);
     BOOST_CHECK(pm.verify());
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 500);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
 
     for (int i = 0; i < 100; i++) {
         PeerId p = pm.selectPeer();
         BOOST_CHECK(p == peerids[1] || p == peerids[3] || p == peerids[4] ||
                     p == peerids[5] || p == peerids[6]);
     }
 
     // Removing non existent peers fails.
     BOOST_CHECK(!pm.removePeer(peerids[0]));
     BOOST_CHECK(!pm.removePeer(peerids[2]));
     BOOST_CHECK(!pm.removePeer(peerids[7]));
     BOOST_CHECK(!pm.removePeer(NO_PEER));
 }
 
 BOOST_AUTO_TEST_CASE(compact_slots) {
     PeerManager pm;
 
     // Add 4 peers.
     std::array<PeerId, 4> peerids;
     for (int i = 0; i < 4; i++) {
-        peerids[i] = pm.getPeerId(buildRandomProof(100));
+        Proof p = buildRandomProof(100);
+        peerids[i] = pm.getPeerId(p);
+        BOOST_CHECK(
+            pm.addNode(InsecureRand32(), p, DelegationBuilder(p).build()));
     }
 
     // Remove all peers.
     for (auto p : peerids) {
         pm.removePeer(p);
     }
 
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 300);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 300);
 
     for (int i = 0; i < 100; i++) {
         BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER);
     }
 
     BOOST_CHECK_EQUAL(pm.compact(), 300);
     BOOST_CHECK(pm.verify());
     BOOST_CHECK_EQUAL(pm.getSlotCount(), 0);
     BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
 }
 
 BOOST_AUTO_TEST_CASE(node_crud) {
     PeerManager pm;
 
     // Create one peer.
     Proof proof = buildRandomProof(100000000);
     Delegation dg = DelegationBuilder(proof).build();
     BOOST_CHECK_EQUAL(pm.selectNode(), NO_NODE);
 
     // Add 4 nodes.
     for (int i = 0; i < 4; i++) {
         BOOST_CHECK(pm.addNode(i, proof, dg));
     }
 
     for (int i = 0; i < 100; i++) {
         NodeId n = pm.selectNode();
         BOOST_CHECK(n >= 0 && n < 4);
         BOOST_CHECK(
             pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
     }
 
     // Remove a node, check that it doesn't show up.
     BOOST_CHECK(pm.removeNode(2));
 
     for (int i = 0; i < 100; i++) {
         NodeId n = pm.selectNode();
         BOOST_CHECK(n == 0 || n == 1 || n == 3);
         BOOST_CHECK(
             pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
     }
 
     // Push a node's timeout in the future, so that it doesn't show up.
     BOOST_CHECK(pm.updateNextRequestTime(1, std::chrono::steady_clock::now() +
                                                 std::chrono::hours(24)));
 
     for (int i = 0; i < 100; i++) {
         NodeId n = pm.selectNode();
         BOOST_CHECK(n == 0 || n == 3);
         BOOST_CHECK(
             pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
     }
 
     // Move a node from a peer to another. This peer has a very low score such
     // as chances of being picked are 1 in a billion.
     Proof altproof = buildRandomProof(1);
     Delegation altdg = DelegationBuilder(altproof).build();
     BOOST_CHECK(pm.addNode(3, altproof, altdg));
 
     int node3selected = 0;
     for (int i = 0; i < 100; i++) {
         NodeId n = pm.selectNode();
         if (n == 3) {
             // Selecting this node should be exceedingly unlikely.
             BOOST_CHECK(node3selected++ < 1);
         } else {
             BOOST_CHECK_EQUAL(n, 0);
         }
         BOOST_CHECK(
             pm.updateNextRequestTime(n, std::chrono::steady_clock::now()));
     }
 }
 
 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.getPeerId(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()