Fabcoin Core  0.16.2 P2P Digital Currency
equihash.cpp
Go to the documentation of this file.
1 // Copyright (c) 2016 Jack Grigg
2 // Copyright (c) 2016 The Zcash developers
3 // Distributed under the MIT software license, see the accompanying
5
6 // Implementation of the Equihash Proof-of-Work algorithm.
7 //
8 // Reference
9 // =========
10 // Alex Biryukov and Dmitry Khovratovich
11 // Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem
12 // NDSS ’16, 21-24 February 2016, San Diego, CA, USA
13 // https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf
14
15 #if defined(HAVE_CONFIG_H)
16 #include "config/fabcoin-config.h"
17 #endif
18
19 #include "crypto/equihash.h"
20 #ifndef NO_UTIL_LOG
21 #include "util.h"
22 #else
23 #define LogPrint(...)
24 #endif
25
26 #include <algorithm>
27 #include <iostream>
28 #include <stdexcept>
29
30 #include <boost/optional.hpp>
31
33
34 template<unsigned int N, unsigned int K>
36 {
37  uint32_t le_N = htole32(N);
38  uint32_t le_K = htole32(K);
39  unsigned char personalization[crypto_generichash_blake2b_PERSONALBYTES] = {};
40  if( (le_N == 200 && le_K == 9) || (le_N == 96 && le_K == 5) )
41  memcpy(personalization, "ZcashPoW", 8);
42  else
43  memcpy(personalization, "FABcoin_", 8);
44  memcpy(personalization+8, &le_N, 4);
45  memcpy(personalization+12, &le_K, 4);
46  return crypto_generichash_blake2b_init_salt_personal(&base_state,
47  NULL, 0, // No key.
48  HashOutput,
49  NULL, // No salt.
50  personalization);
51 }
52
53 void GenerateHash(const eh_HashState& base_state, eh_index g,
54  unsigned char* hash, size_t hLen)
55 {
56  eh_HashState state;
57  state = base_state;
58  eh_index lei = htole32(g);
59  crypto_generichash_blake2b_update(&state, (const unsigned char*) &lei,
60  sizeof(eh_index));
61  crypto_generichash_blake2b_final(&state, hash, hLen);
62 }
63
64 void ExpandArray(const unsigned char* in, size_t in_len,
65  unsigned char* out, size_t out_len,
66  size_t bit_len, size_t byte_pad)
67 {
68 // assert(bit_len >= 8);
69 // assert(8*sizeof(uint32_t) >= 7+bit_len);
70
71  size_t out_width { (bit_len+7)/8 + byte_pad };
72
73 // assert(out_len == 8*out_width*in_len/bit_len);
74
75  uint32_t bit_len_mask { ((uint32_t)1 << bit_len) - 1 };
76
77  // The acc_bits least-significant bits of acc_value represent a bit sequence
78  // in big-endian order.
79  size_t acc_bits = 0;
80  uint32_t acc_value = 0;
81
82  size_t j = 0;
83  for (size_t i = 0; i < in_len; i++) {
84  acc_value = (acc_value << 8) | in[i];
85  acc_bits += 8;
86
87  // When we have bit_len or more bits in the accumulator, write the next
88  // output element.
89  if (acc_bits >= bit_len) {
90  acc_bits -= bit_len;
91  for (size_t x = 0; x < byte_pad; x++) {
92  out[j+x] = 0;
93  }
94  for (size_t x = byte_pad; x < out_width; x++) {
95  out[j+x] = (
96  // Big-endian
97  acc_value >> (acc_bits+(8*(out_width-x-1)))
98  ) & (
99  // Apply bit_len_mask across byte boundaries
100  (bit_len_mask >> (8*(out_width-x-1))) & 0xFF
101  );
102  }
103  j += out_width;
104  }
105  }
106 }
107
108 void CompressArray(const unsigned char* in, size_t in_len,
109  unsigned char* out, size_t out_len,
110  size_t bit_len, size_t byte_pad)
111 {
112  assert(bit_len >= 8);
113  assert(8*sizeof(uint32_t) >= 7+bit_len);
114
115  size_t in_width { (bit_len+7)/8 + byte_pad };
116  assert(out_len == bit_len*in_len/(8*in_width));
117
118  uint32_t bit_len_mask { ((uint32_t)1 << bit_len) - 1 };
119
120  // The acc_bits least-significant bits of acc_value represent a bit sequence
121  // in big-endian order.
122  size_t acc_bits = 0;
123  uint32_t acc_value = 0;
124
125  size_t j = 0;
126  for (size_t i = 0; i < out_len; i++) {
127  // When we have fewer than 8 bits left in the accumulator, read the next
128  // input element.
129  if (acc_bits < 8) {
130  acc_value = acc_value << bit_len;
131  for (size_t x = byte_pad; x < in_width; x++) {
132  acc_value = acc_value | (
133  (
134  // Apply bit_len_mask across byte boundaries
135  in[j+x] & ((bit_len_mask >> (8*(in_width-x-1))) & 0xFF)
136  ) << (8*(in_width-x-1))); // Big-endian
137  }
138  j += in_width;
139  acc_bits += bit_len;
140  }
141
142  acc_bits -= 8;
143  out[i] = (acc_value >> acc_bits) & 0xFF;
144  }
145 }
146
147 // Big-endian so that lexicographic array comparison is equivalent to integer
148 // comparison
149 void EhIndexToArray(const eh_index i, unsigned char* array)
150 {
151  BOOST_STATIC_ASSERT(sizeof(eh_index) == 4);
152  eh_index bei = htobe32(i);
153  memcpy(array, &bei, sizeof(eh_index));
154 }
155
156 // Big-endian so that lexicographic array comparison is equivalent to integer
157 // comparison
158 eh_index ArrayToEhIndex(const unsigned char* array)
159 {
160  BOOST_STATIC_ASSERT(sizeof(eh_index) == 4);
161  eh_index bei;
162  memcpy(&bei, array, sizeof(eh_index));
163  return be32toh(bei);
164 }
165
166 eh_trunc TruncateIndex(const eh_index i, const unsigned int ilen)
167 {
168  // Truncate to 8 bits
169  BOOST_STATIC_ASSERT(sizeof(eh_trunc) == 1);
170  return (i >> (ilen - 8)) & 0xff;
171 }
172
173 eh_index UntruncateIndex(const eh_trunc t, const eh_index r, const unsigned int ilen)
174 {
175  eh_index i{t};
176  return (i << (ilen - 8)) | r;
177 }
178
179 std::vector<eh_index> GetIndicesFromMinimal(std::vector<unsigned char> minimal,
180  size_t cBitLen)
181 {
182  assert(((cBitLen+1)+7)/8 <= sizeof(eh_index));
183  size_t lenIndices { 8*sizeof(eh_index)*minimal.size()/(cBitLen+1) };
184  size_t bytePad { sizeof(eh_index) - ((cBitLen+1)+7)/8 };
185  std::vector<unsigned char> array(lenIndices);
186  ExpandArray(minimal.data(), minimal.size(),
187  array.data(), lenIndices, cBitLen+1, bytePad);
188  std::vector<eh_index> ret;
189  for (size_t i = 0; i < lenIndices; i += sizeof(eh_index)) {
190  ret.push_back(ArrayToEhIndex(array.data()+i));
191  }
192  return ret;
193 }
194
195 std::vector<unsigned char> GetMinimalFromIndices(std::vector<eh_index> indices,
196  size_t cBitLen)
197 {
198  assert(((cBitLen+1)+7)/8 <= sizeof(eh_index));
199  size_t lenIndices { indices.size()*sizeof(eh_index) };
200  size_t minLen { (cBitLen+1)*lenIndices/(8*sizeof(eh_index)) };
201  size_t bytePad { sizeof(eh_index) - ((cBitLen+1)+7)/8 };
202  std::vector<unsigned char> array(lenIndices);
203  for (size_t i = 0; i < indices.size(); i++) {
204  EhIndexToArray(indices[i], array.data()+(i*sizeof(eh_index)));
205  }
206  std::vector<unsigned char> ret(minLen);
207  CompressArray(array.data(), lenIndices,
208  ret.data(), minLen, cBitLen+1, bytePad);
209  return ret;
210 }
211
212 template<size_t WIDTH>
213 StepRow<WIDTH>::StepRow(const unsigned char* hashIn, size_t hInLen,
214  size_t hLen, size_t cBitLen)
215 {
216  assert(hLen <= WIDTH);
217  ExpandArray(hashIn, hInLen, hash, hLen, cBitLen);
218 }
219
220 template<size_t WIDTH> template<size_t W>
222 {
223  BOOST_STATIC_ASSERT(W <= WIDTH);
224  std::copy(a.hash, a.hash+W, hash);
225 }
226
227 template<size_t WIDTH>
228 FullStepRow<WIDTH>::FullStepRow(const unsigned char* hashIn, size_t hInLen,
229  size_t hLen, size_t cBitLen, eh_index i) :
230  StepRow<WIDTH> {hashIn, hInLen, hLen, cBitLen}
231 {
232  EhIndexToArray(i, hash+hLen);
233 }
234
235 template<size_t WIDTH> template<size_t W>
236 FullStepRow<WIDTH>::FullStepRow(const FullStepRow<W>& a, const FullStepRow<W>& b, size_t len, size_t lenIndices, size_t trim) :
237  StepRow<WIDTH> {a}
238 {
239  assert(len+lenIndices <= W);
240  assert(len-trim+(2*lenIndices) <= WIDTH);
241  for (size_t i = trim; i < len; i++)
242  hash[i-trim] = a.hash[i] ^ b.hash[i];
243  if (a.IndicesBefore(b, len, lenIndices)) {
244  std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim);
245  std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim+lenIndices);
246  } else {
247  std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim);
248  std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim+lenIndices);
249  }
250 }
251
252 template<size_t WIDTH>
254 {
255  std::copy(a.hash, a.hash+WIDTH, hash);
256  return *this;
257 }
258
259 template<size_t WIDTH>
260 bool StepRow<WIDTH>::IsZero(size_t len)
261 {
262  // This doesn't need to be constant time.
263  for (size_t i = 0; i < len; i++) {
264  if (hash[i] != 0)
265  return false;
266  }
267  return true;
268 }
269
270 template<size_t WIDTH>
271 std::vector<unsigned char> FullStepRow<WIDTH>::GetIndices(size_t len, size_t lenIndices,
272  size_t cBitLen) const
273 {
274  assert(((cBitLen+1)+7)/8 <= sizeof(eh_index));
275  size_t minLen { (cBitLen+1)*lenIndices/(8*sizeof(eh_index)) };
276  size_t bytePad { sizeof(eh_index) - ((cBitLen+1)+7)/8 };
277  std::vector<unsigned char> ret(minLen);
278  CompressArray(hash+len, lenIndices, ret.data(), minLen, cBitLen+1, bytePad);
279  return ret;
280 }
281
282 template<size_t WIDTH>
284 {
285  // This doesn't need to be constant time.
286  for (size_t j = 0; j < l; j++) {
287  if (a.hash[j] != b.hash[j])
288  return false;
289  }
290  return true;
291 }
292
293 template<size_t WIDTH>
294 TruncatedStepRow<WIDTH>::TruncatedStepRow(const unsigned char* hashIn, size_t hInLen,
295  size_t hLen, size_t cBitLen,
296  eh_index i, unsigned int ilen) :
297  StepRow<WIDTH> {hashIn, hInLen, hLen, cBitLen}
298 {
299  hash[hLen] = TruncateIndex(i, ilen);
300 }
301
302 template<size_t WIDTH> template<size_t W>
303 TruncatedStepRow<WIDTH>::TruncatedStepRow(const TruncatedStepRow<W>& a, const TruncatedStepRow<W>& b, size_t len, size_t lenIndices, size_t trim) :
304  StepRow<WIDTH> {a}
305 {
306  assert(len+lenIndices <= W);
307  assert(len-trim+(2*lenIndices) <= WIDTH);
308  for (size_t i = trim; i < len; i++)
309  hash[i-trim] = a.hash[i] ^ b.hash[i];
310  if (a.IndicesBefore(b, len, lenIndices)) {
311  std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim);
312  std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim+lenIndices);
313  } else {
314  std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim);
315  std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim+lenIndices);
316  }
317 }
318
319 template<size_t WIDTH>
321 {
322  std::copy(a.hash, a.hash+WIDTH, hash);
323  return *this;
324 }
325
326 template<size_t WIDTH>
327 std::shared_ptr<eh_trunc> TruncatedStepRow<WIDTH>::GetTruncatedIndices(size_t len, size_t lenIndices) const
328 {
329  std::shared_ptr<eh_trunc> p (new eh_trunc[lenIndices], std::default_delete<eh_trunc[]>());
330  std::copy(hash+len, hash+len+lenIndices, p.get());
331  return p;
332 }
333
334 template<unsigned int N, unsigned int K>
336  const std::function<bool(std::vector<unsigned char>)> validBlock,
337  const std::function<bool(EhSolverCancelCheck)> cancelled)
338 {
339  eh_index init_size { 1 << (CollisionBitLength + 1) };
340
341  // 1) Generate first list
342  //LogPrint(BCLog::POW, "Generating first list\n");
343  size_t hashLen = HashLength;
344  size_t lenIndices = sizeof(eh_index);
345  std::vector<FullStepRow<FullWidth>> X;
346  X.reserve(init_size);
347  unsigned char tmpHash[HashOutput];
348  for (eh_index g = 0; X.size() < init_size; g++) {
349  GenerateHash(base_state, g, tmpHash, HashOutput);
350  for (eh_index i = 0; i < IndicesPerHashOutput && X.size() < init_size; i++) {
351  X.emplace_back(tmpHash+(i*N/8), N/8, HashLength,
352  CollisionBitLength, (g*IndicesPerHashOutput)+i);
353  }
354  if (cancelled(ListGeneration)) throw solver_cancelled;
355  }
356
357  // 3) Repeat step 2 until 2n/(k+1) bits remain
358  for (unsigned int r = 1; r < K && X.size() > 0; r++) {
359  //LogPrint(BCLog::POW, "Round %u:\n", r);
360  // 2a) Sort the list
361  //LogPrint(BCLog::POW, "- Sorting list\n");
362  std::sort(X.begin(), X.end(), CompareSR(CollisionByteLength));
363  if (cancelled(ListSorting)) throw solver_cancelled;
364
365  //LogPrint(BCLog::POW, "- Finding collisions\n");
366  size_t i = 0;
367  size_t posFree = 0;
368  std::vector<FullStepRow<FullWidth>> Xc;
369  while (i < X.size() - 1) {
370  // 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
371  size_t j = 1;
372  while (i+j < X.size() &&
373  HasCollision(X[i], X[i+j], CollisionByteLength)) {
374  j++;
375  }
376
377  // 2c) Calculate tuples (X_i ^ X_j, (i, j))
378  for (size_t l = 0; l < j - 1; l++) {
379  for (size_t m = l + 1; m < j; m++) {
380  if (DistinctIndices(X[i+l], X[i+m], hashLen, lenIndices)) {
381  Xc.emplace_back(X[i+l], X[i+m], hashLen, lenIndices, CollisionByteLength);
382  }
383  }
384  }
385
386  // 2d) Store tuples on the table in-place if possible
387  while (posFree < i+j && Xc.size() > 0) {
388  X[posFree++] = Xc.back();
389  Xc.pop_back();
390  }
391
392  i += j;
393  if (cancelled(ListColliding)) throw solver_cancelled;
394  }
395
396  // 2e) Handle edge case where final table entry has no collision
397  while (posFree < X.size() && Xc.size() > 0) {
398  X[posFree++] = Xc.back();
399  Xc.pop_back();
400  }
401
402  if (Xc.size() > 0) {
403  // 2f) Add overflow to end of table
404  X.insert(X.end(), Xc.begin(), Xc.end());
405  } else if (posFree < X.size()) {
406  // 2g) Remove empty space at the end
407  X.erase(X.begin()+posFree, X.end());
408  X.shrink_to_fit();
409  }
410
411  hashLen -= CollisionByteLength;
412  lenIndices *= 2;
413  if (cancelled(RoundEnd)) throw solver_cancelled;
414  }
415
416  // k+1) Find a collision on last 2n(k+1) bits
417  //LogPrint(BCLog::POW, "Final round:\n");
418  if (X.size() > 1) {
419  //LogPrint(BCLog::POW, "- Sorting list\n");
420  std::sort(X.begin(), X.end(), CompareSR(hashLen));
421  if (cancelled(FinalSorting)) throw solver_cancelled;
422  //LogPrint(BCLog::POW, "- Finding collisions\n");
423  size_t i = 0;
424  while (i < X.size() - 1) {
425  size_t j = 1;
426  while (i+j < X.size() &&
427  HasCollision(X[i], X[i+j], hashLen)) {
428  j++;
429  }
430
431  for (size_t l = 0; l < j - 1; l++) {
432  for (size_t m = l + 1; m < j; m++) {
433  FullStepRow<FinalFullWidth> res(X[i+l], X[i+m], hashLen, lenIndices, 0);
434  if (DistinctIndices(X[i+l], X[i+m], hashLen, lenIndices)) {
435  auto soln = res.GetIndices(hashLen, 2*lenIndices, CollisionBitLength);
436  assert(soln.size() == equihash_solution_size(N, K));
437  if (validBlock(soln)) {
438  return true;
439  }
440  }
441  }
442  }
443
444  i += j;
445  if (cancelled(FinalColliding)) throw solver_cancelled;
446  }
447  } else{
448  LogPrint(BCLog::POW, "- List is empty\n");
449  }
450
451  return false;
452 }
453
454 template<size_t WIDTH>
455 void CollideBranches(std::vector<FullStepRow<WIDTH>>& X, const size_t hlen, const size_t lenIndices, const unsigned int clen, const unsigned int ilen, const eh_trunc lt, const eh_trunc rt)
456 {
457  size_t i = 0;
458  size_t posFree = 0;
459  std::vector<FullStepRow<WIDTH>> Xc;
460  while (i < X.size() - 1) {
461  // 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
462  size_t j = 1;
463  while (i+j < X.size() &&
464  HasCollision(X[i], X[i+j], clen)) {
465  j++;
466  }
467
468  // 2c) Calculate tuples (X_i ^ X_j, (i, j))
469  for (size_t l = 0; l < j - 1; l++) {
470  for (size_t m = l + 1; m < j; m++) {
471  if (DistinctIndices(X[i+l], X[i+m], hlen, lenIndices)) {
472  if (IsValidBranch(X[i+l], hlen, ilen, lt) && IsValidBranch(X[i+m], hlen, ilen, rt)) {
473  Xc.emplace_back(X[i+l], X[i+m], hlen, lenIndices, clen);
474  } else if (IsValidBranch(X[i+m], hlen, ilen, lt) && IsValidBranch(X[i+l], hlen, ilen, rt)) {
475  Xc.emplace_back(X[i+m], X[i+l], hlen, lenIndices, clen);
476  }
477  }
478  }
479  }
480
481  // 2d) Store tuples on the table in-place if possible
482  while (posFree < i+j && Xc.size() > 0) {
483  X[posFree++] = Xc.back();
484  Xc.pop_back();
485  }
486
487  i += j;
488  }
489
490  // 2e) Handle edge case where final table entry has no collision
491  while (posFree < X.size() && Xc.size() > 0) {
492  X[posFree++] = Xc.back();
493  Xc.pop_back();
494  }
495
496  if (Xc.size() > 0) {
497  // 2f) Add overflow to end of table
498  X.insert(X.end(), Xc.begin(), Xc.end());
499  } else if (posFree < X.size()) {
500  // 2g) Remove empty space at the end
501  X.erase(X.begin()+posFree, X.end());
502  X.shrink_to_fit();
503  }
504 }
505
506 template<unsigned int N, unsigned int K>
508  const std::function<bool(std::vector<unsigned char>)> validBlock,
509  const std::function<bool(EhSolverCancelCheck)> cancelled)
510 {
511  eh_index init_size { 1 << (CollisionBitLength + 1) };
512  eh_index recreate_size { UntruncateIndex(1, 0, CollisionBitLength + 1) };
513
514  // First run the algorithm with truncated indices
515
516  const eh_index soln_size { 1 << K };
517  std::vector<std::shared_ptr<eh_trunc>> partialSolns;
518  size_t invalidCount = 0;
519  {
520
521  // 1) Generate first list
522  //LogPrint(BCLog::POW, "Generating first list\n");
523  size_t hashLen = HashLength;
524  size_t lenIndices = sizeof(eh_trunc);
525  std::vector<TruncatedStepRow<TruncatedWidth>> Xt;
526  Xt.reserve(init_size);
527  unsigned char tmpHash[HashOutput];
528  for (eh_index g = 0; Xt.size() < init_size; g++) {
529  GenerateHash(base_state, g, tmpHash, HashOutput);
530  for (eh_index i = 0; i < IndicesPerHashOutput && Xt.size() < init_size; i++) {
531  Xt.emplace_back(tmpHash+(i*N/8), N/8, HashLength, CollisionBitLength,
532  (g*IndicesPerHashOutput)+i, CollisionBitLength + 1);
533  }
534  if (cancelled(ListGeneration)) throw solver_cancelled;
535  }
536
537  // 3) Repeat step 2 until 2n/(k+1) bits remain
538  for (size_t r = 1; r < K && Xt.size() > 0; r++) {
539  //LogPrint(BCLog::POW, "Round %zu:\n", r);
540  // 2a) Sort the list
541  //LogPrint(BCLog::POW, "- Sorting list\n");
542  std::sort(Xt.begin(), Xt.end(), CompareSR(CollisionByteLength));
543  if (cancelled(ListSorting)) throw solver_cancelled;
544
545  //LogPrint(BCLog::POW, "- Finding collisions\n");
546  size_t i = 0;
547  size_t posFree = 0;
548  std::vector<TruncatedStepRow<TruncatedWidth>> Xc;
549  while (i < Xt.size() - 1) {
550  // 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
551  size_t j = 1;
552  while (i+j < Xt.size() &&
553  HasCollision(Xt[i], Xt[i+j], CollisionByteLength)) {
554  j++;
555  }
556
557  // 2c) Calculate tuples (X_i ^ X_j, (i, j))
558  //bool checking_for_zero = (i == 0 && Xt[0].IsZero(hashLen));
559  for (size_t l = 0; l < j - 1; l++) {
560  for (size_t m = l + 1; m < j; m++) {
561  // We truncated, so don't check for distinct indices here
562  TruncatedStepRow<TruncatedWidth> Xi {Xt[i+l], Xt[i+m],
563  hashLen, lenIndices,
564  CollisionByteLength};
565  if (!(Xi.IsZero(hashLen-CollisionByteLength) &&
566  IsProbablyDuplicate<soln_size>(Xi.GetTruncatedIndices(hashLen-CollisionByteLength, 2*lenIndices),
567  2*lenIndices))) {
568  Xc.emplace_back(Xi);
569  }
570  }
571  }
572
573  // 2d) Store tuples on the table in-place if possible
574  while (posFree < i+j && Xc.size() > 0) {
575  Xt[posFree++] = Xc.back();
576  Xc.pop_back();
577  }
578
579  i += j;
580  if (cancelled(ListColliding)) throw solver_cancelled;
581  }
582
583  // 2e) Handle edge case where final table entry has no collision
584  while (posFree < Xt.size() && Xc.size() > 0) {
585  Xt[posFree++] = Xc.back();
586  Xc.pop_back();
587  }
588
589  if (Xc.size() > 0) {
590  // 2f) Add overflow to end of table
591  Xt.insert(Xt.end(), Xc.begin(), Xc.end());
592  } else if (posFree < Xt.size()) {
593  // 2g) Remove empty space at the end
594  Xt.erase(Xt.begin()+posFree, Xt.end());
595  Xt.shrink_to_fit();
596  }
597
598  hashLen -= CollisionByteLength;
599  lenIndices *= 2;
600  if (cancelled(RoundEnd)) throw solver_cancelled;
601  }
602
603  // k+1) Find a collision on last 2n(k+1) bits
604  //LogPrint(BCLog::POW, "Final round:\n");
605  if (Xt.size() > 1) {
606  //LogPrint(BCLog::POW, "- Sorting list\n");
607  std::sort(Xt.begin(), Xt.end(), CompareSR(hashLen));
608  if (cancelled(FinalSorting)) throw solver_cancelled;
609  //LogPrint(BCLog::POW, "- Finding collisions\n");
610  size_t i = 0;
611  while (i < Xt.size() - 1) {
612  size_t j = 1;
613  while (i+j < Xt.size() &&
614  HasCollision(Xt[i], Xt[i+j], hashLen)) {
615  j++;
616  }
617
618  for (size_t l = 0; l < j - 1; l++) {
619  for (size_t m = l + 1; m < j; m++) {
620  TruncatedStepRow<FinalTruncatedWidth> res(Xt[i+l], Xt[i+m],
621  hashLen, lenIndices, 0);
622  auto soln = res.GetTruncatedIndices(hashLen, 2*lenIndices);
623  if (!IsProbablyDuplicate<soln_size>(soln, 2*lenIndices)) {
624  partialSolns.push_back(soln);
625  }
626  }
627  }
628
629  i += j;
630  if (cancelled(FinalColliding)) throw solver_cancelled;
631  }
632  } else{
633  LogPrint(BCLog::POW, "- List is empty\n");
634  }
635
636
637  } // Ensure Xt goes out of scope and is destroyed
638
639  //LogPrint(BCLog::POW, "Found %d partial solutions\n", partialSolns.size());
640
641  // Now for each solution run the algorithm again to recreate the indices
642  //LogPrint(BCLog::POW, "Culling solutions\n");
643  for (std::shared_ptr<eh_trunc> partialSoln : partialSolns) {
644  std::set<std::vector<unsigned char>> solns;
645  size_t hashLen;
646  size_t lenIndices;
647  unsigned char tmpHash[HashOutput];
648  std::vector<boost::optional<std::vector<FullStepRow<FinalFullWidth>>>> X;
649  X.reserve(K+1);
650
651  // 3) Repeat steps 1 and 2 for each partial index
652  for (eh_index i = 0; i < soln_size; i++) {
653  // 1) Generate first list of possibilities
654  std::vector<FullStepRow<FinalFullWidth>> icv;
655  icv.reserve(recreate_size);
656  for (eh_index j = 0; j < recreate_size; j++) {
657  eh_index newIndex { UntruncateIndex(partialSoln.get()[i], j, CollisionBitLength + 1) };
658  if (j == 0 || newIndex % IndicesPerHashOutput == 0) {
659  GenerateHash(base_state, newIndex/IndicesPerHashOutput,
660  tmpHash, HashOutput);
661  }
662  icv.emplace_back(tmpHash+((newIndex % IndicesPerHashOutput) * N/8),
663  N/8, HashLength, CollisionBitLength, newIndex);
664  if (cancelled(PartialGeneration)) throw solver_cancelled;
665  }
666  boost::optional<std::vector<FullStepRow<FinalFullWidth>>> ic = icv;
667
668  // 2a) For each pair of lists:
669  hashLen = HashLength;
670  lenIndices = sizeof(eh_index);
671  size_t rti = i;
672  for (size_t r = 0; r <= K; r++) {
673  // 2b) Until we are at the top of a subtree:
674  if (r < X.size()) {
675  if (X[r]) {
676  // 2c) Merge the lists
677  ic->reserve(ic->size() + X[r]->size());
678  ic->insert(ic->end(), X[r]->begin(), X[r]->end());
679  std::sort(ic->begin(), ic->end(), CompareSR(hashLen));
680  if (cancelled(PartialSorting)) throw solver_cancelled;
681  size_t lti = rti-(1<<r);
682  CollideBranches(*ic, hashLen, lenIndices,
683  CollisionByteLength,
684  CollisionBitLength + 1,
685  partialSoln.get()[lti], partialSoln.get()[rti]);
686
687  // 2d) Check if this has become an invalid solution
688  if (ic->size() == 0)
689  goto invalidsolution;
690
691  X[r] = boost::none;
692  hashLen -= CollisionByteLength;
693  lenIndices *= 2;
694  rti = lti;
695  } else {
696  X[r] = *ic;
697  break;
698  }
699  } else {
700  X.push_back(ic);
701  break;
702  }
703  if (cancelled(PartialSubtreeEnd)) throw solver_cancelled;
704  }
705  if (cancelled(PartialIndexEnd)) throw solver_cancelled;
706  }
707
708  // We are at the top of the tree
709  assert(X.size() == K+1);
710  for (FullStepRow<FinalFullWidth> row : *X[K]) {
711  auto soln = row.GetIndices(hashLen, lenIndices, CollisionBitLength);
712  assert(soln.size() == equihash_solution_size(N, K));
713  solns.insert(soln);
714  }
715  for (auto soln : solns) {
716  if (validBlock(soln))
717  return true;
718  }
719  if (cancelled(PartialEnd)) throw solver_cancelled;
720  continue;
721
722 invalidsolution:
723  invalidCount++;
724  }
725  //LogPrint(BCLog::POW, "- Number of invalid solutions found: %zu\n", invalidCount);
726
727  return false;
728 }
729
730 template<unsigned int N, unsigned int K>
731 bool Equihash<N,K>::IsValidSolution(const eh_HashState& base_state, std::vector<unsigned char> soln)
732 {
733  if (soln.size() != SolutionWidth) {
734  LogPrint(BCLog::POW, "Invalid solution length: %d (expected %d)\n",
735  soln.size(), SolutionWidth);
736  return false;
737  }
738
739  std::vector<FullStepRow<FinalFullWidth>> X;
740  X.reserve(1 << K);
741  unsigned char tmpHash[HashOutput] = {};
742  for (eh_index i : GetIndicesFromMinimal(soln, CollisionBitLength)) {
743  GenerateHash(base_state, i/IndicesPerHashOutput, tmpHash, HashOutput);
744  X.emplace_back(tmpHash+((i % IndicesPerHashOutput) * HashLen),
745  HashLen, HashLength, CollisionBitLength, i);
746  }
747
748  size_t hashLen = HashLength;
749  size_t lenIndices = sizeof(eh_index);
750  while (X.size() > 1) {
751  std::vector<FullStepRow<FinalFullWidth>> Xc;
752  for (size_t i = 0; i < X.size(); i += 2) {
753  if (!HasCollision(X[i], X[i+1], CollisionByteLength)) {
754  LogPrint(BCLog::POW, "Invalid solution: invalid collision length between StepRows\n");
755  LogPrint(BCLog::POW, "X[i] = %s\n", X[i].GetHex(hashLen));
756  LogPrint(BCLog::POW, "X[i+1] = %s\n", X[i+1].GetHex(hashLen));
757  return false;
758  }
759  if (X[i+1].IndicesBefore(X[i], hashLen, lenIndices)) {
760  LogPrint(BCLog::POW, "Invalid solution: Index tree incorrectly ordered\n");
761  return false;
762  }
763  if (!DistinctIndices(X[i], X[i+1], hashLen, lenIndices)) {
764  LogPrint(BCLog::POW, "Invalid solution: duplicate indices\n");
765  return false;
766  }
767  Xc.emplace_back(X[i], X[i+1], hashLen, lenIndices, CollisionByteLength);
768  }
769  X = Xc;
770  hashLen -= CollisionByteLength;
771  lenIndices *= 2;
772  }
773
774  assert(X.size() == 1);
775  return X[0].IsZero(hashLen);
776 }
777
778 // Explicit instantiations for Equihash<96,3>
779 template int Equihash<96,3>::InitialiseState(eh_HashState& base_state);
780 template bool Equihash<96,3>::BasicSolve(const eh_HashState& base_state,
781  const std::function<bool(std::vector<unsigned char>)> validBlock,
782  const std::function<bool(EhSolverCancelCheck)> cancelled);
783 template bool Equihash<96,3>::OptimisedSolve(const eh_HashState& base_state,
784  const std::function<bool(std::vector<unsigned char>)> validBlock,
785  const std::function<bool(EhSolverCancelCheck)> cancelled);
786 template bool Equihash<96,3>::IsValidSolution(const eh_HashState& base_state, std::vector<unsigned char> soln);
787
788 // Explicit instantiations for Equihash<200,9>
789 template int Equihash<200,9>::InitialiseState(eh_HashState& base_state);
790 template bool Equihash<200,9>::BasicSolve(const eh_HashState& base_state,
791  const std::function<bool(std::vector<unsigned char>)> validBlock,
792  const std::function<bool(EhSolverCancelCheck)> cancelled);
793 template bool Equihash<200,9>::OptimisedSolve(const eh_HashState& base_state,
794  const std::function<bool(std::vector<unsigned char>)> validBlock,
795  const std::function<bool(EhSolverCancelCheck)> cancelled);
796 template bool Equihash<200,9>::IsValidSolution(const eh_HashState& base_state, std::vector<unsigned char> soln);
797
798 // Explicit instantiations for Equihash<96,5>
799 template int Equihash<96,5>::InitialiseState(eh_HashState& base_state);
800 template bool Equihash<96,5>::BasicSolve(const eh_HashState& base_state,
801  const std::function<bool(std::vector<unsigned char>)> validBlock,
802  const std::function<bool(EhSolverCancelCheck)> cancelled);
803 template bool Equihash<96,5>::OptimisedSolve(const eh_HashState& base_state,
804  const std::function<bool(std::vector<unsigned char>)> validBlock,
805  const std::function<bool(EhSolverCancelCheck)> cancelled);
806 template bool Equihash<96,5>::IsValidSolution(const eh_HashState& base_state, std::vector<unsigned char> soln);
807
808 // Explicit instantiations for Equihash<48,5>
809 template int Equihash<48,5>::InitialiseState(eh_HashState& base_state);
810 template bool Equihash<48,5>::BasicSolve(const eh_HashState& base_state,
811  const std::function<bool(std::vector<unsigned char>)> validBlock,
812  const std::function<bool(EhSolverCancelCheck)> cancelled);
813 template bool Equihash<48,5>::OptimisedSolve(const eh_HashState& base_state,
814  const std::function<bool(std::vector<unsigned char>)> validBlock,
815  const std::function<bool(EhSolverCancelCheck)> cancelled);
816 template bool Equihash<48,5>::IsValidSolution(const eh_HashState& base_state, std::vector<unsigned char> soln);
817
818 // Explicit instantiations for Equihash<184,7>
819 template int Equihash<184,7>::InitialiseState(eh_HashState& base_state);
820 template bool Equihash<184,7>::BasicSolve(const eh_HashState& base_state,
821  const std::function<bool(std::vector<unsigned char>)> validBlock,
822  const std::function<bool(EhSolverCancelCheck)> cancelled);
823 template bool Equihash<184,7>::OptimisedSolve(const eh_HashState& base_state,
824  const std::function<bool(std::vector<unsigned char>)> validBlock,
825  const std::function<bool(EhSolverCancelCheck)> cancelled);
826 template bool Equihash<184,7>::IsValidSolution(const eh_HashState& base_state, std::vector<unsigned char> soln);
827
uint32_t htobe32(uint32_t host_32bits)
Definition: endian.h:139
#define function(a, b, c, d, k, s)
std::vector< unsigned char > GetIndices(size_t len, size_t lenIndices, size_t cBitLen) const
Definition: equihash.cpp:271
friend class StepRow
Definition: equihash.h:47
bool IsValidSolution(const eh_HashState &base_state, std::vector< unsigned char > soln)
Definition: equihash.cpp:731
std::vector< unsigned char > GetMinimalFromIndices(std::vector< eh_index > indices, size_t cBitLen)
Definition: equihash.cpp:195
constexpr size_t equihash_solution_size(unsigned int N, unsigned int K)
Definition: equihash.h:159
friend class FullStepRow
Definition: equihash.h:87
#define g(i)
Definition: sha.cpp:735
assert(len-trim+(2 *lenIndices)<=WIDTH)
friend class CompareSR
Definition: equihash.h:48
void CompressArray(const unsigned char *in, size_t in_len, unsigned char *out, size_t out_len, size_t bit_len, size_t byte_pad)
Definition: equihash.cpp:108
if(a.IndicesBefore(b, len, lenIndices))
Definition: equihash.cpp:243
TruncatedStepRow & operator=(const TruncatedStepRow< WIDTH > &a)
Definition: equihash.cpp:320
friend class TruncatedStepRow
Definition: equihash.h:116
eh_trunc TruncateIndex(const eh_index i, const unsigned int ilen)
Definition: equihash.cpp:166
void EhIndexToArray(const eh_index i, unsigned char *array)
Definition: equihash.cpp:149
#define a(i)
#define x(i)
eh_index ArrayToEhIndex(const unsigned char *array)
Definition: equihash.cpp:158
void GenerateHash(const eh_HashState &base_state, eh_index g, unsigned char *hash, size_t hLen)
Definition: equihash.cpp:53
FullStepRow & operator=(const FullStepRow< WIDTH > &a)
Definition: equihash.cpp:253
bool IndicesBefore(const TruncatedStepRow< WIDTH > &a, size_t len, size_t lenIndices) const
Definition: equihash.h:131
std::string GetHex(size_t len)
Definition: equihash.h:62
void ExpandArray(const unsigned char *in, size_t in_len, unsigned char *out, size_t out_len, size_t bit_len, size_t byte_pad)
Definition: equihash.cpp:64
std::shared_ptr< eh_trunc > GetTruncatedIndices(size_t len, size_t lenIndices) const
Definition: equihash.cpp:327
int InitialiseState(eh_HashState &base_state)
Definition: equihash.cpp:35
bool BasicSolve(const eh_HashState &base_state, const std::function< bool(std::vector< unsigned char >)> validBlock, const std::function< bool(EhSolverCancelCheck)> cancelled)
Definition: equihash.cpp:335
std::vector< eh_index > GetIndicesFromMinimal(std::vector< unsigned char > minimal, size_t cBitLen)
Definition: equihash.cpp:179
#define b(i, j)
#define LogPrint(category,...)
Definition: util.h:164
#define X(name)
Definition: net.cpp:642
crypto_generichash_blake2b_state eh_HashState
Definition: equihash.h:24
unsigned char hash[WIDTH]
Definition: equihash.h:51
uint8_t eh_trunc
Definition: equihash.h:26
void * memcpy(void *a, const void *b, size_t c)
friend bool HasCollision(StepRow< W > &a, StepRow< W > &b, size_t l)
EhSolverCancelCheck
Definition: equihash.h:135
bool OptimisedSolve(const eh_HashState &base_state, const std::function< bool(std::vector< unsigned char >)> validBlock, const std::function< bool(EhSolverCancelCheck)> cancelled)
Definition: equihash.cpp:507
bool IsZero(size_t len)
Definition: equihash.cpp:260
uint32_t htole32(uint32_t host_32bits)
Definition: endian.h:146
EhSolverCancelledException solver_cancelled
Definition: equihash.cpp:32
uint32_t eh_index
Definition: equihash.h:25
void CollideBranches(std::vector< FullStepRow< WIDTH >> &X, const size_t hlen, const size_t lenIndices, const unsigned int clen, const unsigned int ilen, const eh_trunc lt, const eh_trunc rt)
Definition: equihash.cpp:455
eh_index UntruncateIndex(const eh_trunc t, const eh_index r, const unsigned int ilen)
Definition: equihash.cpp:173
uint32_t be32toh(uint32_t big_endian_32bits)
Definition: endian.h:153