src/ecmult_impl.h

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