Bitcoin ABC 0.26.3
P2P Digital Currency
Loading...
Searching...
No Matches
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
18#if defined(EXHAUSTIVE_TEST_ORDER)
19/* We need to lower these values for exhaustive tests because
20 * the tables cannot have infinities in them (this breaks the
21 * affine-isomorphism stuff which tracks z-ratios) */
22# if EXHAUSTIVE_TEST_ORDER > 128
23# define WINDOW_A 5
24# define WINDOW_G 8
25# elif EXHAUSTIVE_TEST_ORDER > 8
26# define WINDOW_A 4
27# define WINDOW_G 4
28# else
29# define WINDOW_A 2
30# define WINDOW_G 2
31# endif
32#else
33/* optimal for 128-bit and 256-bit exponents. */
34# define WINDOW_A 5
44# define WINDOW_G ECMULT_WINDOW_SIZE
45#endif
46
47/* Noone will ever need more than a window size of 24. The code might
48 * be correct for larger values of ECMULT_WINDOW_SIZE but this is not
49 * tested.
50 *
51 * The following limitations are known, and there are probably more:
52 * If WINDOW_G > 27 and size_t has 32 bits, then the code is incorrect
53 * because the size of the memory object that we allocate (in bytes)
54 * will not fit in a size_t.
55 * If WINDOW_G > 31 and int has 32 bits, then the code is incorrect
56 * because certain expressions will overflow.
57 */
58#if ECMULT_WINDOW_SIZE < 2 || ECMULT_WINDOW_SIZE > 24
59# error Set ECMULT_WINDOW_SIZE to an integer in range [2..24].
60#endif
61
62#define WNAF_BITS 128
63#define WNAF_SIZE_BITS(bits, w) (((bits) + (w) - 1) / (w))
64#define WNAF_SIZE(w) WNAF_SIZE_BITS(WNAF_BITS, w)
65
67#define ECMULT_TABLE_SIZE(w) (1 << ((w)-2))
68
69/* The number of objects allocated on the scratch space for ecmult_multi algorithms */
70#define PIPPENGER_SCRATCH_OBJECTS 6
71#define STRAUSS_SCRATCH_OBJECTS 6
72
73#define PIPPENGER_MAX_BUCKET_WINDOW 12
74
75/* Minimum number of points for which pippenger_wnaf is faster than strauss wnaf */
76#define ECMULT_PIPPENGER_THRESHOLD 88
77
78#define ECMULT_MAX_POINTS_PER_BATCH 5000000
79
88 int i;
89
90 VERIFY_CHECK(!a->infinity);
91
93
94 /*
95 * Perform the additions on an isomorphism where 'd' is affine: drop the z coordinate
96 * of 'd', and scale the 1P starting value's x/y coordinates without changing its z.
97 */
98 d_ge.x = d.x;
99 d_ge.y = d.y;
100 d_ge.infinity = 0;
101
103 prej[0].x = a_ge.x;
104 prej[0].y = a_ge.y;
105 prej[0].z = a->z;
106 prej[0].infinity = 0;
107
108 zr[0] = d.z;
109 for (i = 1; i < n; i++) {
110 secp256k1_gej_add_ge_var(&prej[i], &prej[i-1], &d_ge, &zr[i]);
111 }
112
113 /*
114 * Each point in 'prej' has a z coordinate too small by a factor of 'd.z'. Only
115 * the final point's z coordinate is actually used though, so just update that.
116 */
117 secp256k1_fe_mul(&prej[n-1].z, &prej[n-1].z, &d.z);
118}
119
138
139 /* Compute the odd multiples in Jacobian form. */
141 /* Bring them to the same Z denominator. */
143}
144
150 secp256k1_fe zr;
152 int i;
153
154 VERIFY_CHECK(!a->infinity);
155
157
158 /* First, we perform all the additions in an isomorphic curve obtained by multiplying
159 * all `z` coordinates by 1/`d.z`. In these coordinates `d` is affine so we can use
160 * `secp256k1_gej_add_ge_var` to perform the additions. For each addition, we store
161 * the resulting y-coordinate and the z-ratio, since we only have enough memory to
162 * store two field elements. These are sufficient to efficiently undo the isomorphism
163 * and recompute all the `x`s.
164 */
165 d_ge.x = d.x;
166 d_ge.y = d.y;
167 d_ge.infinity = 0;
168
170 pj.x = p_ge.x;
171 pj.y = p_ge.y;
172 pj.z = a->z;
173 pj.infinity = 0;
174
175 for (i = 0; i < (n - 1); i++) {
177 secp256k1_fe_to_storage(&pre[i].y, &pj.y);
180 secp256k1_fe_to_storage(&pre[i].x, &zr);
181 }
182
183 /* Invert d.z in the same batch, preserving pj.z so we can extract 1/d.z */
184 secp256k1_fe_mul(&zi, &pj.z, &d.z);
186
187 /* Directly set `pre[n - 1]` to `pj`, saving the inverted z-coordinate so
188 * that we can combine it with the saved z-ratios to compute the other zs
189 * without any more inversions. */
192
193 /* Compute the actual x-coordinate of D, which will be needed below. */
194 secp256k1_fe_mul(&d.z, &zi, &pj.z); /* d.z = 1/d.z */
197
198 /* Going into the second loop, we have set `pre[n-1]` to its final affine
199 * form, but still need to set `pre[i]` for `i` in 0 through `n-2`. We
200 * have `zi = (p.z * d.z)^-1`, where
201 *
202 * `p.z` is the z-coordinate of the point on the isomorphic curve
203 * which was ultimately assigned to `pre[n-1]`.
204 * `d.z` is the multiplier that must be applied to all z-coordinates
205 * to move from our isomorphic curve back to secp256k1; so the
206 * product `p.z * d.z` is the z-coordinate of the secp256k1
207 * point assigned to `pre[n-1]`.
208 *
209 * All subsequent inverse-z-coordinates can be obtained by multiplying this
210 * factor by successive z-ratios, which is much more efficient than directly
211 * computing each one.
212 *
213 * Importantly, these inverse-zs will be coordinates of points on secp256k1,
214 * while our other stored values come from computations on the isomorphic
215 * curve. So in the below loop, we will take care not to actually use `zi`
216 * or any derived values until we're back on secp256k1.
217 */
218 i = n - 1;
219 while (i > 0) {
221 const secp256k1_fe *rzr;
222 i--;
223
225
226 /* For each remaining point, we extract the z-ratio from the stored
227 * x-coordinate, compute its z^-1 from that, and compute the full
228 * point from that. */
229 rzr = &p_ge.x;
233 /* To compute the actual x-coordinate, we use the stored z ratio and
234 * y-coordinate, which we obtained from `secp256k1_gej_add_ge_var`
235 * in the loop above, as well as the inverse of the square of its
236 * z-coordinate. We store the latter in the `zi2` variable, which is
237 * computed iteratively starting from the overall Z inverse then
238 * multiplying by each z-ratio in turn.
239 *
240 * Denoting the z-ratio as `rzr`, we observe that it is equal to `h`
241 * from the inside of the above `gej_add_ge_var` call. This satisfies
242 *
243 * rzr = d_x * z^2 - x * d_z^2
244 *
245 * where (`d_x`, `d_z`) are Jacobian coordinates of `D` and `(x, z)`
246 * are Jacobian coordinates of our desired point -- except both are on
247 * the isomorphic curve that we were using when we called `gej_add_ge_var`.
248 * To get back to secp256k1, we must multiply both `z`s by `d_z`, or
249 * equivalently divide both `x`s by `d_z^2`. Our equation then becomes
250 *
251 * rzr = d_x * z^2 / d_z^2 - x
252 *
253 * (The left-hand-side, being a ratio of z-coordinates, is unaffected
254 * by the isomorphism.)
255 *
256 * Rearranging to solve for `x`, we have
257 *
258 * x = d_x * z^2 / d_z^2 - rzr
259 *
260 * But what we actually want is the affine coordinate `X = x/z^2`,
261 * which will satisfy
262 *
263 * X = d_x / d_z^2 - rzr / z^2
264 * = dx_over_dz_squared - rzr * zi2
265 */
267 secp256k1_fe_negate(&p_ge.x, &p_ge.x, 1);
269 /* y is stored_y/z^3, as we expect */
270 secp256k1_fe_mul(&p_ge.y, &p_ge.y, &zi3);
271 /* Store */
273 }
274}
275
278#define ECMULT_TABLE_GET_GE(r,pre,n,w) do { \
279 VERIFY_CHECK(((n) & 1) == 1); \
280 VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
281 VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
282 if ((n) > 0) { \
283 *(r) = (pre)[((n)-1)/2]; \
284 } else { \
285 *(r) = (pre)[(-(n)-1)/2]; \
286 secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
287 } \
288} while(0)
289
290#define ECMULT_TABLE_GET_GE_STORAGE(r,pre,n,w) do { \
291 VERIFY_CHECK(((n) & 1) == 1); \
292 VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
293 VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
294 if ((n) > 0) { \
295 secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
296 } else { \
297 secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
298 secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
299 } \
300} while(0)
301
304 + ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G))
305 ;
306
308 ctx->pre_g = NULL;
309 ctx->pre_g_128 = NULL;
310}
311
314 void* const base = *prealloc;
316
317 if (ctx->pre_g != NULL) {
318 return;
319 }
320
321 /* get the generator */
323
324 {
325 size_t size = sizeof((*ctx->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G));
326 /* check for overflow */
327 VERIFY_CHECK(size / sizeof((*ctx->pre_g)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)));
328 ctx->pre_g = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size);
329 }
330
331 /* precompute the tables with odd multiples */
333
334 {
336 int i;
337
338 size_t size = sizeof((*ctx->pre_g_128)[0]) * ((size_t) ECMULT_TABLE_SIZE(WINDOW_G));
339 /* check for overflow */
340 VERIFY_CHECK(size / sizeof((*ctx->pre_g_128)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)));
341 ctx->pre_g_128 = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size);
342
343 /* calculate 2^128*generator */
344 g_128j = gj;
345 for (i = 0; i < 128; i++) {
347 }
349 }
350}
351
353 if (src->pre_g != NULL) {
354 /* We cast to void* first to suppress a -Wcast-align warning. */
355 dst->pre_g = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g) - (unsigned char*)src));
356 }
357 if (src->pre_g_128 != NULL) {
358 dst->pre_g_128 = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g_128) - (unsigned char*)src));
359 }
360}
361
363 return ctx->pre_g != NULL;
364}
365
369
377static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) {
379 int last_set_bit = -1;
380 int bit = 0;
381 int sign = 1;
382 int carry = 0;
383
384 VERIFY_CHECK(wnaf != NULL);
385 VERIFY_CHECK(0 <= len && len <= 256);
386 VERIFY_CHECK(a != NULL);
387 VERIFY_CHECK(2 <= w && w <= 31);
388
389 memset(wnaf, 0, len * sizeof(wnaf[0]));
390
391 s = *a;
392 if (secp256k1_scalar_get_bits(&s, 255, 1)) {
394 sign = -1;
395 }
396
397 while (bit < len) {
398 int now;
399 int word;
400 if (secp256k1_scalar_get_bits(&s, bit, 1) == (unsigned int)carry) {
401 bit++;
402 continue;
403 }
404
405 now = w;
406 if (now > len - bit) {
407 now = len - bit;
408 }
409
411
412 carry = (word >> (w-1)) & 1;
413 word -= carry << w;
414
415 wnaf[bit] = sign * word;
417
418 bit += now;
419 }
420#ifdef VERIFY
421 CHECK(carry == 0);
422 while (bit < 256) {
423 CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0);
424 }
425#endif
426 return last_set_bit + 1;
427}
428
437
445
449 /* Splitted G factors. */
451 int wnaf_ng_1[129];
452 int bits_ng_1 = 0;
453 int wnaf_ng_128[129];
454 int bits_ng_128 = 0;
455 int i;
456 int bits = 0;
457 size_t np;
458 size_t no = 0;
459
460 for (np = 0; np < num; ++np) {
462 continue;
463 }
464 state->ps[no].input_pos = np;
465 /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
466 secp256k1_scalar_split_lambda(&state->ps[no].na_1, &state->ps[no].na_lam, &na[np]);
467
468 /* build wnaf representation for na_1 and na_lam. */
469 state->ps[no].bits_na_1 = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_1, 129, &state->ps[no].na_1, WINDOW_A);
470 state->ps[no].bits_na_lam = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_lam, 129, &state->ps[no].na_lam, WINDOW_A);
471 VERIFY_CHECK(state->ps[no].bits_na_1 <= 129);
472 VERIFY_CHECK(state->ps[no].bits_na_lam <= 129);
473 if (state->ps[no].bits_na_1 > bits) {
474 bits = state->ps[no].bits_na_1;
475 }
476 if (state->ps[no].bits_na_lam > bits) {
477 bits = state->ps[no].bits_na_lam;
478 }
479 ++no;
480 }
481
482 /* Calculate odd multiples of a.
483 * All multiples are brought to the same Z 'denominator', which is stored
484 * in Z. Due to secp256k1' isomorphism we can do all operations pretending
485 * that the Z coordinate was 1, use affine addition formulae, and correct
486 * the Z coordinate of the result once at the end.
487 * The exception is the precomputed G table points, which are actually
488 * affine. Compared to the base used for other points, they have a Z ratio
489 * of 1/Z, so we can use secp256k1_gej_add_zinv_var, which uses the same
490 * isomorphism to efficiently add with a known Z inverse.
491 */
492 if (no > 0) {
493 /* Compute the odd multiples in Jacobian form. */
495 for (np = 1; np < no; ++np) {
496 secp256k1_gej tmp = a[state->ps[np].input_pos];
497#ifdef VERIFY
499#endif
502 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));
503 }
504 /* Bring them to the same Z denominator. */
506 } else {
508 }
509
510 for (np = 0; np < no; ++np) {
511 for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
513 }
514 }
515
516 if (ng) {
517 /* 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) */
519
520 /* Build wnaf representation for ng_1 and ng_128 */
523 if (bits_ng_1 > bits) {
524 bits = bits_ng_1;
525 }
526 if (bits_ng_128 > bits) {
527 bits = bits_ng_128;
528 }
529 }
530
532
533 for (i = bits - 1; i >= 0; i--) {
534 int n;
536 for (np = 0; np < no; ++np) {
537 if (i < state->ps[np].bits_na_1 && (n = state->ps[np].wnaf_na_1[i])) {
540 }
541 if (i < state->ps[np].bits_na_lam && (n = state->ps[np].wnaf_na_lam[i])) {
544 }
545 }
546 if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
549 }
550 if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
551 ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g_128, n, WINDOW_G);
553 }
554 }
555
556 if (!r->infinity) {
557 secp256k1_fe_mul(&r->z, &r->z, &Z);
558 }
559}
560
567 struct secp256k1_strauss_state state;
568
569 state.prej = prej;
570 state.zr = zr;
571 state.pre_a = pre_a;
572 state.pre_a_lam = pre_a_lam;
573 state.ps = ps;
574 secp256k1_ecmult_strauss_wnaf(ctx, &state, r, 1, a, na, ng);
575}
576
578 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);
579 return n_points*point_size;
580}
581
584 secp256k1_scalar* scalars;
585 struct secp256k1_strauss_state state;
586 size_t i;
587 const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
588
590 if (inp_g_sc == NULL && n_points == 0) {
591 return 1;
592 }
593
594 points = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_gej));
595 scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_scalar));
596 state.prej = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_gej));
597 state.zr = (secp256k1_fe*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe));
598 state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
599 state.pre_a_lam = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
600 state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
601
602 if (points == NULL || scalars == NULL || state.prej == NULL || state.zr == NULL || state.pre_a == NULL || state.pre_a_lam == NULL || state.ps == NULL) {
604 return 0;
605 }
606
607 for (i = 0; i < n_points; i++) {
608 secp256k1_ge point;
609 if (!cb(&scalars[i], &point, i+cb_offset, cbdata)) {
611 return 0;
612 }
613 secp256k1_gej_set_ge(&points[i], &point);
614 }
617 return 1;
618}
619
620/* Wrapper for secp256k1_ecmult_multi_func interface */
622 return secp256k1_ecmult_strauss_batch(error_callback, actx, scratch, r, inp_g_sc, cb, cbdata, n, 0);
623}
624
625static size_t secp256k1_strauss_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
627}
628
636static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w) {
637 int skew = 0;
638 int pos;
639 int max_pos;
640 int last_w;
641 const secp256k1_scalar *work = s;
642
644 for (pos = 0; pos < WNAF_SIZE(w); pos++) {
645 wnaf[pos] = 0;
646 }
647 return 0;
648 }
649
651 skew = 1;
652 }
653
654 wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
655 /* Compute last window size. Relevant when window size doesn't divide the
656 * number of bits in the scalar */
657 last_w = WNAF_BITS - (WNAF_SIZE(w) - 1) * w;
658
659 /* Store the position of the first nonzero word in max_pos to allow
660 * skipping leading zeros when calculating the wnaf. */
661 for (pos = WNAF_SIZE(w) - 1; pos > 0; pos--) {
662 int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
663 if(val != 0) {
664 break;
665 }
666 wnaf[pos] = 0;
667 }
668 max_pos = pos;
669 pos = 1;
670
671 while (pos <= max_pos) {
672 int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
673 if ((val & 1) == 0) {
674 wnaf[pos - 1] -= (1 << w);
675 wnaf[pos] = (val + 1);
676 } else {
677 wnaf[pos] = val;
678 }
679 /* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
680 * is strictly negative or strictly positive respectively. Only change
681 * coefficients at previous positions because above code assumes that
682 * wnaf[pos - 1] is odd.
683 */
684 if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) || (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
685 if (wnaf[pos - 1] == 1) {
686 wnaf[pos - 2] += 1 << w;
687 } else {
688 wnaf[pos - 2] -= 1 << w;
689 }
690 wnaf[pos - 1] = 0;
691 }
692 ++pos;
693 }
694
695 return skew;
696}
697
702
707
708/*
709 * pippenger_wnaf computes the result of a multi-point multiplication as
710 * follows: The scalars are brought into wnaf with n_wnaf elements each. Then
711 * for every i < n_wnaf, first each point is added to a "bucket" corresponding
712 * to the point's wnaf[i]. Second, the buckets are added together such that
713 * r += 1*bucket[0] + 3*bucket[1] + 5*bucket[2] + ...
714 */
716 size_t n_wnaf = WNAF_SIZE(bucket_window+1);
717 size_t np;
718 size_t no = 0;
719 int i;
720 int j;
721
722 for (np = 0; np < num; ++np) {
724 continue;
725 }
726 state->ps[no].input_pos = np;
727 state->ps[no].skew_na = secp256k1_wnaf_fixed(&state->wnaf_na[no*n_wnaf], &sc[np], bucket_window+1);
728 no++;
729 }
731
732 if (no == 0) {
733 return 1;
734 }
735
736 for (i = n_wnaf - 1; i >= 0; i--) {
738
739 for(j = 0; j < ECMULT_TABLE_SIZE(bucket_window+2); j++) {
741 }
742
743 for (np = 0; np < no; ++np) {
744 int n = state->wnaf_na[np*n_wnaf + i];
746 secp256k1_ge tmp;
747 int idx;
748
749 if (i == 0) {
750 /* correct for wnaf skew */
751 int skew = point_state.skew_na;
752 if (skew) {
753 secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
755 }
756 }
757 if (n > 0) {
758 idx = (n - 1)/2;
759 secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
760 } else if (n < 0) {
761 idx = -(n + 1)/2;
762 secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
763 secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);
764 }
765 }
766
767 for(j = 0; j < bucket_window; j++) {
769 }
770
772 /* Accumulate the sum: bucket[0] + 3*bucket[1] + 5*bucket[2] + 7*bucket[3] + ...
773 * = bucket[0] + bucket[1] + bucket[2] + bucket[3] + ...
774 * + 2 * (bucket[1] + 2*bucket[2] + 3*bucket[3] + ...)
775 * using an intermediate running sum:
776 * running_sum = bucket[0] + bucket[1] + bucket[2] + ...
777 *
778 * The doubling is done implicitly by deferring the final window doubling (of 'r').
779 */
780 for(j = ECMULT_TABLE_SIZE(bucket_window+2) - 1; j > 0; j--) {
783 }
784
788 }
789 return 1;
790}
791
797 if (n <= 1) {
798 return 1;
799 } else if (n <= 4) {
800 return 2;
801 } else if (n <= 20) {
802 return 3;
803 } else if (n <= 57) {
804 return 4;
805 } else if (n <= 136) {
806 return 5;
807 } else if (n <= 235) {
808 return 6;
809 } else if (n <= 1260) {
810 return 7;
811 } else if (n <= 4420) {
812 return 9;
813 } else if (n <= 7880) {
814 return 10;
815 } else if (n <= 16050) {
816 return 11;
817 } else {
819 }
820}
821
826 switch(bucket_window) {
827 case 1: return 1;
828 case 2: return 4;
829 case 3: return 20;
830 case 4: return 57;
831 case 5: return 136;
832 case 6: return 235;
833 case 7: return 1260;
834 case 8: return 1260;
835 case 9: return 4420;
836 case 10: return 7880;
837 case 11: return 16050;
839 }
840 return 0;
841}
842
843
858
864 size_t entries = 2*n_points + 2;
865 size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
866 return (sizeof(secp256k1_gej) << bucket_window) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size;
867}
868
870 const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch);
871 /* Use 2(n+1) with the endomorphism, when calculating batch
872 * sizes. The reason for +1 is that we add the G scalar to the list of
873 * other scalars. */
874 size_t entries = 2*n_points + 2;
876 secp256k1_scalar *scalars;
879 size_t idx = 0;
880 size_t point_idx = 0;
881 int i, j;
882 int bucket_window;
883
884 (void)ctx;
886 if (inp_g_sc == NULL && n_points == 0) {
887 return 1;
888 }
889
891 points = (secp256k1_ge *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*points));
892 scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*scalars));
893 state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(error_callback, scratch, sizeof(*state_space));
894 if (points == NULL || scalars == NULL || state_space == NULL) {
896 return 0;
897 }
898
899 state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*state_space->ps));
900 state_space->wnaf_na = (int *) secp256k1_scratch_alloc(error_callback, scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int));
901 buckets = (secp256k1_gej *) secp256k1_scratch_alloc(error_callback, scratch, (1<<bucket_window) * sizeof(*buckets));
902 if (state_space->ps == NULL || state_space->wnaf_na == NULL || buckets == NULL) {
904 return 0;
905 }
906
907 if (inp_g_sc != NULL) {
908 scalars[0] = *inp_g_sc;
910 idx++;
911 secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]);
912 idx++;
913 }
914
915 while (point_idx < n_points) {
916 if (!cb(&scalars[idx], &points[idx], point_idx + cb_offset, cbdata)) {
918 return 0;
919 }
920 idx++;
921 secp256k1_ecmult_endo_split(&scalars[idx - 1], &scalars[idx], &points[idx - 1], &points[idx]);
922 idx++;
923 point_idx++;
924 }
925
927
928 /* Clear data */
929 for(i = 0; (size_t)i < idx; i++) {
930 secp256k1_scalar_clear(&scalars[i]);
931 state_space->ps[i].skew_na = 0;
932 for(j = 0; j < WNAF_SIZE(bucket_window+1); j++) {
933 state_space->wnaf_na[i * WNAF_SIZE(bucket_window+1) + j] = 0;
934 }
935 }
936 for(i = 0; i < 1<<bucket_window; i++) {
938 }
940 return 1;
941}
942
943/* Wrapper for secp256k1_ecmult_multi_func interface */
945 return secp256k1_ecmult_pippenger_batch(error_callback, actx, scratch, r, inp_g_sc, cb, cbdata, n, 0);
946}
947
953static size_t secp256k1_pippenger_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) {
955 int bucket_window;
956 size_t res = 0;
957
959 size_t n_points;
961 size_t space_for_points;
962 size_t space_overhead;
963 size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
964
968 break;
969 }
971
974 if (n_points > res) {
975 res = n_points;
976 }
977 if (n_points < max_points) {
978 /* A larger bucket_window may support even more points. But if we
979 * would choose that then the caller couldn't safely use any number
980 * smaller than what this function returns */
981 break;
982 }
983 }
984 return res;
985}
986
987/* Computes ecmult_multi by simply multiplying and adding each point. Does not
988 * require a scratch space */
990 size_t point_idx;
993
997 /* r = inp_g_sc*G */
999 for (point_idx = 0; point_idx < n_points; point_idx++) {
1000 secp256k1_ge point;
1002 secp256k1_scalar scalar;
1003 if (!cb(&scalar, &point, point_idx, cbdata)) {
1004 return 0;
1005 }
1006 /* r += scalar*point */
1007 secp256k1_gej_set_ge(&pointj, &point);
1008 secp256k1_ecmult(ctx, &tmpj, &pointj, &scalar, NULL);
1010 }
1011 return 1;
1012}
1013
1014/* Compute the number of batches and the batch size given the maximum batch size and the
1015 * total number of points */
1017 if (max_n_batch_points == 0) {
1018 return 0;
1019 }
1022 }
1023 if (n == 0) {
1024 *n_batches = 0;
1025 *n_batch_points = 0;
1026 return 1;
1027 }
1028 /* Compute ceil(n/max_n_batch_points) and ceil(n/n_batches) */
1029 *n_batches = 1 + (n - 1) / max_n_batch_points;
1030 *n_batch_points = 1 + (n - 1) / *n_batches;
1031 return 1;
1032}
1033
1036 size_t i;
1037
1039 size_t n_batches;
1040 size_t n_batch_points;
1041
1043 if (inp_g_sc == NULL && n == 0) {
1044 return 1;
1045 } else if (n == 0) {
1049 return 1;
1050 }
1051 if (scratch == NULL) {
1053 }
1054
1055 /* Compute the batch sizes for Pippenger's algorithm given a scratch space. If it's greater than
1056 * a threshold use Pippenger's algorithm. Otherwise use Strauss' algorithm.
1057 * As a first step check if there's enough space for Pippenger's algo (which requires less space
1058 * than Strauss' algo) and if not, use the simple algorithm. */
1061 }
1064 } else {
1067 }
1069 }
1070 for(i = 0; i < n_batches; i++) {
1071 size_t nbp = n < n_batch_points ? n : n_batch_points;
1072 size_t offset = n_batch_points*i;
1073 secp256k1_gej tmp;
1074 if (!f(error_callback, ctx, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) {
1075 return 0;
1076 }
1077 secp256k1_gej_add_var(r, r, &tmp, NULL);
1078 n -= nbp;
1079 }
1080 return 1;
1081}
1082
1083#endif /* SECP256K1_ECMULT_IMPL_H */
secp256k1_context * ctx
int() secp256k1_ecmult_multi_callback(secp256k1_scalar *sc, secp256k1_ge *pt, size_t idx, void *data)
Definition ecmult.h:29
#define STRAUSS_SCRATCH_OBJECTS
Definition ecmult_impl.h:71
static size_t secp256k1_pippenger_bucket_window_inv(int bucket_window)
Returns the maximum optimal number of points for a bucket_window.
static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx)
static int secp256k1_ecmult_pippenger_batch(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset)
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.
#define WNAF_SIZE(w)
Definition ecmult_impl.h:64
static size_t secp256k1_strauss_max_points(const secp256k1_callback *error_callback, secp256k1_scratch *scratch)
static void secp256k1_ecmult_odd_multiples_table_globalz_windowa(secp256k1_ge *pre, secp256k1_fe *globalz, const secp256k1_gej *a)
Fill a table 'pre' with precomputed odd multiples of a.
static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w)
Convert a number to WNAF notation.
static SECP256K1_INLINE void secp256k1_ecmult_endo_split(secp256k1_scalar *s1, secp256k1_scalar *s2, secp256k1_ge *p1, secp256k1_ge *p2)
static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx)
#define ECMULT_TABLE_GET_GE_STORAGE(r, pre, n, w)
static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w)
Convert a number to WNAF notation.
static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, secp256k1_fe *zr, const secp256k1_gej *a)
Fill a table 'prej' with precomputed odd multiples of a.
Definition ecmult_impl.h:85
static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n)
#define WINDOW_A
Definition ecmult_impl.h:34
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)
static size_t secp256k1_strauss_scratch_size(size_t n_points)
#define ECMULT_PIPPENGER_THRESHOLD
Definition ecmult_impl.h:76
static const size_t SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE
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...
#define WNAF_BITS
Definition ecmult_impl.h:62
static void secp256k1_ecmult_strauss_wnaf(const secp256k1_ecmult_context *ctx, const struct secp256k1_strauss_state *state, secp256k1_gej *r, size_t num, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
#define ECMULT_MAX_POINTS_PER_BATCH
Definition ecmult_impl.h:78
#define PIPPENGER_MAX_BUCKET_WINDOW
Definition ecmult_impl.h:73
#define ECMULT_TABLE_SIZE(w)
The number of entries a table with precomputed multiples needs to have.
Definition ecmult_impl.h:67
#define PIPPENGER_SCRATCH_OBJECTS
Definition ecmult_impl.h:70
static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx)
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)
static void secp256k1_ecmult_context_finalize_memcpy(secp256k1_ecmult_context *dst, const secp256k1_ecmult_context *src)
static void secp256k1_ecmult(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, void **prealloc)
static int secp256k1_ecmult_strauss_batch(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset)
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)
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...
int(* secp256k1_ecmult_multi_func)(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *, secp256k1_scratch *, secp256k1_gej *, const secp256k1_scalar *, secp256k1_ecmult_multi_callback cb, void *, size_t)
static int secp256k1_ecmult_multi_var(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n)
static int secp256k1_ecmult_strauss_batch_single(const secp256k1_callback *error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n)
static void secp256k1_ecmult_odd_multiples_table_storage_var(const int n, secp256k1_ge_storage *pre, const secp256k1_gej *a)
#define ECMULT_TABLE_GET_GE(r, pre, n, w)
The following two macro retrieves a particular odd multiple from a table of precomputed multiples.
#define WINDOW_G
Larger values for ECMULT_WINDOW_SIZE result in possibly better performance at the cost of an exponent...
Definition ecmult_impl.h:44
static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a)
Potentially faster version of secp256k1_fe_inv, without constant-time guarantee.
static void secp256k1_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 void secp256k1_fe_set_int(secp256k1_fe *r, int a)
Set a field element equal to a small 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_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a)
Sets a field element to be the square of another.
static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a)
Adds a field element to another.
static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a)
Convert a field element to the storage type.
static void secp256k1_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_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_globalz_set_table_gej(size_t len, secp256k1_ge *r, secp256k1_fe *globalz, const secp256k1_gej *a, const secp256k1_fe *zr)
Bring a batch inputs given in jacobian coordinates (with known z-ratios) to the same global z "denomi...
static 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_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_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Convert a group element to the storage type.
static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi)
Definition group_impl.h:62
static const secp256k1_ge secp256k1_ge_const_g
Generator for secp256k1, value 'g' defined in "Standards for Efficient Cryptography" (SEC2) 2....
Definition group_impl.h:52
T GetRand(T nMax=std::numeric_limits< T >::max()) noexcept
Generate a uniform random integer of type T in the range [0..nMax) nMax defaults to std::numeric_limi...
Definition random.h:85
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 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 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_checkpoint(const secp256k1_callback *error_callback, const secp256k1_scratch *scratch)
Returns an opaque object used to "checkpoint" a scratch space.
static SECP256K1_INLINE void * manual_alloc(void **prealloc_ptr, size_t alloc_size, void *base, size_t max_size)
Definition util.h:134
#define ROUND_TO_ALIGN(size)
Definition util.h:116
#define CHECK(cond)
Definition util.h:53
#define VERIFY_CHECK(cond)
Definition util.h:68
#define SECP256K1_INLINE
Definition secp256k1.h:127
secp256k1_ge_storage(* pre_g_128)[]
Definition ecmult.h:17
secp256k1_ge_storage(* pre_g)[]
Definition ecmult.h:16
A group element of the secp256k1 curve, in affine coordinates.
Definition group.h:13
A group element of the secp256k1 curve, in jacobian coordinates.
Definition group.h:23
secp256k1_fe y
Definition group.h:25
secp256k1_fe x
Definition group.h:24
int infinity
Definition group.h:27
secp256k1_fe z
Definition group.h:26
struct secp256k1_pippenger_point_state * ps
A scalar modulo the group order of the secp256k1 curve.
Definition scalar_4x64.h:13
secp256k1_ge * pre_a_lam
struct secp256k1_strauss_point_state * ps
secp256k1_gej * prej