Bitcoin Core  24.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 equvalent to a.
101  * Set zr[0] to C, which is the ratio between the omitted z(pre_a[0]) value and a.z.
102  */
103  zr[0] = d.z;
104 
105  for (i = 1; i < n; i++) {
106  secp256k1_gej_add_ge_var(&ai, &ai, &d_ge, &zr[i]);
107  secp256k1_ge_set_xy(&pre_a[i], &ai.x, &ai.y);
108  }
109 
110  /* Multiply the last z-coordinate by C to undo the isomorphism.
111  * Since the z-coordinates of the pre_a values are implied by the zr array of z-coordinate ratios,
112  * undoing the isomorphism here undoes the isomorphism for all pre_a values.
113  */
114  secp256k1_fe_mul(z, &ai.z, &d.z);
115 }
116 
117 #define SECP256K1_ECMULT_TABLE_VERIFY(n,w) \
118  VERIFY_CHECK(((n) & 1) == 1); \
119  VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
120  VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1));
121 
122 SECP256K1_INLINE static void secp256k1_ecmult_table_get_ge(secp256k1_ge *r, const secp256k1_ge *pre, int n, int w) {
124  if (n > 0) {
125  *r = pre[(n-1)/2];
126  } else {
127  *r = pre[(-n-1)/2];
128  secp256k1_fe_negate(&(r->y), &(r->y), 1);
129  }
130 }
131 
134  if (n > 0) {
135  secp256k1_ge_set_xy(r, &x[(n-1)/2], &pre[(n-1)/2].y);
136  } else {
137  secp256k1_ge_set_xy(r, &x[(-n-1)/2], &pre[(-n-1)/2].y);
138  secp256k1_fe_negate(&(r->y), &(r->y), 1);
139  }
140 }
141 
144  if (n > 0) {
145  secp256k1_ge_from_storage(r, &pre[(n-1)/2]);
146  } else {
147  secp256k1_ge_from_storage(r, &pre[(-n-1)/2]);
148  secp256k1_fe_negate(&(r->y), &(r->y), 1);
149  }
150 }
151 
159 static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) {
161  int last_set_bit = -1;
162  int bit = 0;
163  int sign = 1;
164  int carry = 0;
165 
166  VERIFY_CHECK(wnaf != NULL);
167  VERIFY_CHECK(0 <= len && len <= 256);
168  VERIFY_CHECK(a != NULL);
169  VERIFY_CHECK(2 <= w && w <= 31);
170 
171  memset(wnaf, 0, len * sizeof(wnaf[0]));
172 
173  s = *a;
174  if (secp256k1_scalar_get_bits(&s, 255, 1)) {
175  secp256k1_scalar_negate(&s, &s);
176  sign = -1;
177  }
178 
179  while (bit < len) {
180  int now;
181  int word;
182  if (secp256k1_scalar_get_bits(&s, bit, 1) == (unsigned int)carry) {
183  bit++;
184  continue;
185  }
186 
187  now = w;
188  if (now > len - bit) {
189  now = len - bit;
190  }
191 
192  word = secp256k1_scalar_get_bits_var(&s, bit, now) + carry;
193 
194  carry = (word >> (w-1)) & 1;
195  word -= carry << w;
196 
197  wnaf[bit] = sign * word;
198  last_set_bit = bit;
199 
200  bit += now;
201  }
202 #ifdef VERIFY
203  CHECK(carry == 0);
204  while (bit < 256) {
205  CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0);
206  }
207 #endif
208  return last_set_bit + 1;
209 }
210 
212  int wnaf_na_1[129];
213  int wnaf_na_lam[129];
216 };
217 
219  /* aux is used to hold z-ratios, and then used to hold pre_a[i].x * BETA values. */
223 };
224 
225 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) {
226  secp256k1_ge tmpa;
227  secp256k1_fe Z;
228  /* Split G factors. */
229  secp256k1_scalar ng_1, ng_128;
230  int wnaf_ng_1[129];
231  int bits_ng_1 = 0;
232  int wnaf_ng_128[129];
233  int bits_ng_128 = 0;
234  int i;
235  int bits = 0;
236  size_t np;
237  size_t no = 0;
238 
239  secp256k1_fe_set_int(&Z, 1);
240  for (np = 0; np < num; ++np) {
241  secp256k1_gej tmp;
242  secp256k1_scalar na_1, na_lam;
243  if (secp256k1_scalar_is_zero(&na[np]) || secp256k1_gej_is_infinity(&a[np])) {
244  continue;
245  }
246  /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
247  secp256k1_scalar_split_lambda(&na_1, &na_lam, &na[np]);
248 
249  /* build wnaf representation for na_1 and na_lam. */
250  state->ps[no].bits_na_1 = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_1, 129, &na_1, WINDOW_A);
251  state->ps[no].bits_na_lam = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_lam, 129, &na_lam, WINDOW_A);
252  VERIFY_CHECK(state->ps[no].bits_na_1 <= 129);
253  VERIFY_CHECK(state->ps[no].bits_na_lam <= 129);
254  if (state->ps[no].bits_na_1 > bits) {
255  bits = state->ps[no].bits_na_1;
256  }
257  if (state->ps[no].bits_na_lam > bits) {
258  bits = state->ps[no].bits_na_lam;
259  }
260 
261  /* Calculate odd multiples of a.
262  * All multiples are brought to the same Z 'denominator', which is stored
263  * in Z. Due to secp256k1' isomorphism we can do all operations pretending
264  * that the Z coordinate was 1, use affine addition formulae, and correct
265  * the Z coordinate of the result once at the end.
266  * The exception is the precomputed G table points, which are actually
267  * affine. Compared to the base used for other points, they have a Z ratio
268  * of 1/Z, so we can use secp256k1_gej_add_zinv_var, which uses the same
269  * isomorphism to efficiently add with a known Z inverse.
270  */
271  tmp = a[np];
272  if (no) {
273 #ifdef VERIFY
275 #endif
276  secp256k1_gej_rescale(&tmp, &Z);
277  }
279  if (no) secp256k1_fe_mul(state->aux + no * ECMULT_TABLE_SIZE(WINDOW_A), state->aux + no * ECMULT_TABLE_SIZE(WINDOW_A), &(a[np].z));
280 
281  ++no;
282  }
283 
284  /* Bring them to the same Z denominator. */
286 
287  for (np = 0; np < no; ++np) {
288  for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
290  }
291  }
292 
293  if (ng) {
294  /* 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) */
295  secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
296 
297  /* Build wnaf representation for ng_1 and ng_128 */
298  bits_ng_1 = secp256k1_ecmult_wnaf(wnaf_ng_1, 129, &ng_1, WINDOW_G);
299  bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, 129, &ng_128, WINDOW_G);
300  if (bits_ng_1 > bits) {
301  bits = bits_ng_1;
302  }
303  if (bits_ng_128 > bits) {
304  bits = bits_ng_128;
305  }
306  }
307 
309 
310  for (i = bits - 1; i >= 0; i--) {
311  int n;
312  secp256k1_gej_double_var(r, r, NULL);
313  for (np = 0; np < no; ++np) {
314  if (i < state->ps[np].bits_na_1 && (n = state->ps[np].wnaf_na_1[i])) {
316  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
317  }
318  if (i < state->ps[np].bits_na_lam && (n = state->ps[np].wnaf_na_lam[i])) {
320  secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
321  }
322  }
323  if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
325  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
326  }
327  if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
329  secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
330  }
331  }
332 
333  if (!r->infinity) {
334  secp256k1_fe_mul(&r->z, &r->z, &Z);
335  }
336 }
337 
338 static void secp256k1_ecmult(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
341  struct secp256k1_strauss_point_state ps[1];
342  struct secp256k1_strauss_state state;
343 
344  state.aux = aux;
345  state.pre_a = pre_a;
346  state.ps = ps;
347  secp256k1_ecmult_strauss_wnaf(&state, r, 1, a, na, ng);
348 }
349 
350 static size_t secp256k1_strauss_scratch_size(size_t n_points) {
351  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);
352  return n_points*point_size;
353 }
354 
355 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) {
356  secp256k1_gej* points;
357  secp256k1_scalar* scalars;
358  struct secp256k1_strauss_state state;
359  size_t i;
360  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
361 
363  if (inp_g_sc == NULL && n_points == 0) {
364  return 1;
365  }
366 
367  /* We allocate STRAUSS_SCRATCH_OBJECTS objects on the scratch space. If these
368  * allocations change, make sure to update the STRAUSS_SCRATCH_OBJECTS
369  * constant and strauss_scratch_size accordingly. */
370  points = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_gej));
371  scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_scalar));
372  state.aux = (secp256k1_fe*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe));
373  state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
374  state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
375 
376  if (points == NULL || scalars == NULL || state.aux == NULL || state.pre_a == NULL || state.ps == NULL) {
377  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
378  return 0;
379  }
380 
381  for (i = 0; i < n_points; i++) {
382  secp256k1_ge point;
383  if (!cb(&scalars[i], &point, i+cb_offset, cbdata)) {
384  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
385  return 0;
386  }
387  secp256k1_gej_set_ge(&points[i], &point);
388  }
389  secp256k1_ecmult_strauss_wnaf(&state, r, n_points, points, scalars, inp_g_sc);
390  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
391  return 1;
392 }
393 
394 /* Wrapper for secp256k1_ecmult_multi_func interface */
395 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) {
396  return secp256k1_ecmult_strauss_batch(error_callback, scratch, r, inp_g_sc, cb, cbdata, n, 0);
397 }
398 
399 static size_t secp256k1_strauss_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
401 }
402 
410 static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w) {
411  int skew = 0;
412  int pos;
413  int max_pos;
414  int last_w;
415  const secp256k1_scalar *work = s;
416 
417  if (secp256k1_scalar_is_zero(s)) {
418  for (pos = 0; pos < WNAF_SIZE(w); pos++) {
419  wnaf[pos] = 0;
420  }
421  return 0;
422  }
423 
424  if (secp256k1_scalar_is_even(s)) {
425  skew = 1;
426  }
427 
428  wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
429  /* Compute last window size. Relevant when window size doesn't divide the
430  * number of bits in the scalar */
431  last_w = WNAF_BITS - (WNAF_SIZE(w) - 1) * w;
432 
433  /* Store the position of the first nonzero word in max_pos to allow
434  * skipping leading zeros when calculating the wnaf. */
435  for (pos = WNAF_SIZE(w) - 1; pos > 0; pos--) {
436  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
437  if(val != 0) {
438  break;
439  }
440  wnaf[pos] = 0;
441  }
442  max_pos = pos;
443  pos = 1;
444 
445  while (pos <= max_pos) {
446  int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
447  if ((val & 1) == 0) {
448  wnaf[pos - 1] -= (1 << w);
449  wnaf[pos] = (val + 1);
450  } else {
451  wnaf[pos] = val;
452  }
453  /* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
454  * is strictly negative or strictly positive respectively. Only change
455  * coefficients at previous positions because above code assumes that
456  * wnaf[pos - 1] is odd.
457  */
458  if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) || (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
459  if (wnaf[pos - 1] == 1) {
460  wnaf[pos - 2] += 1 << w;
461  } else {
462  wnaf[pos - 2] -= 1 << w;
463  }
464  wnaf[pos - 1] = 0;
465  }
466  ++pos;
467  }
468 
469  return skew;
470 }
471 
473  int skew_na;
474  size_t input_pos;
475 };
476 
478  int *wnaf_na;
480 };
481 
482 /*
483  * pippenger_wnaf computes the result of a multi-point multiplication as
484  * follows: The scalars are brought into wnaf with n_wnaf elements each. Then
485  * for every i < n_wnaf, first each point is added to a "bucket" corresponding
486  * to the point's wnaf[i]. Second, the buckets are added together such that
487  * r += 1*bucket[0] + 3*bucket[1] + 5*bucket[2] + ...
488  */
489 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) {
490  size_t n_wnaf = WNAF_SIZE(bucket_window+1);
491  size_t np;
492  size_t no = 0;
493  int i;
494  int j;
495 
496  for (np = 0; np < num; ++np) {
497  if (secp256k1_scalar_is_zero(&sc[np]) || secp256k1_ge_is_infinity(&pt[np])) {
498  continue;
499  }
500  state->ps[no].input_pos = np;
501  state->ps[no].skew_na = secp256k1_wnaf_fixed(&state->wnaf_na[no*n_wnaf], &sc[np], bucket_window+1);
502  no++;
503  }
505 
506  if (no == 0) {
507  return 1;
508  }
509 
510  for (i = n_wnaf - 1; i >= 0; i--) {
511  secp256k1_gej running_sum;
512 
513  for(j = 0; j < ECMULT_TABLE_SIZE(bucket_window+2); j++) {
514  secp256k1_gej_set_infinity(&buckets[j]);
515  }
516 
517  for (np = 0; np < no; ++np) {
518  int n = state->wnaf_na[np*n_wnaf + i];
519  struct secp256k1_pippenger_point_state point_state = state->ps[np];
520  secp256k1_ge tmp;
521  int idx;
522 
523  if (i == 0) {
524  /* correct for wnaf skew */
525  int skew = point_state.skew_na;
526  if (skew) {
527  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
528  secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);
529  }
530  }
531  if (n > 0) {
532  idx = (n - 1)/2;
533  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
534  } else if (n < 0) {
535  idx = -(n + 1)/2;
536  secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
537  secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);
538  }
539  }
540 
541  for(j = 0; j < bucket_window; j++) {
542  secp256k1_gej_double_var(r, r, NULL);
543  }
544 
545  secp256k1_gej_set_infinity(&running_sum);
546  /* Accumulate the sum: bucket[0] + 3*bucket[1] + 5*bucket[2] + 7*bucket[3] + ...
547  * = bucket[0] + bucket[1] + bucket[2] + bucket[3] + ...
548  * + 2 * (bucket[1] + 2*bucket[2] + 3*bucket[3] + ...)
549  * using an intermediate running sum:
550  * running_sum = bucket[0] + bucket[1] + bucket[2] + ...
551  *
552  * The doubling is done implicitly by deferring the final window doubling (of 'r').
553  */
554  for(j = ECMULT_TABLE_SIZE(bucket_window+2) - 1; j > 0; j--) {
555  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[j], NULL);
556  secp256k1_gej_add_var(r, r, &running_sum, NULL);
557  }
558 
559  secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[0], NULL);
560  secp256k1_gej_double_var(r, r, NULL);
561  secp256k1_gej_add_var(r, r, &running_sum, NULL);
562  }
563  return 1;
564 }
565 
570 static int secp256k1_pippenger_bucket_window(size_t n) {
571  if (n <= 1) {
572  return 1;
573  } else if (n <= 4) {
574  return 2;
575  } else if (n <= 20) {
576  return 3;
577  } else if (n <= 57) {
578  return 4;
579  } else if (n <= 136) {
580  return 5;
581  } else if (n <= 235) {
582  return 6;
583  } else if (n <= 1260) {
584  return 7;
585  } else if (n <= 4420) {
586  return 9;
587  } else if (n <= 7880) {
588  return 10;
589  } else if (n <= 16050) {
590  return 11;
591  } else {
593  }
594 }
595 
599 static size_t secp256k1_pippenger_bucket_window_inv(int bucket_window) {
600  switch(bucket_window) {
601  case 1: return 1;
602  case 2: return 4;
603  case 3: return 20;
604  case 4: return 57;
605  case 5: return 136;
606  case 6: return 235;
607  case 7: return 1260;
608  case 8: return 1260;
609  case 9: return 4420;
610  case 10: return 7880;
611  case 11: return 16050;
612  case PIPPENGER_MAX_BUCKET_WINDOW: return SIZE_MAX;
613  }
614  return 0;
615 }
616 
617 
619  secp256k1_scalar tmp = *s1;
620  secp256k1_scalar_split_lambda(s1, s2, &tmp);
621  secp256k1_ge_mul_lambda(p2, p1);
622 
623  if (secp256k1_scalar_is_high(s1)) {
624  secp256k1_scalar_negate(s1, s1);
625  secp256k1_ge_neg(p1, p1);
626  }
627  if (secp256k1_scalar_is_high(s2)) {
628  secp256k1_scalar_negate(s2, s2);
629  secp256k1_ge_neg(p2, p2);
630  }
631 }
632 
637 static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window) {
638  size_t entries = 2*n_points + 2;
639  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
640  return (sizeof(secp256k1_gej) << bucket_window) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size;
641 }
642 
643 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) {
644  const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
645  /* Use 2(n+1) with the endomorphism, when calculating batch
646  * sizes. The reason for +1 is that we add the G scalar to the list of
647  * other scalars. */
648  size_t entries = 2*n_points + 2;
649  secp256k1_ge *points;
650  secp256k1_scalar *scalars;
651  secp256k1_gej *buckets;
652  struct secp256k1_pippenger_state *state_space;
653  size_t idx = 0;
654  size_t point_idx = 0;
655  int i, j;
656  int bucket_window;
657 
659  if (inp_g_sc == NULL && n_points == 0) {
660  return 1;
661  }
662  bucket_window = secp256k1_pippenger_bucket_window(n_points);
663 
664  /* We allocate PIPPENGER_SCRATCH_OBJECTS objects on the scratch space. If
665  * these allocations change, make sure to update the
666  * PIPPENGER_SCRATCH_OBJECTS constant and pippenger_scratch_size
667  * accordingly. */
668  points = (secp256k1_ge *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*points));
669  scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*scalars));
670  state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(error_callback, scratch, sizeof(*state_space));
671  if (points == NULL || scalars == NULL || state_space == NULL) {
672  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
673  return 0;
674  }
675  state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*state_space->ps));
676  state_space->wnaf_na = (int *) secp256k1_scratch_alloc(error_callback, scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int));
677  buckets = (secp256k1_gej *) secp256k1_scratch_alloc(error_callback, scratch, (1<<bucket_window) * sizeof(*buckets));
678  if (state_space->ps == NULL || state_space->wnaf_na == NULL || buckets == NULL) {
679  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
680  return 0;
681  }
682 
683  if (inp_g_sc != NULL) {
684  scalars[0] = *inp_g_sc;
685  points[0] = secp256k1_ge_const_g;
686  idx++;
687  secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]);
688  idx++;
689  }
690 
691  while (point_idx < n_points) {
692  if (!cb(&scalars[idx], &points[idx], point_idx + cb_offset, cbdata)) {
693  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
694  return 0;
695  }
696  idx++;
697  secp256k1_ecmult_endo_split(&scalars[idx - 1], &scalars[idx], &points[idx - 1], &points[idx]);
698  idx++;
699  point_idx++;
700  }
701 
702  secp256k1_ecmult_pippenger_wnaf(buckets, bucket_window, state_space, r, scalars, points, idx);
703 
704  /* Clear data */
705  for(i = 0; (size_t)i < idx; i++) {
706  secp256k1_scalar_clear(&scalars[i]);
707  state_space->ps[i].skew_na = 0;
708  for(j = 0; j < WNAF_SIZE(bucket_window+1); j++) {
709  state_space->wnaf_na[i * WNAF_SIZE(bucket_window+1) + j] = 0;
710  }
711  }
712  for(i = 0; i < 1<<bucket_window; i++) {
713  secp256k1_gej_clear(&buckets[i]);
714  }
715  secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint);
716  return 1;
717 }
718 
719 /* Wrapper for secp256k1_ecmult_multi_func interface */
720 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) {
721  return secp256k1_ecmult_pippenger_batch(error_callback, scratch, r, inp_g_sc, cb, cbdata, n, 0);
722 }
723 
729 static size_t secp256k1_pippenger_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
730  size_t max_alloc = secp256k1_scratch_max_allocation(error_callback, scratch, PIPPENGER_SCRATCH_OBJECTS);
731  int bucket_window;
732  size_t res = 0;
733 
734  for (bucket_window = 1; bucket_window <= PIPPENGER_MAX_BUCKET_WINDOW; bucket_window++) {
735  size_t n_points;
736  size_t max_points = secp256k1_pippenger_bucket_window_inv(bucket_window);
737  size_t space_for_points;
738  size_t space_overhead;
739  size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
740 
741  entry_size = 2*entry_size;
742  space_overhead = (sizeof(secp256k1_gej) << bucket_window) + entry_size + sizeof(struct secp256k1_pippenger_state);
743  if (space_overhead > max_alloc) {
744  break;
745  }
746  space_for_points = max_alloc - space_overhead;
747 
748  n_points = space_for_points/entry_size;
749  n_points = n_points > max_points ? max_points : n_points;
750  if (n_points > res) {
751  res = n_points;
752  }
753  if (n_points < max_points) {
754  /* A larger bucket_window may support even more points. But if we
755  * would choose that then the caller couldn't safely use any number
756  * smaller than what this function returns */
757  break;
758  }
759  }
760  return res;
761 }
762 
763 /* Computes ecmult_multi by simply multiplying and adding each point. Does not
764  * require a scratch space */
765 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) {
766  size_t point_idx;
767  secp256k1_scalar szero;
768  secp256k1_gej tmpj;
769 
770  secp256k1_scalar_set_int(&szero, 0);
773  /* r = inp_g_sc*G */
774  secp256k1_ecmult(r, &tmpj, &szero, inp_g_sc);
775  for (point_idx = 0; point_idx < n_points; point_idx++) {
776  secp256k1_ge point;
777  secp256k1_gej pointj;
778  secp256k1_scalar scalar;
779  if (!cb(&scalar, &point, point_idx, cbdata)) {
780  return 0;
781  }
782  /* r += scalar*point */
783  secp256k1_gej_set_ge(&pointj, &point);
784  secp256k1_ecmult(&tmpj, &pointj, &scalar, NULL);
785  secp256k1_gej_add_var(r, r, &tmpj, NULL);
786  }
787  return 1;
788 }
789 
790 /* Compute the number of batches and the batch size given the maximum batch size and the
791  * total number of points */
792 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) {
793  if (max_n_batch_points == 0) {
794  return 0;
795  }
796  if (max_n_batch_points > ECMULT_MAX_POINTS_PER_BATCH) {
797  max_n_batch_points = ECMULT_MAX_POINTS_PER_BATCH;
798  }
799  if (n == 0) {
800  *n_batches = 0;
801  *n_batch_points = 0;
802  return 1;
803  }
804  /* Compute ceil(n/max_n_batch_points) and ceil(n/n_batches) */
805  *n_batches = 1 + (n - 1) / max_n_batch_points;
806  *n_batch_points = 1 + (n - 1) / *n_batches;
807  return 1;
808 }
809 
811 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) {
812  size_t i;
813 
814  int (*f)(const secp256k1_callback* error_callback, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t);
815  size_t n_batches;
816  size_t n_batch_points;
817 
819  if (inp_g_sc == NULL && n == 0) {
820  return 1;
821  } else if (n == 0) {
822  secp256k1_scalar szero;
823  secp256k1_scalar_set_int(&szero, 0);
824  secp256k1_ecmult(r, r, &szero, inp_g_sc);
825  return 1;
826  }
827  if (scratch == NULL) {
828  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
829  }
830 
831  /* Compute the batch sizes for Pippenger's algorithm given a scratch space. If it's greater than
832  * a threshold use Pippenger's algorithm. Otherwise use Strauss' algorithm.
833  * As a first step check if there's enough space for Pippenger's algo (which requires less space
834  * than Strauss' algo) and if not, use the simple algorithm. */
835  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(error_callback, scratch), n)) {
836  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
837  }
838  if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) {
840  } else {
841  if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(error_callback, scratch), n)) {
842  return secp256k1_ecmult_multi_simple_var(r, inp_g_sc, cb, cbdata, n);
843  }
845  }
846  for(i = 0; i < n_batches; i++) {
847  size_t nbp = n < n_batch_points ? n : n_batch_points;
848  size_t offset = n_batch_points*i;
849  secp256k1_gej tmp;
850  if (!f(error_callback, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) {
851  return 0;
852  }
853  secp256k1_gej_add_var(r, r, &tmp, NULL);
854  n -= nbp;
855  }
856  return 1;
857 }
858 
859 #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:30
int() secp256k1_ecmult_multi_callback(secp256k1_scalar *sc, secp256k1_ge *pt, size_t idx, void *data)
Definition: ecmult.h:35
#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:599
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:729
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:643
#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:395
static size_t secp256k1_strauss_max_points(const secp256k1_callback *error_callback, secp256k1_scratch *scratch)
Definition: ecmult_impl.h:399
static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w)
Convert a number to WNAF notation.
Definition: ecmult_impl.h:410
static SECP256K1_INLINE void secp256k1_ecmult_endo_split(secp256k1_scalar *s1, secp256k1_scalar *s2, secp256k1_ge *p1, secp256k1_ge *p2)
Definition: ecmult_impl.h:618
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:159
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:142
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:811
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:132
#define SECP256K1_ECMULT_TABLE_VERIFY(n, w)
Definition: ecmult_impl.h:117
#define WINDOW_A
Definition: ecmult_impl.h:32
static size_t secp256k1_strauss_scratch_size(size_t n_points)
Definition: ecmult_impl.h:350
#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:765
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:570
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:720
#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:355
static void secp256k1_ecmult(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
Definition: ecmult_impl.h:338
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:792
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:489
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:637
static SECP256K1_INLINE void secp256k1_ecmult_table_get_ge(secp256k1_ge *r, const secp256k1_ge *pre, int n, int w)
Definition: ecmult_impl.h:122
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:225
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:810
static void secp256k1_fe_normalize_var(secp256k1_fe *r)
Normalize a field element, without constant-time guarantee.
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 const secp256k1_fe secp256k1_const_beta
Definition: field.h:36
static void secp256k1_fe_set_int(secp256k1_fe *r, int a)
Set a field element equal to a small (not greater than 0x7FFF), non-negative integer.
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_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:67
static const secp256k1_ge secp256k1_ge_const_g
Definition: group_impl.h:62
#define CHECK(cond)
Unconditional failure on condition failure.
Definition: util.h:35
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 void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
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 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 void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k)
Find r1 and r2 such that r1+r2*lambda = k, where r1 and r2 or their negations are maximum 128 bits lo...
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 VERIFY_CHECK(cond)
Definition: util.h:95
#define SECP256K1_INLINE
Definition: secp256k1.h:127
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:479
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
secp256k1_fe * aux
Definition: ecmult_impl.h:220
struct secp256k1_strauss_point_state * ps
Definition: ecmult_impl.h:222
secp256k1_ge * pre_a
Definition: ecmult_impl.h:221