Bitcoin ABC  0.26.3
P2P Digital Currency
muhash.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017-2020 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <crypto/muhash.h>
6 
7 #include <crypto/chacha20.h>
8 #include <crypto/common.h>
9 #include <hash.h>
10 
11 #include <cassert>
12 #include <cstdio>
13 #include <limits>
14 
15 namespace {
16 
17 using limb_t = Num3072::limb_t;
18 using double_limb_t = Num3072::double_limb_t;
19 constexpr int LIMB_SIZE = Num3072::LIMB_SIZE;
24 constexpr limb_t MAX_PRIME_DIFF = 1103717;
25 
30 inline void extract3(limb_t &c0, limb_t &c1, limb_t &c2, limb_t &n) {
31  n = c0;
32  c0 = c1;
33  c1 = c2;
34  c2 = 0;
35 }
36 
38 inline void mul(limb_t &c0, limb_t &c1, const limb_t &a, const limb_t &b) {
39  double_limb_t t = (double_limb_t)a * b;
40  c1 = t >> LIMB_SIZE;
41  c0 = t;
42 }
43 
44 /* [c0,c1,c2] += n * [d0,d1,d2]. c2 is 0 initially */
45 inline void mulnadd3(limb_t &c0, limb_t &c1, limb_t &c2, limb_t &d0, limb_t &d1,
46  limb_t &d2, const limb_t &n) {
47  double_limb_t t = (double_limb_t)d0 * n + c0;
48  c0 = t;
49  t >>= LIMB_SIZE;
50  t += (double_limb_t)d1 * n + c1;
51  c1 = t;
52  t >>= LIMB_SIZE;
53  c2 = t + d2 * n;
54 }
55 
56 /* [c0,c1] *= n */
57 inline void muln2(limb_t &c0, limb_t &c1, const limb_t &n) {
58  double_limb_t t = (double_limb_t)c0 * n;
59  c0 = t;
60  t >>= LIMB_SIZE;
61  t += (double_limb_t)c1 * n;
62  c1 = t;
63 }
64 
66 inline void muladd3(limb_t &c0, limb_t &c1, limb_t &c2, const limb_t &a,
67  const limb_t &b) {
68  double_limb_t t = (double_limb_t)a * b;
69  limb_t th = t >> LIMB_SIZE;
70  limb_t tl = t;
71 
72  c0 += tl;
73  th += (c0 < tl) ? 1 : 0;
74  c1 += th;
75  c2 += (c1 < th) ? 1 : 0;
76 }
77 
79 inline void muldbladd3(limb_t &c0, limb_t &c1, limb_t &c2, const limb_t &a,
80  const limb_t &b) {
81  double_limb_t t = (double_limb_t)a * b;
82  limb_t th = t >> LIMB_SIZE;
83  limb_t tl = t;
84 
85  c0 += tl;
86  limb_t tt = th + ((c0 < tl) ? 1 : 0);
87  c1 += tt;
88  c2 += (c1 < tt) ? 1 : 0;
89  c0 += tl;
90  th += (c0 < tl) ? 1 : 0;
91  c1 += th;
92  c2 += (c1 < th) ? 1 : 0;
93 }
94 
99 inline void addnextract2(limb_t &c0, limb_t &c1, const limb_t &a, limb_t &n) {
100  limb_t c2 = 0;
101 
102  // add
103  c0 += a;
104  if (c0 < a) {
105  c1 += 1;
106 
107  // Handle case when c1 has overflown
108  if (c1 == 0) {
109  c2 = 1;
110  }
111  }
112 
113  // extract
114  n = c0;
115  c0 = c1;
116  c1 = c2;
117 }
118 
120 inline void square_n_mul(Num3072 &in_out, const int sq, const Num3072 &mul) {
121  for (int j = 0; j < sq; ++j) {
122  in_out.Square();
123  }
124  in_out.Multiply(mul);
125 }
126 
127 } // namespace
128 
130 bool Num3072::IsOverflow() const {
131  if (this->limbs[0] <= std::numeric_limits<limb_t>::max() - MAX_PRIME_DIFF) {
132  return false;
133  }
134  for (int i = 1; i < LIMBS; ++i) {
135  if (this->limbs[i] != std::numeric_limits<limb_t>::max()) {
136  return false;
137  }
138  }
139  return true;
140 }
141 
143  limb_t c0 = MAX_PRIME_DIFF;
144  limb_t c1 = 0;
145  for (int i = 0; i < LIMBS; ++i) {
146  addnextract2(c0, c1, this->limbs[i], this->limbs[i]);
147  }
148 }
149 
151  // For fast exponentiation a sliding window exponentiation with repunit
152  // precomputation is utilized. See "Fast Point Decompression for Standard
153  // Elliptic Curves" (Brumley, J√§rvinen, 2008).
154 
155  // p[i] = a^(2^(2^i)-1)
156  Num3072 p[12];
157 
158  p[0] = *this;
159 
160  for (int i = 0; i < 11; ++i) {
161  p[i + 1] = p[i];
162  for (int j = 0; j < (1 << i); ++j) {
163  p[i + 1].Square();
164  }
165  p[i + 1].Multiply(p[i]);
166  }
167 
168  Num3072 out;
169 
170  out = p[11];
171 
172  square_n_mul(out, 512, p[9]);
173  square_n_mul(out, 256, p[8]);
174  square_n_mul(out, 128, p[7]);
175  square_n_mul(out, 64, p[6]);
176  square_n_mul(out, 32, p[5]);
177  square_n_mul(out, 8, p[3]);
178  square_n_mul(out, 2, p[1]);
179  square_n_mul(out, 1, p[0]);
180  square_n_mul(out, 5, p[2]);
181  square_n_mul(out, 3, p[0]);
182  square_n_mul(out, 2, p[0]);
183  square_n_mul(out, 4, p[0]);
184  square_n_mul(out, 4, p[1]);
185  square_n_mul(out, 3, p[0]);
186 
187  return out;
188 }
189 
190 void Num3072::Multiply(const Num3072 &a) {
191  limb_t c0 = 0, c1 = 0, c2 = 0;
192  Num3072 tmp;
193 
194  /* Compute limbs 0..N-2 of this*a into tmp, including one reduction. */
195  for (int j = 0; j < LIMBS - 1; ++j) {
196  limb_t d0 = 0, d1 = 0, d2 = 0;
197  mul(d0, d1, this->limbs[1 + j], a.limbs[LIMBS + j - (1 + j)]);
198  for (int i = 2 + j; i < LIMBS; ++i) {
199  muladd3(d0, d1, d2, this->limbs[i], a.limbs[LIMBS + j - i]);
200  }
201  mulnadd3(c0, c1, c2, d0, d1, d2, MAX_PRIME_DIFF);
202  for (int i = 0; i < j + 1; ++i) {
203  muladd3(c0, c1, c2, this->limbs[i], a.limbs[j - i]);
204  }
205  extract3(c0, c1, c2, tmp.limbs[j]);
206  }
207 
208  /* Compute limb N-1 of a*b into tmp. */
209  assert(c2 == 0);
210  for (int i = 0; i < LIMBS; ++i) {
211  muladd3(c0, c1, c2, this->limbs[i], a.limbs[LIMBS - 1 - i]);
212  }
213  extract3(c0, c1, c2, tmp.limbs[LIMBS - 1]);
214 
215  /* Perform a second reduction. */
216  muln2(c0, c1, MAX_PRIME_DIFF);
217  for (int j = 0; j < LIMBS; ++j) {
218  addnextract2(c0, c1, tmp.limbs[j], this->limbs[j]);
219  }
220 
221  assert(c1 == 0);
222  assert(c0 == 0 || c0 == 1);
223 
229  if (this->IsOverflow()) {
230  this->FullReduce();
231  }
232  if (c0) {
233  this->FullReduce();
234  }
235 }
236 
238  limb_t c0 = 0, c1 = 0, c2 = 0;
239  Num3072 tmp;
240 
241  /* Compute limbs 0..N-2 of this*this into tmp, including one reduction. */
242  for (int j = 0; j < LIMBS - 1; ++j) {
243  limb_t d0 = 0, d1 = 0, d2 = 0;
244  for (int i = 0; i < (LIMBS - 1 - j) / 2; ++i) {
245  muldbladd3(d0, d1, d2, this->limbs[i + j + 1],
246  this->limbs[LIMBS - 1 - i]);
247  }
248  if ((j + 1) & 1) {
249  muladd3(d0, d1, d2, this->limbs[(LIMBS - 1 - j) / 2 + j + 1],
250  this->limbs[LIMBS - 1 - (LIMBS - 1 - j) / 2]);
251  }
252  mulnadd3(c0, c1, c2, d0, d1, d2, MAX_PRIME_DIFF);
253  for (int i = 0; i < (j + 1) / 2; ++i) {
254  muldbladd3(c0, c1, c2, this->limbs[i], this->limbs[j - i]);
255  }
256  if ((j + 1) & 1) {
257  muladd3(c0, c1, c2, this->limbs[(j + 1) / 2],
258  this->limbs[j - (j + 1) / 2]);
259  }
260  extract3(c0, c1, c2, tmp.limbs[j]);
261  }
262 
263  assert(c2 == 0);
264  for (int i = 0; i < LIMBS / 2; ++i) {
265  muldbladd3(c0, c1, c2, this->limbs[i], this->limbs[LIMBS - 1 - i]);
266  }
267  extract3(c0, c1, c2, tmp.limbs[LIMBS - 1]);
268 
269  /* Perform a second reduction. */
270  muln2(c0, c1, MAX_PRIME_DIFF);
271  for (int j = 0; j < LIMBS; ++j) {
272  addnextract2(c0, c1, tmp.limbs[j], this->limbs[j]);
273  }
274 
275  assert(c1 == 0);
276  assert(c0 == 0 || c0 == 1);
277 
283  if (this->IsOverflow()) {
284  this->FullReduce();
285  }
286  if (c0) {
287  this->FullReduce();
288  }
289 }
290 
292  this->limbs[0] = 1;
293  for (int i = 1; i < LIMBS; ++i) {
294  this->limbs[i] = 0;
295  }
296 }
297 
298 void Num3072::Divide(const Num3072 &a) {
299  if (this->IsOverflow()) {
300  this->FullReduce();
301  }
302 
303  Num3072 inv{};
304  if (a.IsOverflow()) {
305  Num3072 b = a;
306  b.FullReduce();
307  inv = b.GetInverse();
308  } else {
309  inv = a.GetInverse();
310  }
311 
312  this->Multiply(inv);
313  if (this->IsOverflow()) {
314  this->FullReduce();
315  }
316 }
317 
318 Num3072::Num3072(const uint8_t (&data)[BYTE_SIZE]) {
319  for (int i = 0; i < LIMBS; ++i) {
320  if (sizeof(limb_t) == 4) {
321  this->limbs[i] = ReadLE32(data + 4 * i);
322  } else if (sizeof(limb_t) == 8) {
323  this->limbs[i] = ReadLE64(data + 8 * i);
324  }
325  }
326 }
327 
328 void Num3072::ToBytes(uint8_t (&out)[BYTE_SIZE]) {
329  for (int i = 0; i < LIMBS; ++i) {
330  if (sizeof(limb_t) == 4) {
331  WriteLE32(out + i * 4, this->limbs[i]);
332  } else if (sizeof(limb_t) == 8) {
333  WriteLE64(out + i * 8, this->limbs[i]);
334  }
335  }
336 }
337 
339  uint8_t tmp[Num3072::BYTE_SIZE];
340 
341  uint256 hashed_in = (CHashWriter(SER_DISK, 0) << in).GetSHA256();
342  ChaCha20(hashed_in.data(), hashed_in.size())
344  Num3072 out{tmp};
345 
346  return out;
347 }
348 
350  m_numerator = ToNum3072(in);
351 }
352 
353 void MuHash3072::Finalize(uint256 &out) noexcept {
354  m_numerator.Divide(m_denominator);
355  // Needed to keep the MuHash object valid
356  m_denominator.SetToOne();
357 
358  uint8_t data[Num3072::BYTE_SIZE];
359  m_numerator.ToBytes(data);
360 
361  out = (CHashWriter(SER_DISK, 0) << data).GetSHA256();
362 }
363 
365  m_numerator.Multiply(mul.m_numerator);
366  m_denominator.Multiply(mul.m_denominator);
367  return *this;
368 }
369 
371  m_numerator.Multiply(div.m_denominator);
372  m_denominator.Multiply(div.m_numerator);
373  return *this;
374 }
375 
377  m_numerator.Multiply(ToNum3072(in));
378  return *this;
379 }
380 
382  m_denominator.Multiply(ToNum3072(in));
383  return *this;
384 }
A writer stream (for serialization) that computes a 256-bit hash.
Definition: hash.h:100
A class for ChaCha20 256-bit stream cipher developed by Daniel J.
Definition: chacha20.h:15
void Keystream(uint8_t *c, size_t bytes)
outputs the keystream of size <bytes> into
Definition: chacha20.cpp:79
A class representing MuHash sets.
Definition: muhash.h:96
Num3072 ToNum3072(Span< const uint8_t > in)
Definition: muhash.cpp:338
MuHash3072 & Remove(Span< const uint8_t > in) noexcept
Definition: muhash.cpp:381
void Finalize(uint256 &out) noexcept
Definition: muhash.cpp:353
MuHash3072() noexcept
Definition: muhash.h:105
MuHash3072 & operator/=(const MuHash3072 &div) noexcept
Definition: muhash.cpp:370
MuHash3072 & Insert(Span< const uint8_t > in) noexcept
Definition: muhash.cpp:376
MuHash3072 & operator*=(const MuHash3072 &mul) noexcept
Definition: muhash.cpp:364
Definition: muhash.h:18
Num3072 GetInverse() const
Definition: muhash.cpp:150
void Square()
Definition: muhash.cpp:237
static constexpr int LIMBS
Definition: muhash.h:35
static constexpr size_t BYTE_SIZE
Definition: muhash.h:25
bool IsOverflow() const
Indicates whether d is larger than the modulus.
Definition: muhash.cpp:130
void ToBytes(uint8_t(&out)[BYTE_SIZE])
Definition: muhash.cpp:328
limb_t limbs[LIMBS]
Definition: muhash.h:38
void SetToOne()
Definition: muhash.cpp:291
static constexpr int LIMB_SIZE
Definition: muhash.h:36
void Divide(const Num3072 &a)
Definition: muhash.cpp:298
void FullReduce()
Definition: muhash.cpp:142
uint64_t double_limb_t
Definition: muhash.h:33
uint32_t limb_t
Definition: muhash.h:34
Num3072()
Definition: muhash.h:56
void Multiply(const Num3072 &a)
Definition: muhash.cpp:190
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:93
unsigned int size() const
Definition: uint256.h:91
const uint8_t * data() const
Definition: uint256.h:80
256-bit opaque blob.
Definition: uint256.h:127
static void WriteLE32(uint8_t *ptr, uint32_t x)
Definition: common.h:40
static uint64_t ReadLE64(const uint8_t *ptr)
Definition: common.h:29
static uint32_t ReadLE32(const uint8_t *ptr)
Definition: common.h:23
static void WriteLE64(uint8_t *ptr, uint64_t x)
Definition: common.h:45
@ SER_DISK
Definition: serialize.h:167
assert(!tx.IsCoinBase())