diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -541,6 +541,7 @@
add_library(server
addrdb.cpp
addrman.cpp
+ # TODO Create an avalanche library
avalanche/avalanche.cpp
avalanche/delegation.cpp
avalanche/delegationbuilder.cpp
@@ -550,6 +551,7 @@
avalanche/proof.cpp
avalanche/proofid.cpp
avalanche/proofbuilder.cpp
+ avalanche/utxostore.cpp
avalanche/voterecord.cpp
banman.cpp
blockencodings.cpp
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
@@ -19,6 +19,7 @@
processor_tests.cpp
proof_tests.cpp
proofcomparator_tests.cpp
+ utxostore_tests.cpp
)
target_link_libraries(test-avalanche server testutil)
diff --git a/src/avalanche/test/utxostore_tests.cpp b/src/avalanche/test/utxostore_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/test/utxostore_tests.cpp
@@ -0,0 +1,307 @@
+// 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/utxostore.h>
+
+#include <avalanche/proof.h>
+#include <avalanche/proofbuilder.h>
+
+#include <avalanche/test/util.h>
+#include <test/util/setup_common.h>
+
+#include <boost/test/unit_test.hpp>
+
+#include <set>
+
+using namespace avalanche;
+
+BOOST_FIXTURE_TEST_SUITE(utxostore_tests, TestingSetup)
+
+static bool isProofAttached(const UtxoStore &utxos, const ProofRef &proof) {
+ bool hasAllUtxos = true;
+ for (const SignedStake &ss : proof->getStakes()) {
+ hasAllUtxos =
+ hasAllUtxos &&
+ utxos.forUtxo(ss.getStake().getUTXO(), [&](const auto &proofs) {
+ return proofs.find(proof) != proofs.end();
+ });
+ }
+
+ return hasAllUtxos;
+}
+
+static bool isAllBest(const UtxoStore &utxos, const ProofRef &proof) {
+ bool isAllBest = true;
+ for (const SignedStake &ss : proof->getStakes()) {
+ isAllBest =
+ isAllBest &&
+ utxos.forUtxo(ss.getStake().getUTXO(), [&](const auto &proofs) {
+ return !proofs.empty() &&
+ (*proofs.begin())->getId() == proof->getId();
+ });
+ }
+
+ return isAllBest;
+}
+
+static void checkProofAttachement(size_t maxProofs) {
+ UtxoStore utxos(maxProofs);
+
+ const CKey key = CKey::MakeCompressedKey();
+ size_t depth = 2 * maxProofs;
+
+ {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+ // Attaching a single proof several times has no effect
+ for (size_t i = 0; i < 10; i++) {
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+ BOOST_CHECK(isAllBest(utxos, proof));
+ BOOST_CHECK(shifted.empty());
+ }
+ }
+
+ // Non conflicting proofs, single utxo
+ for (size_t i = 0; i < depth; i++) {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+ BOOST_CHECK(isAllBest(utxos, proof));
+ BOOST_CHECK(shifted.empty());
+ }
+
+ // Non conflicting proofs, multiple utxos
+ for (size_t i = 0; i < depth; i++) {
+ ProofBuilder pb(0, 0, key);
+ for (size_t j = 0; j < 10; j++) {
+ BOOST_CHECK(pb.addUTXO({TxId(GetRandHash()), 0}, 10 * COIN, 42,
+ false, key));
+ }
+ auto proof = pb.build();
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+ BOOST_CHECK(isAllBest(utxos, proof));
+ BOOST_CHECK(shifted.empty());
+ }
+
+ {
+ // Conflicting proofs, single utxo
+ std::vector<ProofRef> proofs;
+ const COutPoint outpoint(TxId(GetRandHash()), 0);
+ for (size_t i = 0; i < depth; i++) {
+ // Increment the sequence number each time
+ ProofBuilder pb(i, 0, key);
+ BOOST_CHECK(pb.addUTXO(outpoint, 10 * COIN, 42, false, key));
+ auto proof = pb.build();
+ proofs.emplace_back(proof);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+
+ // This is our favorite
+ BOOST_CHECK(isAllBest(utxos, proof));
+
+ // Last maxProofs proofs should be attached
+ for (size_t j = 0; j < std::min(i, maxProofs); j++) {
+ BOOST_CHECK(isProofAttached(utxos, proofs[i - j]));
+ }
+
+ // Last [1, maxProofs) proofs should be shifted
+ std::set<ProofRef> expectedShifted(proofs.begin() + i -
+ std::min(i, maxProofs),
+ proofs.begin() + i);
+ BOOST_CHECK_EQUAL_COLLECTIONS(shifted.begin(), shifted.end(),
+ expectedShifted.begin(),
+ expectedShifted.end());
+
+ // Proofs over maxProofs are evicted
+ for (size_t j = maxProofs; j < std::max(i, maxProofs); j++) {
+ BOOST_CHECK(!isProofAttached(utxos, proofs[i - j]));
+ }
+ }
+ }
+
+ {
+ // Conflicting proofs, multiples utxos
+ std::vector<ProofRef> proofs;
+
+ std::vector<COutPoint> outpoints;
+ for (size_t i = 0; i < 10; i++) {
+ outpoints.emplace_back(TxId(GetRandHash()), 0);
+ }
+
+ for (size_t i = 0; i < depth; i++) {
+ // Increment the sequence number each time
+ ProofBuilder pb(i, 0, key);
+ for (const COutPoint &o : outpoints) {
+ BOOST_CHECK(pb.addUTXO(o, 10 * COIN, 42, false, key));
+ }
+ auto proof = pb.build();
+ proofs.emplace_back(proof);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+
+ // This is our favorite
+ BOOST_CHECK(isAllBest(utxos, proof));
+
+ // Last maxProofs proofs should be attached
+ for (size_t j = 0; j < std::min(i, maxProofs); j++) {
+ BOOST_CHECK(isProofAttached(utxos, proofs[i - j]));
+ }
+
+ // Last [1, maxProofs) proofs should be shifted
+ std::set<ProofRef> expectedShifted(proofs.begin() + i -
+ std::min(i, maxProofs),
+ proofs.begin() + i);
+ BOOST_CHECK_EQUAL_COLLECTIONS(shifted.begin(), shifted.end(),
+ expectedShifted.begin(),
+ expectedShifted.end());
+
+ // Proofs over maxProofs are evicted
+ for (size_t j = maxProofs; j < std::max(i, maxProofs); j++) {
+ BOOST_CHECK(!isProofAttached(utxos, proofs[i - j]));
+ }
+ }
+ }
+}
+
+BOOST_AUTO_TEST_CASE(attach_proof) {
+ for (size_t maxProof : {1, 2, 5, 10, 20, 50}) {
+ checkProofAttachement(maxProof);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(overlapping_proofs) {
+ const CKey key = CKey::MakeCompressedKey();
+
+ const COutPoint outpoint1{TxId(GetRandHash()), 0};
+ const COutPoint outpoint2{TxId(GetRandHash()), 0};
+ const COutPoint outpoint3{TxId(GetRandHash()), 0};
+ const COutPoint outpoint4{TxId(GetRandHash()), 0};
+
+ auto buildProof = [&](uint64_t sequence,
+ const std::vector<COutPoint> outpoints) {
+ ProofBuilder pb(sequence, 0, key);
+ for (const COutPoint &o : outpoints) {
+ BOOST_CHECK(pb.addUTXO(o, 10 * COIN, 42, false, key));
+ }
+ return pb.build();
+ };
+
+ // proof13 < proof23 < proof12 < proof1234
+ auto proof1234 =
+ buildProof(0, {outpoint1, outpoint2, outpoint3, outpoint4});
+ auto proof12 = buildProof(10, {outpoint1, outpoint2});
+ auto proof23 = buildProof(20, {outpoint2, outpoint3});
+ auto proof13 = buildProof(30, {outpoint1, outpoint3});
+ std::vector<ProofRef> proofs{proof12, proof23, proof13};
+
+ const std::vector<ProofRef> expectedOutpoint1 = {proof13, proof12};
+ const std::vector<ProofRef> expectedOutpoint2 = {proof23, proof12};
+ const std::vector<ProofRef> expectedOutpoint3 = {proof13, proof23};
+
+ auto checkUtxo = [&](const UtxoStore &utxos, const COutPoint &outpoint,
+ const std::vector<ProofRef> &expectedOutpoint) {
+ BOOST_CHECK(utxos.forUtxo(outpoint, [&](const auto &proofs) {
+ BOOST_CHECK_EQUAL_COLLECTIONS(proofs.begin(), proofs.end(),
+ expectedOutpoint.begin(),
+ expectedOutpoint.end());
+ return true;
+ }));
+ };
+
+ for (size_t i = 0; i < 10; i++) {
+ UtxoStore utxos(2);
+
+ Shuffle(proofs.begin(), proofs.end(), FastRandomContext());
+
+ for (const auto &p : proofs) {
+ std::set<ProofRef> shifted;
+ utxos.attachProof(p, shifted);
+ }
+
+ checkUtxo(utxos, outpoint1, expectedOutpoint1);
+ checkUtxo(utxos, outpoint2, expectedOutpoint2);
+ checkUtxo(utxos, outpoint3, expectedOutpoint3);
+
+ // proof1234 will be evicted because all its utxos can't make it to the
+ // store
+ BOOST_CHECK(!isProofAttached(utxos, proof1234));
+ }
+}
+
+BOOST_AUTO_TEST_CASE(detach_proof) {
+ UtxoStore utxos(2);
+
+ // Detaching a proof which is not in the store has no effect
+ BOOST_CHECK(utxos.detachProof(buildRandomProof(MIN_VALID_PROOF_SCORE)));
+
+ // Sequentially attach and detach
+ for (size_t i = 0; i < 10; i++) {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+ BOOST_CHECK(isProofAttached(utxos, proof));
+
+ BOOST_CHECK(utxos.detachProof(proof));
+ BOOST_CHECK(!isProofAttached(utxos, proof));
+ }
+
+ {
+ // Attach and detach in batch
+ std::vector<ProofRef> proofs;
+ for (size_t i = 0; i < 10; i++) {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+ proofs.emplace_back(proof);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+ BOOST_CHECK(isProofAttached(utxos, proof));
+ }
+ for (const auto &proof : proofs) {
+ BOOST_CHECK(utxos.detachProof(proof));
+ BOOST_CHECK(!isProofAttached(utxos, proof));
+ }
+ }
+
+ {
+ // Check detaching a proof with variable position depending on the utxo
+ const CKey key = CKey::MakeCompressedKey();
+ const COutPoint outpoint1{TxId(GetRandHash()), 0};
+ const COutPoint outpoint2{TxId(GetRandHash()), 0};
+ const COutPoint outpoint3{TxId(GetRandHash()), 0};
+
+ auto buildProof = [&](uint64_t sequence,
+ const std::vector<COutPoint> outpoints) {
+ ProofBuilder pb(sequence, 0, key);
+ for (const COutPoint &o : outpoints) {
+ BOOST_CHECK(pb.addUTXO(o, 10 * COIN, 42, false, key));
+ }
+ return pb.build();
+ };
+
+ // proof13 < proof23 < proof12
+ auto proof12 = buildProof(10, {outpoint1, outpoint2});
+ auto proof23 = buildProof(20, {outpoint2, outpoint3});
+ auto proof13 = buildProof(30, {outpoint1, outpoint3});
+ std::vector<ProofRef> proofs{proof12, proof23, proof13};
+
+ for (const auto &proof : proofs) {
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(utxos.attachProof(proof, shifted));
+ BOOST_CHECK(isProofAttached(utxos, proof));
+ }
+
+ for (const auto &proof : proofs) {
+ BOOST_CHECK(utxos.detachProof(proof));
+ BOOST_CHECK(!isProofAttached(utxos, proof));
+ }
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/avalanche/utxostore.h b/src/avalanche/utxostore.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/utxostore.h
@@ -0,0 +1,55 @@
+// 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_UTXOSTORE_H
+#define BITCOIN_AVALANCHE_UTXOSTORE_H
+
+#include <avalanche/proof.h>
+#include <avalanche/proofcomparator.h>
+#include <coins.h> // For SaltedOutpointHasher
+#include <primitives/transaction.h> // For COutPoint
+
+#include <set>
+#include <unordered_map>
+
+namespace avalanche {
+
+/**
+ * Remembers which utxo is associated with which avalanche proof.
+ *
+ * TODO Implement the CCoinsView interface and use it to determine if a coin is
+ * locked due to staking.
+ */
+class UtxoStore {
+ size_t maxProofs;
+
+ using UtxoMap =
+ std::unordered_map<COutPoint,
+ std::set<ProofRef, ConflictingProofComparator>,
+ SaltedOutpointHasher>;
+ UtxoMap utxos;
+
+public:
+ UtxoStore(size_t maxProofsIn = 2) : maxProofs(maxProofsIn) {}
+
+ bool attachProof(const ProofRef &proof, std::set<ProofRef> &shifted);
+
+ template <typename Callable>
+ bool forUtxo(const COutPoint &outpoint, Callable fun) const {
+ auto it = utxos.find(outpoint);
+ return it != utxos.end() && fun(it->second);
+ }
+
+ template <typename Callable> void forEachUtxo(Callable fun) const {
+ for (const auto &p : utxos) {
+ fun(p.second);
+ }
+ }
+
+ bool detachProof(const ProofRef &proof);
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_UTXOSTORE_H
\ No newline at end of file
diff --git a/src/avalanche/utxostore.cpp b/src/avalanche/utxostore.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/utxostore.cpp
@@ -0,0 +1,59 @@
+// 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/utxostore.h>
+
+#include <unordered_set>
+
+#include <iterator>
+
+namespace avalanche {
+
+bool UtxoStore::attachProof(const ProofRef &proof,
+ std::set<ProofRef> &shifted) {
+ bool success = true;
+ for (const auto &ss : proof->getStakes()) {
+ auto &proofs = utxos[ss.getStake().getUTXO()];
+
+ auto p = proofs.emplace(proof);
+ if (!p.second) {
+ // Already there
+ continue;
+ }
+
+ shifted.insert(std::next(p.first), proofs.end());
+
+ // Trim
+ if (proofs.size() > maxProofs) {
+ auto pit = std::prev(proofs.end());
+
+ // Don't keep half baked proofs
+ detachProof(*pit);
+ }
+ assert(proofs.size() <= maxProofs);
+
+ // TODO Use contains after C++20
+ success = success && proofs.count(proof) > 0;
+ }
+
+ return success;
+}
+
+bool UtxoStore::detachProof(const ProofRef &proof) {
+ for (const SignedStake &ss : proof->getStakes()) {
+ auto it = utxos.find(ss.getStake().getUTXO());
+ if (it == utxos.end()) {
+ continue;
+ }
+
+ it->second.erase(proof);
+ if (it->second.size() == 0) {
+ utxos.erase(it);
+ }
+ }
+
+ return true;
+}
+
+} // namespace avalanche