Differential D10459 Diff 30909 src/avalanche/test/proofpool_tests.cpp

Changeset View

Standalone View

src/avalanche/test/proofpool_tests.cpp

This file was added.

				// 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()