diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -15,6 +15,7 @@
 
 #include <boost/multi_index/composite_key.hpp>
 #include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/mem_fun.hpp>
 #include <boost/multi_index/member.hpp>
 #include <boost/multi_index/ordered_index.hpp>
 #include <boost/multi_index_container.hpp>
@@ -90,9 +91,25 @@
     uint32_t getScore() const { return proof->getScore(); }
 };
 
-struct proof_index {
+struct ProofPoolEntry {
+    size_t utxoIndex;
+    ProofRef proof;
+
+    const COutPoint &getUTXO() const {
+        return proof->getStakes().at(utxoIndex).getStake().getUTXO();
+    }
+
+    ProofPoolEntry(size_t _utxoIndex, const ProofRef &_proof)
+        : utxoIndex(_utxoIndex), proof(_proof) {}
+};
+
+struct by_utxo;
+
+template <typename StructWithProof> struct proof_index {
     using result_type = ProofId;
-    result_type operator()(const Peer &p) const { return p.proof->getId(); }
+    result_type operator()(const StructWithProof &s) const {
+        return s.proof->getId();
+    }
 };
 
 struct next_request_time {};
@@ -124,13 +141,30 @@
                   // index by peerid
                   bmi::hashed_unique<bmi::member<Peer, PeerId, &Peer::peerid>>,
                   // index by proof
-                  bmi::hashed_unique<bmi::tag<by_proofid>, proof_index,
+                  bmi::hashed_unique<bmi::tag<by_proofid>, proof_index<Peer>,
                                      SaltedProofIdHasher>>>;
 
     PeerId nextPeerId = 0;
     PeerSet peers;
 
-    std::unordered_map<COutPoint, ProofRef, SaltedOutpointHasher> utxos;
+    /**
+     * Map a proof to each utxo. A proof can be mapped with several utxos.
+     */
+    using ProofPool = boost::multi_index_container<
+        ProofPoolEntry,
+        bmi::indexed_by<
+            // index by utxo
+            bmi::hashed_unique<
+                bmi::tag<by_utxo>,
+                bmi::const_mem_fun<ProofPoolEntry, const COutPoint &,
+                                   &ProofPoolEntry::getUTXO>,
+                SaltedOutpointHasher>,
+            // index by proofid
+            bmi::hashed_non_unique<bmi::tag<by_proofid>,
+                                   proof_index<ProofPoolEntry>,
+                                   SaltedProofIdHasher>>>;
+
+    ProofPool validProofPool;
 
     using NodeSet = boost::multi_index_container<
         Node,
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -265,23 +265,23 @@
 
     // Attach UTXOs to this proof.
     std::unordered_set<ProofRef> conflicting_proofs;
-    for (const auto &s : proof->getStakes()) {
-        auto p = utxos.emplace(s.getStake().getUTXO(), proof);
+    for (size_t i = 0; i < proof->getStakes().size(); i++) {
+        auto p = validProofPool.emplace(i, proof);
         if (!p.second) {
             // We have a collision with an existing proof.
-            conflicting_proofs.insert(p.first->second);
+            conflicting_proofs.insert(p.first->proof);
         }
     }
 
     // For now, if there is a conflict, just cleanup the mess.
     if (conflicting_proofs.size() > 0) {
         for (const auto &s : proof->getStakes()) {
-            auto it = utxos.find(s.getStake().getUTXO());
-            assert(it != utxos.end());
+            auto it = validProofPool.find(s.getStake().getUTXO());
+            assert(it != validProofPool.end());
 
             // We need to delete that one.
-            if (it->second->getId() == proofid) {
-                utxos.erase(it);
+            if (it->proof->getId() == proofid) {
+                validProofPool.erase(it);
             }
         }
 
@@ -341,7 +341,7 @@
 
     // Release UTXOs attached to this proof.
     for (const auto &s : it->proof->getStakes()) {
-        bool deleted = utxos.erase(s.getStake().getUTXO()) > 0;
+        bool deleted = validProofPool.erase(s.getStake().getUTXO()) > 0;
         assert(deleted);
     }
 
@@ -430,18 +430,18 @@
             return false;
         }
 
-        // Check utxos consistency
+        // Check proof pool consistency
         for (const auto &ss : p.proof->getStakes()) {
-            auto it = utxos.find(ss.getStake().getUTXO());
+            auto it = validProofPool.find(ss.getStake().getUTXO());
 
-            if (it == utxos.end()) {
+            if (it == validProofPool.end()) {
                 return false;
             }
-            if (it->second->getId() != p.getProofId()) {
+            if (it->proof->getId() != p.getProofId()) {
                 return false;
             }
 
-            if (!peersUtxos.emplace(it->first).second) {
+            if (!peersUtxos.emplace(it->getUTXO()).second) {
                 return false;
             }
         }
@@ -483,8 +483,8 @@
     }
 
     // Check there is no dangling utxo
-    for (const auto &[outpoint, proof] : utxos) {
-        if (!peersUtxos.count(outpoint)) {
+    for (const auto &entry : validProofPool) {
+        if (!peersUtxos.count(entry.getUTXO())) {
             return false;
         }
     }
diff --git a/test/lint/lint-boost-dependencies.sh b/test/lint/lint-boost-dependencies.sh
--- a/test/lint/lint-boost-dependencies.sh
+++ b/test/lint/lint-boost-dependencies.sh
@@ -21,6 +21,7 @@
     boost/multi_index/composite_key.hpp
     boost/multi_index/hashed_index.hpp
     boost/multi_index/member.hpp
+    boost/multi_index/mem_fun.hpp
     boost/multi_index/ordered_index.hpp
     boost/multi_index/sequenced_index.hpp
     boost/multi_index_container.hpp