Bitcoin Core  0.20.99
P2P Digital Currency
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 http://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 
18 #if defined(EXHAUSTIVE_TEST_ORDER)
19 /* We need to lower these values for exhaustive tests because
20  * the tables cannot have infinities in them (this breaks the
21  * affine-isomorphism stuff which tracks z-ratios) */
22 # if EXHAUSTIVE_TEST_ORDER > 128
23 # define WINDOW_A 5
24 # define WINDOW_G 8
25 # elif EXHAUSTIVE_TEST_ORDER > 8
26 # define WINDOW_A 4
27 # define WINDOW_G 4
28 # else
29 # define WINDOW_A 2
30 # define WINDOW_G 2
31 # endif
32 #else
33 /* optimal for 128-bit and 256-bit exponents. */
34 # define WINDOW_A 5
35 
44 # define WINDOW_G ECMULT_WINDOW_SIZE
45 #endif
46 
47 /* Noone will ever need more than a window size of 24. The code might
48  * be correct for larger values of ECMULT_WINDOW_SIZE but this is not
49  * not tested.
50  *
51  * The following limitations are known, and there are probably more:
52  * If WINDOW_G > 27 and size_t has 32 bits, then the code is incorrect
53  * because the size of the memory object that we allocate (in bytes)
54  * will not fit in a size_t.
55  * If WINDOW_G > 31 and int has 32 bits, then the code is incorrect
56  * because certain expressions will overflow.
57  */
58 #if ECMULT_WINDOW_SIZE < 2 || ECMULT_WINDOW_SIZE > 24
59 # error Set ECMULT_WINDOW_SIZE to an integer in range [2..24].
60 #endif
61 
62 #ifdef USE_ENDOMORPHISM
63  #define WNAF_BITS 128
64 #else
65  #define WNAF_BITS 256
66 #endif
67 #define WNAF_SIZE_BITS(bits, w) (((bits) + (w) - 1) / (w))
68 #define WNAF_SIZE(w) WNAF_SIZE_BITS(WNAF_BITS, w)
69 
71 #define ECMULT_TABLE_SIZE(w) (1 << ((w)-2))
72 
73 /* The number of objects allocated on the scratch space for ecmult_multi algorithms */
74 #define PIPPENGER_SCRATCH_OBJECTS 6
75 #define STRAUSS_SCRATCH_OBJECTS 6
76 
77 #define PIPPENGER_MAX_BUCKET_WINDOW 12
78 
79 /* Minimum number of points for which pippenger_wnaf is faster than strauss wnaf */
80 #ifdef USE_ENDOMORPHISM
81  #define ECMULT_PIPPENGER_THRESHOLD 88
82 #else
83  #define ECMULT_PIPPENGER_THRESHOLD 160
84 #endif
85 
86 #ifdef USE_ENDOMORPHISM
87  #define ECMULT_MAX_POINTS_PER_BATCH 5000000
88 #else
89  #define ECMULT_MAX_POINTS_PER_BATCH 10000000
90 #endif
91 
98  secp256k1_gej d;
99  secp256k1_ge a_ge, d_ge;
100  int i;
101 
102  VERIFY_CHECK(!a->infinity);
103 
104  secp256k1_gej_double_var(&d, a, NULL);
105 
106  /*
107  * Perform the additions on an isomorphism where 'd' is affine: drop the z coordinate
108  * of 'd', and scale the 1P starting value's x/y coordinates without changing its z.
109  */
110  d_ge.x = d.x;
111  d_ge.y = d.y;
112  d_ge.infinity = 0;
113 
114  secp256k1_ge_set_gej_zinv(&a_ge, a, &d.z);
115  prej[0].x = a_ge.x;
116  prej[0].y = a_ge.y;
117  prej[0].z = a->z;
118  prej[0].infinity = 0;
119 
120  zr[0] = d.z;
121  for (i = 1; i < n; i++) {
122  secp256k1_gej_add_ge_var(&prej[i], &prej[i-1], &d_ge, &zr[i]);
123  }
124 
125  /*
126  * Each point in 'prej' has a z coordinate too small by a factor of 'd.z'. Only
127  * the final point's z coordinate is actually used though, so just update that.
128  */
129  secp256k1_fe_mul(&prej[n-1].z, &prej[n-1].z, &d.z);
130 }
131 
150 
151  /* Compute the odd multiples in Jacobian form. */
153  /* Bring them to the same Z denominator. */
155 }
156 
158  secp256k1_gej d;
159  secp256k1_ge d_ge, p_ge;
160  secp256k1_gej pj;
161  secp256k1_fe zi;
162  secp256k1_fe zr;
163  secp256k1_fe dx_over_dz_squared;
164  int i;
165 
166  VERIFY_CHECK(!a->infinity);
167 
168  secp256k1_gej_double_var(&d, a, NULL);
169 
170  /* First, we perform all the additions in an isomorphic curve obtained by multiplying
171  * all `z` coordinates by 1/`d.z`. In these coordinates `d` is affine so we can use
172  * `secp256k1_gej_add_ge_var` to perform the additions. For each addition, we store
173  * the resulting y-coordinate and the z-ratio, since we only have enough memory to
174  * store two field elements. These are sufficient to efficiently undo the isomorphism
175  * and recompute all the `x`s.
176  */
177  d_ge.x = d.x;
178  d_ge.y = d.y;
179  d_ge.infinity = 0;
180 
181  secp256k1_ge_set_gej_zinv(&p_ge, a, &d.z);
182  pj.x = p_ge.x;
183  pj.y = p_ge.y;
184  pj.z = a->z;
185  pj.infinity = 0;
186 
187  for (i = 0; i < (n - 1); i++) {
189  secp256k1_fe_to_storage(&pre[i].y, &pj.y);
190  secp256k1_gej_add_ge_var(&pj, &pj, &d_ge, &zr);
192  secp256k1_fe_to_storage(&pre[i].x, &zr);
193  }
194 
195  /* Invert d.z in the same batch, preserving pj.z so we can extract 1/d.z */
196  secp256k1_fe_mul(&zi, &pj.z, &d.z);
197  secp256k1_fe_inv_var(&zi, &zi);
198 
199  /* Directly set `pre[n - 1]` to `pj`, saving the inverted z-coordinate so
200  * that we can combine it with the saved z-ratios to compute the other zs
201  * without any more inversions. */
202  secp256k1_ge_set_gej_zinv(&p_ge, &pj, &zi);
203  secp256k1_ge_to_storage(&pre[n - 1], &p_ge);
204 
205  /* Compute the actual x-coordinate of D, which will be needed below. */
206  secp256k1_fe_mul(&d.z, &zi, &pj.z); /* d.z = 1/d.z */
207  secp256k1_fe_sqr(&dx_over_dz_squared, &d.z);
208  secp256k1_fe_mul(&dx_over_dz_squared, &dx_over_dz_squared, &d.x);
209 
210  /* Going into the second loop, we have set `pre[n-1]` to its final affine
211  * form, but still need to set `pre[i]` for `i` in 0 through `n-2`. We
212  * have `zi = (p.z * d.z)^-1`, where
213  *
214  * `p.z` is the z-coordinate of the point on the isomorphic curve
215  * which was ultimately assigned to `pre[n-1]`.
216  * `d.z` is the multiplier that must be applied to all z-coordinates
217  * to move from our isomorphic curve back to secp256k1; so the
218  * product `p.z * d.z` is the z-coordinate of the secp256k1
219  * point assigned to `pre[n-1]`.
220  *
221  * All subsequent inverse-z-coordinates can be obtained by multiplying this
222  * factor by successive z-ratios, which is much more efficient than directly
223  * computing each one.
224  *
225  * Importantly, these inverse-zs will be coordinates of points on secp256k1,
226  * while our other stored values come from computations on the isomorphic
227  * curve. So in the below loop, we will take care not to actually use `zi`
228  * or any derived values until we're back on secp256k1.
229  */
230  i = n - 1;
231  while (i > 0) {
232  secp256k1_fe zi2, zi3;
233  const secp256k1_fe *rzr;
234  i--;
235 
236  secp256k1_ge_from_storage(&p_ge, &pre[i]);
237 
238  /* For each remaining point, we extract the z-ratio from the stored
239  * x-coordinate, compute its z^-1 from that, and compute the full
240  * point from that. */
241  rzr = &p_ge.x;
242  secp256k1_fe_mul(&zi, &zi, rzr);
243  secp256k1_fe_sqr(&zi2, &zi);
244  secp256k1_fe_mul(&zi3, &zi2, &zi);
245  /* To compute the actual x-coordinate, we use the stored z ratio and
246  * y-coordinate, which we obtained from `secp256k1_gej_add_ge_var`
247  * in the loop above, as well as the inverse of the square of its
248  * z-coordinate. We store the latter in the `zi2` variable, which is
249  * computed iteratively starting from the overall Z inverse then
250  * multiplying by each z-ratio in turn.
251  *
252  * Denoting the z-ratio as `rzr`, we observe that it is equal to `h`
253  * from the inside of the above `gej_add_ge_var` call. This satisfies
254  *
255  * rzr = d_x * z^2 - x * d_z^2
256  *
257  * where (`d_x`, `d_z`) are Jacobian coordinates of `D` and `(x, z)`
258  * are Jacobian coordinates of our desired point -- except both are on
259  * the isomorphic curve that we were using when we called `gej_add_ge_var`.
260  * To get back to secp256k1, we must multiply both `z`s by `d_z`, or
261  * equivalently divide both `x`s by `d_z^2`. Our equation then becomes
262  *
263  * rzr = d_x * z^2 / d_z^2 - x
264  *
265  * (The left-hand-side, being a ratio of z-coordinates, is unaffected
266  * by the isomorphism.)
267  *
268  * Rearranging to solve for `x`, we have
269  *
270  * x = d_x * z^2 / d_z^2 - rzr
271  *
272  * But what we actually want is the affine coordinate `X = x/z^2`,
273  * which will satisfy
274  *
275  * X = d_x / d_z^2 - rzr / z^2
276  * = dx_over_dz_squared - rzr * zi2
277  */
278  secp256k1_fe_mul(&p_ge.x, rzr, &zi2);
279  secp256k1_fe_negate(&p_ge.x, &p_ge.x, 1);
280  secp256k1_fe_add(&p_ge.x, &dx_over_dz_squared);
281  /* y is stored_y/z^3, as we expect */
282  secp256k1_fe_mul(&p_ge.y, &p_ge.y, &zi3);
283  /* Store */
284  secp256k1_ge_to_storage(&pre[i], &p_ge);
285  }
286 }
287 
290 #define ECMULT_TABLE_GET_GE(r,pre,n,w) do { \
291  VERIFY_CHECK(((n) & 1) == 1); \
292  VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
293  VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
294  if ((n) > 0) { \
295  *(r) = (pre)[((n)-1)/2]; \
296  } else { \
297  *(r) = (pre)[(-(n)-1)/2]; \
298  secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
299  } \
300 } while(0)
301 
302 #define ECMULT_TABLE_GET_GE_STORAGE(r,pre,n,w) do { \
303  VERIFY_CHECK(((n) & 1) == 1); \
304  VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
305  VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
306  if ((n) > 0) { \
307  secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
308  } else { \
309  secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
310  secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
311  } \
312 } while(0)
313 
315  ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G))
316 #ifdef USE_ENDOMORPHISM
317  + ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G))
318 #endif
319  ;
320 
322  ctx->pre_g = NULL;
323 #ifdef USE_ENDOMORPHISM
324  ctx->pre_g_128 = NULL;
325 #endif
326 }
327 
329  secp256k1_gej gj;
330  void* const base = *prealloc;
331  size_t const prealloc_size = SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE;
332 
333  if (ctx->pre_g != NULL) {
334  return;
335  }
336 
337  /* get the generator */
339 
340  {
341  size_t size = sizeof((*ctx->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G));
342  /* check for overflow */
343  VERIFY_CHECK(size / sizeof((*ctx->pre_g)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)));
344  ctx->pre_g = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size);
345  }
346 
347  /* precompute the tables with odd multiples */
349 
350 #ifdef USE_ENDOMORPHISM
351  {
352  secp256k1_gej g_128j;
353  int i;
354 
355  size_t size = sizeof((*ctx->pre_g_128)[0]) * ((size_t) ECMULT_TABLE_SIZE(WINDOW_G));
356  /* check for overflow */
357  VERIFY_CHECK(size / sizeof((*ctx->pre_g_128)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)));
358  ctx->pre_g_128 = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size);
359 
360  /* calculate 2^128*generator */
361  g_128j = gj;
362  for (i = 0; i < 128; i++) {
363  secp256k1_gej_double_var(&g_128j, &g_128j, NULL);
364  }
366  }
367 #endif
368 }
369 
371  if (src->pre_g != NULL) {
372  /* We cast to void* first to suppress a -Wcast-align warning. */
373  dst->pre_g = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g) - (unsigned char*)src));
374  }
375 #ifdef USE_ENDOMORPHISM
376  if (src->pre_g_128 != NULL) {
377  dst->pre_g_128 = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g_128) - (unsigned char*)src));
378  }
379 #endif
380 }
381 
383  return ctx->pre_g != NULL;
384 }
385 
388 }
389 
397 static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) {
399  int last_set_bit = -1;
400  int bit = 0;
401  int sign = 1;
402  int carry = 0;
403 
404  VERIFY_CHECK(wnaf != NULL);
405  VERIFY_CHECK(0 <= len && len <= 256);
406  VERIFY_CHECK(a != NULL);
407  VERIFY_CHECK(2 <= w && w <= 31);
408 
409  memset(wnaf, 0, len * sizeof(wnaf[0]));
410 
411  s = *a;
412  if (secp256k1_scalar_get_bits(&s, 255, 1)) {
413  secp256k1_scalar_negate(&s, &s);
414  sign = -1;
415  }
416 
417  while (bit < len) {
418  int now;
419  int word;
420  if (secp256k1_scalar_get_bits(&s, bit, 1) == (unsigned int)carry) {
421  bit++;
422  continue;
423  }
424 
425  now = w;
426  if (now > len - bit) {
427  now = len - bit;
428  }
429 
430  word = secp256k1_scalar_get_bits_var(&s, bit, now) + carry;
431 
432  carry = (word >> (w-1)) & 1;
433  word -= carry << w;
434 
435  wnaf[bit] = sign * word;
436  last_set_bit = bit;
437 
438  bit += now;
439  }
440 #ifdef VERIFY
441  CHECK(carry == 0);
442  while (bit < 256) {
443  CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0);
444  }
445 #endif
446  return last_set_bit + 1;
447 }
448 
450 #ifdef USE_ENDOMORPHISM
451  secp256k1_scalar na_1, na_lam;
452  int wnaf_na_1[130];
453  int wnaf_na_lam[130];
454  int bits_na_1;
455  int bits_na_lam;
456 #else
457  int wnaf_na[256];
458  int bits_na;
459 #endif
460  size_t input_pos;
461 };
462 
467 #ifdef USE_ENDOMORPHISM
468  secp256k1_ge* pre_a_lam;
469 #endif
471 };
472 
473 static void secp256k1_ecmult_strauss_wnaf(const secp256k1_ecmult_context *ctx, const struct secp256k1_strauss_state *state, secp256k1_gej *r, int num, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
474  secp256k1_ge tmpa;
475  secp256k1_fe Z;
476 #ifdef USE_ENDOMORPHISM
477  /* Splitted G factors. */
478  secp256k1_scalar ng_1, ng_128;
479  int wnaf_ng_1[129];
480  int bits_ng_1 = 0;
481  int wnaf_ng_128[129];
482  int bits_ng_128 = 0;
483 #else
484  int wnaf_ng[256];
485  int bits_ng = 0;
486 #endif
487  int i;
488  int bits = 0;
489  int np;
490  int no = 0;
491 
492  for (np = 0; np < num; ++np) {
493  if (secp256k1_scalar_is_zero(&na[np]) || secp256k1_gej_is_infinity(&a[np])) {
494  continue;
495  }
496  state->ps[no].input_pos = np;
497 #ifdef USE_ENDOMORPHISM
498  /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
499  secp256k1_scalar_split_lambda(&state->ps[no].na_1, &state->ps[no].na_lam, &na[np]);
500 
501  /* build wnaf representation for na_1 and na_lam. */
502  state->ps[no].bits_na_1 = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_1, 130, &state->ps[no].na_1, WINDOW_A);
503  state->ps[no].bits_na_lam = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_lam, 130, &state->ps[no].na_lam, WINDOW_A);
504  VERIFY_CHECK(state->ps[no].bits_na_1 <= 130);
505  VERIFY_CHECK(state->ps[no].bits_na_lam <= 130);
506  if (state->ps[no].bits_na_1 > bits) {
507  bits = state->ps[no].bits_na_1;
508  }
509  if (state->ps[no].bits_na_lam > bits) {
510  bits = state->ps[no].bits_na_lam;
511  }
512 #else
513  /* build wnaf representation for na. */
514  state->ps[no].bits_na = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na, 256, &na[np], WINDOW_A);
515  if (state->ps[no].bits_na > bits) {
516  bits = state->ps[no].bits_na;
517  }
518 #endif
519  ++no;
520  }
521 
522  /* Calculate odd multiples of a.
523  * All multiples are brought to the same Z 'denominator', which is stored
524  * in Z. Due to secp256k1' isomorphism we can do all operations pretending
525  * that the Z coordinate was 1, use affine addition formulae, and correct
526  * the Z coordinate of the result once at the end.
527  * The exception is the precomputed G table points, which are actually
528  * affine. Compared to the base used for other points, they have a Z ratio
529  * of 1/Z, so we can use secp256k1_gej_add_zinv_var, which uses the same
530  * isomorphism to efficiently add with a known Z inverse.
531  */
532  if (no > 0) {
533  /* Compute the odd multiples in Jacobian form. */
535  for (np = 1; np < no; ++np) {
536  secp256k1_gej tmp = a[state->ps[np].input_pos];
537 #ifdef VERIFY
539 #endif
540  secp256k1_gej_rescale(&tmp, &(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
542  secp256k1_fe_mul(state->zr + np * ECMULT_TABLE_SIZE(WINDOW_A), state->zr + np * ECMULT_TABLE_SIZE(WINDOW_A), &(a[state->ps[np].input_pos].z));
543  }
544  /* Bring them to the same Z denominator. */
545  secp256k1_ge_globalz_set_table_gej(ECMULT_TABLE_SIZE(WINDOW_A) * no, state->pre_a, &Z, state->prej, state->zr);
546  } else {
547  secp256k1_fe_set_int(&Z, 1);
548  }
549 
550 #ifdef USE_ENDOMORPHISM
551  for (np = 0; np < no; ++np) {
552  for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
553  secp256k1_ge_mul_lambda(&state->pre_a_lam[np * ECMULT_TABLE_SIZE(WINDOW_A) + i], &state->pre_a[np * ECMULT_TABLE_SIZE(WINDOW_A) + i]);
554  }
555  }
556 
557  if (ng) {
558  /* 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) */
559  secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
560 
561  /* Build wnaf representation for ng_1 and ng_128 */
562  bits_ng_1 = secp256k1_ecmult_wnaf(wnaf_ng_1, 129, &ng_1, WINDOW_G);
563  bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, 129, &ng_128, WINDOW_G);
564  if (bits_ng_1 > bits) {
565  bits = bits_ng_1;
566  }
567  if (bits_ng_128 > bits) {
568  bits = bits_ng_128;
569  }
570  }
571 #else
572  if (ng) {
573  bits_ng = secp256k1_ecmult_wnaf(wnaf_ng, 256, ng, WINDOW_G);
574  if (bits_ng > bits) {
575  bits = bits_ng;
576  }
577  }
578 #endif
579 
581 
582  for (i = bits - 1; i >= 0; i--) {
583  int n;
584  secp256k1_gej_double_var(r, r, NULL);
585 #ifdef USE_ENDOMORPHISM
586  for (np = 0; np < no; ++np) {
587  if (i < state->ps[np].bits_na_1 && (n = state->ps[np].wnaf_na_1[i])) {
588  ECMULT_TABLE_GET_GE(&tmpa, state->pre_a + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
589  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
590  }
591  if (i < state->ps[np].bits_na_lam && (n = state->ps[np].wnaf_na_lam[i])) {
592  ECMULT_TABLE_GET_GE(&tmpa, state->pre_a_lam + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
593  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
594  }
595  }
596  if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
597  ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g, n, WINDOW_G);
598  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
599  }
600  if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
601  ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g_128, n, WINDOW_G);
602  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
603  }
604 #else
605  for (np = 0; np < no; ++np) {
606  if (i < state->ps[np].bits_na && (n = state->ps[np].wnaf_na[i])) {
607  ECMULT_TABLE_GET_GE(&tmpa, state->pre_a + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
608  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
609  }
610  }
611  if (i < bits_ng && (n = wnaf_ng[i])) {
612  ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g, n, WINDOW_G);
613  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
614  }
615 #endif
616  }
617 
618  if (!r->infinity) {
619  secp256k1_fe_mul(&r->z, &r->z, &Z);
620  }
621 }
622 
627  struct secp256k1_strauss_point_state ps[1];
628 #ifdef USE_ENDOMORPHISM
630 #endif
631  struct secp256k1_strauss_state state;
632 
633  state.prej = prej;
634  state.zr = zr;
635  state.pre_a = pre_a;
636 #ifdef USE_ENDOMORPHISM
637  state.pre_a_lam = pre_a_lam;
638 #endif
639  state.ps = ps;
640  secp256k1_ecmult_strauss_wnaf(ctx, &state, r, 1, a, na, ng);
641 }
642 
643 static size_t secp256k1_strauss_scratch_size(size_t n_points) {
644 #ifdef USE_ENDOMORPHISM
645  static const size_t point_size = (2 * sizeof(secp256k1_ge) + sizeof(secp256k1_gej) + sizeof(secp256k1_fe)) * ECMULT_TABLE_SIZE(WINDOW_A) + sizeof(struct secp256k1_strauss_point_state) + sizeof(secp256k1_gej) + sizeof(secp256k1_scalar);
646 #else
647  static const size_t point_size = (sizeof(secp256k1_ge) + sizeof(secp256k1_gej) + sizeof(secp256k1_fe)) * ECMULT_TABLE_SIZE(WINDOW_A) + sizeof(struct secp256k1_strauss_point_state) + sizeof(secp256k1_gej) + sizeof(secp256k1_scalar);
648 #endif
649  return n_points*point_size;
650 }
651 
652 static int secp256k1_ecmult_strauss_batch(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *ctx, 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) {
653  secp256k1_gej* points;
654  secp256k1_scalar* scalars;
655  struct secp256k1_strauss_state state;
656  size_t i;
657  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
658 
660  if (inp_g_sc == NULL && n_points == 0) {
661  return 1;
662  }
663 
664  points = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_gej));
665  scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_scalar));
666  state.prej = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_gej));
667  state.zr = (secp256k1_fe*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe));
668 #ifdef USE_ENDOMORPHISM
669  state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * 2 * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
670  state.pre_a_lam = state.pre_a + n_points * ECMULT_TABLE_SIZE(WINDOW_A);
671 #else
672  state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
673 #endif
674  state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
675 
676  if (points == NULL || scalars == NULL || state.prej == NULL || state.zr == NULL || state.pre_a == NULL) {
677  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
678  return 0;
679  }
680 
681  for (i = 0; i < n_points; i++) {
682  secp256k1_ge point;
683  if (!cb(&scalars[i], &point, i+cb_offset, cbdata)) {
684  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
685  return 0;
686  }
687  secp256k1_gej_set_ge(&points[i], &point);
688  }
689  secp256k1_ecmult_strauss_wnaf(ctx, &state, r, n_points, points, scalars, inp_g_sc);
690  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
691  return 1;
692 }
693 
694 /* Wrapper for secp256k1_ecmult_multi_func interface */
695 static int secp256k1_ecmult_strauss_batch_single(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
696  return secp256k1_ecmult_strauss_batch(error_callback, actx, scratch, r, inp_g_sc, cb, cbdata, n, 0);
697 }
698 
699 static size_t secp256k1_strauss_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
701 }
702 
710 static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w) {
711  int skew = 0;
712  int pos;
713  int max_pos;
714  int last_w;
715  const secp256k1_scalar *work = s;
716 
717  if (secp256k1_scalar_is_zero(s)) {
718  for (pos = 0; pos < WNAF_SIZE(w); pos++) {
719  wnaf[pos] = 0;
720  }
721  return 0;
722  }
723 
724  if (secp256k1_scalar_is_even(s)) {
725  skew = 1;
726  }
727 
728  wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
729  /* Compute last window size. Relevant when window size doesn't divide the
730  * number of bits in the scalar */
731  last_w = WNAF_BITS - (WNAF_SIZE(w) - 1) * w;
732 
733  /* Store the position of the first nonzero word in max_pos to allow
734  * skipping leading zeros when calculating the wnaf. */
735  for (pos = WNAF_SIZE(w) - 1; pos > 0; pos--) {
736  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
737  if(val != 0) {
738  break;
739  }
740  wnaf[pos] = 0;
741  }
742  max_pos = pos;
743  pos = 1;
744 
745  while (pos <= max_pos) {
746  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
747  if ((val & 1) == 0) {
748  wnaf[pos - 1] -= (1 << w);
749  wnaf[pos] = (val + 1);
750  } else {
751  wnaf[pos] = val;
752  }
753  /* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
754  * is strictly negative or strictly positive respectively. Only change
755  * coefficients at previous positions because above code assumes that
756  * wnaf[pos - 1] is odd.
757  */
758  if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) || (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
759  if (wnaf[pos - 1] == 1) {
760  wnaf[pos - 2] += 1 << w;
761  } else {
762  wnaf[pos - 2] -= 1 << w;
763  }
764  wnaf[pos - 1] = 0;
765  }
766  ++pos;
767  }
768 
769  return skew;
770 }
771 
773  int skew_na;
774  size_t input_pos;
775 };
776 
778  int *wnaf_na;
780 };
781 
782 /*
783  * pippenger_wnaf computes the result of a multi-point multiplication as
784  * follows: The scalars are brought into wnaf with n_wnaf elements each. Then
785  * for every i < n_wnaf, first each point is added to a "bucket" corresponding
786  * to the point's wnaf[i]. Second, the buckets are added together such that
787  * r += 1*bucket[0] + 3*bucket[1] + 5*bucket[2] + ...
788  */
789 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) {
790  size_t n_wnaf = WNAF_SIZE(bucket_window+1);
791  size_t np;
792  size_t no = 0;
793  int i;
794  int j;
795 
796  for (np = 0; np < num; ++np) {
797  if (secp256k1_scalar_is_zero(&sc[np]) || secp256k1_ge_is_infinity(&pt[np])) {
798  continue;
799  }
800  state->ps[no].input_pos = np;
801  state->ps[no].skew_na = secp256k1_wnaf_fixed(&state->wnaf_na[no*n_wnaf], &sc[np], bucket_window+1);
802  no++;
803  }
805 
806  if (no == 0) {
807  return 1;
808  }
809 
810  for (i = n_wnaf - 1; i >= 0; i--) {
811  secp256k1_gej running_sum;
812 
813  for(j = 0; j < ECMULT_TABLE_SIZE(bucket_window+2); j++) {
814  secp256k1_gej_set_infinity(&buckets[j]);
815  }
816 
817  for (np = 0; np < no; ++np) {
818  int n = state->wnaf_na[np*n_wnaf + i];
819  struct secp256k1_pippenger_point_state point_state = state->ps[np];
820  secp256k1_ge tmp;
821  int idx;
822 
823  if (i == 0) {
824  /* correct for wnaf skew */
825  int skew = point_state.skew_na;
826  if (skew) {
827  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
828  secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);
829  }
830  }
831  if (n > 0) {
832  idx = (n - 1)/2;
833  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
834  } else if (n < 0) {
835  idx = -(n + 1)/2;
836  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
837  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);
838  }
839  }
840 
841  for(j = 0; j < bucket_window; j++) {
842  secp256k1_gej_double_var(r, r, NULL);
843  }
844 
845  secp256k1_gej_set_infinity(&running_sum);
846  /* Accumulate the sum: bucket[0] + 3*bucket[1] + 5*bucket[2] + 7*bucket[3] + ...
847  * = bucket[0] + bucket[1] + bucket[2] + bucket[3] + ...
848  * + 2 * (bucket[1] + 2*bucket[2] + 3*bucket[3] + ...)
849  * using an intermediate running sum:
850  * running_sum = bucket[0] + bucket[1] + bucket[2] + ...
851  *
852  * The doubling is done implicitly by deferring the final window doubling (of 'r').
853  */
854  for(j = ECMULT_TABLE_SIZE(bucket_window+2) - 1; j > 0; j--) {
855  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[j], NULL);
856  secp256k1_gej_add_var(r, r, &running_sum, NULL);
857  }
858 
859  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[0], NULL);
860  secp256k1_gej_double_var(r, r, NULL);
861  secp256k1_gej_add_var(r, r, &running_sum, NULL);
862  }
863  return 1;
864 }
865 
870 static int secp256k1_pippenger_bucket_window(size_t n) {
871 #ifdef USE_ENDOMORPHISM
872  if (n <= 1) {
873  return 1;
874  } else if (n <= 4) {
875  return 2;
876  } else if (n <= 20) {
877  return 3;
878  } else if (n <= 57) {
879  return 4;
880  } else if (n <= 136) {
881  return 5;
882  } else if (n <= 235) {
883  return 6;
884  } else if (n <= 1260) {
885  return 7;
886  } else if (n <= 4420) {
887  return 9;
888  } else if (n <= 7880) {
889  return 10;
890  } else if (n <= 16050) {
891  return 11;
892  } else {
894  }
895 #else
896  if (n <= 1) {
897  return 1;
898  } else if (n <= 11) {
899  return 2;
900  } else if (n <= 45) {
901  return 3;
902  } else if (n <= 100) {
903  return 4;
904  } else if (n <= 275) {
905  return 5;
906  } else if (n <= 625) {
907  return 6;
908  } else if (n <= 1850) {
909  return 7;
910  } else if (n <= 3400) {
911  return 8;
912  } else if (n <= 9630) {
913  return 9;
914  } else if (n <= 17900) {
915  return 10;
916  } else if (n <= 32800) {
917  return 11;
918  } else {
920  }
921 #endif
922 }
923 
927 static size_t secp256k1_pippenger_bucket_window_inv(int bucket_window) {
928  switch(bucket_window) {
929 #ifdef USE_ENDOMORPHISM
930  case 1: return 1;
931  case 2: return 4;
932  case 3: return 20;
933  case 4: return 57;
934  case 5: return 136;
935  case 6: return 235;
936  case 7: return 1260;
937  case 8: return 1260;
938  case 9: return 4420;
939  case 10: return 7880;
940  case 11: return 16050;
941  case PIPPENGER_MAX_BUCKET_WINDOW: return SIZE_MAX;
942 #else
943  case 1: return 1;
944  case 2: return 11;
945  case 3: return 45;
946  case 4: return 100;
947  case 5: return 275;
948  case 6: return 625;
949  case 7: return 1850;
950  case 8: return 3400;
951  case 9: return 9630;
952  case 10: return 17900;
953  case 11: return 32800;
954  case PIPPENGER_MAX_BUCKET_WINDOW: return SIZE_MAX;
955 #endif
956  }
957  return 0;
958 }
959 
960 
961 #ifdef USE_ENDOMORPHISM
962 SECP256K1_INLINE static void secp256k1_ecmult_endo_split(secp256k1_scalar *s1, secp256k1_scalar *s2, secp256k1_ge *p1, secp256k1_ge *p2) {
963  secp256k1_scalar tmp = *s1;
964  secp256k1_scalar_split_lambda(s1, s2, &tmp);
965  secp256k1_ge_mul_lambda(p2, p1);
966 
967  if (secp256k1_scalar_is_high(s1)) {
968  secp256k1_scalar_negate(s1, s1);
969  secp256k1_ge_neg(p1, p1);
970  }
971  if (secp256k1_scalar_is_high(s2)) {
972  secp256k1_scalar_negate(s2, s2);
973  secp256k1_ge_neg(p2, p2);
974  }
975 }
976 #endif
977 
982 static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window) {
983 #ifdef USE_ENDOMORPHISM
984  size_t entries = 2*n_points + 2;
985 #else
986  size_t entries = n_points + 1;
987 #endif
988  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
989  return (sizeof(secp256k1_gej) << bucket_window) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size;
990 }
991 
992 static int secp256k1_ecmult_pippenger_batch(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *ctx, 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) {
993  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
994  /* Use 2(n+1) with the endomorphism, n+1 without, when calculating batch
995  * sizes. The reason for +1 is that we add the G scalar to the list of
996  * other scalars. */
997 #ifdef USE_ENDOMORPHISM
998  size_t entries = 2*n_points + 2;
999 #else
1000  size_t entries = n_points + 1;
1001 #endif
1002  secp256k1_ge *points;
1003  secp256k1_scalar *scalars;
1004  secp256k1_gej *buckets;
1005  struct secp256k1_pippenger_state *state_space;
1006  size_t idx = 0;
1007  size_t point_idx = 0;
1008  int i, j;
1009  int bucket_window;
1010 
1011  (void)ctx;
1013  if (inp_g_sc == NULL && n_points == 0) {
1014  return 1;
1015  }
1016 
1017  bucket_window = secp256k1_pippenger_bucket_window(n_points);
1018  points = (secp256k1_ge *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*points));
1019  scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*scalars));
1020  state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(error_callback, scratch, sizeof(*state_space));
1021  if (points == NULL || scalars == NULL || state_space == NULL) {
1022  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
1023  return 0;
1024  }
1025 
1026  state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*state_space->ps));
1027  state_space->wnaf_na = (int *) secp256k1_scratch_alloc(error_callback, scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int));
1028  buckets = (secp256k1_gej *) secp256k1_scratch_alloc(error_callback, scratch, (1<<bucket_window) * sizeof(*buckets));
1029  if (state_space->ps == NULL || state_space->wnaf_na == NULL || buckets == NULL) {
1030  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
1031  return 0;
1032  }
1033 
1034  if (inp_g_sc != NULL) {
1035  scalars[0] = *inp_g_sc;
1036  points[0] = secp256k1_ge_const_g;
1037  idx++;
1038 #ifdef USE_ENDOMORPHISM
1039  secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]);
1040  idx++;
1041 #endif
1042  }
1043 
1044  while (point_idx < n_points) {
1045  if (!cb(&scalars[idx], &points[idx], point_idx + cb_offset, cbdata)) {
1046  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
1047  return 0;
1048  }
1049  idx++;
1050 #ifdef USE_ENDOMORPHISM
1051  secp256k1_ecmult_endo_split(&scalars[idx - 1], &scalars[idx], &points[idx - 1], &points[idx]);
1052  idx++;
1053 #endif
1054  point_idx++;
1055  }
1056 
1057  secp256k1_ecmult_pippenger_wnaf(buckets, bucket_window, state_space, r, scalars, points, idx);
1058 
1059  /* Clear data */
1060  for(i = 0; (size_t)i < idx; i++) {
1061  secp256k1_scalar_clear(&scalars[i]);
1062  state_space->ps[i].skew_na = 0;
1063  for(j = 0; j < WNAF_SIZE(bucket_window+1); j++) {
1064  state_space->wnaf_na[i * WNAF_SIZE(bucket_window+1) + j] = 0;
1065  }
1066  }
1067  for(i = 0; i < 1<<bucket_window; i++) {
1068  secp256k1_gej_clear(&buckets[i]);
1069  }
1070  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
1071  return 1;
1072 }
1073 
1074 /* Wrapper for secp256k1_ecmult_multi_func interface */
1075 static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
1076  return secp256k1_ecmult_pippenger_batch(error_callback, actx, scratch, r, inp_g_sc, cb, cbdata, n, 0);
1077 }
1078 
1084 static size_t secp256k1_pippenger_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
1085  size_t max_alloc = secp256k1_scratch_max_allocation(error_callback, scratch, PIPPENGER_SCRATCH_OBJECTS);
1086  int bucket_window;
1087  size_t res = 0;
1088 
1089  for (bucket_window = 1; bucket_window <= PIPPENGER_MAX_BUCKET_WINDOW; bucket_window++) {
1090  size_t n_points;
1091  size_t max_points = secp256k1_pippenger_bucket_window_inv(bucket_window);
1092  size_t space_for_points;
1093  size_t space_overhead;
1094  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
1095 
1096 #ifdef USE_ENDOMORPHISM
1097  entry_size = 2*entry_size;
1098 #endif
1099  space_overhead = (sizeof(secp256k1_gej) << bucket_window) + entry_size + sizeof(struct secp256k1_pippenger_state);
1100  if (space_overhead > max_alloc) {
1101  break;
1102  }
1103  space_for_points = max_alloc - space_overhead;
1104 
1105  n_points = space_for_points/entry_size;
1106  n_points = n_points > max_points ? max_points : n_points;
1107  if (n_points > res) {
1108  res = n_points;
1109  }
1110  if (n_points < max_points) {
1111  /* A larger bucket_window may support even more points. But if we
1112  * would choose that then the caller couldn't safely use any number
1113  * smaller than what this function returns */
1114  break;
1115  }
1116  }
1117  return res;
1118 }
1119 
1120 /* Computes ecmult_multi by simply multiplying and adding each point. Does not
1121  * require a scratch space */
1122 static int secp256k1_ecmult_multi_simple_var(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points) {
1123  size_t point_idx;
1124  secp256k1_scalar szero;
1125  secp256k1_gej tmpj;
1126 
1127  secp256k1_scalar_set_int(&szero, 0);
1130  /* r = inp_g_sc*G */
1131  secp256k1_ecmult(ctx, r, &tmpj, &szero, inp_g_sc);
1132  for (point_idx = 0; point_idx < n_points; point_idx++) {
1133  secp256k1_ge point;
1134  secp256k1_gej pointj;
1135  secp256k1_scalar scalar;
1136  if (!cb(&scalar, &point, point_idx, cbdata)) {
1137  return 0;
1138  }
1139  /* r += scalar*point */
1140  secp256k1_gej_set_ge(&pointj, &point);
1141  secp256k1_ecmult(ctx, &tmpj, &pointj, &scalar, NULL);
1142  secp256k1_gej_add_var(r, r, &tmpj, NULL);
1143  }
1144  return 1;
1145 }
1146 
1147 /* Compute the number of batches and the batch size given the maximum batch size and the
1148  * total number of points */
1149 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) {
1150  if (max_n_batch_points == 0) {
1151  return 0;
1152  }
1153  if (max_n_batch_points > ECMULT_MAX_POINTS_PER_BATCH) {
1154  max_n_batch_points = ECMULT_MAX_POINTS_PER_BATCH;
1155  }
1156  if (n == 0) {
1157  *n_batches = 0;
1158  *n_batch_points = 0;
1159  return 1;
1160  }
1161  /* Compute ceil(n/max_n_batch_points) and ceil(n/n_batches) */
1162  *n_batches = 1 + (n - 1) / max_n_batch_points;
1163  *n_batch_points = 1 + (n - 1) / *n_batches;
1164  return 1;
1165 }
1166 
1168 static int secp256k1_ecmult_multi_var(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
1169  size_t i;
1170 
1171  int (*f)(const secp256k1_callback* error_callback, const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t);
1172  size_t n_batches;
1173  size_t n_batch_points;
1174 
1176  if (inp_g_sc == NULL && n == 0) {
1177  return 1;
1178  } else if (n == 0) {
1179  secp256k1_scalar szero;
1180  secp256k1_scalar_set_int(&szero, 0);
1181  secp256k1_ecmult(ctx, r, r, &szero, inp_g_sc);
1182  return 1;
1183  }
1184  if (scratch == NULL) {
1185  return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n);
1186  }
1187 
1188  /* Compute the batch sizes for Pippenger's algorithm given a scratch space. If it's greater than
1189  * a threshold use Pippenger's algorithm. Otherwise use Strauss' algorithm.
1190  * As a first step check if there's enough space for Pippenger's algo (which requires less space
1191  * than Strauss' algo) and if not, use the simple algorithm. */
1192  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(error_callback, scratch), n)) {
1193  return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n);
1194  }
1195  if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) {
1197  } else {
1198  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(error_callback, scratch), n)) {
1199  return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n);
1200  }
1202  }
1203  for(i = 0; i < n_batches; i++) {
1204  size_t nbp = n < n_batch_points ? n : n_batch_points;
1205  size_t offset = n_batch_points*i;
1206  secp256k1_gej tmp;
1207  if (!f(error_callback, ctx, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) {
1208  return 0;
1209  }
1210  secp256k1_gej_add_var(r, r, &tmp, NULL);
1211  n -= nbp;
1212  }
1213  return 1;
1214 }
1215 
1216 #endif /* SECP256K1_ECMULT_IMPL_H */
static void secp256k1_ge_globalz_set_table_gej(size_t len, secp256k1_ge *r, secp256k1_fe *globalz, const secp256k1_gej *a, const secp256k1_fe *zr)
Bring a batch inputs given in jacobian coordinates (with known z-ratios) to the same global z "denomi...
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Check whether a group element is the point at infinity.
#define VERIFY_CHECK(cond)
Definition: util.h:68
static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx)
Definition: ecmult_impl.h:382
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Check whether a group element is the point at infinity.
struct secp256k1_strauss_point_state * ps
Definition: ecmult_impl.h:470
static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr)
Set r equal to the sum of a and b.
static int secp256k1_scalar_is_even(const secp256k1_scalar *a)
Check whether a scalar, considered as an nonnegative integer, is even.
static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx)
Definition: ecmult_impl.h:386
static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window)
Returns the scratch size required for a given number of points (excluding base point G) without consi...
Definition: ecmult_impl.h:982
static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx)
Definition: ecmult_impl.h:321
#define WNAF_BITS
Definition: ecmult_impl.h:65
static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a)
static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe *SECP256K1_RESTRICT b)
Sets a field element to be the product of two others.
static void secp256k1_fe_normalize_var(secp256k1_fe *r)
Normalize a field element, without constant-time guarantee.
secp256k1_fe x
Definition: group.h:25
static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, void **prealloc)
Definition: ecmult_impl.h:328
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)
Definition: ecmult_impl.h:789
static int secp256k1_ecmult_multi_var(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n)
Definition: ecmult_impl.h:1168
static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m)
Set a field element equal to the additive inverse of another.
static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
Access bits from a scalar.
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
#define PIPPENGER_MAX_BUCKET_WINDOW
Definition: ecmult_impl.h:77
static int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
Check whether a scalar equals zero.
#define ECMULT_TABLE_GET_GE_STORAGE(r, pre, n, w)
Definition: ecmult_impl.h:302
#define ECMULT_TABLE_SIZE(w)
The number of entries a table with precomputed multiples needs to have.
Definition: ecmult_impl.h:71
static int secp256k1_ecmult_pippenger_batch(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *ctx, 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)
Definition: ecmult_impl.h:992
static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv)
Set r equal to the sum of a and b (with the inverse of b&#39;s Z coordinate passed as bzinv)...
int(* secp256k1_ecmult_multi_func)(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *, secp256k1_scratch *, secp256k1_gej *, const secp256k1_scalar *, secp256k1_ecmult_multi_callback cb, void *, size_t)
Definition: ecmult_impl.h:1167
static size_t secp256k1_scratch_checkpoint(const secp256k1_callback *error_callback, const secp256k1_scratch *scratch)
Returns an opaque object used to "checkpoint" a scratch space.
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:24
static void secp256k1_fe_set_int(secp256k1_fe *r, int a)
Set a field element equal to a small integer.
static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a)
Convert a field element to the storage type.
static void secp256k1_ecmult_odd_multiples_table_storage_var(const int n, secp256k1_ge_storage *pre, const secp256k1_gej *a)
Definition: ecmult_impl.h:157
static SECP256K1_INLINE void * manual_alloc(void **prealloc_ptr, size_t alloc_size, void *base, size_t max_size)
Definition: util.h:134
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Set a group element (jacobian) equal to the point at infinity.
static int secp256k1_ecmult_multi_simple_var(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points)
Definition: ecmult_impl.h:1122
static void * secp256k1_scratch_alloc(const secp256k1_callback *error_callback, secp256k1_scratch *scratch, size_t n)
Returns a pointer into the most recently allocated frame, or NULL if there is insufficient available ...
static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a)
Adds a field element to another.
static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr)
Set r equal to the sum of a and b (with b given in affine coordinates).
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Set r equal to the double of a.
static const secp256k1_ge secp256k1_ge_const_g
Generator for secp256k1, value &#39;g&#39; defined in "Standards for Efficient Cryptography" (SEC2) 2...
Definition: group_impl.h:64
static int secp256k1_ecmult_strauss_batch(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *ctx, 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)
Definition: ecmult_impl.h:652
#define WINDOW_G
Larger values for ECMULT_WINDOW_SIZE result in possibly better performance at the cost of an exponent...
Definition: ecmult_impl.h:44
static size_t secp256k1_strauss_max_points(const secp256k1_callback *error_callback, secp256k1_scratch *scratch)
Definition: ecmult_impl.h:699
#define SECP256K1_INLINE
Definition: secp256k1.h:124
static void secp256k1_ecmult_odd_multiples_table_globalz_windowa(secp256k1_ge *pre, secp256k1_fe *globalz, const secp256k1_gej *a)
Fill a table &#39;pre&#39; with precomputed odd multiples of a.
Definition: ecmult_impl.h:147
#define PIPPENGER_SCRATCH_OBJECTS
Definition: ecmult_impl.h:74
static const size_t SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE
Definition: ecmult_impl.h:314
static size_t secp256k1_pippenger_bucket_window_inv(int bucket_window)
Returns the maximum optimal number of points for a bucket_window.
Definition: ecmult_impl.h:927
#define ECMULT_PIPPENGER_THRESHOLD
Definition: ecmult_impl.h:83
static secp256k1_context * ctx
Definition: tests.c:36
int infinity
Definition: group.h:28
static void secp256k1_gej_clear(secp256k1_gej *r)
Clear a secp256k1_gej to prevent leaking sensitive information.
static int secp256k1_scalar_is_high(const secp256k1_scalar *a)
Check whether a scalar is higher than the group order divided by 2.
static int secp256k1_pippenger_bucket_window(size_t n)
Returns optimal bucket_window (number of bits of a scalar represented by a set of buckets) for a give...
Definition: ecmult_impl.h:870
static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w)
Convert a number to WNAF notation.
Definition: ecmult_impl.h:710
#define ECMULT_MAX_POINTS_PER_BATCH
Definition: ecmult_impl.h:89
static void secp256k1_scalar_clear(secp256k1_scalar *r)
Clear a scalar to prevent the leak of sensitive data.
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
secp256k1_fe x
Definition: group.h:15
static size_t secp256k1_strauss_scratch_size(size_t n_points)
Definition: ecmult_impl.h:643
#define CHECK(cond)
Definition: util.h:53
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
int infinity
Definition: group.h:17
#define WINDOW_A
Definition: ecmult_impl.h:34
static size_t secp256k1_scratch_max_allocation(const secp256k1_callback *error_callback, const secp256k1_scratch *scratch, size_t n_objects)
Returns the maximum allocation the scratch space will allow.
#define STRAUSS_SCRATCH_OBJECTS
Definition: ecmult_impl.h:75
static void secp256k1_scratch_apply_checkpoint(const secp256k1_callback *error_callback, secp256k1_scratch *scratch, size_t checkpoint)
Applies a check point received from secp256k1_scratch_checkpoint, undoing all allocations since that ...
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a)
Sets a field element to be the square of another.
static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a)
static void secp256k1_ecmult_strauss_wnaf(const secp256k1_ecmult_context *ctx, const struct secp256k1_strauss_state *state, secp256k1_gej *r, int num, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
Definition: ecmult_impl.h:473
secp256k1_ge * pre_a
Definition: ecmult_impl.h:466
static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *b)
Rescale a jacobian point by b which must be non-zero.
#define ECMULT_TABLE_GET_GE(r, pre, n, w)
The following two macro retrieves a particular odd multiple from a table of precomputed multiples...
Definition: ecmult_impl.h:290
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
static int secp256k1_ecmult_strauss_batch_single(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n)
Definition: ecmult_impl.h:695
static size_t secp256k1_pippenger_max_points(const secp256k1_callback *error_callback, secp256k1_scratch *scratch)
Returns the maximum number of points in addition to G that can be used with a given scratch space...
Definition: ecmult_impl.h:1084
static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi)
Definition: group_impl.h:74
secp256k1_fe z
Definition: group.h:27
static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, secp256k1_fe *zr, const secp256k1_gej *a)
Fill a table &#39;prej&#39; with precomputed odd multiples of a.
Definition: ecmult_impl.h:97
#define WNAF_SIZE(w)
Definition: ecmult_impl.h:68
struct secp256k1_pippenger_point_state * ps
Definition: ecmult_impl.h:779
static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
Access bits from a scalar.
static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n)
Definition: ecmult_impl.h:1075
#define ROUND_TO_ALIGN(size)
Definition: util.h:116
secp256k1_gej * prej
Definition: ecmult_impl.h:464
int() secp256k1_ecmult_multi_callback(secp256k1_scalar *sc, secp256k1_ge *pt, size_t idx, void *data)
Definition: ecmult.h:33
static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Convert a group element back from the storage type.
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Set a group element (jacobian) equal to another which is given in affine coordinates.
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)
Definition: ecmult_impl.h:1149
static void secp256k1_ecmult_context_finalize_memcpy(secp256k1_ecmult_context *dst, const secp256k1_ecmult_context *src)
Definition: ecmult_impl.h:370
secp256k1_fe y
Definition: group.h:26
static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w)
Convert a number to WNAF notation.
Definition: ecmult_impl.h:397
static void secp256k1_ecmult(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
Definition: ecmult_impl.h:623
secp256k1_fe y
Definition: group.h:16
static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a)
Potentially faster version of secp256k1_fe_inv, without constant-time guarantee.
static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Convert a group element to the storage type.
secp256k1_ge_storage(* pre_g)[]
Definition: ecmult.h:17