Bitcoin Core  27.99.0
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 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
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 
74  secp256k1_gej d, ai;
75  secp256k1_ge d_ge;
76  int i;
77 
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 equivalent 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 
118  (void)n;
119  (void)w;
120  VERIFY_CHECK(((n) & 1) == 1);
121  VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1));
122  VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1));
123 }
124 
125 SECP256K1_INLINE static void secp256k1_ecmult_table_get_ge(secp256k1_ge *r, const secp256k1_ge *pre, int n, int w) {
127  if (n > 0) {
128  *r = pre[(n-1)/2];
129  } else {
130  *r = pre[(-n-1)/2];
131  secp256k1_fe_negate(&(r->y), &(r->y), 1);
132  }
133 }
134 
137  if (n > 0) {
138  secp256k1_ge_set_xy(r, &x[(n-1)/2], &pre[(n-1)/2].y);
139  } else {
140  secp256k1_ge_set_xy(r, &x[(-n-1)/2], &pre[(-n-1)/2].y);
141  secp256k1_fe_negate(&(r->y), &(r->y), 1);
142  }
143 }
144 
147  if (n > 0) {
148  secp256k1_ge_from_storage(r, &pre[(n-1)/2]);
149  } else {
150  secp256k1_ge_from_storage(r, &pre[(-n-1)/2]);
151  secp256k1_fe_negate(&(r->y), &(r->y), 1);
152  }
153 }
154 
162 static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) {
164  int last_set_bit = -1;
165  int bit = 0;
166  int sign = 1;
167  int carry = 0;
168 
169  VERIFY_CHECK(wnaf != NULL);
170  VERIFY_CHECK(0 <= len && len <= 256);
171  VERIFY_CHECK(a != NULL);
172  VERIFY_CHECK(2 <= w && w <= 31);
173 
174  memset(wnaf, 0, len * sizeof(wnaf[0]));
175 
176  s = *a;
177  if (secp256k1_scalar_get_bits(&s, 255, 1)) {
178  secp256k1_scalar_negate(&s, &s);
179  sign = -1;
180  }
181 
182  while (bit < len) {
183  int now;
184  int word;
185  if (secp256k1_scalar_get_bits(&s, bit, 1) == (unsigned int)carry) {
186  bit++;
187  continue;
188  }
189 
190  now = w;
191  if (now > len - bit) {
192  now = len - bit;
193  }
194 
195  word = secp256k1_scalar_get_bits_var(&s, bit, now) + carry;
196 
197  carry = (word >> (w-1)) & 1;
198  word -= carry << w;
199 
200  wnaf[bit] = sign * word;
201  last_set_bit = bit;
202 
203  bit += now;
204  }
205 #ifdef VERIFY
206  {
207  int verify_bit = bit;
208 
209  VERIFY_CHECK(carry == 0);
210 
211  while (verify_bit < 256) {
212  VERIFY_CHECK(secp256k1_scalar_get_bits(&s, verify_bit, 1) == 0);
213  verify_bit++;
214  }
215  }
216 #endif
217  return last_set_bit + 1;
218 }
219 
221  int wnaf_na_1[129];
222  int wnaf_na_lam[129];
225 };
226 
228  /* aux is used to hold z-ratios, and then used to hold pre_a[i].x * BETA values. */
232 };
233 
234 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) {
235  secp256k1_ge tmpa;
236  secp256k1_fe Z;
237  /* Split G factors. */
238  secp256k1_scalar ng_1, ng_128;
239  int wnaf_ng_1[129];
240  int bits_ng_1 = 0;
241  int wnaf_ng_128[129];
242  int bits_ng_128 = 0;
243  int i;
244  int bits = 0;
245  size_t np;
246  size_t no = 0;
247 
248  secp256k1_fe_set_int(&Z, 1);
249  for (np = 0; np < num; ++np) {
250  secp256k1_gej tmp;
251  secp256k1_scalar na_1, na_lam;
252  if (secp256k1_scalar_is_zero(&na[np]) || secp256k1_gej_is_infinity(&a[np])) {
253  continue;
254  }
255  /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
256  secp256k1_scalar_split_lambda(&na_1, &na_lam, &na[np]);
257 
258  /* build wnaf representation for na_1 and na_lam. */
259  state->ps[no].bits_na_1 = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_1, 129, &na_1, WINDOW_A);
260  state->ps[no].bits_na_lam = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_lam, 129, &na_lam, WINDOW_A);
261  VERIFY_CHECK(state->ps[no].bits_na_1 <= 129);
262  VERIFY_CHECK(state->ps[no].bits_na_lam <= 129);
263  if (state->ps[no].bits_na_1 > bits) {
264  bits = state->ps[no].bits_na_1;
265  }
266  if (state->ps[no].bits_na_lam > bits) {
267  bits = state->ps[no].bits_na_lam;
268  }
269 
270  /* Calculate odd multiples of a.
271  * All multiples are brought to the same Z 'denominator', which is stored
272  * in Z. Due to secp256k1' isomorphism we can do all operations pretending
273  * that the Z coordinate was 1, use affine addition formulae, and correct
274  * the Z coordinate of the result once at the end.
275  * The exception is the precomputed G table points, which are actually
276  * affine. Compared to the base used for other points, they have a Z ratio
277  * of 1/Z, so we can use secp256k1_gej_add_zinv_var, which uses the same
278  * isomorphism to efficiently add with a known Z inverse.
279  */
280  tmp = a[np];
281  if (no) {
282  secp256k1_gej_rescale(&tmp, &Z);
283  }
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  if (no) {
293  }
294 
295  for (np = 0; np < no; ++np) {
296  for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
298  }
299  }
300 
301  if (ng) {
302  /* 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) */
303  secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
304 
305  /* Build wnaf representation for ng_1 and ng_128 */
306  bits_ng_1 = secp256k1_ecmult_wnaf(wnaf_ng_1, 129, &ng_1, WINDOW_G);
307  bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, 129, &ng_128, WINDOW_G);
308  if (bits_ng_1 > bits) {
309  bits = bits_ng_1;
310  }
311  if (bits_ng_128 > bits) {
312  bits = bits_ng_128;
313  }
314  }
315 
317 
318  for (i = bits - 1; i >= 0; i--) {
319  int n;
320  secp256k1_gej_double_var(r, r, NULL);
321  for (np = 0; np < no; ++np) {
322  if (i < state->ps[np].bits_na_1 && (n = state->ps[np].wnaf_na_1[i])) {
324  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
325  }
326  if (i < state->ps[np].bits_na_lam && (n = state->ps[np].wnaf_na_lam[i])) {
328  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
329  }
330  }
331  if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
333  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
334  }
335  if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
337  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
338  }
339  }
340 
341  if (!r->infinity) {
342  secp256k1_fe_mul(&r->z, &r->z, &Z);
343  }
344 }
345 
346 static void secp256k1_ecmult(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
349  struct secp256k1_strauss_point_state ps[1];
350  struct secp256k1_strauss_state state;
351 
352  state.aux = aux;
353  state.pre_a = pre_a;
354  state.ps = ps;
355  secp256k1_ecmult_strauss_wnaf(&state, r, 1, a, na, ng);
356 }
357 
358 static size_t secp256k1_strauss_scratch_size(size_t n_points) {
359  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);
360  return n_points*point_size;
361 }
362 
363 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) {
364  secp256k1_gej* points;
365  secp256k1_scalar* scalars;
366  struct secp256k1_strauss_state state;
367  size_t i;
368  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
369 
371  if (inp_g_sc == NULL && n_points == 0) {
372  return 1;
373  }
374 
375  /* We allocate STRAUSS_SCRATCH_OBJECTS objects on the scratch space. If these
376  * allocations change, make sure to update the STRAUSS_SCRATCH_OBJECTS
377  * constant and strauss_scratch_size accordingly. */
378  points = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_gej));
379  scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_scalar));
380  state.aux = (secp256k1_fe*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe));
381  state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
382  state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
383 
384  if (points == NULL || scalars == NULL || state.aux == NULL || state.pre_a == NULL || state.ps == NULL) {
385  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
386  return 0;
387  }
388 
389  for (i = 0; i < n_points; i++) {
390  secp256k1_ge point;
391  if (!cb(&scalars[i], &point, i+cb_offset, cbdata)) {
392  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
393  return 0;
394  }
395  secp256k1_gej_set_ge(&points[i], &point);
396  }
397  secp256k1_ecmult_strauss_wnaf(&state, r, n_points, points, scalars, inp_g_sc);
398  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
399  return 1;
400 }
401 
402 /* Wrapper for secp256k1_ecmult_multi_func interface */
403 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) {
404  return secp256k1_ecmult_strauss_batch(error_callback, scratch, r, inp_g_sc, cb, cbdata, n, 0);
405 }
406 
407 static size_t secp256k1_strauss_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
409 }
410 
418 static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w) {
419  int skew = 0;
420  int pos;
421  int max_pos;
422  int last_w;
423  const secp256k1_scalar *work = s;
424 
425  if (secp256k1_scalar_is_zero(s)) {
426  for (pos = 0; pos < WNAF_SIZE(w); pos++) {
427  wnaf[pos] = 0;
428  }
429  return 0;
430  }
431 
432  if (secp256k1_scalar_is_even(s)) {
433  skew = 1;
434  }
435 
436  wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
437  /* Compute last window size. Relevant when window size doesn't divide the
438  * number of bits in the scalar */
439  last_w = WNAF_BITS - (WNAF_SIZE(w) - 1) * w;
440 
441  /* Store the position of the first nonzero word in max_pos to allow
442  * skipping leading zeros when calculating the wnaf. */
443  for (pos = WNAF_SIZE(w) - 1; pos > 0; pos--) {
444  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
445  if(val != 0) {
446  break;
447  }
448  wnaf[pos] = 0;
449  }
450  max_pos = pos;
451  pos = 1;
452 
453  while (pos <= max_pos) {
454  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
455  if ((val & 1) == 0) {
456  wnaf[pos - 1] -= (1 << w);
457  wnaf[pos] = (val + 1);
458  } else {
459  wnaf[pos] = val;
460  }
461  /* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
462  * is strictly negative or strictly positive respectively. Only change
463  * coefficients at previous positions because above code assumes that
464  * wnaf[pos - 1] is odd.
465  */
466  if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) || (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
467  if (wnaf[pos - 1] == 1) {
468  wnaf[pos - 2] += 1 << w;
469  } else {
470  wnaf[pos - 2] -= 1 << w;
471  }
472  wnaf[pos - 1] = 0;
473  }
474  ++pos;
475  }
476 
477  return skew;
478 }
479 
481  int skew_na;
482  size_t input_pos;
483 };
484 
486  int *wnaf_na;
488 };
489 
490 /*
491  * pippenger_wnaf computes the result of a multi-point multiplication as
492  * follows: The scalars are brought into wnaf with n_wnaf elements each. Then
493  * for every i < n_wnaf, first each point is added to a "bucket" corresponding
494  * to the point's wnaf[i]. Second, the buckets are added together such that
495  * r += 1*bucket[0] + 3*bucket[1] + 5*bucket[2] + ...
496  */
497 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) {
498  size_t n_wnaf = WNAF_SIZE(bucket_window+1);
499  size_t np;
500  size_t no = 0;
501  int i;
502  int j;
503 
504  for (np = 0; np < num; ++np) {
505  if (secp256k1_scalar_is_zero(&sc[np]) || secp256k1_ge_is_infinity(&pt[np])) {
506  continue;
507  }
508  state->ps[no].input_pos = np;
509  state->ps[no].skew_na = secp256k1_wnaf_fixed(&state->wnaf_na[no*n_wnaf], &sc[np], bucket_window+1);
510  no++;
511  }
513 
514  if (no == 0) {
515  return 1;
516  }
517 
518  for (i = n_wnaf - 1; i >= 0; i--) {
519  secp256k1_gej running_sum;
520 
521  for(j = 0; j < ECMULT_TABLE_SIZE(bucket_window+2); j++) {
522  secp256k1_gej_set_infinity(&buckets[j]);
523  }
524 
525  for (np = 0; np < no; ++np) {
526  int n = state->wnaf_na[np*n_wnaf + i];
527  struct secp256k1_pippenger_point_state point_state = state->ps[np];
528  secp256k1_ge tmp;
529  int idx;
530 
531  if (i == 0) {
532  /* correct for wnaf skew */
533  int skew = point_state.skew_na;
534  if (skew) {
535  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
536  secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);
537  }
538  }
539  if (n > 0) {
540  idx = (n - 1)/2;
541  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
542  } else if (n < 0) {
543  idx = -(n + 1)/2;
544  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
545  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);
546  }
547  }
548 
549  for(j = 0; j < bucket_window; j++) {
550  secp256k1_gej_double_var(r, r, NULL);
551  }
552 
553  secp256k1_gej_set_infinity(&running_sum);
554  /* Accumulate the sum: bucket[0] + 3*bucket[1] + 5*bucket[2] + 7*bucket[3] + ...
555  * = bucket[0] + bucket[1] + bucket[2] + bucket[3] + ...
556  * + 2 * (bucket[1] + 2*bucket[2] + 3*bucket[3] + ...)
557  * using an intermediate running sum:
558  * running_sum = bucket[0] + bucket[1] + bucket[2] + ...
559  *
560  * The doubling is done implicitly by deferring the final window doubling (of 'r').
561  */
562  for(j = ECMULT_TABLE_SIZE(bucket_window+2) - 1; j > 0; j--) {
563  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[j], NULL);
564  secp256k1_gej_add_var(r, r, &running_sum, NULL);
565  }
566 
567  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[0], NULL);
568  secp256k1_gej_double_var(r, r, NULL);
569  secp256k1_gej_add_var(r, r, &running_sum, NULL);
570  }
571  return 1;
572 }
573 
578 static int secp256k1_pippenger_bucket_window(size_t n) {
579  if (n <= 1) {
580  return 1;
581  } else if (n <= 4) {
582  return 2;
583  } else if (n <= 20) {
584  return 3;
585  } else if (n <= 57) {
586  return 4;
587  } else if (n <= 136) {
588  return 5;
589  } else if (n <= 235) {
590  return 6;
591  } else if (n <= 1260) {
592  return 7;
593  } else if (n <= 4420) {
594  return 9;
595  } else if (n <= 7880) {
596  return 10;
597  } else if (n <= 16050) {
598  return 11;
599  } else {
601  }
602 }
603 
607 static size_t secp256k1_pippenger_bucket_window_inv(int bucket_window) {
608  switch(bucket_window) {
609  case 1: return 1;
610  case 2: return 4;
611  case 3: return 20;
612  case 4: return 57;
613  case 5: return 136;
614  case 6: return 235;
615  case 7: return 1260;
616  case 8: return 1260;
617  case 9: return 4420;
618  case 10: return 7880;
619  case 11: return 16050;
620  case PIPPENGER_MAX_BUCKET_WINDOW: return SIZE_MAX;
621  }
622  return 0;
623 }
624 
625 
627  secp256k1_scalar tmp = *s1;
628  secp256k1_scalar_split_lambda(s1, s2, &tmp);
629  secp256k1_ge_mul_lambda(p2, p1);
630 
631  if (secp256k1_scalar_is_high(s1)) {
632  secp256k1_scalar_negate(s1, s1);
633  secp256k1_ge_neg(p1, p1);
634  }
635  if (secp256k1_scalar_is_high(s2)) {
636  secp256k1_scalar_negate(s2, s2);
637  secp256k1_ge_neg(p2, p2);
638  }
639 }
640 
645 static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window) {
646  size_t entries = 2*n_points + 2;
647  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
648  return (sizeof(secp256k1_gej) << bucket_window) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size;
649 }
650 
651 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) {
652  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
653  /* Use 2(n+1) with the endomorphism, when calculating batch
654  * sizes. The reason for +1 is that we add the G scalar to the list of
655  * other scalars. */
656  size_t entries = 2*n_points + 2;
657  secp256k1_ge *points;
658  secp256k1_scalar *scalars;
659  secp256k1_gej *buckets;
660  struct secp256k1_pippenger_state *state_space;
661  size_t idx = 0;
662  size_t point_idx = 0;
663  int i, j;
664  int bucket_window;
665 
667  if (inp_g_sc == NULL && n_points == 0) {
668  return 1;
669  }
670  bucket_window = secp256k1_pippenger_bucket_window(n_points);
671 
672  /* We allocate PIPPENGER_SCRATCH_OBJECTS objects on the scratch space. If
673  * these allocations change, make sure to update the
674  * PIPPENGER_SCRATCH_OBJECTS constant and pippenger_scratch_size
675  * accordingly. */
676  points = (secp256k1_ge *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*points));
677  scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*scalars));
678  state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(error_callback, scratch, sizeof(*state_space));
679  if (points == NULL || scalars == NULL || state_space == NULL) {
680  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
681  return 0;
682  }
683  state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*state_space->ps));
684  state_space->wnaf_na = (int *) secp256k1_scratch_alloc(error_callback, scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int));
685  buckets = (secp256k1_gej *) secp256k1_scratch_alloc(error_callback, scratch, ((size_t)1 << bucket_window) * sizeof(*buckets));
686  if (state_space->ps == NULL || state_space->wnaf_na == NULL || buckets == NULL) {
687  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
688  return 0;
689  }
690 
691  if (inp_g_sc != NULL) {
692  scalars[0] = *inp_g_sc;
693  points[0] = secp256k1_ge_const_g;
694  idx++;
695  secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]);
696  idx++;
697  }
698 
699  while (point_idx < n_points) {
700  if (!cb(&scalars[idx], &points[idx], point_idx + cb_offset, cbdata)) {
701  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
702  return 0;
703  }
704  idx++;
705  secp256k1_ecmult_endo_split(&scalars[idx - 1], &scalars[idx], &points[idx - 1], &points[idx]);
706  idx++;
707  point_idx++;
708  }
709 
710  secp256k1_ecmult_pippenger_wnaf(buckets, bucket_window, state_space, r, scalars, points, idx);
711 
712  /* Clear data */
713  for(i = 0; (size_t)i < idx; i++) {
714  secp256k1_scalar_clear(&scalars[i]);
715  state_space->ps[i].skew_na = 0;
716  for(j = 0; j < WNAF_SIZE(bucket_window+1); j++) {
717  state_space->wnaf_na[i * WNAF_SIZE(bucket_window+1) + j] = 0;
718  }
719  }
720  for(i = 0; i < 1<<bucket_window; i++) {
721  secp256k1_gej_clear(&buckets[i]);
722  }
723  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
724  return 1;
725 }
726 
727 /* Wrapper for secp256k1_ecmult_multi_func interface */
728 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) {
729  return secp256k1_ecmult_pippenger_batch(error_callback, scratch, r, inp_g_sc, cb, cbdata, n, 0);
730 }
731 
737 static size_t secp256k1_pippenger_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
738  size_t max_alloc = secp256k1_scratch_max_allocation(error_callback, scratch, PIPPENGER_SCRATCH_OBJECTS);
739  int bucket_window;
740  size_t res = 0;
741 
742  for (bucket_window = 1; bucket_window <= PIPPENGER_MAX_BUCKET_WINDOW; bucket_window++) {
743  size_t n_points;
744  size_t max_points = secp256k1_pippenger_bucket_window_inv(bucket_window);
745  size_t space_for_points;
746  size_t space_overhead;
747  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
748 
749  entry_size = 2*entry_size;
750  space_overhead = (sizeof(secp256k1_gej) << bucket_window) + entry_size + sizeof(struct secp256k1_pippenger_state);
751  if (space_overhead > max_alloc) {
752  break;
753  }
754  space_for_points = max_alloc - space_overhead;
755 
756  n_points = space_for_points/entry_size;
757  n_points = n_points > max_points ? max_points : n_points;
758  if (n_points > res) {
759  res = n_points;
760  }
761  if (n_points < max_points) {
762  /* A larger bucket_window may support even more points. But if we
763  * would choose that then the caller couldn't safely use any number
764  * smaller than what this function returns */
765  break;
766  }
767  }
768  return res;
769 }
770 
771 /* Computes ecmult_multi by simply multiplying and adding each point. Does not
772  * require a scratch space */
773 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) {
774  size_t point_idx;
775  secp256k1_gej tmpj;
776 
779  /* r = inp_g_sc*G */
780  secp256k1_ecmult(r, &tmpj, &secp256k1_scalar_zero, 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 
825  if (inp_g_sc == NULL && n == 0) {
826  return 1;
827  } else if (n == 0) {
828  secp256k1_ecmult(r, r, &secp256k1_scalar_zero, inp_g_sc);
829  return 1;
830  }
831  if (scratch == NULL) {
832  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
833  }
834 
835  /* Compute the batch sizes for Pippenger's algorithm given a scratch space. If it's greater than
836  * a threshold use Pippenger's algorithm. Otherwise use Strauss' algorithm.
837  * As a first step check if there's enough space for Pippenger's algo (which requires less space
838  * than Strauss' algo) and if not, use the simple algorithm. */
839  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(error_callback, scratch), n)) {
840  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
841  }
842  if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) {
844  } else {
845  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(error_callback, scratch), n)) {
846  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
847  }
849  }
850  for(i = 0; i < n_batches; i++) {
851  size_t nbp = n < n_batch_points ? n : n_batch_points;
852  size_t offset = n_batch_points*i;
853  secp256k1_gej tmp;
854  if (!f(error_callback, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) {
855  return 0;
856  }
857  secp256k1_gej_add_var(r, r, &tmp, NULL);
858  n -= nbp;
859  }
860  return 1;
861 }
862 
863 #endif /* SECP256K1_ECMULT_IMPL_H */
#define ECMULT_TABLE_SIZE(w)
The number of entries a table with precomputed multiples needs to have.
Definition: ecmult.h:41
int() secp256k1_ecmult_multi_callback(secp256k1_scalar *sc, secp256k1_ge *pt, size_t idx, void *data)
Definition: ecmult.h:46
#define STRAUSS_SCRATCH_OBJECTS
Definition: ecmult_impl.h:50
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:607
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:737
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)
Definition: ecmult_impl.h:651
#define WNAF_SIZE(w)
Definition: ecmult_impl.h:46
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)
Definition: ecmult_impl.h:403
static size_t secp256k1_strauss_max_points(const secp256k1_callback *error_callback, secp256k1_scratch *scratch)
Definition: ecmult_impl.h:407
static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w)
Convert a number to WNAF notation.
Definition: ecmult_impl.h:418
static SECP256K1_INLINE void secp256k1_ecmult_endo_split(secp256k1_scalar *s1, secp256k1_scalar *s2, secp256k1_ge *p1, secp256k1_ge *p2)
Definition: ecmult_impl.h:626
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:162
static SECP256K1_INLINE void secp256k1_ecmult_table_get_ge_storage(secp256k1_ge *r, const secp256k1_ge_storage *pre, int n, int w)
Definition: ecmult_impl.h:145
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)
Definition: ecmult_impl.h:817
static SECP256K1_INLINE void secp256k1_ecmult_table_get_ge_lambda(secp256k1_ge *r, const secp256k1_ge *pre, const secp256k1_fe *x, int n, int w)
Definition: ecmult_impl.h:135
#define WINDOW_A
Definition: ecmult_impl.h:32
static size_t secp256k1_strauss_scratch_size(size_t n_points)
Definition: ecmult_impl.h:358
#define ECMULT_PIPPENGER_THRESHOLD
Definition: ecmult_impl.h:55
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)
Definition: ecmult_impl.h:773
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:578
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)
Definition: ecmult_impl.h:728
#define WNAF_BITS
Larger values for ECMULT_WINDOW_SIZE result in possibly better performance at the cost of an exponent...
Definition: ecmult_impl.h:44
#define ECMULT_MAX_POINTS_PER_BATCH
Definition: ecmult_impl.h:57
#define PIPPENGER_MAX_BUCKET_WINDOW
Definition: ecmult_impl.h:52
#define PIPPENGER_SCRATCH_OBJECTS
Definition: ecmult_impl.h:49
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)
Definition: ecmult_impl.h:363
static void secp256k1_ecmult(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
Definition: ecmult_impl.h:346
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:798
static SECP256K1_INLINE void secp256k1_ecmult_table_verify(int n, int w)
Definition: ecmult_impl.h:117
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:497
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:645
static SECP256K1_INLINE void secp256k1_ecmult_table_get_ge(secp256k1_ge *r, const secp256k1_ge *pre, int n, int w)
Definition: ecmult_impl.h:125
static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_ge *pre_a, secp256k1_fe *zr, secp256k1_fe *z, const secp256k1_gej *a)
Fill a table 'pre_a' with precomputed odd multiples of a.
Definition: ecmult_impl.h:73
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)
Definition: ecmult_impl.h:234
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
#define secp256k1_fe_negate(r, a, m)
Negate a field element.
Definition: field.h:216
static const secp256k1_fe secp256k1_const_beta
Definition: field.h:69
#define secp256k1_fe_mul
Definition: field.h:94
#define secp256k1_fe_set_int
Definition: field.h:83
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 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's Z coordinate passed as bzinv).
static void secp256k1_gej_clear(secp256k1_gej *r)
Clear a secp256k1_gej to prevent leaking sensitive information.
static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a)
Set r to be equal to lambda times a, where lambda is chosen in a way such that this is very fast.
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Set a group element (jacobian) equal to the point at infinity.
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Check whether a group element is the point at infinity.
static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y)
Set a group element equal to the point with given X and Y coordinates.
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_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Convert a group element back from the storage type.
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 void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *b)
Rescale a jacobian point by b which must be non-zero.
static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr)
Bring a batch of inputs to the same global z "denominator", based on ratios between (omitted) z coord...
static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a)
Set r equal to the inverse of a (i.e., mirrored around the X axis)
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Check whether a group element is the point at infinity.
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 void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi)
Definition: group_impl.h:97
static const secp256k1_ge secp256k1_ge_const_g
Definition: group_impl.h:70
const secp256k1_ge_storage secp256k1_pre_g_128[ECMULT_TABLE_SIZE(WINDOW_G)]
const secp256k1_ge_storage secp256k1_pre_g[ECMULT_TABLE_SIZE(WINDOW_G)]
#define WINDOW_G
static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k)
Find r1 and r2 such that r1+r2*2^128 = k.
static int secp256k1_scalar_is_even(const secp256k1_scalar *a)
Check whether a scalar, considered as an nonnegative integer, is even.
static int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
Check whether a scalar equals zero.
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).
static int secp256k1_scalar_is_high(const secp256k1_scalar *a)
Check whether a scalar is higher than the group order divided by 2.
static void secp256k1_scalar_split_lambda(secp256k1_scalar *SECP256K1_RESTRICT r1, secp256k1_scalar *SECP256K1_RESTRICT r2, const secp256k1_scalar *SECP256K1_RESTRICT k)
Find r1 and r2 such that r1+r2*lambda = k, where r1 and r2 or their negations are maximum 128 bits lo...
static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
Access bits from a scalar.
static void secp256k1_scalar_clear(secp256k1_scalar *r)
Clear a scalar to prevent the leak of sensitive data.
static const secp256k1_scalar secp256k1_scalar_zero
Definition: scalar_impl.h:28
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_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 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.
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.
#define SECP256K1_INLINE
Definition: util.h:48
#define VERIFY_CHECK(cond)
Definition: util.h:139
This field implementation represents the value as 10 uint32_t limbs in base 2^26.
Definition: field_10x26.h:14
A group element in affine coordinates on the secp256k1 curve, or occasionally on an isomorphic curve ...
Definition: group.h:16
secp256k1_fe y
Definition: group.h:18
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:28
secp256k1_fe y
Definition: group.h:30
secp256k1_fe x
Definition: group.h:29
int infinity
Definition: group.h:32
secp256k1_fe z
Definition: group.h:31
struct secp256k1_pippenger_point_state * ps
Definition: ecmult_impl.h:487
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
secp256k1_fe * aux
Definition: ecmult_impl.h:229
struct secp256k1_strauss_point_state * ps
Definition: ecmult_impl.h:231
secp256k1_ge * pre_a
Definition: ecmult_impl.h:230