diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h --- a/src/avalanche/peermanager.h +++ b/src/avalanche/peermanager.h @@ -8,9 +8,11 @@ #include #include #include +#include #include #include #include +#include #include #include @@ -155,6 +157,9 @@ ProofPool conflictingProofPool; ProofPool orphanProofPool; + using ProofRadixTree = RadixTree; + ProofRadixTree shareableProofs; + using NodeSet = boost::multi_index_container< Node, bmi::indexed_by< @@ -356,6 +361,10 @@ bool isOrphan(const ProofId &proofid) const; bool isInConflictingPool(const ProofId &proofid) const; + const ProofRadixTree &getShareableProofsSnapshot() const { + return shareableProofs; + } + private: template void moveToConflictingPool(const ProofContainer &proofs); diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -313,6 +313,9 @@ auto inserted = peers.emplace(peerid, proof, nextCooldownTimePoint); assert(inserted.second); + auto insertedRadixTree = shareableProofs.insert(proof); + assert(insertedRadixTree); + // Add to our registered score when adding to the peer list totalPeersScore += proof->getScore(); @@ -503,6 +506,9 @@ // Release UTXOs attached to this proof. validProofPool.removeProof(it->getProofId()); + auto removed = shareableProofs.remove(Uint256RadixKey(it->getProofId())); + assert(removed != nullptr); + m_unbroadcast_proofids.erase(it->getProofId()); // Remove the peer from the PeerSet and remove its score from the registered @@ -662,6 +668,11 @@ if (slots[p.index].getScore() != p.getScore()) { return false; } + + // Check the proof is in the radix tree + if (shareableProofs.get(p.getProofId()) == nullptr) { + return false; + } } // Check our accumulated scores against our registred and allocated scores @@ -678,7 +689,10 @@ return false; } - return true; + // Check there is no dangling proof in the radix tree + return shareableProofs.forEachLeaf([&](RCUPtr pLeaf) { + return isBoundToPeer(pLeaf->getId()); + }); } PeerId selectPeerImpl(const std::vector &slots, const uint64_t slot, diff --git a/src/avalanche/proofradixtreeadapter.h b/src/avalanche/proofradixtreeadapter.h new file mode 100644 --- /dev/null +++ b/src/avalanche/proofradixtreeadapter.h @@ -0,0 +1,22 @@ +// Copyright (c) 2022 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_AVALANCHE_PROOFRADIXTREEADAPTER_H +#define BITCOIN_AVALANCHE_PROOFRADIXTREEADAPTER_H + +#include +#include + +namespace avalanche { + +/** + * Radix tree adapter for storing a proof as a tree element. + */ +struct ProofRadixTreeAdapter { + Uint256RadixKey getId(const Proof &proof) const { return proof.getId(); } +}; + +} // namespace avalanche + +#endif // BITCOIN_AVALANCHE_PROOFRADIXTREEADAPTER_H 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 @@ -1625,4 +1625,120 @@ checkScores(0, 0); } +BOOST_FIXTURE_TEST_CASE(proof_radix_tree, NoCoolDownFixture) { + avalanche::PeerManager pm; + + gArgs.ForceSetArg("-enableavalancheproofreplacement", "1"); + + struct ProofComparatorById { + bool operator()(const ProofRef &lhs, const ProofRef &rhs) const { + return lhs->getId() < rhs->getId(); + }; + }; + using ProofSetById = std::set; + // Maintain a list of the expected proofs through this test + ProofSetById expectedProofs; + + auto matchExpectedContent = [&](const auto &tree) { + auto it = expectedProofs.begin(); + return tree.forEachLeaf([&](auto pLeaf) { + return it != expectedProofs.end() && + pLeaf->getId() == (*it++)->getId(); + }); + }; + + CKey key = CKey::MakeCompressedKey(); + const int64_t sequence = 10; + + // Add some initial proofs + for (size_t i = 0; i < 10; i++) { + auto outpoint = createUtxo(key); + auto proof = buildProofWithSequence(key, {{outpoint}}, sequence); + BOOST_CHECK(pm.registerProof(proof)); + expectedProofs.insert(std::move(proof)); + } + + const auto &treeRef = pm.getShareableProofsSnapshot(); + BOOST_CHECK(matchExpectedContent(treeRef)); + + // Create a copy + auto tree = pm.getShareableProofsSnapshot(); + + // Adding more proofs doesn't change the tree... + ProofSetById addedProofs; + std::vector outpointsToSpend; + for (size_t i = 0; i < 10; i++) { + auto outpoint = createUtxo(key); + auto proof = buildProofWithSequence(key, {{outpoint}}, sequence); + BOOST_CHECK(pm.registerProof(proof)); + addedProofs.insert(std::move(proof)); + outpointsToSpend.push_back(std::move(outpoint)); + } + + BOOST_CHECK(matchExpectedContent(tree)); + + // ...until we get a new copy + tree = pm.getShareableProofsSnapshot(); + expectedProofs.insert(addedProofs.begin(), addedProofs.end()); + BOOST_CHECK(matchExpectedContent(tree)); + + // Spend some coins to make the associated proofs invalid + { + LOCK(cs_main); + CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); + for (const auto &outpoint : outpointsToSpend) { + coins.SpendCoin(outpoint); + } + } + + pm.updatedBlockTip(); + + // This doesn't change the tree... + BOOST_CHECK(matchExpectedContent(tree)); + + // ...until we get a new copy + tree = pm.getShareableProofsSnapshot(); + for (const auto &proof : addedProofs) { + BOOST_CHECK_EQUAL(expectedProofs.erase(proof), 1); + } + BOOST_CHECK(matchExpectedContent(tree)); + + // Add some more proof for which we will create conflicts + std::vector conflictingProofs; + std::vector conflictingOutpoints; + for (size_t i = 0; i < 10; i++) { + auto outpoint = createUtxo(key); + auto proof = buildProofWithSequence(key, {{outpoint}}, sequence); + BOOST_CHECK(pm.registerProof(proof)); + conflictingProofs.push_back(std::move(proof)); + conflictingOutpoints.push_back(std::move(outpoint)); + } + + tree = pm.getShareableProofsSnapshot(); + expectedProofs.insert(conflictingProofs.begin(), conflictingProofs.end()); + BOOST_CHECK(matchExpectedContent(tree)); + + // Build a bunch of conflicting proofs, half better, half worst + for (size_t i = 0; i < 10; i += 2) { + // The worst proof is not added to the expected set + BOOST_CHECK(!pm.registerProof(buildProofWithSequence( + key, {{conflictingOutpoints[i]}}, sequence - 1))); + + // But the better proof should replace its conflicting one + auto replacementProof = buildProofWithSequence( + key, {{conflictingOutpoints[i + 1]}}, sequence + 1); + BOOST_CHECK(pm.registerProof(replacementProof)); + BOOST_CHECK_EQUAL(expectedProofs.erase(conflictingProofs[i + 1]), 1); + BOOST_CHECK(expectedProofs.insert(replacementProof).second); + } + + tree = pm.getShareableProofsSnapshot(); + BOOST_CHECK(matchExpectedContent(tree)); + + // Check for consistency + pm.verify(); + + gArgs.ClearForcedArg("-enableavalancheproofreplacement"); +} + BOOST_AUTO_TEST_SUITE_END()