Bitcoin Core  22.99.0
P2P Digital Currency
test.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2018,2021 Pieter Wuille, Greg Maxwell, Gleb Naumenko *
3  * Distributed under the MIT software license, see the accompanying *
4  * file LICENSE or http://www.opensource.org/licenses/mit-license.php.*
5  **********************************************************************/
6 
7 #include <algorithm>
8 #include <cstdio>
9 #include <limits>
10 #include <random>
11 #include <stdexcept>
12 #include <vector>
13 
14 #include "../include/minisketch.h"
15 #include "util.h"
16 
17 namespace {
18 
19 uint64_t Combination(uint64_t n, uint64_t k) {
20  if (n - k < k) k = n - k;
21  uint64_t ret = 1;
22  for (uint64_t i = 1; i <= k; ++i) {
23  ret = (ret * n) / i;
24  --n;
25  }
26  return ret;
27 }
28 
30 std::vector<Minisketch> CreateSketches(uint32_t bits, size_t capacity) {
31  if (!Minisketch::BitsSupported(bits)) return {};
32  std::vector<Minisketch> ret;
33  for (uint32_t impl = 0; impl <= Minisketch::MaxImplementation(); ++impl) {
34  if (Minisketch::ImplementationSupported(bits, impl)) {
35  CHECK(Minisketch::BitsSupported(bits));
36  ret.push_back(Minisketch(bits, impl, capacity));
37  CHECK((bool)ret.back());
38  } else {
39  // implementation 0 must always work unless field size is disabled
40  CHECK(impl != 0 || !Minisketch::BitsSupported(bits));
41  }
42  }
43  return ret;
44 }
45 
48 void TestExhaustive(uint32_t bits, size_t capacity) {
49  auto sketches = CreateSketches(bits, capacity);
50  if (sketches.empty()) return;
51  auto sketches_rebuild = CreateSketches(bits, capacity);
52 
53  std::vector<unsigned char> serialized;
54  std::vector<unsigned char> serialized_empty;
55  std::vector<uint64_t> counts;
56  std::vector<uint64_t> elements_0;
57  std::vector<uint64_t> elements_other;
58  std::vector<uint64_t> elements_too_small;
59 
60  counts.resize(capacity + 1);
61  serialized.resize(sketches[0].GetSerializedSize());
62  serialized_empty.resize(sketches[0].GetSerializedSize());
63 
64  // Iterate over all (bits)-bit sketches with (capacity) syndromes.
65  for (uint64_t x = 0; (x >> (bits * capacity)) == 0; ++x) {
66  // Construct the serialization.
67  for (size_t i = 0; i < serialized.size(); ++i) {
68  serialized[i] = (x >> (i * 8)) & 0xFF;
69  }
70 
71  // Compute all the solutions
72  sketches[0].Deserialize(serialized);
73  elements_0.resize(64);
74  bool decodable_0 = sketches[0].Decode(elements_0);
75  std::sort(elements_0.begin(), elements_0.end());
76 
77  // Verify that decoding with other implementations agrees.
78  for (size_t impl = 1; impl < sketches.size(); ++impl) {
79  sketches[impl].Deserialize(serialized);
80  elements_other.resize(64);
81  bool decodable_other = sketches[impl].Decode(elements_other);
82  CHECK(decodable_other == decodable_0);
83  std::sort(elements_other.begin(), elements_other.end());
84  CHECK(elements_other == elements_0);
85  }
86 
87  // If there are solutions:
88  if (decodable_0) {
89  if (!elements_0.empty()) {
90  // Decoding with limit one less than the number of elements should fail.
91  elements_too_small.resize(elements_0.size() - 1);
92  for (size_t impl = 0; impl < sketches.size(); ++impl) {
93  CHECK(!sketches[impl].Decode(elements_too_small));
94  }
95  }
96 
97  // Reconstruct the sketch from the solutions.
98  for (size_t impl = 0; impl < sketches.size(); ++impl) {
99  // Clear the sketch.
100  sketches_rebuild[impl].Deserialize(serialized_empty);
101  // Load all decoded elements into it.
102  for (uint64_t elem : elements_0) {
103  CHECK(elem != 0);
104  CHECK(elem >> bits == 0);
105  sketches_rebuild[impl].Add(elem);
106  }
107  // Reserialize the result
108  auto serialized_rebuild = sketches_rebuild[impl].Serialize();
109  // Compare
110  CHECK(serialized == serialized_rebuild);
111  // Count it
112  if (impl == 0 && elements_0.size() <= capacity) ++counts[elements_0.size()];
113  }
114  }
115  }
116 
117  // Verify that the number of decodable sketches with given elements is expected.
118  uint64_t mask = bits == 64 ? UINT64_MAX : (uint64_t{1} << bits) - 1;
119  for (uint64_t i = 0; i <= capacity && (i & mask) == i; ++i) {
120  CHECK(counts[i] == Combination(mask, i));
121  }
122 }
123 
125 void TestRandomized(uint32_t bits, size_t max_capacity, size_t iter) {
126  std::random_device rnd;
127  std::uniform_int_distribution<uint64_t> capacity_dist(0, std::min<uint64_t>(std::numeric_limits<uint64_t>::max() >> (64 - bits), max_capacity));
128  std::uniform_int_distribution<uint64_t> element_dist(1, std::numeric_limits<uint64_t>::max() >> (64 - bits));
129  std::uniform_int_distribution<uint64_t> rand64(0, std::numeric_limits<uint64_t>::max());
130  std::uniform_int_distribution<int64_t> size_offset_dist(-3, 3);
131 
132  std::vector<uint64_t> decode_0;
133  std::vector<uint64_t> decode_other;
134  std::vector<uint64_t> decode_temp;
135  std::vector<uint64_t> elements;
136 
137  for (size_t i = 0; i < iter; ++i) {
138  // Determine capacity, and construct Minisketch objects for all implementations.
139  uint64_t capacity = capacity_dist(rnd);
140  auto sketches = CreateSketches(bits, capacity);
141  // Sanity checks
142  if (sketches.empty()) return;
143  for (size_t impl = 0; impl < sketches.size(); ++impl) {
144  CHECK(sketches[impl].GetBits() == bits);
145  CHECK(sketches[impl].GetCapacity() == capacity);
146  CHECK(sketches[impl].GetSerializedSize() == sketches[0].GetSerializedSize());
147  }
148  // Determine the number of elements, and create a vector to store them in.
149  size_t element_count = std::max<int64_t>(0, std::max<int64_t>(0, capacity + size_offset_dist(rnd)));
150  elements.resize(element_count);
151  // Add the elements to all sketches
152  for (size_t j = 0; j < element_count; ++j) {
153  uint64_t elem = element_dist(rnd);
154  CHECK(elem != 0);
155  elements[j] = elem;
156  for (auto& sketch : sketches) sketch.Add(elem);
157  }
158  // Remove pairs of duplicates in elements, as they cancel out.
159  std::sort(elements.begin(), elements.end());
160  size_t real_element_count = element_count;
161  for (size_t pos = 0; pos + 1 < elements.size(); ++pos) {
162  if (elements[pos] == elements[pos + 1]) {
163  real_element_count -= 2;
164  // Set both elements to 0; afterwards we will move these to the end.
165  elements[pos] = 0;
166  elements[pos + 1] = 0;
167  ++pos;
168  }
169  }
170  if (real_element_count < element_count) {
171  // Move all introduced zeroes (masking duplicates) to the end.
172  std::sort(elements.begin(), elements.end(), [](uint64_t a, uint64_t b) { return a != b && (b == 0 || (a != 0 && a < b)); });
173  CHECK(elements[real_element_count] == 0);
174  elements.resize(real_element_count);
175  }
176  // Create and compare serializations
177  auto serialized_0 = sketches[0].Serialize();
178  for (size_t impl = 1; impl < sketches.size(); ++impl) {
179  auto serialized_other = sketches[impl].Serialize();
180  CHECK(serialized_other == serialized_0);
181  }
182  // Deserialize and reserialize them
183  for (size_t impl = 0; impl < sketches.size(); ++impl) {
184  sketches[impl].Deserialize(serialized_0);
185  auto reserialized = sketches[impl].Serialize();
186  CHECK(reserialized == serialized_0);
187  }
188  // Decode with limit set to the capacity, and compare results
189  decode_0.resize(capacity);
190  bool decodable_0 = sketches[0].Decode(decode_0);
191  std::sort(decode_0.begin(), decode_0.end());
192  for (size_t impl = 1; impl < sketches.size(); ++impl) {
193  decode_other.resize(capacity);
194  bool decodable_other = sketches[impl].Decode(decode_other);
195  CHECK(decodable_other == decodable_0);
196  std::sort(decode_other.begin(), decode_other.end());
197  CHECK(decode_other == decode_0);
198  }
199  // If the result is decodable, it should also be decodable with limit
200  // set to the actual number of elements, and not with one less.
201  if (decodable_0) {
202  for (auto& sketch : sketches) {
203  decode_temp.resize(decode_0.size());
204  bool decodable = sketch.Decode(decode_temp);
205  CHECK(decodable);
206  std::sort(decode_temp.begin(), decode_temp.end());
207  CHECK(decode_temp == decode_0);
208  if (!decode_0.empty()) {
209  decode_temp.resize(decode_0.size() - 1);
210  decodable = sketch.Decode(decode_temp);
211  CHECK(!decodable);
212  }
213  }
214  }
215  // If the actual number of elements is not higher than the capacity, the
216  // result should be decodable, and the result should match what we put in.
217  if (real_element_count <= capacity) {
218  CHECK(decodable_0);
219  CHECK(decode_0 == elements);
220  }
221  }
222 }
223 
224 void TestComputeFunctions() {
225  for (uint32_t bits = 0; bits <= 256; ++bits) {
226  for (uint32_t fpbits = 0; fpbits <= 512; ++fpbits) {
227  std::vector<size_t> table_max_elements(1025);
228  for (size_t capacity = 0; capacity <= 1024; ++capacity) {
229  table_max_elements[capacity] = minisketch_compute_max_elements(bits, capacity, fpbits);
230  // Exception for bits==0
231  if (bits == 0) CHECK(table_max_elements[capacity] == 0);
232  // A sketch with capacity N cannot guarantee decoding more than N elements.
233  CHECK(table_max_elements[capacity] <= capacity);
234  // When asking for N bits of false positive protection, either no solution exists, or no more than ceil(N / bits) excess capacity should be needed.
235  if (bits > 0) CHECK(table_max_elements[capacity] == 0 || capacity - table_max_elements[capacity] <= (fpbits + bits - 1) / bits);
236  // Increasing capacity by one, if there is a solution, should always increment the max_elements by at least one as well.
237  if (capacity > 0) CHECK(table_max_elements[capacity] == 0 || table_max_elements[capacity] > table_max_elements[capacity - 1]);
238  }
239 
240  std::vector<size_t> table_capacity(513);
241  for (size_t max_elements = 0; max_elements <= 512; ++max_elements) {
242  table_capacity[max_elements] = minisketch_compute_capacity(bits, max_elements, fpbits);
243  // Exception for bits==0
244  if (bits == 0) CHECK(table_capacity[max_elements] == 0);
245  // To be able to decode N elements, capacity needs to be at least N.
246  if (bits > 0) CHECK(table_capacity[max_elements] >= max_elements);
247  // A sketch of N bits in total cannot have more than N bits of false positive protection;
248  if (bits > 0) CHECK(bits * table_capacity[max_elements] >= fpbits);
249  // When asking for N bits of false positive protection, no more than ceil(N / bits) excess capacity should be needed.
250  if (bits > 0) CHECK(table_capacity[max_elements] - max_elements <= (fpbits + bits - 1) / bits);
251  // Increasing max_elements by one can only increment the capacity by 0 or 1.
252  if (max_elements > 0 && fpbits < 256) CHECK(table_capacity[max_elements] == table_capacity[max_elements - 1] || table_capacity[max_elements] == table_capacity[max_elements - 1] + 1);
253  // Check round-tripping max_elements->capacity->max_elements (only a lower bound)
254  CHECK(table_capacity[max_elements] <= 1024);
255  CHECK(table_max_elements[table_capacity[max_elements]] == 0 || table_max_elements[table_capacity[max_elements]] >= max_elements);
256  }
257 
258  for (size_t capacity = 0; capacity <= 512; ++capacity) {
259  // Check round-tripping capacity->max_elements->capacity (exact, if it exists)
260  CHECK(table_max_elements[capacity] <= 512);
261  CHECK(table_max_elements[capacity] == 0 || table_capacity[table_max_elements[capacity]] == capacity);
262  }
263  }
264  }
265 }
266 
267 } // namespace
268 
269 int main(int argc, char** argv) {
270  uint64_t test_complexity = 4;
271  if (argc > 1) {
272  size_t len = 0;
273  std::string arg{argv[1]};
274  try {
275  test_complexity = 0;
276  long long complexity = std::stoll(arg, &len);
277  if (complexity >= 1 && len == arg.size() && ((uint64_t)complexity <= std::numeric_limits<uint64_t>::max() >> 10)) {
278  test_complexity = complexity;
279  }
280  } catch (const std::logic_error&) {}
281  if (test_complexity == 0) {
282  fprintf(stderr, "Invalid complexity specified: '%s'\n", arg.c_str());
283  return 1;
284  }
285  }
286 
287 #ifdef MINISKETCH_VERIFY
288  const char* mode = " in verify mode";
289 #else
290  const char* mode = "";
291 #endif
292  printf("Running libminisketch tests%s with complexity=%llu\n", mode, (unsigned long long)test_complexity);
293 
294  TestComputeFunctions();
295 
296  for (unsigned j = 2; j <= 64; ++j) {
297  TestRandomized(j, 8, (test_complexity << 10) / j);
298  TestRandomized(j, 128, (test_complexity << 7) / j);
299  TestRandomized(j, 4096, test_complexity / j);
300  }
301 
302  // Test capacity==0 together with all field sizes, and then
303  // all combinations of bits and capacity up to a certain bits*capacity,
304  // depending on test_complexity.
305  for (int weight = 0; weight <= 40; ++weight) {
306  for (int bits = 2; weight == 0 ? bits <= 64 : (bits <= 32 && bits <= weight); ++bits) {
307  int capacity = weight / bits;
308  if (capacity * bits != weight) continue;
309  TestExhaustive(bits, capacity);
310  }
311  if (weight >= 16 && test_complexity >> (weight - 16) == 0) break;
312  }
313 
314  printf("All tests successful.\n");
315  return 0;
316 }
bech32::Decode
DecodeResult Decode(const std::string &str)
Decode a Bech32 or Bech32m string.
Definition: bech32.cpp:480
tinyformat::printf
void printf(const char *fmt, const Args &... args)
Format list of arguments to std::cout, according to the given format string.
Definition: tinyformat.h:1079
util.h
minisketch_compute_capacity
MINISKETCH_API size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits)
Compute the capacity needed to achieve a certain rate of false positives.
Definition: minisketch.cpp:482
CHECK
#define CHECK(cond)
Unconditional failure on condition failure.
Definition: util.h:35
main
int main(int argc, char **argv)
Definition: test.cpp:269
minisketch_compute_max_elements
MINISKETCH_API size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits)
Compute what max_elements can be decoded for a certain rate of false positives.
Definition: minisketch.cpp:486
ByteUnit::k
@ k