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,31 @@
+// 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();
+
+        return (scoreLhs != scoreRhs) ? scoreLhs > scoreRhs
+                                      : lhs->getId() < rhs->getId();
+    }
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_PROOFCOMPARATOR_H
diff --git a/src/avalanche/test/CMakeLists.txt b/src/avalanche/test/CMakeLists.txt
--- a/src/avalanche/test/CMakeLists.txt
+++ b/src/avalanche/test/CMakeLists.txt
@@ -18,6 +18,7 @@
 		peermanager_tests.cpp
 		processor_tests.cpp
 		proof_tests.cpp
+		proofcomparator_tests.cpp
 )
 
 target_link_libraries(test-avalanche server testutil)
diff --git a/src/avalanche/test/proofcomparator_tests.cpp b/src/avalanche/test/proofcomparator_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/test/proofcomparator_tests.cpp
@@ -0,0 +1,63 @@
+// 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.
+
+#include <avalanche/proofcomparator.h>
+
+#include <random.h>
+
+#include <avalanche/test/util.h>
+#include <test/util/setup_common.h>
+
+#include <boost/test/unit_test.hpp>
+
+#include <cstdint>
+#include <limits>
+#include <memory>
+
+using namespace avalanche;
+
+BOOST_FIXTURE_TEST_SUITE(proofcomparator_tests, TestingSetup)
+
+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()