diff --git a/src/avalanche/proofcomparator.h b/src/avalanche/proofcomparator.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/proofcomparator.h
@@ -0,0 +1,34 @@
+// Copyright (c) 2021 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_PROOFCOMPARATOR_H
+#define BITCOIN_AVALANCHE_PROOFCOMPARATOR_H
+
+#include <avalanche/proof.h>
+
+#include <cstdint>
+#include <memory>
+
+namespace avalanche {
+
+/**
+ * Compare shared pointers to proof by score, then by id in case of equality.
+ */
+struct ProofSharedPointerComparator {
+    bool operator()(const std::shared_ptr<Proof> &lhs,
+                    const std::shared_ptr<Proof> &rhs) const {
+        uint32_t scoreLhs = lhs->getScore();
+        uint32_t scoreRhs = rhs->getScore();
+
+        if (scoreLhs != scoreRhs) {
+            return scoreLhs > scoreRhs;
+        }
+
+        return lhs->getId() < rhs->getId();
+    }
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_PROOFCOMPARATOR_H
diff --git a/src/avalanche/test/proof_tests.cpp b/src/avalanche/test/proof_tests.cpp
--- a/src/avalanche/test/proof_tests.cpp
+++ b/src/avalanche/test/proof_tests.cpp
@@ -5,6 +5,7 @@
 #include <avalanche/proof.h>
 
 #include <avalanche/proofbuilder.h>
+#include <avalanche/proofcomparator.h>
 #include <avalanche/test/util.h>
 #include <avalanche/validation.h>
 #include <coins.h>
@@ -612,4 +613,45 @@
     BOOST_CHECK_EQUAL(proofid, computeProofId());
 }
 
+BOOST_AUTO_TEST_CASE(proof_shared_pointer_comparator) {
+    uint32_t score = MIN_VALID_PROOF_SCORE;
+
+    auto proofMinScore =
+        std::make_shared<Proof>(buildRandomProof(MIN_VALID_PROOF_SCORE));
+    auto proofMaxScore = std::make_shared<Proof>(
+        buildRandomProof(std::numeric_limits<uint32_t>::max()));
+
+    const ProofSharedPointerComparator comparator;
+
+    auto prevProof = proofMinScore;
+    for (size_t i = 0; i < 100; i++) {
+        score += 1000 + GetRandInt(10000);
+        auto higherScoreProof =
+            std::make_shared<Proof>(buildRandomProof(score));
+        BOOST_CHECK(comparator(higherScoreProof, proofMinScore));
+        BOOST_CHECK(comparator(higherScoreProof, prevProof));
+        BOOST_CHECK(!comparator(higherScoreProof, proofMaxScore));
+        prevProof = higherScoreProof;
+    }
+
+    // Decrement slower than we incremented, so we don't have to check whether
+    // the score reached the minimal value.
+    for (size_t i = 0; i < 100; i++) {
+        score -= 1 + GetRandInt(100);
+        auto lowerScoreProof = std::make_shared<Proof>(buildRandomProof(score));
+        BOOST_CHECK(comparator(lowerScoreProof, proofMinScore));
+        BOOST_CHECK(!comparator(lowerScoreProof, prevProof));
+        BOOST_CHECK(!comparator(lowerScoreProof, proofMaxScore));
+        prevProof = lowerScoreProof;
+    }
+
+    for (size_t i = 0; i < 100; i++) {
+        auto anotherProofMinScore =
+            std::make_shared<Proof>(buildRandomProof(MIN_VALID_PROOF_SCORE));
+        BOOST_CHECK_EQUAL(comparator(anotherProofMinScore, proofMinScore),
+                          anotherProofMinScore->getId() <
+                              proofMinScore->getId());
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()