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/proofpool.cpp avalanche/voterecord.cpp banman.cpp blockencodings.cpp diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h new file mode 100644 --- /dev/null +++ b/src/avalanche/proofpool.h @@ -0,0 +1,50 @@ +// 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_PROOFPOOL_H +#define BITCOIN_AVALANCHE_PROOFPOOL_H + +#include +#include +#include // For SaltedOutpointHasher +#include // For COutPoint + +#include +#include + +namespace avalanche { + +/** + * Store the proofs indexed by utxo, sorted using the conflicting proof + * comparator. + * + * TODO Implement the CCoinsView interface and use it to determine if a coin is + * locked due to staking. + */ +class ProofPool { + size_t maxProofsPerUtxo; + + using UtxoMap = + std::unordered_map, + SaltedOutpointHasher>; + UtxoMap utxos; + +public: + ProofPool(size_t maxProofsPerUtxoIn = 2) + : maxProofsPerUtxo(maxProofsPerUtxoIn) {} + + bool addProof(const ProofRef &proof, std::set &shifted); + bool removeProof(const ProofRef &proof); + + template + bool forUtxo(const COutPoint &outpoint, Callable fun) const { + auto it = utxos.find(outpoint); + return it != utxos.end() && fun(it->second); + } +}; + +} // namespace avalanche + +#endif // BITCOIN_AVALANCHE_PROOFPOOL_H diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche/proofpool.cpp @@ -0,0 +1,58 @@ +// 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 + +#include + +#include + +namespace avalanche { + +bool ProofPool::addProof(const ProofRef &proof, std::set &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() > maxProofsPerUtxo) { + auto pit = std::prev(proofs.end()); + + // Don't keep half baked proofs + removeProof(*pit); + } + assert(proofs.size() <= maxProofsPerUtxo); + + // TODO Use contains after C++20 + success = success && proofs.count(proof) > 0; + } + + return success; +} + +bool ProofPool::removeProof(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 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 + proofpool_tests.cpp ) target_link_libraries(test-avalanche server testutil) diff --git a/src/avalanche/test/proofpool_tests.cpp b/src/avalanche/test/proofpool_tests.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche/test/proofpool_tests.cpp @@ -0,0 +1,310 @@ +// 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 + +#include +#include + +#include +#include + +#include + +#include + +using namespace avalanche; + +BOOST_FIXTURE_TEST_SUITE(proofpool_tests, TestingSetup) + +static bool hasAllProofUtxos(const ProofPool &pool, const ProofRef &proof) { + bool hasAllUtxos = true; + for (const SignedStake &ss : proof->getStakes()) { + hasAllUtxos = + hasAllUtxos && + pool.forUtxo(ss.getStake().getUTXO(), [&](const auto &proofs) { + return proofs.find(proof) != proofs.end(); + }); + } + + return hasAllUtxos; +} + +static bool isBestCandidateForAllUtxos(const ProofPool &pool, + const ProofRef &proof) { + bool isBestCandidateForAllUtxos = true; + for (const SignedStake &ss : proof->getStakes()) { + isBestCandidateForAllUtxos = + isBestCandidateForAllUtxos && + pool.forUtxo(ss.getStake().getUTXO(), [&](const auto &proofs) { + return !proofs.empty() && + (*proofs.begin())->getId() == proof->getId(); + }); + } + + return isBestCandidateForAllUtxos; +} + +static void checkAddProof(size_t maxProofsPerUtxo) { + ProofPool pool(maxProofsPerUtxo); + + const CKey key = CKey::MakeCompressedKey(); + size_t depth = 2 * maxProofsPerUtxo; + + { + auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); + // Adding a single proof several times has no effect + for (size_t i = 0; i < 10; i++) { + std::set shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + BOOST_CHECK(isBestCandidateForAllUtxos(pool, 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 shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof)); + BOOST_CHECK(shifted.empty()); + } + + // Non conflicting proofs, multiple pool + 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 shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof)); + BOOST_CHECK(shifted.empty()); + } + + { + // Conflicting proofs, single utxo + std::vector 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 shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + + // This is our favorite + BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof)); + + // Last maxProofsPerUtxo proofs should be added + for (size_t j = 0; j < std::min(i, maxProofsPerUtxo); j++) { + BOOST_CHECK(hasAllProofUtxos(pool, proofs[i - j])); + } + + // Last [1, maxProofsPerUtxo) proofs should be shifted + std::set expectedShifted( + proofs.begin() + i - std::min(i, maxProofsPerUtxo), + proofs.begin() + i); + BOOST_CHECK_EQUAL_COLLECTIONS(shifted.begin(), shifted.end(), + expectedShifted.begin(), + expectedShifted.end()); + + // Proofs over maxProofsPerUtxo are evicted + for (size_t j = maxProofsPerUtxo; j < std::max(i, maxProofsPerUtxo); + j++) { + BOOST_CHECK(!hasAllProofUtxos(pool, proofs[i - j])); + } + } + } + + { + // Conflicting proofs, multiples utxos + std::vector proofs; + + std::vector 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 shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + + // This is our favorite + BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof)); + + // Last maxProofsPerUtxo proofs should be attached + for (size_t j = 0; j < std::min(i, maxProofsPerUtxo); j++) { + BOOST_CHECK(hasAllProofUtxos(pool, proofs[i - j])); + } + + // Last [1, maxProofsPerUtxo) proofs should be shifted + std::set expectedShifted( + proofs.begin() + i - std::min(i, maxProofsPerUtxo), + proofs.begin() + i); + BOOST_CHECK_EQUAL_COLLECTIONS(shifted.begin(), shifted.end(), + expectedShifted.begin(), + expectedShifted.end()); + + // Proofs over maxProofsPerUtxo are evicted + for (size_t j = maxProofsPerUtxo; j < std::max(i, maxProofsPerUtxo); + j++) { + BOOST_CHECK(!hasAllProofUtxos(pool, proofs[i - j])); + } + } + } +} + +BOOST_AUTO_TEST_CASE(add_proof) { + for (size_t maxProof : {1, 2, 5, 10, 20, 50}) { + checkAddProof(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 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 proofs{proof12, proof23, proof13}; + + const std::vector expectedOutpoint1 = {proof13, proof12}; + const std::vector expectedOutpoint2 = {proof23, proof12}; + const std::vector expectedOutpoint3 = {proof13, proof23}; + + auto checkUtxo = [&](const ProofPool &pool, const COutPoint &outpoint, + const std::vector &expectedOutpoint) { + BOOST_CHECK(pool.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++) { + ProofPool pool(2); + + Shuffle(proofs.begin(), proofs.end(), FastRandomContext()); + + for (const auto &p : proofs) { + std::set shifted; + pool.addProof(p, shifted); + } + + checkUtxo(pool, outpoint1, expectedOutpoint1); + checkUtxo(pool, outpoint2, expectedOutpoint2); + checkUtxo(pool, outpoint3, expectedOutpoint3); + + // proof1234 will be evicted because all its utxos can't make it to the + // pool + BOOST_CHECK(!hasAllProofUtxos(pool, proof1234)); + } +} + +BOOST_AUTO_TEST_CASE(remove_proof) { + ProofPool pool(2); + + // Removing a proof which is not in the pool has no effect + BOOST_CHECK(pool.removeProof(buildRandomProof(MIN_VALID_PROOF_SCORE))); + + // Sequentially add and remove + for (size_t i = 0; i < 10; i++) { + auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); + + std::set shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + BOOST_CHECK(hasAllProofUtxos(pool, proof)); + + BOOST_CHECK(pool.removeProof(proof)); + BOOST_CHECK(!hasAllProofUtxos(pool, proof)); + } + + { + // Add and remove in batch + std::vector proofs; + for (size_t i = 0; i < 10; i++) { + auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); + proofs.emplace_back(proof); + + std::set shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + BOOST_CHECK(hasAllProofUtxos(pool, proof)); + } + for (const auto &proof : proofs) { + BOOST_CHECK(pool.removeProof(proof)); + BOOST_CHECK(!hasAllProofUtxos(pool, proof)); + } + } + + { + // Check removing 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 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 proofs{proof12, proof23, proof13}; + + for (const auto &proof : proofs) { + std::set shifted; + BOOST_CHECK(pool.addProof(proof, shifted)); + BOOST_CHECK(hasAllProofUtxos(pool, proof)); + } + + for (const auto &proof : proofs) { + BOOST_CHECK(pool.removeProof(proof)); + BOOST_CHECK(!hasAllProofUtxos(pool, proof)); + } + } +} + +BOOST_AUTO_TEST_SUITE_END()