Page MenuHomePhabricator
Files F13115708

D11453.diff
No OneTemporary
Actions

D11453.diff
View Options

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -544,6 +544,7 @@
addrdb.cpp
addrman.cpp
avalanche/avalanche.cpp
+ avalanche/compactproofs.cpp
avalanche/delegation.cpp
avalanche/delegationbuilder.cpp
avalanche/peermanager.cpp
diff --git a/src/avalanche/compactproofs.h b/src/avalanche/compactproofs.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/compactproofs.h
@@ -0,0 +1,106 @@
+// 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_COMPACTPROOFS_H
+#define BITCOIN_AVALANCHE_COMPACTPROOFS_H
+
+#include <avalanche/proof.h>
+#include <avalanche/proofradixtreeadapter.h>
+
+#include <radix.h>
+#include <random.h>
+#include <serialize.h>
+
+#include <cstdint>
+#include <ios>
+#include <limits>
+#include <utility>
+#include <vector>
+
+namespace avalanche {
+
+namespace {
+ struct TestCompactProofs;
+}
+
+struct ProofId;
+
+struct PrefilledProof {
+ // Used as an offset since last prefilled proof in CompactProofs
+ uint32_t index;
+ avalanche::ProofRef proof;
+
+ class Formatter : public DifferenceFormatter {
+ public:
+ template <typename Stream> void Ser(Stream &s, PrefilledProof pp) {
+ DifferenceFormatter::Ser(s, pp.index);
+ s << pp.proof;
+ }
+
+ template <typename Stream> void Unser(Stream &s, PrefilledProof &pp) {
+ DifferenceFormatter::Unser(s, pp.index);
+ s >> pp.proof;
+ }
+ };
+};
+
+class CompactProofs {
+private:
+ uint64_t shortproofidk0, shortproofidk1;
+ std::vector<uint64_t> shortproofids;
+ std::vector<PrefilledProof> prefilledProofs;
+
+public:
+ static constexpr int SHORTPROOFIDS_LENGTH = 6;
+
+ CompactProofs()
+ : shortproofidk0(GetRand(std::numeric_limits<uint64_t>::max())),
+ shortproofidk1(GetRand(std::numeric_limits<uint64_t>::max())) {}
+ CompactProofs(const RadixTree<const Proof, ProofRadixTreeAdapter> &proofs);
+
+ uint64_t getShortID(const ProofId &proofid) const;
+
+ size_t size() const {
+ return shortproofids.size() + prefilledProofs.size();
+ }
+ std::pair<uint64_t, uint64_t> getKeys() const {
+ return std::make_pair(shortproofidk0, shortproofidk1);
+ }
+
+ SERIALIZE_METHODS(CompactProofs, obj) {
+ READWRITE(
+ obj.shortproofidk0, obj.shortproofidk1,
+ Using<VectorFormatter<CustomUintFormatter<SHORTPROOFIDS_LENGTH>>>(
+ obj.shortproofids),
+ Using<VectorFormatter<PrefilledProof::Formatter>>(
+ obj.prefilledProofs));
+
+ if (ser_action.ForRead() && obj.prefilledProofs.size() > 0) {
+ // Thanks to the DifferenceFormatter, the index values in the
+ // deserialized prefilled proofs are absolute and sorted, so the
+ // last vector item has the highest index value.
+ uint64_t highestPrefilledIndex = obj.prefilledProofs.back().index;
+
+ // Make sure the indexes do not overflow 32 bits.
+ if (highestPrefilledIndex + obj.shortproofids.size() >
+ std::numeric_limits<uint32_t>::max()) {
+ throw std::ios_base::failure("indexes overflowed 32 bits");
+ }
+
+ // Make sure the indexes are contiguous. E.g. if there is no shortid
+ // but 2 prefilled proofs with absolute indexes 0 and 2, then the
+ // proof at index 1 cannot be recovered.
+ if (highestPrefilledIndex >= obj.size()) {
+ throw std::ios_base::failure("non contiguous indexes");
+ }
+ }
+ }
+
+private:
+ friend struct ::avalanche::TestCompactProofs;
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_COMPACTPROOFS_H
diff --git a/src/avalanche/compactproofs.cpp b/src/avalanche/compactproofs.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/compactproofs.cpp
@@ -0,0 +1,28 @@
+// 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.
+
+#include <avalanche/compactproofs.h>
+
+#include <avalanche/proofid.h>
+#include <crypto/siphash.h>
+
+namespace avalanche {
+
+CompactProofs::CompactProofs(
+ const RadixTree<const Proof, ProofRadixTreeAdapter> &proofs)
+ : CompactProofs() {
+ proofs.forEachLeaf([&](auto pLeaf) {
+ shortproofids.push_back(getShortID(pLeaf->getId()));
+ return true;
+ });
+}
+
+uint64_t CompactProofs::getShortID(const ProofId &proofid) const {
+ static_assert(SHORTPROOFIDS_LENGTH == 6,
+ "shortproofids calculation assumes 6-byte shortproofids");
+ return SipHashUint256(shortproofidk0, shortproofidk1, proofid) &
+ 0xffffffffffffL;
+}
+
+} // 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
@@ -13,6 +13,7 @@
util.cpp
TESTS
+ compactproofs_tests.cpp
delegation_tests.cpp
init_tests.cpp
peermanager_tests.cpp
diff --git a/src/avalanche/test/compactproofs_tests.cpp b/src/avalanche/test/compactproofs_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/avalanche/test/compactproofs_tests.cpp
@@ -0,0 +1,318 @@
+// 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.
+
+#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++) {
+ 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;
+ // Due to differential encoding, a value of MAX_SIZE bumps the index by
+ // MAX_SIZE + 1
+ BOOST_CHECK_GE(overflow, MAX_SIZE + 1);
+ const uint64_t overflowIter = overflow / (MAX_SIZE + 1);
+
+ // Make sure the iteration fits in an uint32_t and is <= MAX_SIZE
+ BOOST_CHECK_LE(overflowIter, std::numeric_limits<uint32_t>::max());
+ BOOST_CHECK_LE(overflowIter, MAX_SIZE);
+ uint32_t remainder = uint32_t(overflow - ((MAX_SIZE + 1) * 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 + 1);
+ 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"));
+ }
+
+ {
+ CDataStream ss(SER_DISK, PROTOCOL_VERSION);
+ // shortproofidk0, shortproofidk1
+ ss << uint64_t(0) << uint64_t(0);
+ // shortproofids.size()
+ WriteCompactSize(ss, 1);
+ // shortproofids[0]
+ CustomUintFormatter<CompactProofs::SHORTPROOFIDS_LENGTH>().Ser(ss, 0u);
+ // prefilledProofs.size()
+ WriteCompactSize(ss, overflowIter + 1);
+ 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 prefilled proof isn't enough to cause the overflow alone, but it
+ // overflows due to the extra shortid.
+ WriteCompactSize(ss, remainder - 1);
+ ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+ CompactProofs cp;
+ // ss >> cp;
+ BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+ HasReason("indexes overflowed 32 bits"));
+ }
+
+ {
+ CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+ // shortproofidk0, shortproofidk1
+ ss << uint64_t(0) << uint64_t(0);
+ // shortproofids.size()
+ WriteCompactSize(ss, 0);
+ // prefilledProofs.size()
+ WriteCompactSize(ss, 2);
+ // prefilledProofs[0].index
+ WriteCompactSize(ss, 0);
+ // prefilledProofs[0].proof
+ ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+ // prefilledProofs[1].index = 1 is differentially encoded, which means
+ // it has an absolute index of 2. This leaves no proof at index 1.
+ WriteCompactSize(ss, 1);
+ // prefilledProofs[1].proof
+ ss << buildRandomProof(MIN_VALID_PROOF_SCORE);
+
+ CompactProofs cp;
+ BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
+ HasReason("non contiguous indexes"));
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()

File Metadata

Mime Type
text/plain
Expires
Sat, Mar 1, 11:49 (3 h, 48 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5187699
Default Alt Text
D11453.diff (16 KB)

Event Timeline