diff --git a/src/avalanche/orphanproofpool.h b/src/avalanche/orphanproofpool.h --- a/src/avalanche/orphanproofpool.h +++ b/src/avalanche/orphanproofpool.h @@ -9,6 +9,7 @@ #include #include #include +#include namespace avalanche { @@ -49,6 +50,12 @@ */ void trimToMaximumSize(); + /** + * Return a vector with all proofs in sequential order, and clear the + * orphan pool. + */ + std::vector dump(); + public: OrphanProofPool(size_t maxNumberOfStakes) : maxNumberOfStakes(maxNumberOfStakes) {} @@ -68,6 +75,16 @@ */ const Proof *getProof(const ProofId &proofId) const; + /** + * Rescan the pool to remove previously orphaned proofs that have become + * good or permanently bad. + * + * All proofs are moved to a temporary container, then func is called on + * each of them in sequential order. func is responsible for adding back + * the proofs to the pool if they are still orphan. + */ + void rescan(std::function func); + // 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 @@ -42,6 +42,22 @@ return it == proofs_by_proofid.end() ? nullptr : &*it; } +std::vector OrphanProofPool::dump() { + std::vector out; + for (Proof p : proofs.get()) { + out.push_back(std::move(p)); + } + proofs.get().clear(); + return out; +} + +void OrphanProofPool::rescan(std::function func) { + auto vProofs = dump(); + for (const Proof &proof : vProofs) { + func(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 @@ -24,6 +25,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 { @@ -84,6 +92,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. @@ -140,7 +150,7 @@ NodeId selectNode(); /** - * Update the peer set when a nw block is connected. + * Update the peer set when a new block is connected. */ void updatedBlockTip(); @@ -181,6 +191,8 @@ std::vector getPeers() const; std::vector getNodeIdsForPeer(PeerId peerId) const; + bool isProofOrphan(const ProofId &id); + private: PeerSet::iterator fetchOrCreatePeer(const Proof &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 Proof &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,9 +176,18 @@ 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([&](const Proof &p) { fetchOrCreatePeer(p); }); + } + + for (const auto &p : newOrphans) { + orphanProofs.addProof(std::move(p)); } for (const auto &pid : invalidPeers) { @@ -203,8 +218,12 @@ ProofValidationState state; if (!proof.verify(state, coins)) { + if (isOrphanState(state)) { + orphanProofs.addProof(proof); + } return peers.end(); } + orphanProofs.removeProof(proof.getId()); } // New peer means new peerid! @@ -456,4 +475,8 @@ return nodeids; } +bool PeerManager::isProofOrphan(const ProofId &id) { + return orphanProofs.getProof(id); +} + } // 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 @@ -438,4 +438,110 @@ 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 pb.build(); + }; + + Proof proof1 = makeProof(outpoint1, height); + Proof proof2 = makeProof(outpoint2, height); + Proof 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.isProofOrphan(proof1.getId())); + // MISSING_UTXO + BOOST_CHECK(pm.isProofOrphan(proof2.getId())); + // HEIGHT_MISMATCH + BOOST_CHECK(pm.isProofOrphan(proof3.getId())); + + const auto isGoodPeer = [&pm](const Proof &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.isProofOrphan(proof2.getId())); + BOOST_CHECK(isGoodPeer(proof2)); + // The status of proof1 and proof3 are unchanged + BOOST_CHECK(!pm.isProofOrphan(proof1.getId())); + BOOST_CHECK(isGoodPeer(proof1)); + BOOST_CHECK(pm.isProofOrphan(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.isProofOrphan(proof1.getId())); + BOOST_CHECK(!isGoodPeer(proof1)); + // The status of proof2 and proof3 are unchanged + BOOST_CHECK(!pm.isProofOrphan(proof2.getId())); + BOOST_CHECK(isGoodPeer(proof2)); + BOOST_CHECK(pm.isProofOrphan(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.isProofOrphan(proof3.getId())); + BOOST_CHECK(isGoodPeer(proof3)); + // The status of proof 1 and proof2 are unchanged + BOOST_CHECK(pm.isProofOrphan(proof1.getId())); + BOOST_CHECK(!isGoodPeer(proof1)); + BOOST_CHECK(!pm.isProofOrphan(proof2.getId())); + BOOST_CHECK(isGoodPeer(proof2)); +} + BOOST_AUTO_TEST_SUITE_END()