Bitcoin Core  21.99.0
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;
20 constexpr int LIMBS = Num3072::LIMBS;
22 constexpr limb_t MAX_PRIME_DIFF = 1103717;
23 
25 inline void extract3(limb_t& c0, limb_t& c1, limb_t& c2, limb_t& n)
26 {
27  n = c0;
28  c0 = c1;
29  c1 = c2;
30  c2 = 0;
31 }
32 
34 inline void mul(limb_t& c0, limb_t& c1, const limb_t& a, const limb_t& b)
35 {
36  double_limb_t t = (double_limb_t)a * b;
37  c1 = t >> LIMB_SIZE;
38  c0 = t;
39 }
40 
41 /* [c0,c1,c2] += n * [d0,d1,d2]. c2 is 0 initially */
42 inline void mulnadd3(limb_t& c0, limb_t& c1, limb_t& c2, limb_t& d0, limb_t& d1, limb_t& d2, const limb_t& n)
43 {
44  double_limb_t t = (double_limb_t)d0 * n + c0;
45  c0 = t;
46  t >>= LIMB_SIZE;
47  t += (double_limb_t)d1 * n + c1;
48  c1 = t;
49  t >>= LIMB_SIZE;
50  c2 = t + d2 * n;
51 }
52 
53 /* [c0,c1] *= n */
54 inline void muln2(limb_t& c0, limb_t& c1, const limb_t& n)
55 {
56  double_limb_t t = (double_limb_t)c0 * n;
57  c0 = t;
58  t >>= LIMB_SIZE;
59  t += (double_limb_t)c1 * n;
60  c1 = t;
61 }
62 
64 inline void muladd3(limb_t& c0, limb_t& c1, limb_t& c2, const limb_t& a, const limb_t& b)
65 {
66  double_limb_t t = (double_limb_t)a * b;
67  limb_t th = t >> LIMB_SIZE;
68  limb_t tl = t;
69 
70  c0 += tl;
71  th += (c0 < tl) ? 1 : 0;
72  c1 += th;
73  c2 += (c1 < th) ? 1 : 0;
74 }
75 
77 inline void muldbladd3(limb_t& c0, limb_t& c1, limb_t& c2, const limb_t& a, const limb_t& b)
78 {
79  double_limb_t t = (double_limb_t)a * b;
80  limb_t th = t >> LIMB_SIZE;
81  limb_t tl = t;
82 
83  c0 += tl;
84  limb_t tt = th + ((c0 < tl) ? 1 : 0);
85  c1 += tt;
86  c2 += (c1 < tt) ? 1 : 0;
87  c0 += tl;
88  th += (c0 < tl) ? 1 : 0;
89  c1 += th;
90  c2 += (c1 < th) ? 1 : 0;
91 }
92 
97 inline void addnextract2(limb_t& c0, limb_t& c1, const limb_t& a, limb_t& n)
98 {
99  limb_t c2 = 0;
100 
101  // add
102  c0 += a;
103  if (c0 < a) {
104  c1 += 1;
105 
106  // Handle case when c1 has overflown
107  if (c1 == 0)
108  c2 = 1;
109  }
110 
111  // extract
112  n = c0;
113  c0 = c1;
114  c1 = c2;
115 }
116 
118 inline void square_n_mul(Num3072& in_out, const int sq, const Num3072& mul)
119 {
120  for (int j = 0; j < sq; ++j) in_out.Square();
121  in_out.Multiply(mul);
122 }
123 
124 } // namespace
125 
128 {
129  if (this->limbs[0] <= std::numeric_limits<limb_t>::max() - MAX_PRIME_DIFF) return false;
130  for (int i = 1; i < LIMBS; ++i) {
131  if (this->limbs[i] != std::numeric_limits<limb_t>::max()) return false;
132  }
133  return true;
134 }
135 
137 {
138  limb_t c0 = MAX_PRIME_DIFF;
139  limb_t c1 = 0;
140  for (int i = 0; i < LIMBS; ++i) {
141  addnextract2(c0, c1, this->limbs[i], this->limbs[i]);
142  }
143 }
144 
146 {
147  // For fast exponentiation a sliding window exponentiation with repunit
148  // precomputation is utilized. See "Fast Point Decompression for Standard
149  // Elliptic Curves" (Brumley, J√§rvinen, 2008).
150 
151  Num3072 p[12]; // p[i] = a^(2^(2^i)-1)
152  Num3072 out;
153 
154  p[0] = *this;
155 
156  for (int i = 0; i < 11; ++i) {
157  p[i + 1] = p[i];
158  for (int j = 0; j < (1 << i); ++j) p[i + 1].Square();
159  p[i + 1].Multiply(p[i]);
160  }
161 
162  out = p[11];
163 
164  square_n_mul(out, 512, p[9]);
165  square_n_mul(out, 256, p[8]);
166  square_n_mul(out, 128, p[7]);
167  square_n_mul(out, 64, p[6]);
168  square_n_mul(out, 32, p[5]);
169  square_n_mul(out, 8, p[3]);
170  square_n_mul(out, 2, p[1]);
171  square_n_mul(out, 1, p[0]);
172  square_n_mul(out, 5, p[2]);
173  square_n_mul(out, 3, p[0]);
174  square_n_mul(out, 2, p[0]);
175  square_n_mul(out, 4, p[0]);
176  square_n_mul(out, 4, p[1]);
177  square_n_mul(out, 3, p[0]);
178 
179  return out;
180 }
181 
183 {
184  limb_t c0 = 0, c1 = 0, c2 = 0;
185  Num3072 tmp;
186 
187  /* Compute limbs 0..N-2 of this*a into tmp, including one reduction. */
188  for (int j = 0; j < LIMBS - 1; ++j) {
189  limb_t d0 = 0, d1 = 0, d2 = 0;
190  mul(d0, d1, this->limbs[1 + j], a.limbs[LIMBS + j - (1 + j)]);
191  for (int i = 2 + j; i < LIMBS; ++i) muladd3(d0, d1, d2, this->limbs[i], a.limbs[LIMBS + j - i]);
192  mulnadd3(c0, c1, c2, d0, d1, d2, MAX_PRIME_DIFF);
193  for (int i = 0; i < j + 1; ++i) muladd3(c0, c1, c2, this->limbs[i], a.limbs[j - i]);
194  extract3(c0, c1, c2, tmp.limbs[j]);
195  }
196 
197  /* Compute limb N-1 of a*b into tmp. */
198  assert(c2 == 0);
199  for (int i = 0; i < LIMBS; ++i) muladd3(c0, c1, c2, this->limbs[i], a.limbs[LIMBS - 1 - i]);
200  extract3(c0, c1, c2, tmp.limbs[LIMBS - 1]);
201 
202  /* Perform a second reduction. */
203  muln2(c0, c1, MAX_PRIME_DIFF);
204  for (int j = 0; j < LIMBS; ++j) {
205  addnextract2(c0, c1, tmp.limbs[j], this->limbs[j]);
206  }
207 
208  assert(c1 == 0);
209  assert(c0 == 0 || c0 == 1);
210 
211  /* Perform up to two more reductions if the internal state has already
212  * overflown the MAX of Num3072 or if it is larger than the modulus or
213  * if both are the case.
214  * */
215  if (this->IsOverflow()) this->FullReduce();
216  if (c0) this->FullReduce();
217 }
218 
220 {
221  limb_t c0 = 0, c1 = 0, c2 = 0;
222  Num3072 tmp;
223 
224  /* Compute limbs 0..N-2 of this*this into tmp, including one reduction. */
225  for (int j = 0; j < LIMBS - 1; ++j) {
226  limb_t d0 = 0, d1 = 0, d2 = 0;
227  for (int i = 0; i < (LIMBS - 1 - j) / 2; ++i) muldbladd3(d0, d1, d2, this->limbs[i + j + 1], this->limbs[LIMBS - 1 - i]);
228  if ((j + 1) & 1) muladd3(d0, d1, d2, this->limbs[(LIMBS - 1 - j) / 2 + j + 1], this->limbs[LIMBS - 1 - (LIMBS - 1 - j) / 2]);
229  mulnadd3(c0, c1, c2, d0, d1, d2, MAX_PRIME_DIFF);
230  for (int i = 0; i < (j + 1) / 2; ++i) muldbladd3(c0, c1, c2, this->limbs[i], this->limbs[j - i]);
231  if ((j + 1) & 1) muladd3(c0, c1, c2, this->limbs[(j + 1) / 2], this->limbs[j - (j + 1) / 2]);
232  extract3(c0, c1, c2, tmp.limbs[j]);
233  }
234 
235  assert(c2 == 0);
236  for (int i = 0; i < LIMBS / 2; ++i) muldbladd3(c0, c1, c2, this->limbs[i], this->limbs[LIMBS - 1 - i]);
237  extract3(c0, c1, c2, tmp.limbs[LIMBS - 1]);
238 
239  /* Perform a second reduction. */
240  muln2(c0, c1, MAX_PRIME_DIFF);
241  for (int j = 0; j < LIMBS; ++j) {
242  addnextract2(c0, c1, tmp.limbs[j], this->limbs[j]);
243  }
244 
245  assert(c1 == 0);
246  assert(c0 == 0 || c0 == 1);
247 
248  /* Perform up to two more reductions if the internal state has already
249  * overflown the MAX of Num3072 or if it is larger than the modulus or
250  * if both are the case.
251  * */
252  if (this->IsOverflow()) this->FullReduce();
253  if (c0) this->FullReduce();
254 }
255 
257 {
258  this->limbs[0] = 1;
259  for (int i = 1; i < LIMBS; ++i) this->limbs[i] = 0;
260 }
261 
262 void Num3072::Divide(const Num3072& a)
263 {
264  if (this->IsOverflow()) this->FullReduce();
265 
266  Num3072 inv{};
267  if (a.IsOverflow()) {
268  Num3072 b = a;
269  b.FullReduce();
270  inv = b.GetInverse();
271  } else {
272  inv = a.GetInverse();
273  }
274 
275  this->Multiply(inv);
276  if (this->IsOverflow()) this->FullReduce();
277 }
278 
280  Num3072 out{};
281  uint256 hashed_in = (CHashWriter(SER_DISK, 0) << in).GetSHA256();
282  unsigned char tmp[BYTE_SIZE];
283  ChaCha20(hashed_in.data(), hashed_in.size()).Keystream(tmp, BYTE_SIZE);
284  for (int i = 0; i < LIMBS; ++i) {
285  if (sizeof(limb_t) == 4) {
286  out.limbs[i] = ReadLE32(tmp + 4 * i);
287  } else if (sizeof(limb_t) == 8) {
288  out.limbs[i] = ReadLE64(tmp + 8 * i);
289  }
290  }
291  return out;
292 }
293 
295 {
296  m_numerator = ToNum3072(in);
297 }
298 
299 void MuHash3072::Finalize(uint256& out) noexcept
300 {
301  m_numerator.Divide(m_denominator);
302  m_denominator.SetToOne(); // Needed to keep the MuHash object valid
303 
304  unsigned char data[384];
305  for (int i = 0; i < LIMBS; ++i) {
306  if (sizeof(limb_t) == 4) {
307  WriteLE32(data + i * 4, m_numerator.limbs[i]);
308  } else if (sizeof(limb_t) == 8) {
309  WriteLE64(data + i * 8, m_numerator.limbs[i]);
310  }
311  }
312 
313  out = (CHashWriter(SER_DISK, 0) << data).GetSHA256();
314 }
315 
317 {
318  m_numerator.Multiply(mul.m_numerator);
319  m_denominator.Multiply(mul.m_denominator);
320  return *this;
321 }
322 
324 {
325  m_numerator.Multiply(div.m_denominator);
326  m_denominator.Multiply(div.m_numerator);
327  return *this;
328 }
329 
331  m_numerator.Multiply(ToNum3072(in));
332  return *this;
333 }
334 
336  m_numerator.Divide(ToNum3072(in));
337  return *this;
338 }
Definition: muhash.h:17
assert(!tx.IsCoinBase())
limb_t limbs[LIMBS]
Definition: muhash.h:37
static void WriteLE64(unsigned char *ptr, uint64_t x)
Definition: common.h:50
static void WriteLE32(unsigned char *ptr, uint32_t x)
Definition: common.h:44
uint64_t double_limb_t
Definition: muhash.h:32
uint32_t limb_t
Definition: muhash.h:33
bool IsOverflow() const
Indicates wether d is larger than the modulus.
Definition: muhash.cpp:127
const unsigned char * data() const
Definition: uint256.h:55
void Divide(const Num3072 &a)
Definition: muhash.cpp:262
static constexpr int LIMB_SIZE
Definition: muhash.h:35
static constexpr int LIMBS
Definition: muhash.h:34
A class for ChaCha20 256-bit stream cipher developed by Daniel J.
Definition: chacha20.h:13
void Multiply(const Num3072 &a)
Definition: muhash.cpp:182
MuHash3072() noexcept
Definition: muhash.h:103
unsigned int size() const
Definition: uint256.h:78
MuHash3072 & Remove(Span< const unsigned char > in) noexcept
Definition: muhash.cpp:335
void Finalize(uint256 &out) noexcept
Definition: muhash.cpp:299
Num3072 GetInverse() const
Definition: muhash.cpp:145
static uint32_t ReadLE32(const unsigned char *ptr)
Definition: common.h:24
256-bit opaque blob.
Definition: uint256.h:124
Num3072 ToNum3072(Span< const unsigned char > in)
Definition: muhash.cpp:279
MuHash3072 & operator*=(const MuHash3072 &mul) noexcept
Definition: muhash.cpp:316
static uint64_t ReadLE64(const unsigned char *ptr)
Definition: common.h:31
A class representing MuHash sets.
Definition: muhash.h:91
A writer stream (for serialization) that computes a 256-bit hash.
Definition: hash.h:100
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:92
MuHash3072 & Insert(Span< const unsigned char > in) noexcept
Definition: muhash.cpp:330
void SetToOne()
Definition: muhash.cpp:256
void Square()
Definition: muhash.cpp:219
void FullReduce()
Definition: muhash.cpp:136
MuHash3072 & operator/=(const MuHash3072 &div) noexcept
Definition: muhash.cpp:323