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,164 @@ +// 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(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_EQUAL(pool.getNStakes(), 1); + BOOST_CHECK_EQUAL(pool.getNProofs(), 1); + BOOST_CHECK(pool.getProof(p.getId())); + + BOOST_CHECK(!pool.addProof(p)); + BOOST_CHECK_EQUAL(pool.getNStakes(), 1); + BOOST_CHECK_EQUAL(pool.getNProofs(), 1); + BOOST_CHECK(pool.getProof(p.getId())); +} + +BOOST_AUTO_TEST_CASE(check_eviction_behavior) { + { + // Fill the pool + OrphanProofPool pool{7}; + Proof first = makeProof(4); + pool.addProof(first); + pool.addProof(makeProof(2)); + pool.addProof(makeProof(1)); + BOOST_CHECK_EQUAL(pool.getNStakes(), 7); + BOOST_CHECK_EQUAL(pool.getNProofs(), 3); + BOOST_CHECK(pool.getProof(first.getId())); + } + + { + OrphanProofPool pool{6}; + Proof first = makeProof(4); + pool.addProof(first); + pool.addProof(makeProof(2)); + BOOST_CHECK_EQUAL(pool.getNStakes(), 6); + BOOST_CHECK_EQUAL(pool.getNProofs(), 2); + + // The oldest proof has to be dropped + pool.addProof(makeProof(1)); + BOOST_CHECK_EQUAL(pool.getNStakes(), 3); + BOOST_CHECK_EQUAL(pool.getNProofs(), 2); + BOOST_CHECK(!pool.getProof(first.getId())); + } + + { + OrphanProofPool pool{15}; + Proof first = makeProof(1); + pool.addProof(first); + Proof second = makeProof(2); + pool.addProof(second); + pool.addProof(makeProof(4)); + pool.addProof(makeProof(8)); + BOOST_CHECK_EQUAL(pool.getNStakes(), 15); + BOOST_CHECK_EQUAL(pool.getNProofs(), 4); + + // Multiple proofs are dropped if needed + pool.addProof(makeProof(2)); + BOOST_CHECK_EQUAL(pool.getNStakes(), 14); + BOOST_CHECK_EQUAL(pool.getNProofs(), 3); + BOOST_CHECK(!pool.getProof(first.getId())); + BOOST_CHECK(!pool.getProof(second.getId())); + } +} + +BOOST_AUTO_TEST_CASE(remove_proofs) { + OrphanProofPool pool{1337}; + std::array aProofIds; + + // Add 10 proofs + for (size_t i = 0; i < 10; i++) { + Proof p = makeProof(i + 1); + aProofIds[i] = p.getId(); + BOOST_CHECK(pool.addProof(p)); + } + BOOST_CHECK_EQUAL(pool.getNProofs(), 10); + BOOST_CHECK_EQUAL(pool.getNStakes(), 55); + + // Remove a proof in the middle + BOOST_CHECK(pool.removeProof(aProofIds[5])); + BOOST_CHECK_EQUAL(pool.getNProofs(), 9); + BOOST_CHECK_EQUAL(pool.getNStakes(), 49); + + // Remove a proof at the front + BOOST_CHECK(pool.removeProof(aProofIds[0])); + BOOST_CHECK_EQUAL(pool.getNProofs(), 8); + BOOST_CHECK_EQUAL(pool.getNStakes(), 48); + + // Remove a proof at the back + BOOST_CHECK(pool.removeProof(aProofIds[9])); + BOOST_CHECK_EQUAL(pool.getNProofs(), 7); + BOOST_CHECK_EQUAL(pool.getNStakes(), 38); + + // Fail to remove a proof that is longer in the pool + BOOST_CHECK(!pool.removeProof(aProofIds[5])); + BOOST_CHECK_EQUAL(pool.getNProofs(), 7); + BOOST_CHECK_EQUAL(pool.getNStakes(), 38); + + // 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())); + BOOST_CHECK_EQUAL(pool.getNProofs(), 7); + BOOST_CHECK_EQUAL(pool.getNStakes(), 38); +} + +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()