diff --git a/src/avalanche/orphanproofpool.h b/src/avalanche/orphanproofpool.h --- a/src/avalanche/orphanproofpool.h +++ b/src/avalanche/orphanproofpool.h @@ -68,6 +68,13 @@ */ const Proof *getProof(const ProofId &proofId) const; + /** + * Call a function on all proofs. + * The proofs are accessed in the same order as their insertion, oldest + * one first. + */ + void forEachProof(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,12 @@ return it == proofs_by_proofid.end() ? nullptr : &*it; } +void OrphanProofPool::forEachProof(std::function func) { + for (const Proof &proof : proofs.get()) { + 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,8 @@ void PeerManager::updatedBlockTip() { std::vector invalidPeers; + std::vector noLongerOrphans; + std::vector newOrphans; { LOCK(cs_main); @@ -170,9 +177,28 @@ 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.forEachProof( + [&noLongerOrphans, &coins](const Proof &proof) { + ProofValidationState state; + if (proof.verify(state, coins)) { + noLongerOrphans.push_back(&proof); + } + }); + } + + for (const auto &p : noLongerOrphans) { + fetchOrCreatePeer(*p); + } + + for (const auto &p : newOrphans) { + orphanProofs.addProof(*p); } for (const auto &pid : invalidPeers) { @@ -203,8 +229,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 +486,8 @@ return nodeids; } +bool PeerManager::isProofOrphan(const ProofId &id) { + return orphanProofs.getProof(id); +} + } // namespace avalanche diff --git a/src/avalanche/test/orphanproofpool_tests.cpp b/src/avalanche/test/orphanproofpool_tests.cpp --- a/src/avalanche/test/orphanproofpool_tests.cpp +++ b/src/avalanche/test/orphanproofpool_tests.cpp @@ -161,4 +161,50 @@ BOOST_CHECK_EQUAL(pool.getNProofs(), 0); } +BOOST_AUTO_TEST_CASE(test_forEachProof) { + { + // On an empty pool, the callback is never called + OrphanProofPool pool{7}; + size_t nCalls = 0; + pool.forEachProof([&nCalls](const Proof &proof) { nCalls++; }); + BOOST_CHECK_EQUAL(nCalls, 0); + } + + { + // Verify number of elements, access order and values + OrphanProofPool pool{7}; + + Proof proof1 = makeProof(1); + Proof proof2 = makeProof(2); + Proof proof3 = makeProof(4); + + pool.addProof(proof1); + pool.addProof(proof2); + pool.addProof(proof3); + + // Run it twice to test that it doesn't change the pool + for (size_t i = 0; i < 2; i++) { + std::vector nStakes; + std::vector proofids; + pool.forEachProof([&nStakes, &proofids](const Proof &proof) { + nStakes.push_back(proof.getStakes().size()); + proofids.push_back(proof.getId()); + }); + + BOOST_CHECK_EQUAL(pool.getNProofs(), 3); + BOOST_CHECK_EQUAL(pool.getNStakes(), 7); + BOOST_CHECK_EQUAL(nStakes.size(), 3); + BOOST_CHECK_EQUAL(proofids.size(), 3); + + BOOST_CHECK_EQUAL(nStakes[0], 1); + BOOST_CHECK_EQUAL(nStakes[1], 2); + BOOST_CHECK_EQUAL(nStakes[2], 4); + + BOOST_CHECK_EQUAL(proofids[0], proof1.getId()); + BOOST_CHECK_EQUAL(proofids[1], proof2.getId()); + BOOST_CHECK_EQUAL(proofids[2], proof3.getId()); + } + } +} + BOOST_AUTO_TEST_SUITE_END() 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,89 @@ 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())); + + // 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())); + // The status of proof1 and proof3 are unchanged + BOOST_CHECK(!pm.isProofOrphan(proof1.getId())); + BOOST_CHECK(pm.isProofOrphan(proof3.getId())); + + // Spend outpoint1, proof1 becomes orphan + { + LOCK(cs_main); + CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); + coins.SpendCoin(outpoint1); + } + pm.updatedBlockTip(); + BOOST_CHECK(pm.isProofOrphan(proof1.getId())); + // The status of proof2 and proof3 are unchanged + BOOST_CHECK(!pm.isProofOrphan(proof2.getId())); + BOOST_CHECK(pm.isProofOrphan(proof3.getId())); + + // 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())); + // The status of proof 1 and proof2 are unchanged + BOOST_CHECK(pm.isProofOrphan(proof1.getId())); + BOOST_CHECK(!pm.isProofOrphan(proof2.getId())); +} + BOOST_AUTO_TEST_SUITE_END()