diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -161,7 +161,7 @@ cs_main, return proof->verify(state, ::ChainstateActive().CoinsTip())); if (!valid) { if (isOrphanState(state)) { - orphanProofPool.addProof(proof); + orphanProofPool.addProofIfPreferred(proof); } // Reject invalid proof. @@ -223,7 +223,7 @@ orphanProofPool.rescan(*this); for (auto &p : newOrphans) { - orphanProofPool.addProof(p); + orphanProofPool.addProofIfPreferred(p); } } @@ -254,11 +254,11 @@ bool PeerManager::createPeer(const ProofRef &proof) { assert(proof); - switch (validProofPool.addProof(proof)) { + switch (validProofPool.addProofIfNoConflict(proof)) { case ProofPool::AddProofStatus::REJECTED: // The proof has conflicts, orphan the proof so it can be pulled // back if the conflicting ones are invalidated. - orphanProofPool.addProof(proof); + orphanProofPool.addProofIfPreferred(proof); return false; case ProofPool::AddProofStatus::DUPLICATED: // If the proof was already in the pool, don't duplicate the peer. diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h --- a/src/avalanche/proofpool.h +++ b/src/avalanche/proofpool.h @@ -6,6 +6,7 @@ #define BITCOIN_AVALANCHE_PROOFPOOL_H #include +#include #include #include #include @@ -70,7 +71,24 @@ DUPLICATED = 2, //!< Already in pool }; - AddProofStatus addProof(const ProofRef &proof); + using ConflictingProofSet = std::set; + + /** + * Attempt to add a proof to the pool, and fail if there is a conflict on + * any UTXO. + */ + AddProofStatus addProofIfNoConflict(const ProofRef &proof); + AddProofStatus addProofIfNoConflict(const ProofRef &proof, + ConflictingProofSet &conflictingProofs); + /** + * Attempt to add a proof to the pool. In case there is a conflict with one + * or more UTXO, the proof is only added if it is the best candidate over + * all the conflicting proofs according to ConflictingProofComparator. + */ + AddProofStatus addProofIfPreferred(const ProofRef &proof); + AddProofStatus addProofIfPreferred(const ProofRef &proof, + ConflictingProofSet &conflictingProofs); + bool removeProof(ProofRef proof); void rescan(PeerManager &peerManager); diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp --- a/src/avalanche/proofpool.cpp +++ b/src/avalanche/proofpool.cpp @@ -5,12 +5,19 @@ #include #include +#include namespace avalanche { -ProofPool::AddProofStatus ProofPool::addProof(const ProofRef &proof) { - assert(proof); +ProofPool::AddProofStatus +ProofPool::addProofIfNoConflict(const ProofRef &proof) { + ConflictingProofSet dummy; + return addProofIfNoConflict(proof, dummy); +} +ProofPool::AddProofStatus +ProofPool::addProofIfNoConflict(const ProofRef &proof, + ConflictingProofSet &conflictingProofs) { const ProofId &proofid = proof->getId(); auto &poolView = pool.get(); @@ -19,17 +26,16 @@ } // 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); + conflictingProofs.insert(p.first->proof); } } - // For now, if there is a conflict, just cleanup the mess. - if (conflicting_proofs.size() > 0) { + // If there is a conflict, just cleanup the mess. + if (conflictingProofs.size() > 0) { for (const auto &s : proof->getStakes()) { auto it = pool.find(s.getStake().getUTXO()); assert(it != pool.end()); @@ -46,6 +52,32 @@ return AddProofStatus::SUCCEED; } +ProofPool::AddProofStatus +ProofPool::addProofIfPreferred(const ProofRef &proof) { + ConflictingProofSet dummy; + return addProofIfPreferred(proof, dummy); +} + +ProofPool::AddProofStatus +ProofPool::addProofIfPreferred(const ProofRef &proof, + ConflictingProofSet &conflictingProofs) { + auto added = addProofIfNoConflict(proof, conflictingProofs); + + ConflictingProofComparator compare; + // In case the proof was rejected due to conflict and it is the best + // candidate, override the conflicting ones and add it again + if (!added && compare(proof, *conflictingProofs.begin())) { + for (auto &conflictingProof : conflictingProofs) { + removeProof(conflictingProof); + } + + added = addProofIfNoConflict(proof); + assert(added == AddProofStatus::SUCCEED); + } + + return added; +} + // 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 diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp --- a/src/avalanche/test/peermanager_tests.cpp +++ b/src/avalanche/test/peermanager_tests.cpp @@ -968,9 +968,8 @@ BOOST_CHECK(pm.isOrphan(orphan10->getId())); BOOST_CHECK(!pm.registerProof(orphan20)); - BOOST_CHECK(!pm.isOrphan(orphan20->getId())); - BOOST_CHECK(!pm.exists(orphan20->getId())); - BOOST_CHECK(pm.isOrphan(orphan10->getId())); + BOOST_CHECK(pm.isOrphan(orphan20->getId())); + BOOST_CHECK(!pm.exists(orphan10->getId())); } BOOST_AUTO_TEST_SUITE_END() diff --git a/src/avalanche/test/proofpool_tests.cpp b/src/avalanche/test/proofpool_tests.cpp --- a/src/avalanche/test/proofpool_tests.cpp +++ b/src/avalanche/test/proofpool_tests.cpp @@ -19,19 +19,19 @@ BOOST_FIXTURE_TEST_SUITE(proofpool_tests, TestingSetup) -BOOST_AUTO_TEST_CASE(add_remove_proof) { +BOOST_AUTO_TEST_CASE(add_remove_proof_no_conflict) { 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), + BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(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), + BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(proof), ProofPool::AddProofStatus::DUPLICATED); } proofs.push_back(std::move(proof)); @@ -48,12 +48,12 @@ }; auto proof_seq10 = buildProofWithSequence(10); - BOOST_CHECK_EQUAL(testPool.addProof(proof_seq10), + BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(proof_seq10), ProofPool::AddProofStatus::SUCCEED); proofs.push_back(std::move(proof_seq10)); auto proof_seq20 = buildProofWithSequence(20); - BOOST_CHECK_EQUAL(testPool.addProof(proof_seq20), + BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(proof_seq20), ProofPool::AddProofStatus::REJECTED); // Removing proofs which are not in the pool will fail @@ -83,7 +83,7 @@ std::set poolProofs; for (size_t i = 0; i < 10; i++) { auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); - BOOST_CHECK_EQUAL(testPool.addProof(proof), + BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(proof), ProofPool::AddProofStatus::SUCCEED); poolProofs.insert(std::move(proof)); } @@ -98,6 +98,76 @@ BOOST_CHECK_EQUAL(testPool.size(), 0); } +BOOST_AUTO_TEST_CASE(proof_override) { + ProofPool testPool; + + const CKey key = CKey::MakeCompressedKey(); + + auto buildProofWithSequenceAndOutpoints = + [&](uint64_t sequence, const std::vector &outpoints) { + ProofBuilder pb(sequence, 0, key); + for (const COutPoint &outpoint : outpoints) { + BOOST_CHECK( + pb.addUTXO(outpoint, 10 * COIN, 123456, false, key)); + } + return pb.build(); + }; + + const COutPoint outpoint1{TxId(GetRandHash()), 0}; + const COutPoint outpoint2{TxId(GetRandHash()), 0}; + const COutPoint outpoint3{TxId(GetRandHash()), 0}; + + // Build and register 3 proofs with a single utxo + auto proof_seq10 = buildProofWithSequenceAndOutpoints(10, {outpoint1}); + auto proof_seq20 = buildProofWithSequenceAndOutpoints(20, {outpoint2}); + auto proof_seq30 = buildProofWithSequenceAndOutpoints(30, {outpoint3}); + + BOOST_CHECK_EQUAL(testPool.addProofIfPreferred(proof_seq10), + ProofPool::AddProofStatus::SUCCEED); + BOOST_CHECK(testPool.getProof(proof_seq10->getId())); + + BOOST_CHECK_EQUAL(testPool.addProofIfPreferred(proof_seq20), + ProofPool::AddProofStatus::SUCCEED); + BOOST_CHECK(testPool.getProof(proof_seq20->getId())); + + BOOST_CHECK_EQUAL(testPool.addProofIfPreferred(proof_seq30), + ProofPool::AddProofStatus::SUCCEED); + BOOST_CHECK(testPool.getProof(proof_seq30->getId())); + + // Build a proof that conflicts with the above 3, but has a higher sequence + auto proof_seq123 = buildProofWithSequenceAndOutpoints( + 123, {outpoint1, outpoint2, outpoint3}); + ProofPool::ConflictingProofSet expectedConflictingProofs = { + proof_seq10, proof_seq20, proof_seq30}; + + // The no conflict call should reject out candidate and not alter the 3 + // conflicting proofs + ProofPool::ConflictingProofSet conflictingProofs; + BOOST_CHECK_EQUAL( + testPool.addProofIfNoConflict(proof_seq123, conflictingProofs), + ProofPool::AddProofStatus::REJECTED); + BOOST_CHECK_EQUAL_COLLECTIONS( + conflictingProofs.begin(), conflictingProofs.end(), + expectedConflictingProofs.begin(), expectedConflictingProofs.end()); + BOOST_CHECK(!testPool.getProof(proof_seq123->getId())); + BOOST_CHECK(testPool.getProof(proof_seq10->getId())); + BOOST_CHECK(testPool.getProof(proof_seq20->getId())); + BOOST_CHECK(testPool.getProof(proof_seq30->getId())); + + // The conflict handling call will override the 3 conflicting proofs + conflictingProofs.clear(); + BOOST_CHECK_EQUAL( + testPool.addProofIfPreferred(proof_seq123, conflictingProofs), + ProofPool::AddProofStatus::SUCCEED); + BOOST_CHECK_EQUAL_COLLECTIONS( + conflictingProofs.begin(), conflictingProofs.end(), + expectedConflictingProofs.begin(), expectedConflictingProofs.end()); + BOOST_CHECK(testPool.getProof(proof_seq123->getId())); + BOOST_CHECK(!testPool.getProof(proof_seq10->getId())); + BOOST_CHECK(!testPool.getProof(proof_seq20->getId())); + BOOST_CHECK(!testPool.getProof(proof_seq30->getId())); +} + BOOST_AUTO_TEST_CASE(get_proof) { ProofPool testPool; @@ -107,7 +177,7 @@ for (size_t i = 0; i < 10; i++) { auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); - BOOST_CHECK_EQUAL(testPool.addProof(proof), + BOOST_CHECK_EQUAL(testPool.addProofIfNoConflict(proof), ProofPool::AddProofStatus::SUCCEED); auto retrievedProof = testPool.getProof(proof->getId());