diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -254,7 +254,8 @@ bool PeerManager::createPeer(const ProofRef &proof) { assert(proof); - auto added = validProofPool.addProof(proof); + ProofPool::ConflictingProofSet conflictingProofs; + auto added = validProofPool.addProofNoOverride(proof, conflictingProofs); if (!added) { // The proof has conflicts, orphan the proof so it can be pulled back if 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 @@ -67,7 +68,16 @@ DUPLICATED = 2, //!< Already in pool }; - AddProofStatus addProof(const ProofRef &proof); + using ConflictingProofSet = std::set; + + AddProofStatus addProofNoOverride(const ProofRef &proof, + ConflictingProofSet &conflictingProofs); + AddProofStatus addProof(const ProofRef &proof, + ConflictingProofSet &conflictingProofs); + AddProofStatus addProof(const ProofRef &proof) { + ConflictingProofSet dummy; + return addProof(proof, dummy); + } bool removeProof(ProofRef proof); ProofRef getProof(const ProofId &proofid) const; diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp --- a/src/avalanche/proofpool.cpp +++ b/src/avalanche/proofpool.cpp @@ -4,9 +4,13 @@ #include +#include + namespace avalanche { -ProofPool::AddProofStatus ProofPool::addProof(const ProofRef &proof) { +ProofPool::AddProofStatus +ProofPool::addProofNoOverride(const ProofRef &proof, + ConflictingProofSet &conflictingProofs) { const ProofId &proofid = proof->getId(); auto &poolView = pool.get(); @@ -15,17 +19,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()); @@ -42,6 +45,31 @@ return AddProofStatus::SUCCEED; } +ProofPool::AddProofStatus +ProofPool::addProof(const ProofRef &proof, + ConflictingProofSet &conflictingProofs) { + auto added = addProofNoOverride(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); + } + + // Either the utxo is already mapped to this proof or it is free + for (size_t i = 0; i < proof->getStakes().size(); i++) { + auto p = pool.emplace(i, proof); + assert(p.first->proof->getId() == proof->getId()); + } + + return 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 @@ -67,6 +67,75 @@ BOOST_CHECK(testPool.pool.empty()); } +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.addProof(proof_seq10), + ProofPool::AddProofStatus::SUCCEED); + BOOST_CHECK(testPool.getProof(proof_seq10->getId())); + + BOOST_CHECK_EQUAL(testPool.addProof(proof_seq20), + ProofPool::AddProofStatus::SUCCEED); + BOOST_CHECK(testPool.getProof(proof_seq20->getId())); + + BOOST_CHECK_EQUAL(testPool.addProof(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 override call should reject out candidate and not alter the 3 + // conflicting proofs + ProofPool::ConflictingProofSet conflictingProofs; + BOOST_CHECK_EQUAL( + testPool.addProofNoOverride(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 standard call will override the 3 conflicting proofs + conflictingProofs.clear(); + BOOST_CHECK_EQUAL(testPool.addProof(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;