diff --git a/src/avalanche/orphanproofpool.h b/src/avalanche/orphanproofpool.h --- a/src/avalanche/orphanproofpool.h +++ b/src/avalanche/orphanproofpool.h @@ -14,6 +14,8 @@ namespace avalanche { +class PeerManager; + // Extracts a ProofId from a Proof struct proofid_extractor { using result_type = ProofId; @@ -72,6 +74,12 @@ */ std::shared_ptr getProof(const ProofId &proofId) const; + /** + * Rescan the pool to remove previously orphaned proofs that have become + * good or permanently bad. + */ + void rescan(PeerManager &peerManager); + // For testing size_t getNProofs() const; size_t getNStakes() const; diff --git a/src/avalanche/orphanproofpool.cpp b/src/avalanche/orphanproofpool.cpp --- a/src/avalanche/orphanproofpool.cpp +++ b/src/avalanche/orphanproofpool.cpp @@ -4,6 +4,10 @@ #include +#include + +#include + namespace avalanche { void OrphanProofPool::trimToMaximumSize() { @@ -42,6 +46,15 @@ return it == proofs_by_proofid.end() ? nullptr : *it; } +void OrphanProofPool::rescan(PeerManager &peerManager) { + ProofContainer last_gen_proofs = std::move(proofs); + proofs.clear(); + + for (auto &proof : last_gen_proofs.get()) { + peerManager.getPeerId(proof); + } +} + size_t OrphanProofPool::getNProofs() const { return proofs.size(); } diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h --- a/src/avalanche/peermanager.h +++ b/src/avalanche/peermanager.h @@ -6,6 +6,7 @@ #define BITCOIN_AVALANCHE_PEERMANAGER_H #include +#include #include #include #include @@ -25,6 +26,13 @@ namespace avalanche { +/** + * Maximum number of stakes in the orphanProofs. + * Benchmarking on a consumer grade computer shows that 10000 stakes can be + * verified in less than 1 second. + */ +static constexpr size_t AVALANCHE_ORPHANPROOFPOOL_SIZE = 10000; + class Delegation; struct Slot { @@ -85,6 +93,8 @@ uint64_t slotCount = 0; uint64_t fragmentation = 0; + OrphanProofPool orphanProofs{AVALANCHE_ORPHANPROOFPOOL_SIZE}; + /** * Several nodes can make an avalanche peer. In this case, all nodes are * considered interchangeable parts of the same peer. @@ -184,6 +194,8 @@ std::shared_ptr getProof(const ProofId &proofid) const; + bool isOrphan(const ProofId &id); + private: PeerSet::iterator fetchOrCreatePeer(const std::shared_ptr &proof); bool addNodeToPeer(const PeerSet::iterator &it); diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -13,6 +13,11 @@ namespace avalanche { +static bool isOrphanState(const ProofValidationState &state) { + return state.GetResult() == ProofValidationResult::MISSING_UTXO || + state.GetResult() == ProofValidationResult::HEIGHT_MISMATCH; +} + bool PeerManager::addNode(NodeId nodeid, const std::shared_ptr &proof, const Delegation &delegation) { auto it = fetchOrCreatePeer(proof); @@ -162,6 +167,7 @@ void PeerManager::updatedBlockTip() { std::vector invalidPeers; + std::vector> newOrphans; { LOCK(cs_main); @@ -170,11 +176,20 @@ for (const auto &p : peers) { ProofValidationState state; if (!p.proof->verify(state, coins)) { + if (isOrphanState(state)) { + newOrphans.push_back(p.proof); + } invalidPeers.push_back(p.peerid); } } } + orphanProofs.rescan(*this); + + for (auto &p : newOrphans) { + orphanProofs.addProof(p); + } + for (const auto &pid : invalidPeers) { removePeer(pid); } @@ -202,17 +217,25 @@ } } - { - // Reject invalid proof. + // Check the proof's validity. + ProofValidationState state; + bool valid = [&](ProofValidationState &state) { LOCK(cs_main); const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); + return proof->verify(state, coins); + }(state); - ProofValidationState state; - if (!proof->verify(state, coins)) { - return peers.end(); + if (!valid) { + if (isOrphanState(state)) { + orphanProofs.addProof(proof); } + + // Reject invalid proof. + return peers.end(); } + orphanProofs.removeProof(proof->getId()); + // New peer means new peerid! const PeerId peerid = nextPeerId++; @@ -462,4 +485,8 @@ return nodeids; } +bool PeerManager::isOrphan(const ProofId &id) { + return orphanProofs.getProof(id) != nullptr; +} + } // namespace avalanche 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 @@ -442,4 +442,118 @@ NO_PEER); } +BOOST_AUTO_TEST_CASE(orphan_proofs) { + avalanche::PeerManager pm; + + CKey key; + key.MakeNewKey(true); + const CScript script = GetScriptForDestination(PKHash(key.GetPubKey())); + + COutPoint outpoint1 = COutPoint(TxId(GetRandHash()), 0); + COutPoint outpoint2 = COutPoint(TxId(GetRandHash()), 0); + COutPoint outpoint3 = COutPoint(TxId(GetRandHash()), 0); + + const Amount v = 5 * COIN; + const int height = 1234; + const int wrongHeight = 12345; + + const auto makeProof = [&](const COutPoint &outpoint, const int h) { + ProofBuilder pb(0, 0, CPubKey()); + pb.addUTXO(outpoint, v, h, false, key); + return std::make_shared(pb.build()); + }; + + auto proof1 = makeProof(outpoint1, height); + auto proof2 = makeProof(outpoint2, height); + auto proof3 = makeProof(outpoint3, wrongHeight); + + const Coin coin = Coin(CTxOut(v, script), height, false); + + // Add outpoints 1 and 3, not 2 + { + LOCK(cs_main); + CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); + coins.AddCoin(outpoint1, coin, false); + coins.AddCoin(outpoint3, coin, false); + } + + // Add the proofs + BOOST_CHECK(pm.getPeerId(proof1) != NO_PEER); + BOOST_CHECK(pm.getPeerId(proof2) == NO_PEER); + BOOST_CHECK(pm.getPeerId(proof3) == NO_PEER); + + // Good + BOOST_CHECK(!pm.isOrphan(proof1->getId())); + // MISSING_UTXO + BOOST_CHECK(pm.isOrphan(proof2->getId())); + // HEIGHT_MISMATCH + BOOST_CHECK(pm.isOrphan(proof3->getId())); + + const auto isGoodPeer = [&pm](const std::shared_ptr &p) { + for (const auto &peer : pm.getPeers()) { + if (p->getId() == peer.proof->getId()) { + return true; + } + } + return false; + }; + + BOOST_CHECK(isGoodPeer(proof1)); + BOOST_CHECK(!isGoodPeer(proof2)); + BOOST_CHECK(!isGoodPeer(proof3)); + + // Add outpoint2, proof2 is no longer considered orphan + { + LOCK(cs_main); + CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); + coins.AddCoin(outpoint2, coin, false); + } + + pm.updatedBlockTip(); + BOOST_CHECK(!pm.isOrphan(proof2->getId())); + BOOST_CHECK(isGoodPeer(proof2)); + + // The status of proof1 and proof3 are unchanged + BOOST_CHECK(!pm.isOrphan(proof1->getId())); + BOOST_CHECK(isGoodPeer(proof1)); + BOOST_CHECK(pm.isOrphan(proof3->getId())); + BOOST_CHECK(!isGoodPeer(proof3)); + + // Spend outpoint1, proof1 becomes orphan + { + LOCK(cs_main); + CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); + coins.SpendCoin(outpoint1); + } + + pm.updatedBlockTip(); + BOOST_CHECK(pm.isOrphan(proof1->getId())); + BOOST_CHECK(!isGoodPeer(proof1)); + + // The status of proof2 and proof3 are unchanged + BOOST_CHECK(!pm.isOrphan(proof2->getId())); + BOOST_CHECK(isGoodPeer(proof2)); + BOOST_CHECK(pm.isOrphan(proof3->getId())); + BOOST_CHECK(!isGoodPeer(proof3)); + + // A reorg could make a previous HEIGHT_MISMATCH become valid + { + LOCK(cs_main); + CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); + coins.SpendCoin(outpoint3); + coins.AddCoin(outpoint3, Coin(CTxOut(v, script), wrongHeight, false), + false); + } + + pm.updatedBlockTip(); + BOOST_CHECK(!pm.isOrphan(proof3->getId())); + BOOST_CHECK(isGoodPeer(proof3)); + + // The status of proof 1 and proof2 are unchanged + BOOST_CHECK(pm.isOrphan(proof1->getId())); + BOOST_CHECK(!isGoodPeer(proof1)); + BOOST_CHECK(!pm.isOrphan(proof2->getId())); + BOOST_CHECK(isGoodPeer(proof2)); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/test/lint/lint-circular-dependencies.sh b/test/lint/lint-circular-dependencies.sh --- a/test/lint/lint-circular-dependencies.sh +++ b/test/lint/lint-circular-dependencies.sh @@ -33,6 +33,7 @@ "checkpoints -> validation -> checkpoints" "pow/aserti32d -> validation -> pow/aserti32d" "pow/aserti32d -> validation -> pow/pow -> pow/aserti32d" + "avalanche/orphanproofpool -> avalanche/peermanager -> avalanche/orphanproofpool" ) EXIT_CODE=0