Electroneum
ecmult_impl.h
Go to the documentation of this file.
1 /******************************************************************************
2  * Copyright (c) 2013, 2014, 2017 Pieter Wuille, Andrew Poelstra, Jonas Nick *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or https://www.opensource.org/licenses/mit-license.php. *
5  ******************************************************************************/
6 
7 #ifndef SECP256K1_ECMULT_IMPL_H
8 #define SECP256K1_ECMULT_IMPL_H
9 
10 #include <string.h>
11 #include <stdint.h>
12 
13 #include "util.h"
14 #include "group.h"
15 #include "scalar.h"
16 #include "ecmult.h"
17 #include "precomputed_ecmult.h"
18 
19 #if defined(EXHAUSTIVE_TEST_ORDER)
20 /* We need to lower these values for exhaustive tests because
21  * the tables cannot have infinities in them (this breaks the
22  * affine-isomorphism stuff which tracks z-ratios) */
23 # if EXHAUSTIVE_TEST_ORDER > 128
24 # define WINDOW_A 5
25 # elif EXHAUSTIVE_TEST_ORDER > 8
26 # define WINDOW_A 4
27 # else
28 # define WINDOW_A 2
29 # endif
30 #else
31 /* optimal for 128-bit and 256-bit exponents. */
32 # define WINDOW_A 5
33 
42 #endif
43 
44 #define WNAF_BITS 128
45 #define WNAF_SIZE_BITS(bits, w) (((bits) + (w) - 1) / (w))
46 #define WNAF_SIZE(w) WNAF_SIZE_BITS(WNAF_BITS, w)
47 
48 /* The number of objects allocated on the scratch space for ecmult_multi algorithms */
49 #define PIPPENGER_SCRATCH_OBJECTS 6
50 #define STRAUSS_SCRATCH_OBJECTS 5
51 
52 #define PIPPENGER_MAX_BUCKET_WINDOW 12
53 
54 /* Minimum number of points for which pippenger_wnaf is faster than strauss wnaf */
55 #define ECMULT_PIPPENGER_THRESHOLD 88
56 
57 #define ECMULT_MAX_POINTS_PER_BATCH 5000000
58 
73 static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_ge *pre_a, secp256k1_fe *zr, secp256k1_fe *z, const secp256k1_gej *a) {
74  secp256k1_gej d, ai;
75  secp256k1_ge d_ge;
76  int i;
77 
78  VERIFY_CHECK(!a->infinity);
79 
80  secp256k1_gej_double_var(&d, a, NULL);
81 
82  /*
83  * Perform the additions using an isomorphic curve Y^2 = X^3 + 7*C^6 where C := d.z.
84  * The isomorphism, phi, maps a secp256k1 point (x, y) to the point (x*C^2, y*C^3) on the other curve.
85  * In Jacobian coordinates phi maps (x, y, z) to (x*C^2, y*C^3, z) or, equivalently to (x, y, z/C).
86  *
87  * phi(x, y, z) = (x*C^2, y*C^3, z) = (x, y, z/C)
88  * d_ge := phi(d) = (d.x, d.y, 1)
89  * ai := phi(a) = (a.x*C^2, a.y*C^3, a.z)
90  *
91  * The group addition functions work correctly on these isomorphic curves.
92  * In particular phi(d) is easy to represent in affine coordinates under this isomorphism.
93  * This lets us use the faster secp256k1_gej_add_ge_var group addition function that we wouldn't be able to use otherwise.
94  */
95  secp256k1_ge_set_xy(&d_ge, &d.x, &d.y);
96  secp256k1_ge_set_gej_zinv(&pre_a[0], a, &d.z);
97  secp256k1_gej_set_ge(&ai, &pre_a[0]);
98  ai.z = a->z;
99 
100  /* pre_a[0] is the point (a.x*C^2, a.y*C^3, a.z*C) which is equvalent to a.
101  * Set zr[0] to C, which is the ratio between the omitted z(pre_a[0]) value and a.z.
102  */
103  zr[0] = d.z;
104 
105  for (i = 1; i < n; i++) {
106  secp256k1_gej_add_ge_var(&ai, &ai, &d_ge, &zr[i]);
107  secp256k1_ge_set_xy(&pre_a[i], &ai.x, &ai.y);
108  }
109 
110  /* Multiply the last z-coordinate by C to undo the isomorphism.
111  * Since the z-coordinates of the pre_a values are implied by the zr array of z-coordinate ratios,
112  * undoing the isomorphism here undoes the isomorphism for all pre_a values.
113  */
114  secp256k1_fe_mul(z, &ai.z, &d.z);
115 }
116 
117 #define SECP256K1_ECMULT_TABLE_VERIFY(n,w) \
118  VERIFY_CHECK(((n) & 1) == 1); \
119  VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
120  VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1));
121 
122 SECP256K1_INLINE static void secp256k1_ecmult_table_get_ge(secp256k1_ge *r, const secp256k1_ge *pre, int n, int w) {
124  if (n > 0) {
125  *r = pre[(n-1)/2];
126  } else {
127  *r = pre[(-n-1)/2];
128  secp256k1_fe_negate(&(r->y), &(r->y), 1);
129  }
130 }
131 
132 SECP256K1_INLINE static void secp256k1_ecmult_table_get_ge_lambda(secp256k1_ge *r, const secp256k1_ge *pre, const secp256k1_fe *x, int n, int w) {
134  if (n > 0) {
135  secp256k1_ge_set_xy(r, &x[(n-1)/2], &pre[(n-1)/2].y);
136  } else {
137  secp256k1_ge_set_xy(r, &x[(-n-1)/2], &pre[(-n-1)/2].y);
138  secp256k1_fe_negate(&(r->y), &(r->y), 1);
139  }
140 }
141 
142 SECP256K1_INLINE static void secp256k1_ecmult_table_get_ge_storage(secp256k1_ge *r, const secp256k1_ge_storage *pre, int n, int w) {
144  if (n > 0) {
145  secp256k1_ge_from_storage(r, &pre[(n-1)/2]);
146  } else {
147  secp256k1_ge_from_storage(r, &pre[(-n-1)/2]);
148  secp256k1_fe_negate(&(r->y), &(r->y), 1);
149  }
150 }
151 
159 static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) {
161  int last_set_bit = -1;
162  int bit = 0;
163  int sign = 1;
164  int carry = 0;
165 
166  VERIFY_CHECK(wnaf != NULL);
167  VERIFY_CHECK(0 <= len && len <= 256);
168  VERIFY_CHECK(a != NULL);
169  VERIFY_CHECK(2 <= w && w <= 31);
170 
171  memset(wnaf, 0, len * sizeof(wnaf[0]));
172 
173  s = *a;
174  if (secp256k1_scalar_get_bits(&s, 255, 1)) {
175  secp256k1_scalar_negate(&s, &s);
176  sign = -1;
177  }
178 
179  while (bit < len) {
180  int now;
181  int word;
182  if (secp256k1_scalar_get_bits(&s, bit, 1) == (unsigned int)carry) {
183  bit++;
184  continue;
185  }
186 
187  now = w;
188  if (now > len - bit) {
189  now = len - bit;
190  }
191 
192  word = secp256k1_scalar_get_bits_var(&s, bit, now) + carry;
193 
194  carry = (word >> (w-1)) & 1;
195  word -= carry << w;
196 
197  wnaf[bit] = sign * word;
198  last_set_bit = bit;
199 
200  bit += now;
201  }
202 #ifdef VERIFY
203  {
204  int verify_bit = bit;
205 
206  VERIFY_CHECK(carry == 0);
207 
208  while (verify_bit < 256) {
209  VERIFY_CHECK(secp256k1_scalar_get_bits(&s, verify_bit, 1) == 0);
210  verify_bit++;
211  }
212  }
213 #endif
214  return last_set_bit + 1;
215 }
216 
218  int wnaf_na_1[129];
219  int wnaf_na_lam[129];
222 };
223 
225  /* aux is used to hold z-ratios, and then used to hold pre_a[i].x * BETA values. */
229 };
230 
231 static void secp256k1_ecmult_strauss_wnaf(const struct secp256k1_strauss_state *state, secp256k1_gej *r, size_t num, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
232  secp256k1_ge tmpa;
233  secp256k1_fe Z;
234  /* Split G factors. */
235  secp256k1_scalar ng_1, ng_128;
236  int wnaf_ng_1[129];
237  int bits_ng_1 = 0;
238  int wnaf_ng_128[129];
239  int bits_ng_128 = 0;
240  int i;
241  int bits = 0;
242  size_t np;
243  size_t no = 0;
244 
245  secp256k1_fe_set_int(&Z, 1);
246  for (np = 0; np < num; ++np) {
247  secp256k1_gej tmp;
248  secp256k1_scalar na_1, na_lam;
249  if (secp256k1_scalar_is_zero(&na[np]) || secp256k1_gej_is_infinity(&a[np])) {
250  continue;
251  }
252  /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
253  secp256k1_scalar_split_lambda(&na_1, &na_lam, &na[np]);
254 
255  /* build wnaf representation for na_1 and na_lam. */
256  state->ps[no].bits_na_1 = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_1, 129, &na_1, WINDOW_A);
257  state->ps[no].bits_na_lam = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_lam, 129, &na_lam, WINDOW_A);
258  VERIFY_CHECK(state->ps[no].bits_na_1 <= 129);
259  VERIFY_CHECK(state->ps[no].bits_na_lam <= 129);
260  if (state->ps[no].bits_na_1 > bits) {
261  bits = state->ps[no].bits_na_1;
262  }
263  if (state->ps[no].bits_na_lam > bits) {
264  bits = state->ps[no].bits_na_lam;
265  }
266 
267  /* Calculate odd multiples of a.
268  * All multiples are brought to the same Z 'denominator', which is stored
269  * in Z. Due to secp256k1' isomorphism we can do all operations pretending
270  * that the Z coordinate was 1, use affine addition formulae, and correct
271  * the Z coordinate of the result once at the end.
272  * The exception is the precomputed G table points, which are actually
273  * affine. Compared to the base used for other points, they have a Z ratio
274  * of 1/Z, so we can use secp256k1_gej_add_zinv_var, which uses the same
275  * isomorphism to efficiently add with a known Z inverse.
276  */
277  tmp = a[np];
278  if (no) {
279 #ifdef VERIFY
280  secp256k1_fe_normalize_var(&Z);
281 #endif
282  secp256k1_gej_rescale(&tmp, &Z);
283  }
284  secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), state->pre_a + no * ECMULT_TABLE_SIZE(WINDOW_A), state->aux + no * ECMULT_TABLE_SIZE(WINDOW_A), &Z, &tmp);
285  if (no) secp256k1_fe_mul(state->aux + no * ECMULT_TABLE_SIZE(WINDOW_A), state->aux + no * ECMULT_TABLE_SIZE(WINDOW_A), &(a[np].z));
286 
287  ++no;
288  }
289 
290  /* Bring them to the same Z denominator. */
291  secp256k1_ge_table_set_globalz(ECMULT_TABLE_SIZE(WINDOW_A) * no, state->pre_a, state->aux);
292 
293  for (np = 0; np < no; ++np) {
294  for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
295  secp256k1_fe_mul(&state->aux[np * ECMULT_TABLE_SIZE(WINDOW_A) + i], &state->pre_a[np * ECMULT_TABLE_SIZE(WINDOW_A) + i].x, &secp256k1_const_beta);
296  }
297  }
298 
299  if (ng) {
300  /* split ng into ng_1 and ng_128 (where gn = gn_1 + gn_128*2^128, and gn_1 and gn_128 are ~128 bit) */
301  secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
302 
303  /* Build wnaf representation for ng_1 and ng_128 */
304  bits_ng_1 = secp256k1_ecmult_wnaf(wnaf_ng_1, 129, &ng_1, WINDOW_G);
305  bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, 129, &ng_128, WINDOW_G);
306  if (bits_ng_1 > bits) {
307  bits = bits_ng_1;
308  }
309  if (bits_ng_128 > bits) {
310  bits = bits_ng_128;
311  }
312  }
313 
314  secp256k1_gej_set_infinity(r);
315 
316  for (i = bits - 1; i >= 0; i--) {
317  int n;
318  secp256k1_gej_double_var(r, r, NULL);
319  for (np = 0; np < no; ++np) {
320  if (i < state->ps[np].bits_na_1 && (n = state->ps[np].wnaf_na_1[i])) {
321  secp256k1_ecmult_table_get_ge(&tmpa, state->pre_a + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
322  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
323  }
324  if (i < state->ps[np].bits_na_lam && (n = state->ps[np].wnaf_na_lam[i])) {
325  secp256k1_ecmult_table_get_ge_lambda(&tmpa, state->pre_a + np * ECMULT_TABLE_SIZE(WINDOW_A), state->aux + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
326  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
327  }
328  }
329  if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
330  secp256k1_ecmult_table_get_ge_storage(&tmpa, secp256k1_pre_g, n, WINDOW_G);
331  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
332  }
333  if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
334  secp256k1_ecmult_table_get_ge_storage(&tmpa, secp256k1_pre_g_128, n, WINDOW_G);
335  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
336  }
337  }
338 
339  if (!r->infinity) {
340  secp256k1_fe_mul(&r->z, &r->z, &Z);
341  }
342 }
343 
344 static void secp256k1_ecmult(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
347  struct secp256k1_strauss_point_state ps[1];
349 
350  state.aux = aux;
351  state.pre_a = pre_a;
352  state.ps = ps;
353  secp256k1_ecmult_strauss_wnaf(&state, r, 1, a, na, ng);
354 }
355 
356 static size_t secp256k1_strauss_scratch_size(size_t n_points) {
357  static const size_t point_size = (sizeof(secp256k1_ge) + sizeof(secp256k1_fe)) * ECMULT_TABLE_SIZE(WINDOW_A) + sizeof(struct secp256k1_strauss_point_state) + sizeof(secp256k1_gej) + sizeof(secp256k1_scalar);
358  return n_points*point_size;
359 }
360 
361 static int secp256k1_ecmult_strauss_batch(const secp256k1_callback* error_callback, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) {
362  secp256k1_gej* points;
363  secp256k1_scalar* scalars;
365  size_t i;
366  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
367 
368  secp256k1_gej_set_infinity(r);
369  if (inp_g_sc == NULL && n_points == 0) {
370  return 1;
371  }
372 
373  /* We allocate STRAUSS_SCRATCH_OBJECTS objects on the scratch space. If these
374  * allocations change, make sure to update the STRAUSS_SCRATCH_OBJECTS
375  * constant and strauss_scratch_size accordingly. */
376  points = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_gej));
377  scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_scalar));
378  state.aux = (secp256k1_fe*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe));
379  state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
380  state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
381 
382  if (points == NULL || scalars == NULL || state.aux == NULL || state.pre_a == NULL || state.ps == NULL) {
383  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
384  return 0;
385  }
386 
387  for (i = 0; i < n_points; i++) {
388  secp256k1_ge point;
389  if (!cb(&scalars[i], &point, i+cb_offset, cbdata)) {
390  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
391  return 0;
392  }
393  secp256k1_gej_set_ge(&points[i], &point);
394  }
395  secp256k1_ecmult_strauss_wnaf(&state, r, n_points, points, scalars, inp_g_sc);
396  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
397  return 1;
398 }
399 
400 /* Wrapper for secp256k1_ecmult_multi_func interface */
401 static int secp256k1_ecmult_strauss_batch_single(const secp256k1_callback* error_callback, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
402  return secp256k1_ecmult_strauss_batch(error_callback, scratch, r, inp_g_sc, cb, cbdata, n, 0);
403 }
404 
405 static size_t secp256k1_strauss_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
406  return secp256k1_scratch_max_allocation(error_callback, scratch, STRAUSS_SCRATCH_OBJECTS) / secp256k1_strauss_scratch_size(1);
407 }
408 
416 static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w) {
417  int skew = 0;
418  int pos;
419  int max_pos;
420  int last_w;
421  const secp256k1_scalar *work = s;
422 
423  if (secp256k1_scalar_is_zero(s)) {
424  for (pos = 0; pos < WNAF_SIZE(w); pos++) {
425  wnaf[pos] = 0;
426  }
427  return 0;
428  }
429 
430  if (secp256k1_scalar_is_even(s)) {
431  skew = 1;
432  }
433 
434  wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
435  /* Compute last window size. Relevant when window size doesn't divide the
436  * number of bits in the scalar */
437  last_w = WNAF_BITS - (WNAF_SIZE(w) - 1) * w;
438 
439  /* Store the position of the first nonzero word in max_pos to allow
440  * skipping leading zeros when calculating the wnaf. */
441  for (pos = WNAF_SIZE(w) - 1; pos > 0; pos--) {
442  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
443  if(val != 0) {
444  break;
445  }
446  wnaf[pos] = 0;
447  }
448  max_pos = pos;
449  pos = 1;
450 
451  while (pos <= max_pos) {
452  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
453  if ((val & 1) == 0) {
454  wnaf[pos - 1] -= (1 << w);
455  wnaf[pos] = (val + 1);
456  } else {
457  wnaf[pos] = val;
458  }
459  /* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
460  * is strictly negative or strictly positive respectively. Only change
461  * coefficients at previous positions because above code assumes that
462  * wnaf[pos - 1] is odd.
463  */
464  if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) || (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
465  if (wnaf[pos - 1] == 1) {
466  wnaf[pos - 2] += 1 << w;
467  } else {
468  wnaf[pos - 2] -= 1 << w;
469  }
470  wnaf[pos - 1] = 0;
471  }
472  ++pos;
473  }
474 
475  return skew;
476 }
477 
479  int skew_na;
480  size_t input_pos;
481 };
482 
484  int *wnaf_na;
486 };
487 
488 /*
489  * pippenger_wnaf computes the result of a multi-point multiplication as
490  * follows: The scalars are brought into wnaf with n_wnaf elements each. Then
491  * for every i < n_wnaf, first each point is added to a "bucket" corresponding
492  * to the point's wnaf[i]. Second, the buckets are added together such that
493  * r += 1*bucket[0] + 3*bucket[1] + 5*bucket[2] + ...
494  */
495 static int secp256k1_ecmult_pippenger_wnaf(secp256k1_gej *buckets, int bucket_window, struct secp256k1_pippenger_state *state, secp256k1_gej *r, const secp256k1_scalar *sc, const secp256k1_ge *pt, size_t num) {
496  size_t n_wnaf = WNAF_SIZE(bucket_window+1);
497  size_t np;
498  size_t no = 0;
499  int i;
500  int j;
501 
502  for (np = 0; np < num; ++np) {
503  if (secp256k1_scalar_is_zero(&sc[np]) || secp256k1_ge_is_infinity(&pt[np])) {
504  continue;
505  }
506  state->ps[no].input_pos = np;
507  state->ps[no].skew_na = secp256k1_wnaf_fixed(&state->wnaf_na[no*n_wnaf], &sc[np], bucket_window+1);
508  no++;
509  }
510  secp256k1_gej_set_infinity(r);
511 
512  if (no == 0) {
513  return 1;
514  }
515 
516  for (i = n_wnaf - 1; i >= 0; i--) {
517  secp256k1_gej running_sum;
518 
519  for(j = 0; j < ECMULT_TABLE_SIZE(bucket_window+2); j++) {
520  secp256k1_gej_set_infinity(&buckets[j]);
521  }
522 
523  for (np = 0; np < no; ++np) {
524  int n = state->wnaf_na[np*n_wnaf + i];
525  struct secp256k1_pippenger_point_state point_state = state->ps[np];
526  secp256k1_ge tmp;
527  int idx;
528 
529  if (i == 0) {
530  /* correct for wnaf skew */
531  int skew = point_state.skew_na;
532  if (skew) {
533  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
534  secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);
535  }
536  }
537  if (n > 0) {
538  idx = (n - 1)/2;
539  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
540  } else if (n < 0) {
541  idx = -(n + 1)/2;
542  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
543  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);
544  }
545  }
546 
547  for(j = 0; j < bucket_window; j++) {
548  secp256k1_gej_double_var(r, r, NULL);
549  }
550 
551  secp256k1_gej_set_infinity(&running_sum);
552  /* Accumulate the sum: bucket[0] + 3*bucket[1] + 5*bucket[2] + 7*bucket[3] + ...
553  * = bucket[0] + bucket[1] + bucket[2] + bucket[3] + ...
554  * + 2 * (bucket[1] + 2*bucket[2] + 3*bucket[3] + ...)
555  * using an intermediate running sum:
556  * running_sum = bucket[0] + bucket[1] + bucket[2] + ...
557  *
558  * The doubling is done implicitly by deferring the final window doubling (of 'r').
559  */
560  for(j = ECMULT_TABLE_SIZE(bucket_window+2) - 1; j > 0; j--) {
561  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[j], NULL);
562  secp256k1_gej_add_var(r, r, &running_sum, NULL);
563  }
564 
565  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[0], NULL);
566  secp256k1_gej_double_var(r, r, NULL);
567  secp256k1_gej_add_var(r, r, &running_sum, NULL);
568  }
569  return 1;
570 }
571 
576 static int secp256k1_pippenger_bucket_window(size_t n) {
577  if (n <= 1) {
578  return 1;
579  } else if (n <= 4) {
580  return 2;
581  } else if (n <= 20) {
582  return 3;
583  } else if (n <= 57) {
584  return 4;
585  } else if (n <= 136) {
586  return 5;
587  } else if (n <= 235) {
588  return 6;
589  } else if (n <= 1260) {
590  return 7;
591  } else if (n <= 4420) {
592  return 9;
593  } else if (n <= 7880) {
594  return 10;
595  } else if (n <= 16050) {
596  return 11;
597  } else {
599  }
600 }
601 
605 static size_t secp256k1_pippenger_bucket_window_inv(int bucket_window) {
606  switch(bucket_window) {
607  case 1: return 1;
608  case 2: return 4;
609  case 3: return 20;
610  case 4: return 57;
611  case 5: return 136;
612  case 6: return 235;
613  case 7: return 1260;
614  case 8: return 1260;
615  case 9: return 4420;
616  case 10: return 7880;
617  case 11: return 16050;
619  }
620  return 0;
621 }
622 
623 
624 SECP256K1_INLINE static void secp256k1_ecmult_endo_split(secp256k1_scalar *s1, secp256k1_scalar *s2, secp256k1_ge *p1, secp256k1_ge *p2) {
625  secp256k1_scalar tmp = *s1;
626  secp256k1_scalar_split_lambda(s1, s2, &tmp);
627  secp256k1_ge_mul_lambda(p2, p1);
628 
629  if (secp256k1_scalar_is_high(s1)) {
630  secp256k1_scalar_negate(s1, s1);
631  secp256k1_ge_neg(p1, p1);
632  }
633  if (secp256k1_scalar_is_high(s2)) {
634  secp256k1_scalar_negate(s2, s2);
635  secp256k1_ge_neg(p2, p2);
636  }
637 }
638 
643 static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window) {
644  size_t entries = 2*n_points + 2;
645  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
646  return (sizeof(secp256k1_gej) << bucket_window) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size;
647 }
648 
649 static int secp256k1_ecmult_pippenger_batch(const secp256k1_callback* error_callback, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) {
650  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
651  /* Use 2(n+1) with the endomorphism, when calculating batch
652  * sizes. The reason for +1 is that we add the G scalar to the list of
653  * other scalars. */
654  size_t entries = 2*n_points + 2;
655  secp256k1_ge *points;
656  secp256k1_scalar *scalars;
657  secp256k1_gej *buckets;
658  struct secp256k1_pippenger_state *state_space;
659  size_t idx = 0;
660  size_t point_idx = 0;
661  int i, j;
662  int bucket_window;
663 
664  secp256k1_gej_set_infinity(r);
665  if (inp_g_sc == NULL && n_points == 0) {
666  return 1;
667  }
668  bucket_window = secp256k1_pippenger_bucket_window(n_points);
669 
670  /* We allocate PIPPENGER_SCRATCH_OBJECTS objects on the scratch space. If
671  * these allocations change, make sure to update the
672  * PIPPENGER_SCRATCH_OBJECTS constant and pippenger_scratch_size
673  * accordingly. */
674  points = (secp256k1_ge *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*points));
675  scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*scalars));
676  state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(error_callback, scratch, sizeof(*state_space));
677  if (points == NULL || scalars == NULL || state_space == NULL) {
678  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
679  return 0;
680  }
681  state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*state_space->ps));
682  state_space->wnaf_na = (int *) secp256k1_scratch_alloc(error_callback, scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int));
683  buckets = (secp256k1_gej *) secp256k1_scratch_alloc(error_callback, scratch, (1<<bucket_window) * sizeof(*buckets));
684  if (state_space->ps == NULL || state_space->wnaf_na == NULL || buckets == NULL) {
685  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
686  return 0;
687  }
688 
689  if (inp_g_sc != NULL) {
690  scalars[0] = *inp_g_sc;
691  points[0] = secp256k1_ge_const_g;
692  idx++;
693  secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]);
694  idx++;
695  }
696 
697  while (point_idx < n_points) {
698  if (!cb(&scalars[idx], &points[idx], point_idx + cb_offset, cbdata)) {
699  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
700  return 0;
701  }
702  idx++;
703  secp256k1_ecmult_endo_split(&scalars[idx - 1], &scalars[idx], &points[idx - 1], &points[idx]);
704  idx++;
705  point_idx++;
706  }
707 
708  secp256k1_ecmult_pippenger_wnaf(buckets, bucket_window, state_space, r, scalars, points, idx);
709 
710  /* Clear data */
711  for(i = 0; (size_t)i < idx; i++) {
712  secp256k1_scalar_clear(&scalars[i]);
713  state_space->ps[i].skew_na = 0;
714  for(j = 0; j < WNAF_SIZE(bucket_window+1); j++) {
715  state_space->wnaf_na[i * WNAF_SIZE(bucket_window+1) + j] = 0;
716  }
717  }
718  for(i = 0; i < 1<<bucket_window; i++) {
719  secp256k1_gej_clear(&buckets[i]);
720  }
721  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
722  return 1;
723 }
724 
725 /* Wrapper for secp256k1_ecmult_multi_func interface */
726 static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_callback* error_callback, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
727  return secp256k1_ecmult_pippenger_batch(error_callback, scratch, r, inp_g_sc, cb, cbdata, n, 0);
728 }
729 
735 static size_t secp256k1_pippenger_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
736  size_t max_alloc = secp256k1_scratch_max_allocation(error_callback, scratch, PIPPENGER_SCRATCH_OBJECTS);
737  int bucket_window;
738  size_t res = 0;
739 
740  for (bucket_window = 1; bucket_window <= PIPPENGER_MAX_BUCKET_WINDOW; bucket_window++) {
741  size_t n_points;
742  size_t max_points = secp256k1_pippenger_bucket_window_inv(bucket_window);
743  size_t space_for_points;
744  size_t space_overhead;
745  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
746 
747  entry_size = 2*entry_size;
748  space_overhead = (sizeof(secp256k1_gej) << bucket_window) + entry_size + sizeof(struct secp256k1_pippenger_state);
749  if (space_overhead > max_alloc) {
750  break;
751  }
752  space_for_points = max_alloc - space_overhead;
753 
754  n_points = space_for_points/entry_size;
755  n_points = n_points > max_points ? max_points : n_points;
756  if (n_points > res) {
757  res = n_points;
758  }
759  if (n_points < max_points) {
760  /* A larger bucket_window may support even more points. But if we
761  * would choose that then the caller couldn't safely use any number
762  * smaller than what this function returns */
763  break;
764  }
765  }
766  return res;
767 }
768 
769 /* Computes ecmult_multi by simply multiplying and adding each point. Does not
770  * require a scratch space */
771 static int secp256k1_ecmult_multi_simple_var(secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points) {
772  size_t point_idx;
773  secp256k1_scalar szero;
774  secp256k1_gej tmpj;
775 
776  secp256k1_scalar_set_int(&szero, 0);
777  secp256k1_gej_set_infinity(r);
778  secp256k1_gej_set_infinity(&tmpj);
779  /* r = inp_g_sc*G */
780  secp256k1_ecmult(r, &tmpj, &szero, inp_g_sc);
781  for (point_idx = 0; point_idx < n_points; point_idx++) {
782  secp256k1_ge point;
783  secp256k1_gej pointj;
784  secp256k1_scalar scalar;
785  if (!cb(&scalar, &point, point_idx, cbdata)) {
786  return 0;
787  }
788  /* r += scalar*point */
789  secp256k1_gej_set_ge(&pointj, &point);
790  secp256k1_ecmult(&tmpj, &pointj, &scalar, NULL);
791  secp256k1_gej_add_var(r, r, &tmpj, NULL);
792  }
793  return 1;
794 }
795 
796 /* Compute the number of batches and the batch size given the maximum batch size and the
797  * total number of points */
798 static int secp256k1_ecmult_multi_batch_size_helper(size_t *n_batches, size_t *n_batch_points, size_t max_n_batch_points, size_t n) {
799  if (max_n_batch_points == 0) {
800  return 0;
801  }
802  if (max_n_batch_points > ECMULT_MAX_POINTS_PER_BATCH) {
803  max_n_batch_points = ECMULT_MAX_POINTS_PER_BATCH;
804  }
805  if (n == 0) {
806  *n_batches = 0;
807  *n_batch_points = 0;
808  return 1;
809  }
810  /* Compute ceil(n/max_n_batch_points) and ceil(n/n_batches) */
811  *n_batches = 1 + (n - 1) / max_n_batch_points;
812  *n_batch_points = 1 + (n - 1) / *n_batches;
813  return 1;
814 }
815 
817 static int secp256k1_ecmult_multi_var(const secp256k1_callback* error_callback, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
818  size_t i;
819 
820  int (*f)(const secp256k1_callback* error_callback, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t);
821  size_t n_batches;
822  size_t n_batch_points;
823 
824  secp256k1_gej_set_infinity(r);
825  if (inp_g_sc == NULL && n == 0) {
826  return 1;
827  } else if (n == 0) {
828  secp256k1_scalar szero;
829  secp256k1_scalar_set_int(&szero, 0);
830  secp256k1_ecmult(r, r, &szero, inp_g_sc);
831  return 1;
832  }
833  if (scratch == NULL) {
834  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
835  }
836 
837  /* Compute the batch sizes for Pippenger's algorithm given a scratch space. If it's greater than
838  * a threshold use Pippenger's algorithm. Otherwise use Strauss' algorithm.
839  * As a first step check if there's enough space for Pippenger's algo (which requires less space
840  * than Strauss' algo) and if not, use the simple algorithm. */
841  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(error_callback, scratch), n)) {
842  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
843  }
844  if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) {
845  f = secp256k1_ecmult_pippenger_batch;
846  } else {
847  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(error_callback, scratch), n)) {
848  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
849  }
850  f = secp256k1_ecmult_strauss_batch;
851  }
852  for(i = 0; i < n_batches; i++) {
853  size_t nbp = n < n_batch_points ? n : n_batch_points;
854  size_t offset = n_batch_points*i;
855  secp256k1_gej tmp;
856  if (!f(error_callback, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) {
857  return 0;
858  }
859  secp256k1_gej_add_var(r, r, &tmp, NULL);
860  n -= nbp;
861  }
862  return 1;
863 }
864 
865 #endif /* SECP256K1_ECMULT_IMPL_H */
const char * res
Definition: hmac_keccak.cpp:41
#define VERIFY_CHECK(cond)
Definition: util.h:96
struct secp256k1_strauss_point_state * ps
Definition: ecmult_impl.h:228
#define WNAF_BITS
Definition: ecmult_impl.h:44
#define ECMULT_TABLE_SIZE(w)
Definition: ecmult.h:41
int(* secp256k1_ecmult_multi_func)(const secp256k1_callback *error_callback, secp256k1_scratch *, secp256k1_gej *, const secp256k1_scalar *, secp256k1_ecmult_multi_callback cb, void *, size_t)
Definition: ecmult_impl.h:816
secp256k1_fe x
Definition: group.h:29
#define PIPPENGER_MAX_BUCKET_WINDOW
Definition: ecmult_impl.h:52
secp256k1_fe * aux
Definition: ecmult_impl.h:226
#define WINDOW_G
const secp256k1_ge_storage secp256k1_pre_g_128[ECMULT_TABLE_SIZE(WINDOW_G)]
#define SECP256K1_INLINE
Definition: secp256k1.h:131
#define PIPPENGER_SCRATCH_OBJECTS
Definition: ecmult_impl.h:49
#define ECMULT_PIPPENGER_THRESHOLD
Definition: ecmult_impl.h:55
int infinity
Definition: group.h:32
const secp256k1_ge_storage secp256k1_pre_g[ECMULT_TABLE_SIZE(WINDOW_G)]
#define ECMULT_MAX_POINTS_PER_BATCH
Definition: ecmult_impl.h:57
#define SECP256K1_ECMULT_TABLE_VERIFY(n, w)
Definition: ecmult_impl.h:117
#define WINDOW_A
Definition: ecmult_impl.h:32
#define STRAUSS_SCRATCH_OBJECTS
Definition: ecmult_impl.h:50
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
#define SIZE_MAX
Definition: stdint.h:252
secp256k1_ge * pre_a
Definition: ecmult_impl.h:227
Definition: blake256.h:37
secp256k1_fe z
Definition: group.h:31
#define WNAF_SIZE(w)
Definition: ecmult_impl.h:46
struct secp256k1_pippenger_point_state * ps
Definition: ecmult_impl.h:485
int() secp256k1_ecmult_multi_callback(secp256k1_scalar *sc, secp256k1_ge *pt, size_t idx, void *data)
Definition: ecmult.h:46
secp256k1_fe y
Definition: group.h:30
secp256k1_fe y
Definition: group.h:18
unsigned int bits[ATOMS]
Definition: rctTypes.h:136