diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -550,6 +550,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/peermanager.cpp b/src/avalanche/peermanager.cpp --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -254,51 +254,31 @@ bool PeerManager::createPeer(const ProofRef &proof) { assert(proof); - const ProofId &proofid = proof->getId(); + switch (validProofPool.addProof(proof)) { + case ProofPool::AddProofStatus::REJECTED: + // The proof has conflicts, orphan the proof so it can be pulled + // back if the conflicting ones are invalidated. + orphanProofs.addProof(proof); + return false; + case ProofPool::AddProofStatus::DUPLICATED: + // If the proof was already in the pool, don't duplicate the peer. + return false; + case ProofPool::AddProofStatus::SUCCEED: + break; - if (isBoundToPeer(proofid)) { - return false; + // No default case, so the compiler can warn about missing cases } // New peer means new peerid! const PeerId peerid = nextPeerId++; - // Attach UTXOs to this proof. - std::unordered_set conflicting_proofs; - for (size_t i = 0; i < proof->getStakes().size(); i++) { - auto p = validProofPool.emplace(i, proof); - if (!p.second) { - // We have a collision with an existing proof. - conflicting_proofs.insert(p.first->proof); - } - } - - // For now, if there is a conflict, just cleanup the mess. - if (conflicting_proofs.size() > 0) { - for (const auto &s : proof->getStakes()) { - auto it = validProofPool.find(s.getStake().getUTXO()); - assert(it != validProofPool.end()); - - // We need to delete that one. - if (it->proof->getId() == proofid) { - validProofPool.erase(it); - } - } - - // Orphan the proof so it can be pulled back if the conflicting ones are - // invalidated. - orphanProofs.addProof(proof); - - return false; - } - // We have no peer for this proof, time to create it. auto inserted = peers.emplace(peerid, proof); assert(inserted.second); // If there are nodes waiting for this proof, add them auto &pendingNodesView = pendingNodes.get(); - auto range = pendingNodesView.equal_range(proofid); + auto range = pendingNodesView.equal_range(proof->getId()); // We want to update the nodes then remove them from the pending set. That // will invalidate the range iterators, so we need to save the node ids @@ -340,10 +320,7 @@ peerid, std::chrono::steady_clock::now()))); // Release UTXOs attached to this proof. - for (const auto &s : it->proof->getStakes()) { - bool deleted = validProofPool.erase(s.getStake().getUTXO()) > 0; - assert(deleted); - } + validProofPool.removeProof(it->proof); m_unbroadcast_proofids.erase(it->proof->getId()); @@ -432,9 +409,9 @@ // Check proof pool consistency for (const auto &ss : p.proof->getStakes()) { - auto it = validProofPool.find(ss.getStake().getUTXO()); + auto it = validProofPool.pool.find(ss.getStake().getUTXO()); - if (it == validProofPool.end()) { + if (it == validProofPool.pool.end()) { return false; } if (it->proof->getId() != p.getProofId()) { @@ -483,7 +460,7 @@ } // Check there is no dangling utxo - for (const auto &entry : validProofPool) { + for (const auto &entry : validProofPool.pool) { if (!peersUtxos.count(entry.getUTXO())) { return false; } diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h --- a/src/avalanche/proofpool.h +++ b/src/avalanche/proofpool.h @@ -45,18 +45,31 @@ /** * Map a proof to each utxo. A proof can be mapped with several utxos. */ -using ProofPool = boost::multi_index_container< - ProofPoolEntry, - bmi::indexed_by< - // index by utxo - bmi::hashed_unique, - bmi::const_mem_fun, - SaltedOutpointHasher>, - // index by proofid - bmi::hashed_non_unique, - ProofPoolEntryProofIdKeyExtractor, - SaltedProofIdHasher>>>; +struct ProofPool { + boost::multi_index_container< + ProofPoolEntry, + bmi::indexed_by< + // index by utxo + bmi::hashed_unique< + bmi::tag, + bmi::const_mem_fun, + SaltedOutpointHasher>, + // index by proofid + bmi::hashed_non_unique, + ProofPoolEntryProofIdKeyExtractor, + SaltedProofIdHasher>>> + pool; + + enum AddProofStatus { + REJECTED = 0, //!< Rejected due to conflicts + SUCCEED = 1, //!< Added successfully + DUPLICATED = 2, //!< Already in pool + }; + + AddProofStatus addProof(const ProofRef &proof); + bool removeProof(ProofRef proof); +}; } // namespace avalanche 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,56 @@ +// 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 { + +ProofPool::AddProofStatus ProofPool::addProof(const ProofRef &proof) { + assert(proof); + + const ProofId &proofid = proof->getId(); + + auto &poolView = pool.get(); + if (poolView.find(proofid) != poolView.end()) { + return AddProofStatus::DUPLICATED; + } + + // Attach UTXOs to this proof. + std::unordered_set conflicting_proofs; + for (size_t i = 0; i < proof->getStakes().size(); i++) { + auto p = pool.emplace(i, proof); + if (!p.second) { + // We have a collision with an existing proof. + conflicting_proofs.insert(p.first->proof); + } + } + + // For now, if there is a conflict, just cleanup the mess. + if (conflicting_proofs.size() > 0) { + for (const auto &s : proof->getStakes()) { + auto it = pool.find(s.getStake().getUTXO()); + assert(it != pool.end()); + + // We need to delete that one. + if (it->proof->getId() == proofid) { + pool.erase(it); + } + } + + return AddProofStatus::REJECTED; + } + + return AddProofStatus::SUCCEED; +} + +// Having the ProofRef passed by reference is risky because the proof could be +// deleted during the erasure loop, so we pass it by value. Since it's a shared +// pointer, the copy is cheap enough and should not have any significant impact +// on performance. +bool ProofPool::removeProof(ProofRef proof) { + auto &poolView = pool.get(); + return poolView.erase(proof->getId()); +} + +} // 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,70 @@ +// 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 + +#include + +using namespace avalanche; + +BOOST_FIXTURE_TEST_SUITE(proofpool_tests, TestingSetup) + +BOOST_AUTO_TEST_CASE(add_remove_proof) { + ProofPool testPool; + + std::vector proofs; + for (size_t i = 0; i < 10; i++) { + // Add a bunch of random proofs + auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); + BOOST_CHECK_EQUAL(testPool.addProof(proof), + ProofPool::AddProofStatus::SUCCEED); + + // Trying to add them again will return a duplicated status + for (size_t j = 0; j < 10; j++) { + BOOST_CHECK_EQUAL(testPool.addProof(proof), + ProofPool::AddProofStatus::DUPLICATED); + } + proofs.push_back(std::move(proof)); + } + + const CKey key = CKey::MakeCompressedKey(); + const COutPoint conflictingOutpoint{TxId(GetRandHash()), 0}; + + auto buildProofWithSequence = [&](uint64_t sequence) { + ProofBuilder pb(sequence, 0, key); + BOOST_CHECK( + pb.addUTXO(conflictingOutpoint, 10 * COIN, 123456, false, key)); + return pb.build(); + }; + + auto proof_seq10 = buildProofWithSequence(10); + BOOST_CHECK_EQUAL(testPool.addProof(proof_seq10), + ProofPool::AddProofStatus::SUCCEED); + proofs.push_back(std::move(proof_seq10)); + + auto proof_seq20 = buildProofWithSequence(20); + BOOST_CHECK_EQUAL(testPool.addProof(proof_seq20), + ProofPool::AddProofStatus::REJECTED); + + // Removing proofs which are not in the pool will fail + for (size_t i = 0; i < 10; i++) { + BOOST_CHECK( + !testPool.removeProof(buildRandomProof(MIN_VALID_PROOF_SCORE))); + } + + for (auto proof : proofs) { + BOOST_CHECK(testPool.removeProof(proof)); + } + BOOST_CHECK(testPool.pool.empty()); +} + +BOOST_AUTO_TEST_SUITE_END()