7#ifndef SECP256K1_ECMULT_IMPL_H
8#define SECP256K1_ECMULT_IMPL_H
18#if defined(EXHAUSTIVE_TEST_ORDER)
22# if EXHAUSTIVE_TEST_ORDER > 128
25# elif EXHAUSTIVE_TEST_ORDER > 8
44# define WINDOW_G ECMULT_WINDOW_SIZE
58#if ECMULT_WINDOW_SIZE < 2 || ECMULT_WINDOW_SIZE > 24
59# error Set ECMULT_WINDOW_SIZE to an integer in range [2..24].
63#define WNAF_SIZE_BITS(bits, w) (((bits) + (w) - 1) / (w))
64#define WNAF_SIZE(w) WNAF_SIZE_BITS(WNAF_BITS, w)
67#define ECMULT_TABLE_SIZE(w) (1 << ((w)-2))
70#define PIPPENGER_SCRATCH_OBJECTS 6
71#define STRAUSS_SCRATCH_OBJECTS 6
73#define PIPPENGER_MAX_BUCKET_WINDOW 12
76#define ECMULT_PIPPENGER_THRESHOLD 88
78#define ECMULT_MAX_POINTS_PER_BATCH 5000000
109 for (i = 1; i < n; i++) {
175 for (i = 0; i < (n - 1); i++) {
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)); \
283 *(r) = (pre)[((n)-1)/2]; \
285 *(r) = (pre)[(-(n)-1)/2]; \
286 secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
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)); \
295 secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
297 secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
298 secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
345 for (i = 0; i < 128; i++) {
533 for (i = bits - 1; i >= 0; i--) {
644 for (pos = 0; pos <
WNAF_SIZE(w); pos++) {
661 for (pos =
WNAF_SIZE(w) - 1; pos > 0; pos--) {
673 if ((val & 1) == 0) {
674 wnaf[pos - 1] -= (1 << w);
675 wnaf[pos] = (val + 1);
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;
688 wnaf[pos - 2] -= 1 << w;
736 for (i =
n_wnaf - 1; i >= 0; i--) {
801 }
else if (n <= 20) {
803 }
else if (n <= 57) {
805 }
else if (n <= 136) {
807 }
else if (n <= 235) {
809 }
else if (n <= 1260) {
811 }
else if (n <= 4420) {
813 }
else if (n <= 7880) {
815 }
else if (n <= 16050) {
836 case 10:
return 7880;
837 case 11:
return 16050;
929 for(i = 0; (
size_t)i < idx; i++) {
1045 }
else if (n == 0) {
1051 if (scratch ==
NULL) {
int() secp256k1_ecmult_multi_callback(secp256k1_scalar *sc, secp256k1_ge *pt, size_t idx, void *data)
#define STRAUSS_SCRATCH_OBJECTS
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.
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.
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)
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
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...
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
#define PIPPENGER_MAX_BUCKET_WINDOW
#define ECMULT_TABLE_SIZE(w)
The number of entries a table with precomputed multiples needs to have.
#define PIPPENGER_SCRATCH_OBJECTS
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...
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)
static const secp256k1_ge secp256k1_ge_const_g
Generator for secp256k1, value 'g' defined in "Standards for Efficient Cryptography" (SEC2) 2....
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...
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)
#define ROUND_TO_ALIGN(size)
#define VERIFY_CHECK(cond)
secp256k1_ge_storage(* pre_g_128)[]
secp256k1_ge_storage(* pre_g)[]
A group element of the secp256k1 curve, in affine coordinates.
A group element of the secp256k1 curve, in jacobian coordinates.
struct secp256k1_pippenger_point_state * ps
A scalar modulo the group order of the secp256k1 curve.
struct secp256k1_strauss_point_state * ps