Page MenuHomePhabricator
Files F13711243

D10459.diff
No OneTemporary
Actions

D10459.diff
View Options

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -541,6 +541,7 @@
add_library(server
addrdb.cpp
addrman.cpp
+ # TODO Create an avalanche library
avalanche/avalanche.cpp
avalanche/delegation.cpp
avalanche/delegationbuilder.cpp
@@ -550,6 +551,7 @@
avalanche/proof.cpp
avalanche/proofid.cpp
avalanche/proofbuilder.cpp
+ avalanche/proofpool.cpp
avalanche/voterecord.cpp
banman.cpp
blockencodings.cpp
diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/proofpool.h
@@ -0,0 +1,50 @@
+// Copyright (c) 2021 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_PROOFPOOL_H
+#define BITCOIN_AVALANCHE_PROOFPOOL_H
+
+#include <avalanche/proof.h>
+#include <avalanche/proofcomparator.h>
+#include <coins.h> // For SaltedOutpointHasher
+#include <primitives/transaction.h> // For COutPoint
+
+#include <set>
+#include <unordered_map>
+
+namespace avalanche {
+
+/**
+ * Store the proofs indexed by utxo, sorted using the conflicting proof
+ * comparator.
+ *
+ * TODO Implement the CCoinsView interface and use it to determine if a coin is
+ * locked due to staking.
+ */
+class ProofPool {
+ size_t maxProofsPerUtxo;
+
+ using UtxoMap =
+ std::unordered_map<COutPoint,
+ std::set<ProofRef, ConflictingProofComparator>,
+ SaltedOutpointHasher>;
+ UtxoMap utxos;
+
+public:
+ ProofPool(size_t maxProofsPerUtxoIn = 2)
+ : maxProofsPerUtxo(maxProofsPerUtxoIn) {}
+
+ bool addProof(const ProofRef &proof, std::set<ProofRef> &shifted);
+ bool removeProof(const ProofRef &proof);
+
+ template <typename Callable>
+ bool forUtxo(const COutPoint &outpoint, Callable fun) const {
+ auto it = utxos.find(outpoint);
+ return it != utxos.end() && fun(it->second);
+ }
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_PROOFPOOL_H
diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/proofpool.cpp
@@ -0,0 +1,58 @@
+// Copyright (c) 2021 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <avalanche/proofpool.h>
+
+#include <unordered_set>
+
+#include <iterator>
+
+namespace avalanche {
+
+bool ProofPool::addProof(const ProofRef &proof, std::set<ProofRef> &shifted) {
+ bool success = true;
+ for (const auto &ss : proof->getStakes()) {
+ auto &proofs = utxos[ss.getStake().getUTXO()];
+
+ auto p = proofs.emplace(proof);
+ if (!p.second) {
+ // Already there
+ continue;
+ }
+
+ shifted.insert(std::next(p.first), proofs.end());
+
+ // Trim
+ if (proofs.size() > maxProofsPerUtxo) {
+ auto pit = std::prev(proofs.end());
+
+ // Don't keep half baked proofs
+ removeProof(*pit);
+ }
+ assert(proofs.size() <= maxProofsPerUtxo);
+
+ // TODO Use contains after C++20
+ success = success && proofs.count(proof) > 0;
+ }
+
+ return success;
+}
+
+bool ProofPool::removeProof(const ProofRef &proof) {
+ for (const SignedStake &ss : proof->getStakes()) {
+ auto it = utxos.find(ss.getStake().getUTXO());
+ if (it == utxos.end()) {
+ continue;
+ }
+
+ it->second.erase(proof);
+ if (it->second.size() == 0) {
+ utxos.erase(it);
+ }
+ }
+
+ return true;
+}
+
+} // namespace avalanche
diff --git a/src/avalanche/test/CMakeLists.txt b/src/avalanche/test/CMakeLists.txt
--- a/src/avalanche/test/CMakeLists.txt
+++ b/src/avalanche/test/CMakeLists.txt
@@ -19,6 +19,7 @@
processor_tests.cpp
proof_tests.cpp
proofcomparator_tests.cpp
+ proofpool_tests.cpp
)
target_link_libraries(test-avalanche server testutil)
diff --git a/src/avalanche/test/proofpool_tests.cpp b/src/avalanche/test/proofpool_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/test/proofpool_tests.cpp
@@ -0,0 +1,310 @@
+// Copyright (c) 2021 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <avalanche/proofpool.h>
+
+#include <avalanche/proof.h>
+#include <avalanche/proofbuilder.h>
+
+#include <avalanche/test/util.h>
+#include <test/util/setup_common.h>
+
+#include <boost/test/unit_test.hpp>
+
+#include <set>
+
+using namespace avalanche;
+
+BOOST_FIXTURE_TEST_SUITE(proofpool_tests, TestingSetup)
+
+static bool hasAllProofUtxos(const ProofPool &pool, const ProofRef &proof) {
+ bool hasAllUtxos = true;
+ for (const SignedStake &ss : proof->getStakes()) {
+ hasAllUtxos =
+ hasAllUtxos &&
+ pool.forUtxo(ss.getStake().getUTXO(), [&](const auto &proofs) {
+ return proofs.find(proof) != proofs.end();
+ });
+ }
+
+ return hasAllUtxos;
+}
+
+static bool isBestCandidateForAllUtxos(const ProofPool &pool,
+ const ProofRef &proof) {
+ bool isBestCandidateForAllUtxos = true;
+ for (const SignedStake &ss : proof->getStakes()) {
+ isBestCandidateForAllUtxos =
+ isBestCandidateForAllUtxos &&
+ pool.forUtxo(ss.getStake().getUTXO(), [&](const auto &proofs) {
+ return !proofs.empty() &&
+ (*proofs.begin())->getId() == proof->getId();
+ });
+ }
+
+ return isBestCandidateForAllUtxos;
+}
+
+static void checkAddProof(size_t maxProofsPerUtxo) {
+ ProofPool pool(maxProofsPerUtxo);
+
+ const CKey key = CKey::MakeCompressedKey();
+ size_t depth = 2 * maxProofsPerUtxo;
+
+ {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+ // Adding a single proof several times has no effect
+ for (size_t i = 0; i < 10; i++) {
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+ BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof));
+ BOOST_CHECK(shifted.empty());
+ }
+ }
+
+ // Non conflicting proofs, single utxo
+ for (size_t i = 0; i < depth; i++) {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+ BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof));
+ BOOST_CHECK(shifted.empty());
+ }
+
+ // Non conflicting proofs, multiple pool
+ for (size_t i = 0; i < depth; i++) {
+ ProofBuilder pb(0, 0, key);
+ for (size_t j = 0; j < 10; j++) {
+ BOOST_CHECK(pb.addUTXO({TxId(GetRandHash()), 0}, 10 * COIN, 42,
+ false, key));
+ }
+ auto proof = pb.build();
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+ BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof));
+ BOOST_CHECK(shifted.empty());
+ }
+
+ {
+ // Conflicting proofs, single utxo
+ std::vector<ProofRef> proofs;
+ const COutPoint outpoint(TxId(GetRandHash()), 0);
+ for (size_t i = 0; i < depth; i++) {
+ // Increment the sequence number each time
+ ProofBuilder pb(i, 0, key);
+ BOOST_CHECK(pb.addUTXO(outpoint, 10 * COIN, 42, false, key));
+ auto proof = pb.build();
+ proofs.emplace_back(proof);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+
+ // This is our favorite
+ BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof));
+
+ // Last maxProofsPerUtxo proofs should be added
+ for (size_t j = 0; j < std::min(i, maxProofsPerUtxo); j++) {
+ BOOST_CHECK(hasAllProofUtxos(pool, proofs[i - j]));
+ }
+
+ // Last [1, maxProofsPerUtxo) proofs should be shifted
+ std::set<ProofRef> expectedShifted(
+ proofs.begin() + i - std::min(i, maxProofsPerUtxo),
+ proofs.begin() + i);
+ BOOST_CHECK_EQUAL_COLLECTIONS(shifted.begin(), shifted.end(),
+ expectedShifted.begin(),
+ expectedShifted.end());
+
+ // Proofs over maxProofsPerUtxo are evicted
+ for (size_t j = maxProofsPerUtxo; j < std::max(i, maxProofsPerUtxo);
+ j++) {
+ BOOST_CHECK(!hasAllProofUtxos(pool, proofs[i - j]));
+ }
+ }
+ }
+
+ {
+ // Conflicting proofs, multiples utxos
+ std::vector<ProofRef> proofs;
+
+ std::vector<COutPoint> outpoints;
+ for (size_t i = 0; i < 10; i++) {
+ outpoints.emplace_back(TxId(GetRandHash()), 0);
+ }
+
+ for (size_t i = 0; i < depth; i++) {
+ // Increment the sequence number each time
+ ProofBuilder pb(i, 0, key);
+ for (const COutPoint &o : outpoints) {
+ BOOST_CHECK(pb.addUTXO(o, 10 * COIN, 42, false, key));
+ }
+ auto proof = pb.build();
+ proofs.emplace_back(proof);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+
+ // This is our favorite
+ BOOST_CHECK(isBestCandidateForAllUtxos(pool, proof));
+
+ // Last maxProofsPerUtxo proofs should be attached
+ for (size_t j = 0; j < std::min(i, maxProofsPerUtxo); j++) {
+ BOOST_CHECK(hasAllProofUtxos(pool, proofs[i - j]));
+ }
+
+ // Last [1, maxProofsPerUtxo) proofs should be shifted
+ std::set<ProofRef> expectedShifted(
+ proofs.begin() + i - std::min(i, maxProofsPerUtxo),
+ proofs.begin() + i);
+ BOOST_CHECK_EQUAL_COLLECTIONS(shifted.begin(), shifted.end(),
+ expectedShifted.begin(),
+ expectedShifted.end());
+
+ // Proofs over maxProofsPerUtxo are evicted
+ for (size_t j = maxProofsPerUtxo; j < std::max(i, maxProofsPerUtxo);
+ j++) {
+ BOOST_CHECK(!hasAllProofUtxos(pool, proofs[i - j]));
+ }
+ }
+ }
+}
+
+BOOST_AUTO_TEST_CASE(add_proof) {
+ for (size_t maxProof : {1, 2, 5, 10, 20, 50}) {
+ checkAddProof(maxProof);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(overlapping_proofs) {
+ const CKey key = CKey::MakeCompressedKey();
+
+ const COutPoint outpoint1{TxId(GetRandHash()), 0};
+ const COutPoint outpoint2{TxId(GetRandHash()), 0};
+ const COutPoint outpoint3{TxId(GetRandHash()), 0};
+ const COutPoint outpoint4{TxId(GetRandHash()), 0};
+
+ auto buildProof = [&](uint64_t sequence,
+ const std::vector<COutPoint> outpoints) {
+ ProofBuilder pb(sequence, 0, key);
+ for (const COutPoint &o : outpoints) {
+ BOOST_CHECK(pb.addUTXO(o, 10 * COIN, 42, false, key));
+ }
+ return pb.build();
+ };
+
+ // proof13 < proof23 < proof12 < proof1234
+ auto proof1234 =
+ buildProof(0, {outpoint1, outpoint2, outpoint3, outpoint4});
+ auto proof12 = buildProof(10, {outpoint1, outpoint2});
+ auto proof23 = buildProof(20, {outpoint2, outpoint3});
+ auto proof13 = buildProof(30, {outpoint1, outpoint3});
+ std::vector<ProofRef> proofs{proof12, proof23, proof13};
+
+ const std::vector<ProofRef> expectedOutpoint1 = {proof13, proof12};
+ const std::vector<ProofRef> expectedOutpoint2 = {proof23, proof12};
+ const std::vector<ProofRef> expectedOutpoint3 = {proof13, proof23};
+
+ auto checkUtxo = [&](const ProofPool &pool, const COutPoint &outpoint,
+ const std::vector<ProofRef> &expectedOutpoint) {
+ BOOST_CHECK(pool.forUtxo(outpoint, [&](const auto &proofs) {
+ BOOST_CHECK_EQUAL_COLLECTIONS(proofs.begin(), proofs.end(),
+ expectedOutpoint.begin(),
+ expectedOutpoint.end());
+ return true;
+ }));
+ };
+
+ for (size_t i = 0; i < 10; i++) {
+ ProofPool pool(2);
+
+ Shuffle(proofs.begin(), proofs.end(), FastRandomContext());
+
+ for (const auto &p : proofs) {
+ std::set<ProofRef> shifted;
+ pool.addProof(p, shifted);
+ }
+
+ checkUtxo(pool, outpoint1, expectedOutpoint1);
+ checkUtxo(pool, outpoint2, expectedOutpoint2);
+ checkUtxo(pool, outpoint3, expectedOutpoint3);
+
+ // proof1234 will be evicted because all its utxos can't make it to the
+ // pool
+ BOOST_CHECK(!hasAllProofUtxos(pool, proof1234));
+ }
+}
+
+BOOST_AUTO_TEST_CASE(remove_proof) {
+ ProofPool pool(2);
+
+ // Removing a proof which is not in the pool has no effect
+ BOOST_CHECK(pool.removeProof(buildRandomProof(MIN_VALID_PROOF_SCORE)));
+
+ // Sequentially add and remove
+ for (size_t i = 0; i < 10; i++) {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+ BOOST_CHECK(hasAllProofUtxos(pool, proof));
+
+ BOOST_CHECK(pool.removeProof(proof));
+ BOOST_CHECK(!hasAllProofUtxos(pool, proof));
+ }
+
+ {
+ // Add and remove in batch
+ std::vector<ProofRef> proofs;
+ for (size_t i = 0; i < 10; i++) {
+ auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+ proofs.emplace_back(proof);
+
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+ BOOST_CHECK(hasAllProofUtxos(pool, proof));
+ }
+ for (const auto &proof : proofs) {
+ BOOST_CHECK(pool.removeProof(proof));
+ BOOST_CHECK(!hasAllProofUtxos(pool, proof));
+ }
+ }
+
+ {
+ // Check removing a proof with variable position depending on the utxo
+ const CKey key = CKey::MakeCompressedKey();
+ const COutPoint outpoint1{TxId(GetRandHash()), 0};
+ const COutPoint outpoint2{TxId(GetRandHash()), 0};
+ const COutPoint outpoint3{TxId(GetRandHash()), 0};
+
+ auto buildProof = [&](uint64_t sequence,
+ const std::vector<COutPoint> outpoints) {
+ ProofBuilder pb(sequence, 0, key);
+ for (const COutPoint &o : outpoints) {
+ BOOST_CHECK(pb.addUTXO(o, 10 * COIN, 42, false, key));
+ }
+ return pb.build();
+ };
+
+ // proof13 < proof23 < proof12
+ auto proof12 = buildProof(10, {outpoint1, outpoint2});
+ auto proof23 = buildProof(20, {outpoint2, outpoint3});
+ auto proof13 = buildProof(30, {outpoint1, outpoint3});
+ std::vector<ProofRef> proofs{proof12, proof23, proof13};
+
+ for (const auto &proof : proofs) {
+ std::set<ProofRef> shifted;
+ BOOST_CHECK(pool.addProof(proof, shifted));
+ BOOST_CHECK(hasAllProofUtxos(pool, proof));
+ }
+
+ for (const auto &proof : proofs) {
+ BOOST_CHECK(pool.removeProof(proof));
+ BOOST_CHECK(!hasAllProofUtxos(pool, proof));
+ }
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()

File Metadata

Mime Type
text/plain
Expires
Sat, Apr 26, 11:07 (10 h, 58 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5573364
Default Alt Text
D10459.diff (15 KB)

Event Timeline