Changeset View
Changeset View
Standalone View
Standalone View
src/avalanche/test/compactproofs_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/compactproofs.h> | |||||
#include <avalanche/test/util.h> | |||||
#include <streams.h> | |||||
#include <test/util/setup_common.h> | |||||
#include <boost/test/unit_test.hpp> | |||||
#include <algorithm> | |||||
namespace avalanche { | |||||
namespace { | |||||
struct TestCompactProofs { | |||||
static std::vector<uint64_t> getShortProofIds(const CompactProofs &cp) { | |||||
return cp.shortproofids; | |||||
} | |||||
static std::vector<PrefilledProof> | |||||
getPrefilledProofs(const CompactProofs &cp) { | |||||
return cp.prefilledProofs; | |||||
} | |||||
static void addPrefilledProof(CompactProofs &cp, uint32_t index, | |||||
const ProofRef &proof) { | |||||
PrefilledProof pp{index, proof}; | |||||
cp.prefilledProofs.push_back(std::move(pp)); | |||||
} | |||||
}; | |||||
} // namespace | |||||
} // namespace avalanche | |||||
using namespace avalanche; | |||||
// TestingSetup is required for buildRandomProof() | |||||
BOOST_FIXTURE_TEST_SUITE(compactproofs_tests, TestingSetup) | |||||
BOOST_AUTO_TEST_CASE(compactproofs_roundtrip) { | |||||
{ | |||||
CompactProofs cpw; | |||||
BOOST_CHECK_EQUAL(cpw.size(), 0); | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
BOOST_CHECK_NO_THROW(ss << cpw); | |||||
CompactProofs cpr; | |||||
BOOST_CHECK_NO_THROW(ss >> cpr); | |||||
BOOST_CHECK_EQUAL(cpr.size(), 0); | |||||
BOOST_CHECK_EQUAL(cpr.getKeys().first, cpw.getKeys().first); | |||||
BOOST_CHECK_EQUAL(cpr.getKeys().second, cpw.getKeys().second); | |||||
} | |||||
{ | |||||
// Check index boundaries | |||||
CompactProofs cp; | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, std::numeric_limits<uint32_t>::max(), | |||||
buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
BOOST_CHECK_NO_THROW(ss << cp); | |||||
auto prefilledProofs = TestCompactProofs::getPrefilledProofs(cp); | |||||
BOOST_CHECK_EQUAL(prefilledProofs.size(), 2); | |||||
BOOST_CHECK_EQUAL(prefilledProofs[0].index, 0); | |||||
BOOST_CHECK_EQUAL(prefilledProofs[1].index, | |||||
std::numeric_limits<uint32_t>::max()); | |||||
} | |||||
auto checkCompactProof = [&](size_t numofProof, | |||||
size_t numofPrefilledProof) { | |||||
RadixTree<const Proof, ProofRadixTreeAdapter> proofs; | |||||
for (size_t i = 0; i < numofProof; i++) { | |||||
BOOST_CHECK(proofs.insert(buildRandomProof(MIN_VALID_PROOF_SCORE))); | |||||
} | |||||
CompactProofs cpw(proofs); | |||||
BOOST_CHECK_EQUAL(cpw.size(), numofProof); | |||||
uint32_t prefilledProofIndex = 0; | |||||
for (size_t i = 0; i < numofPrefilledProof; i++) { | |||||
prefilledProofIndex += | |||||
std::min(MAX_SIZE, std::numeric_limits<uint32_t>::max() / | |||||
numofPrefilledProof); | |||||
TestCompactProofs::addPrefilledProof( | |||||
cpw, prefilledProofIndex, | |||||
buildRandomProof( | |||||
GetRand(std::numeric_limits<uint32_t>::max()))); | |||||
} | |||||
auto prefilledProofs = TestCompactProofs::getPrefilledProofs(cpw); | |||||
BOOST_CHECK_EQUAL(prefilledProofs.size(), numofPrefilledProof); | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
BOOST_CHECK_NO_THROW(ss << cpw); | |||||
CompactProofs cpr; | |||||
BOOST_CHECK_NO_THROW(ss >> cpr); | |||||
BOOST_CHECK_EQUAL(cpr.size(), numofProof + numofPrefilledProof); | |||||
BOOST_CHECK_EQUAL(cpr.getKeys().first, cpw.getKeys().first); | |||||
BOOST_CHECK_EQUAL(cpr.getKeys().second, cpw.getKeys().second); | |||||
auto comparePrefilledProof = [](const PrefilledProof &lhs, | |||||
const PrefilledProof &rhs) { | |||||
return lhs.index == rhs.index && | |||||
lhs.proof->getId() == rhs.proof->getId() && | |||||
lhs.proof->getSignature() == rhs.proof->getSignature(); | |||||
}; | |||||
auto prefilledProofsCpr = TestCompactProofs::getPrefilledProofs(cpr); | |||||
BOOST_CHECK(std::equal(prefilledProofsCpr.begin(), | |||||
prefilledProofsCpr.end(), | |||||
prefilledProofs.begin(), comparePrefilledProof)); | |||||
auto shortIds = TestCompactProofs::getShortProofIds(cpr); | |||||
size_t index = 0; | |||||
proofs.forEachLeaf([&](auto pLeaf) { | |||||
const ProofId &proofid = pLeaf->getId(); | |||||
BOOST_CHECK_EQUAL(cpr.getShortID(proofid), cpw.getShortID(proofid)); | |||||
BOOST_CHECK_EQUAL(cpr.getShortID(proofid), shortIds[index]); | |||||
++index; | |||||
return true; | |||||
}); | |||||
}; | |||||
// No proof at all | |||||
checkCompactProof(0, 0); | |||||
// No prefilled proofs | |||||
checkCompactProof(1000, 0); | |||||
// Only prefilled proofs | |||||
checkCompactProof(0, 1000); | |||||
// Mixed case | |||||
checkCompactProof(1000, 1000); | |||||
} | |||||
BOOST_AUTO_TEST_CASE(compactproofs_overflow) { | |||||
{ | |||||
CompactProofs cp; | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure, | |||||
HasReason("differential value overflow")); | |||||
} | |||||
{ | |||||
CompactProofs cp; | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, 1, buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure, | |||||
HasReason("differential value overflow")); | |||||
} | |||||
{ | |||||
CompactProofs cp; | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, std::numeric_limits<uint32_t>::max(), | |||||
buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
TestCompactProofs::addPrefilledProof( | |||||
cp, 0, buildRandomProof(MIN_VALID_PROOF_SCORE)); | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure, | |||||
HasReason("differential value overflow")); | |||||
} | |||||
{ | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
// shortproofidk0, shortproofidk1 | |||||
ss << uint64_t(0) << uint64_t(0); | |||||
// shortproofids.size() | |||||
WriteCompactSize(ss, MAX_SIZE + 1); | |||||
CompactProofs cp; | |||||
BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure, | |||||
HasReason("ReadCompactSize(): size too large")); | |||||
} | |||||
{ | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
// shortproofidk0, shortproofidk1 | |||||
ss << uint64_t(0) << uint64_t(0); | |||||
// shortproofids.size() | |||||
WriteCompactSize(ss, 0); | |||||
// prefilledProofs.size() | |||||
WriteCompactSize(ss, MAX_SIZE + 1); | |||||
CompactProofs cp; | |||||
BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure, | |||||
HasReason("ReadCompactSize(): size too large")); | |||||
} | |||||
{ | |||||
CDataStream ss(SER_NETWORK, PROTOCOL_VERSION); | |||||
// shortproofidk0, shortproofidk1 | |||||
ss << uint64_t(0) << uint64_t(0); | |||||
// shortproofids.size() | |||||
WriteCompactSize(ss, 0); | |||||
// prefilledProofs.size() | |||||
WriteCompactSize(ss, 1); | |||||
// prefilledProofs[0].index | |||||
WriteCompactSize(ss, MAX_SIZE + 1); | |||||
// prefilledProofs[0].proof | |||||
ss << buildRandomProof(MIN_VALID_PROOF_SCORE); | |||||
CompactProofs cp; | |||||
BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure, | |||||
HasReason("ReadCompactSize(): size too large")); | |||||
} | |||||
{ | |||||
// Compute the number of MAX_SIZE increment we need to cause an overflow | |||||
const uint64_t overflow = | |||||
uint64_t(std::numeric_limits<uint32_t>::max()) + 1; | |||||
BOOST_CHECK_GE(overflow, MAX_SIZE); | |||||
const uint64_t overflowIter = overflow / MAX_SIZE; | |||||
// Make sure the iteration fits in an uint32_t | |||||
BOOST_CHECK_LE(overflowIter, std::numeric_limits<uint32_t>::max()); | |||||
uint32_t remainder = uint32_t(overflow - (MAX_SIZE * overflowIter)); | |||||
CDataStream ss(SER_DISK, PROTOCOL_VERSION); | |||||
// shortproofidk0, shortproofidk1 | |||||
ss << uint64_t(0) << uint64_t(0); | |||||
// shortproofids.size() | |||||
WriteCompactSize(ss, 0); | |||||
// prefilledProofs.size() | |||||
WriteCompactSize(ss, overflowIter); | |||||
for (uint32_t i = 0; i < overflowIter; i++) { | |||||
// prefilledProofs[i].index | |||||
WriteCompactSize(ss, MAX_SIZE); | |||||
// prefilledProofs[i].proof | |||||
ss << buildRandomProof(MIN_VALID_PROOF_SCORE); | |||||
} | |||||
// This is the prefilled proof causing the overflow | |||||
WriteCompactSize(ss, remainder); | |||||
ss << buildRandomProof(MIN_VALID_PROOF_SCORE); | |||||
CompactProofs cp; | |||||
BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure, | |||||
HasReason("differential value overflow")); | |||||
} | |||||
} | |||||
BOOST_AUTO_TEST_SUITE_END() |