Bitcoin ABC  0.26.3
P2P Digital Currency
compactproofs_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2022 The Bitcoin developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
6 
7 #include <avalanche/test/util.h>
8 #include <streams.h>
9 
10 #include <test/util/setup_common.h>
11 
12 #include <boost/test/unit_test.hpp>
13 
14 #include <algorithm>
15 
16 namespace avalanche {
17 namespace {
18  struct TestCompactProofs {
19  static std::vector<uint64_t> getShortProofIds(const CompactProofs &cp) {
20  return cp.shortproofids;
21  }
22 
23  static std::vector<PrefilledProof>
24  getPrefilledProofs(const CompactProofs &cp) {
25  return cp.prefilledProofs;
26  }
27 
28  static void addPrefilledProof(CompactProofs &cp, uint32_t index,
29  const ProofRef &proof) {
30  PrefilledProof pp{index, proof};
31  cp.prefilledProofs.push_back(std::move(pp));
32  }
33  };
34 } // namespace
35 } // namespace avalanche
36 
37 using namespace avalanche;
38 
39 // TestingSetup is required for buildRandomProof()
40 BOOST_FIXTURE_TEST_SUITE(compactproofs_tests, TestingSetup)
41 
42 BOOST_AUTO_TEST_CASE(compactproofs_roundtrip) {
43  {
44  CompactProofs cpw;
45  BOOST_CHECK_EQUAL(cpw.size(), 0);
46 
48  BOOST_CHECK_NO_THROW(ss << cpw);
49 
50  CompactProofs cpr;
51  BOOST_CHECK_NO_THROW(ss >> cpr);
52 
53  BOOST_CHECK_EQUAL(cpr.size(), 0);
54  BOOST_CHECK_EQUAL(cpr.getKeys().first, cpw.getKeys().first);
55  BOOST_CHECK_EQUAL(cpr.getKeys().second, cpw.getKeys().second);
56  }
57 
58  CChainState &active_chainstate =
59  Assert(m_node.chainman)->ActiveChainstate();
60 
61  {
62  // Check index boundaries
63  CompactProofs cp;
64 
65  TestCompactProofs::addPrefilledProof(
66  cp, 0, buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
67  TestCompactProofs::addPrefilledProof(
68  cp, std::numeric_limits<uint32_t>::max(),
69  buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
70 
72  BOOST_CHECK_NO_THROW(ss << cp);
73 
74  auto prefilledProofs = TestCompactProofs::getPrefilledProofs(cp);
75  BOOST_CHECK_EQUAL(prefilledProofs.size(), 2);
76 
77  BOOST_CHECK_EQUAL(prefilledProofs[0].index, 0);
78  BOOST_CHECK_EQUAL(prefilledProofs[1].index,
79  std::numeric_limits<uint32_t>::max());
80  }
81 
82  auto checkCompactProof = [&](size_t numofProof,
83  size_t numofPrefilledProof) {
85  for (size_t i = 0; i < numofProof; i++) {
86  BOOST_CHECK(proofs.insert(
87  buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE)));
88  }
89 
90  CompactProofs cpw(proofs);
91  BOOST_CHECK_EQUAL(cpw.size(), numofProof);
92 
93  uint32_t prefilledProofIndex = 0;
94  for (size_t i = 0; i < numofPrefilledProof; i++) {
95  TestCompactProofs::addPrefilledProof(
96  cpw, prefilledProofIndex++,
98  active_chainstate,
99  GetRand(std::numeric_limits<uint32_t>::max())));
100  }
101  auto prefilledProofs = TestCompactProofs::getPrefilledProofs(cpw);
102  BOOST_CHECK_EQUAL(prefilledProofs.size(), numofPrefilledProof);
103 
105  BOOST_CHECK_NO_THROW(ss << cpw);
106 
107  CompactProofs cpr;
108  BOOST_CHECK_NO_THROW(ss >> cpr);
109 
110  BOOST_CHECK_EQUAL(cpr.size(), numofProof + numofPrefilledProof);
111  BOOST_CHECK_EQUAL(cpr.getKeys().first, cpw.getKeys().first);
112  BOOST_CHECK_EQUAL(cpr.getKeys().second, cpw.getKeys().second);
113 
114  auto comparePrefilledProof = [](const PrefilledProof &lhs,
115  const PrefilledProof &rhs) {
116  return lhs.index == rhs.index &&
117  lhs.proof->getId() == rhs.proof->getId() &&
118  lhs.proof->getSignature() == rhs.proof->getSignature();
119  };
120 
121  auto prefilledProofsCpr = TestCompactProofs::getPrefilledProofs(cpr);
122  BOOST_CHECK(std::equal(prefilledProofsCpr.begin(),
123  prefilledProofsCpr.end(),
124  prefilledProofs.begin(), comparePrefilledProof));
125 
126  auto shortIds = TestCompactProofs::getShortProofIds(cpr);
127  size_t index = 0;
128  proofs.forEachLeaf([&](auto pLeaf) {
129  const ProofId &proofid = pLeaf->getId();
130  BOOST_CHECK_EQUAL(cpr.getShortID(proofid), cpw.getShortID(proofid));
131  BOOST_CHECK_EQUAL(cpr.getShortID(proofid), shortIds[index]);
132  ++index;
133 
134  return true;
135  });
136  };
137 
138  // No proof at all
139  checkCompactProof(0, 0);
140 
141  // No prefilled proofs
142  checkCompactProof(1000, 0);
143 
144  // Only prefilled proofs
145  checkCompactProof(0, 1000);
146 
147  // Mixed case
148  checkCompactProof(1000, 1000);
149 }
150 
151 BOOST_AUTO_TEST_CASE(compactproofs_overflow) {
152  CChainState &active_chainstate =
153  Assert(m_node.chainman)->ActiveChainstate();
154  {
155  CompactProofs cp;
156 
157  TestCompactProofs::addPrefilledProof(
158  cp, 0, buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
159  TestCompactProofs::addPrefilledProof(
160  cp, 0, buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
161 
163  BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure,
164  HasReason("differential value overflow"));
165  }
166 
167  {
168  CompactProofs cp;
169 
170  TestCompactProofs::addPrefilledProof(
171  cp, 1, buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
172  TestCompactProofs::addPrefilledProof(
173  cp, 0, buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
174 
176  BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure,
177  HasReason("differential value overflow"));
178  }
179 
180  {
181  CompactProofs cp;
182 
183  TestCompactProofs::addPrefilledProof(
184  cp, std::numeric_limits<uint32_t>::max(),
185  buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
186  TestCompactProofs::addPrefilledProof(
187  cp, 0, buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE));
188 
190  BOOST_CHECK_EXCEPTION(ss << cp, std::ios_base::failure,
191  HasReason("differential value overflow"));
192  }
193 
194  {
196  // shortproofidk0, shortproofidk1
197  ss << uint64_t(0) << uint64_t(0);
198  // shortproofids.size()
199  WriteCompactSize(ss, MAX_SIZE + 1);
200 
201  CompactProofs cp;
202  BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
203  HasReason("ReadCompactSize(): size too large"));
204  }
205 
206  {
208  // shortproofidk0, shortproofidk1
209  ss << uint64_t(0) << uint64_t(0);
210  // shortproofids.size()
211  WriteCompactSize(ss, 0);
212  // prefilledProofs.size()
213  WriteCompactSize(ss, MAX_SIZE + 1);
214 
215  CompactProofs cp;
216  BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
217  HasReason("ReadCompactSize(): size too large"));
218  }
219 
220  {
222  // shortproofidk0, shortproofidk1
223  ss << uint64_t(0) << uint64_t(0);
224  // shortproofids.size()
225  WriteCompactSize(ss, 0);
226  // prefilledProofs.size()
227  WriteCompactSize(ss, 1);
228  // prefilledProofs[0].index
229  WriteCompactSize(ss, MAX_SIZE + 1);
230  // prefilledProofs[0].proof
231  ss << buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE);
232 
233  CompactProofs cp;
234  BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
235  HasReason("ReadCompactSize(): size too large"));
236  }
237 
238  // Compute the number of MAX_SIZE increment we need to cause an overflow
239  const uint64_t overflow =
240  uint64_t(std::numeric_limits<uint32_t>::max()) + 1;
241  // Due to differential encoding, a value of MAX_SIZE bumps the index by
242  // MAX_SIZE + 1
243  BOOST_CHECK_GE(overflow, MAX_SIZE + 1);
244  const uint64_t overflowIter = overflow / (MAX_SIZE + 1);
245 
246  // Make sure the iteration fits in an uint32_t and is <= MAX_SIZE
247  BOOST_CHECK_LE(overflowIter, std::numeric_limits<uint32_t>::max());
248  BOOST_CHECK_LE(overflowIter, MAX_SIZE);
249  uint32_t remainder = uint32_t(overflow - ((MAX_SIZE + 1) * overflowIter));
250 
251  {
253  // shortproofidk0, shortproofidk1
254  ss << uint64_t(0) << uint64_t(0);
255  // shortproofids.size()
256  WriteCompactSize(ss, 0);
257  // prefilledProofs.size()
258  WriteCompactSize(ss, overflowIter + 1);
259  for (uint32_t i = 0; i < overflowIter; i++) {
260  // prefilledProofs[i].index
262  // prefilledProofs[i].proof
263  ss << buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE);
264  }
265  // This is the prefilled proof causing the overflow
266  WriteCompactSize(ss, remainder);
267  ss << buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE);
268 
269  CompactProofs cp;
270  BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
271  HasReason("differential value overflow"));
272  }
273 
274  {
276  // shortproofidk0, shortproofidk1
277  ss << uint64_t(0) << uint64_t(0);
278  // shortproofids.size()
279  WriteCompactSize(ss, 1);
280  // shortproofids[0]
282  // prefilledProofs.size()
283  WriteCompactSize(ss, overflowIter + 1);
284  for (uint32_t i = 0; i < overflowIter; i++) {
285  // prefilledProofs[i].index
287  // prefilledProofs[i].proof
288  ss << buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE);
289  }
290  // This prefilled proof isn't enough to cause the overflow alone, but it
291  // overflows due to the extra shortid.
292  WriteCompactSize(ss, remainder - 1);
293  ss << buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE);
294 
295  CompactProofs cp;
296  // ss >> cp;
297  BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
298  HasReason("indexes overflowed 32 bits"));
299  }
300 
301  {
303  // shortproofidk0, shortproofidk1
304  ss << uint64_t(0) << uint64_t(0);
305  // shortproofids.size()
306  WriteCompactSize(ss, 0);
307  // prefilledProofs.size()
308  WriteCompactSize(ss, 2);
309  // prefilledProofs[0].index
310  WriteCompactSize(ss, 0);
311  // prefilledProofs[0].proof
312  ss << buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE);
313  // prefilledProofs[1].index = 1 is differentially encoded, which means
314  // it has an absolute index of 2. This leaves no proof at index 1.
315  WriteCompactSize(ss, 1);
316  // prefilledProofs[1].proof
317  ss << buildRandomProof(active_chainstate, MIN_VALID_PROOF_SCORE);
318 
319  CompactProofs cp;
320  BOOST_CHECK_EXCEPTION(ss >> cp, std::ios_base::failure,
321  HasReason("non contiguous indexes"));
322  }
323 }
324 
#define Assert(val)
Identity function.
Definition: check.h:56
CChainState stores and provides an API to update our local knowledge of the current best chain.
Definition: validation.h:808
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:197
std::vector< PrefilledProof > prefilledProofs
Definition: compactproofs.h:58
uint64_t getShortID(const ProofId &proofid) const
std::pair< uint64_t, uint64_t > getKeys() const
Definition: compactproofs.h:73
std::vector< uint64_t > shortproofids
Definition: compactproofs.h:57
const ProofId & getId() const
Definition: proof.h:169
const SchnorrSig & getSignature() const
Definition: proof.h:167
BOOST_AUTO_TEST_CASE(compactproofs_roundtrip)
NodeContext & m_node
Definition: chain.cpp:484
constexpr uint32_t MIN_VALID_PROOF_SCORE
Definition: util.h:17
ProofRef buildRandomProof(CChainState &active_chainstate, uint32_t score, int height, const CKey &masterKey)
Definition: util.cpp:20
#define BOOST_AUTO_TEST_SUITE_END()
Definition: object.cpp:16
#define BOOST_FIXTURE_TEST_SUITE(a, b)
Definition: object.cpp:14
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
#define BOOST_CHECK_NO_THROW(stmt)
Definition: object.cpp:28
#define BOOST_CHECK(expr)
Definition: object.cpp:17
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:650
static constexpr uint64_t MAX_SIZE
The maximum size of a serialized object in bytes or number of elements (for eg vectors) when the size...
Definition: serialize.h:31
@ SER_DISK
Definition: serialize.h:167
@ SER_NETWORK
Definition: serialize.h:166
void WriteCompactSize(CSizeComputer &os, uint64_t nSize)
Definition: serialize.h:1255
Serialization wrapper class for custom integers and enums.
Definition: serialize.h:624
void Ser(Stream &s, I v)
Definition: serialize.h:629
std::unique_ptr< ChainstateManager > chainman
Definition: context.h:40
bool forEachLeaf(Callable &&func) const
Definition: radix.h:143
bool insert(const RCUPtr< T > &value)
Insert a value into the tree.
Definition: radix.h:111
avalanche::ProofRef proof
Definition: compactproofs.h:33
static const int PROTOCOL_VERSION
network protocol versioning
Definition: version.h:11