diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -539,6 +539,7 @@ addrman.cpp avalanche/delegation.cpp avalanche/delegationbuilder.cpp + avalanche/orphanproofpool.cpp avalanche/peermanager.cpp avalanche/processor.cpp avalanche/proof.cpp diff --git a/src/avalanche/orphanproofpool.h b/src/avalanche/orphanproofpool.h new file mode 100644 --- /dev/null +++ b/src/avalanche/orphanproofpool.h @@ -0,0 +1,78 @@ +// 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_ORPHANPROOFPOOL_H +#define BITCOIN_AVALANCHE_ORPHANPROOFPOOL_H + +#include + +#include +#include +#include + +namespace avalanche { + +// Extracts a ProofId from a Proof +struct proofid_extractor { + using result_type = ProofId; + result_type operator()(const Proof &proof) const { return proof.getId(); } +}; + +struct by_sequence {}; +struct by_proofid {}; + +using ProofContainer = boost::multi_index_container< + Proof, + boost::multi_index::indexed_by< + // keep insertion order + boost::multi_index::sequenced>, + // indexed by proofid + boost::multi_index::hashed_unique, + proofid_extractor, + SaltedProofIdHasher>>>; + +/** + * OrphanProofPool stores orphan proofs waiting for their UTXOs to be + * discovered. + * The pool has a size limit. When the pool is full, the oldest proof is + * removed when a new one is added. + */ +class OrphanProofPool { + ProofContainer proofs; + + const size_t maxNumberOfStakes; + size_t nStakes = 0; + + /** + * Trim the proof pool to given max size. + * It the current size is <= max size this has no effect. + */ + void trimToMaximumSize(); + +public: + OrphanProofPool(size_t maxNumberOfStakes) + : maxNumberOfStakes(maxNumberOfStakes) {} + + /** + * Add a proof to the pool. + * The caller is responsible for checking the proof. + */ + bool addProof(Proof proof); + + /** Remove a proof from the pool. */ + bool removeProof(const ProofId &proofId); + + /** + * Get a pointer to a proof by id, or nullptr if the proof is not in the + * pool. + */ + const Proof *getProof(const ProofId &proofId) const; + + // For testing + size_t getNProofs() const; + size_t getNStakes() const; +}; + +} // namespace avalanche + +#endif // BITCOIN_AVALANCHE_ORPHANPROOFPOOL_H diff --git a/src/avalanche/orphanproofpool.cpp b/src/avalanche/orphanproofpool.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche/orphanproofpool.cpp @@ -0,0 +1,53 @@ +// 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 + +namespace avalanche { + +void OrphanProofPool::trimToMaximumSize() { + auto &proofs_by_sequence = proofs.get(); + auto it = proofs_by_sequence.begin(); + while (nStakes > maxNumberOfStakes) { + nStakes -= it->getStakes().size(); + it = proofs_by_sequence.erase(it); + } +} + +bool OrphanProofPool::addProof(Proof proof) { + size_t nStakesProof = proof.getStakes().size(); + if (!proofs.push_back(std::move(proof)).second) { + return false; + } + nStakes += nStakesProof; + trimToMaximumSize(); + return true; +} + +bool OrphanProofPool::removeProof(const ProofId &proofId) { + auto &proofs_by_id = proofs.get(); + auto it = proofs_by_id.find(proofId); + if (it == proofs_by_id.end()) { + return false; + } + nStakes -= it->getStakes().size(); + proofs_by_id.erase(it); + return true; +} + +const Proof *OrphanProofPool::getProof(const ProofId &proofId) const { + auto &proofs_by_proofid = proofs.get(); + auto it = proofs_by_proofid.find(proofId); + return it == proofs_by_proofid.end() ? nullptr : &*it; +} + +size_t OrphanProofPool::getNProofs() const { + return proofs.size(); +} + +size_t OrphanProofPool::getNStakes() const { + return nStakes; +} + +} // namespace avalanche diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h --- a/src/avalanche/peermanager.h +++ b/src/avalanche/peermanager.h @@ -77,13 +77,6 @@ result_type operator()(const Peer &p) const { return p.proof.getId(); } }; -class SaltedProofIdHasher : private SaltedUint256Hasher { -public: - SaltedProofIdHasher() : SaltedUint256Hasher() {} - - size_t operator()(const ProofId &proofid) const { return hash(proofid); } -}; - struct next_request_time {}; class PeerManager { diff --git a/src/avalanche/proofid.h b/src/avalanche/proofid.h --- a/src/avalanche/proofid.h +++ b/src/avalanche/proofid.h @@ -5,6 +5,7 @@ #ifndef BITCOIN_AVALANCHE_PROOFID_H #define BITCOIN_AVALANCHE_PROOFID_H +#include #include #include @@ -21,6 +22,13 @@ return r; } }; + +class SaltedProofIdHasher : private SaltedUint256Hasher { +public: + SaltedProofIdHasher() : SaltedUint256Hasher() {} + size_t operator()(const ProofId &proofid) const { return hash(proofid); } +}; + } // namespace avalanche #endif // BITCOIN_AVALANCHE_PROOFID_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 @@ -14,6 +14,7 @@ TESTS delegation_tests.cpp + orphanproofpool_tests.cpp peermanager_tests.cpp processor_tests.cpp proof_tests.cpp diff --git a/src/avalanche/test/orphanproofpool_tests.cpp b/src/avalanche/test/orphanproofpool_tests.cpp new file mode 100644 --- /dev/null +++ b/src/avalanche/test/orphanproofpool_tests.cpp @@ -0,0 +1,174 @@ +// 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 + +using namespace avalanche; + +BOOST_FIXTURE_TEST_SUITE(orphanproofpool_tests, TestingSetup) + +/** Make a proof with stakes using random txids */ +static Proof makeProof(const size_t nStakes) { + const Amount v = 5 * COIN; + const int height = 1234; + CKey key; + key.MakeNewKey(true); + ProofBuilder pb(0, 0, CPubKey()); + for (size_t i = 0; i < nStakes; i++) { + TxId txid(GetRandHash()); + pb.addUTXO(COutPoint(txid, 0), v, height, false, key); + } + return pb.build(); +} + +BOOST_AUTO_TEST_CASE(pool_starts_empty) { + OrphanProofPool pool{10}; + BOOST_CHECK_EQUAL(pool.getNProofs(), 0); + BOOST_CHECK_EQUAL(pool.getNStakes(), 0); +} + +BOOST_AUTO_TEST_CASE(fail_to_add_same_proof_twice) { + OrphanProofPool pool{10}; + Proof p = makeProof(1); + BOOST_CHECK(!pool.getProof(p.getId())); + BOOST_CHECK(pool.addProof(p)); + BOOST_CHECK(pool.getProof(p.getId())); + BOOST_CHECK(!pool.addProof(p)); + BOOST_CHECK(pool.getProof(p.getId())); +} + +BOOST_AUTO_TEST_CASE(check_eviction_behavior) { + // The size 1035 causes the pool to be filled to maximum capacity + // at one point (1 + 2 ... + 45). + // We do not check pool sizes smaller than the largest possible proof, + // as this is not expected to be used in production and already has + // a (simpler) unit test. + std::vector maxPoolSizes{1035, 1337}; + + for (size_t maxPoolSize : maxPoolSizes) { + std::queue> qProofSizes; + OrphanProofPool pool{maxPoolSize}; + + size_t nStakes = 0; + size_t nextProofSize = 1; + size_t nProofs = 0; + + // Fill the pool with proofs of various sizes + while (nStakes + nextProofSize <= maxPoolSize) { + Proof p = makeProof(nextProofSize); + BOOST_CHECK(pool.addProof(p)); + BOOST_CHECK(pool.getProof(p.getId())); + + nProofs++; + nStakes += nextProofSize; + BOOST_CHECK_EQUAL(pool.getNStakes(), nStakes); + BOOST_CHECK_EQUAL(pool.getNProofs(), nProofs); + + qProofSizes.push(std::make_pair(p.getId(), p.getStakes().size())); + nextProofSize = (nextProofSize + 1) % AVALANCHE_MAX_PROOF_STAKES; + } + + // Keep adding proofs, check that now we are dropping earlier proofs + for (size_t i = 0; i < 100; i++) { + BOOST_CHECK(pool.getProof(qProofSizes.front().first)); + + Proof p = makeProof(nextProofSize); + BOOST_CHECK(pool.addProof(p)); + BOOST_CHECK(pool.getProof(p.getId())); + qProofSizes.push(std::make_pair(p.getId(), p.getStakes().size())); + + nStakes += nextProofSize; + nProofs += 1; + while (nStakes > maxPoolSize) { + BOOST_CHECK(!pool.getProof(qProofSizes.front().first)); + nStakes -= qProofSizes.front().second; + nProofs -= 1; + qProofSizes.pop(); + } + + BOOST_CHECK_EQUAL(pool.getNStakes(), nStakes); + BOOST_CHECK_EQUAL(pool.getNProofs(), nProofs); + + nextProofSize = (nextProofSize + 1) % AVALANCHE_MAX_PROOF_STAKES; + } + } +} + +BOOST_AUTO_TEST_CASE(remove_proofs) { + OrphanProofPool pool{1337}; + std::vector vProofIds; + + // Add a few proofs + size_t nStakes = 0; + for (size_t i = 1; i <= 10; i++) { + Proof p = makeProof(i); + vProofIds.push_back(p.getId()); + BOOST_CHECK(pool.addProof(p)); + nStakes += i; + } + + const auto checkSize = [&](const size_t expectedNProofs) { + BOOST_CHECK_EQUAL(pool.getNProofs(), expectedNProofs); + BOOST_CHECK_EQUAL(pool.getNStakes(), nStakes); + }; + + // Remove a proof in the middle + BOOST_CHECK(pool.removeProof(vProofIds.at(5))); + nStakes -= 6; + checkSize(9); + + ProofId deletedProofId = vProofIds[5]; + vProofIds.erase(vProofIds.begin() + 5); + + // Remove a proof at the front + BOOST_CHECK(pool.removeProof(vProofIds.front())); + nStakes -= 1; + checkSize(8); + vProofIds.erase(vProofIds.begin()); + + // Remove a proof at the back + BOOST_CHECK(pool.removeProof(vProofIds.back())); + nStakes -= 10; + checkSize(7); + vProofIds.pop_back(); + + // Fail to remove a proof that is longer in the pool + BOOST_CHECK(!pool.removeProof(deletedProofId)); + checkSize(7); + + // Fail to remove a proof that was never in the pool + Proof p = makeProof(11); + BOOST_CHECK(!pool.getProof(p.getId())); + BOOST_CHECK(!pool.removeProof(p.getId())); + checkSize(7); +} + +BOOST_AUTO_TEST_CASE(add_proof_larger_than_pool) { + OrphanProofPool pool{AVALANCHE_MAX_PROOF_STAKES - 1}; + + // Add a couple of small proofs + BOOST_CHECK(pool.addProof(makeProof(1))); + BOOST_CHECK_EQUAL(pool.getNStakes(), 1); + BOOST_CHECK_EQUAL(pool.getNProofs(), 1); + + BOOST_CHECK(pool.addProof(makeProof(2))); + BOOST_CHECK_EQUAL(pool.getNStakes(), 3); + BOOST_CHECK_EQUAL(pool.getNProofs(), 2); + + // Adding a proof larger than the pool causes the pool to be emptied + BOOST_CHECK(pool.addProof(makeProof(AVALANCHE_MAX_PROOF_STAKES))); + BOOST_CHECK_EQUAL(pool.getNStakes(), 0); + BOOST_CHECK_EQUAL(pool.getNProofs(), 0); +} + +BOOST_AUTO_TEST_SUITE_END()