Bitcoin Core  0.20.99
P2P Digital Currency
Classes | Macros | Typedefs | Functions | Variables
ecmult_impl.h File Reference
#include <string.h>
#include <stdint.h>
#include "util.h"
#include "group.h"
#include "scalar.h"
#include "ecmult.h"
Include dependency graph for ecmult_impl.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  secp256k1_strauss_point_state
 
struct  secp256k1_strauss_state
 
struct  secp256k1_pippenger_point_state
 
struct  secp256k1_pippenger_state
 

Macros

#define WINDOW_A   5
 
#define WINDOW_G   ECMULT_WINDOW_SIZE
 Larger values for ECMULT_WINDOW_SIZE result in possibly better performance at the cost of an exponentially larger precomputed table. More...
 
#define WNAF_BITS   128
 
#define WNAF_SIZE_BITS(bits, w)   (((bits) + (w) - 1) / (w))
 
#define WNAF_SIZE(w)   WNAF_SIZE_BITS(WNAF_BITS, w)
 
#define ECMULT_TABLE_SIZE(w)   (1 << ((w)-2))
 The number of entries a table with precomputed multiples needs to have. More...
 
#define PIPPENGER_SCRATCH_OBJECTS   6
 
#define STRAUSS_SCRATCH_OBJECTS   6
 
#define PIPPENGER_MAX_BUCKET_WINDOW   12
 
#define ECMULT_PIPPENGER_THRESHOLD   88
 
#define ECMULT_MAX_POINTS_PER_BATCH   5000000
 
#define ECMULT_TABLE_GET_GE(r, pre, n, w)
 The following two macro retrieves a particular odd multiple from a table of precomputed multiples. More...
 
#define ECMULT_TABLE_GET_GE_STORAGE(r, pre, n, w)
 

Typedefs

typedef 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)
 

Functions

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. More...
 
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. More...
 
static void secp256k1_ecmult_odd_multiples_table_storage_var (const int n, secp256k1_ge_storage *pre, const secp256k1_gej *a)
 
static void secp256k1_ecmult_context_init (secp256k1_ecmult_context *ctx)
 
static void secp256k1_ecmult_context_build (secp256k1_ecmult_context *ctx, void **prealloc)
 
static void secp256k1_ecmult_context_finalize_memcpy (secp256k1_ecmult_context *dst, const secp256k1_ecmult_context *src)
 
static int secp256k1_ecmult_context_is_built (const secp256k1_ecmult_context *ctx)
 
static void secp256k1_ecmult_context_clear (secp256k1_ecmult_context *ctx)
 
static int secp256k1_ecmult_wnaf (int *wnaf, int len, const secp256k1_scalar *a, int w)
 Convert a number to WNAF notation. More...
 
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)
 
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 size_t secp256k1_strauss_scratch_size (size_t n_points)
 
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_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 size_t secp256k1_strauss_max_points (const secp256k1_callback *error_callback, secp256k1_scratch *scratch)
 
static int secp256k1_wnaf_fixed (int *wnaf, const secp256k1_scalar *s, int w)
 Convert a number to WNAF notation. More...
 
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 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 given number of points. More...
 
static size_t secp256k1_pippenger_bucket_window_inv (int bucket_window)
 Returns the maximum optimal number of points for a bucket_window. More...
 
static SECP256K1_INLINE void secp256k1_ecmult_endo_split (secp256k1_scalar *s1, secp256k1_scalar *s2, secp256k1_ge *p1, secp256k1_ge *p2)
 
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 considering alignment. More...
 
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 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 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. More...
 
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 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 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)
 

Variables

static const size_t SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE
 

Macro Definition Documentation

◆ ECMULT_MAX_POINTS_PER_BATCH

#define ECMULT_MAX_POINTS_PER_BATCH   5000000

Definition at line 78 of file ecmult_impl.h.

◆ ECMULT_PIPPENGER_THRESHOLD

#define ECMULT_PIPPENGER_THRESHOLD   88

Definition at line 76 of file ecmult_impl.h.

◆ ECMULT_TABLE_GET_GE

#define ECMULT_TABLE_GET_GE (   r,
  pre,
  n,
 
)
Value:
do { \
VERIFY_CHECK(((n) & 1) == 1); \
VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
if ((n) > 0) { \
*(r) = (pre)[((n)-1)/2]; \
} else { \
*(r) = (pre)[(-(n)-1)/2]; \
secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
} \
} while(0)

The following two macro retrieves a particular odd multiple from a table of precomputed multiples.

Definition at line 278 of file ecmult_impl.h.

◆ ECMULT_TABLE_GET_GE_STORAGE

#define ECMULT_TABLE_GET_GE_STORAGE (   r,
  pre,
  n,
 
)
Value:
do { \
VERIFY_CHECK(((n) & 1) == 1); \
VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
if ((n) > 0) { \
secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
} else { \
secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
} \
} while(0)

Definition at line 290 of file ecmult_impl.h.

◆ ECMULT_TABLE_SIZE

#define ECMULT_TABLE_SIZE (   w)    (1 << ((w)-2))

The number of entries a table with precomputed multiples needs to have.

Definition at line 67 of file ecmult_impl.h.

◆ PIPPENGER_MAX_BUCKET_WINDOW

#define PIPPENGER_MAX_BUCKET_WINDOW   12

Definition at line 73 of file ecmult_impl.h.

◆ PIPPENGER_SCRATCH_OBJECTS

#define PIPPENGER_SCRATCH_OBJECTS   6

Definition at line 70 of file ecmult_impl.h.

◆ STRAUSS_SCRATCH_OBJECTS

#define STRAUSS_SCRATCH_OBJECTS   6

Definition at line 71 of file ecmult_impl.h.

◆ WINDOW_A

#define WINDOW_A   5

Definition at line 34 of file ecmult_impl.h.

◆ WINDOW_G

#define WINDOW_G   ECMULT_WINDOW_SIZE

Larger values for ECMULT_WINDOW_SIZE result in possibly better performance at the cost of an exponentially larger precomputed table.

The exact table size is (1 << (WINDOW_G - 2)) * sizeof(secp256k1_ge_storage) bytes, where sizeof(secp256k1_ge_storage) is typically 64 bytes but can be larger due to platform-specific padding and alignment. Two tables of this size are used (due to the endomorphism optimization).

Definition at line 44 of file ecmult_impl.h.

◆ WNAF_BITS

#define WNAF_BITS   128

Definition at line 62 of file ecmult_impl.h.

◆ WNAF_SIZE

#define WNAF_SIZE (   w)    WNAF_SIZE_BITS(WNAF_BITS, w)

Definition at line 64 of file ecmult_impl.h.

◆ WNAF_SIZE_BITS

#define WNAF_SIZE_BITS (   bits,
 
)    (((bits) + (w) - 1) / (w))

Definition at line 63 of file ecmult_impl.h.

Typedef Documentation

◆ secp256k1_ecmult_multi_func

typedef 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)

Definition at line 1034 of file ecmult_impl.h.

Function Documentation

◆ secp256k1_ecmult()

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

Definition at line 561 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_context_build()

static void secp256k1_ecmult_context_build ( secp256k1_ecmult_context ctx,
void **  prealloc 
)
static

Definition at line 312 of file ecmult_impl.h.

Here is the call graph for this function:

◆ secp256k1_ecmult_context_clear()

static void secp256k1_ecmult_context_clear ( secp256k1_ecmult_context ctx)
static

Definition at line 366 of file ecmult_impl.h.

Here is the call graph for this function:

◆ secp256k1_ecmult_context_finalize_memcpy()

static void secp256k1_ecmult_context_finalize_memcpy ( secp256k1_ecmult_context dst,
const secp256k1_ecmult_context src 
)
static

Definition at line 352 of file ecmult_impl.h.

◆ secp256k1_ecmult_context_init()

static void secp256k1_ecmult_context_init ( secp256k1_ecmult_context ctx)
static

Definition at line 307 of file ecmult_impl.h.

Here is the caller graph for this function:

◆ secp256k1_ecmult_context_is_built()

static int secp256k1_ecmult_context_is_built ( const secp256k1_ecmult_context ctx)
static

Definition at line 362 of file ecmult_impl.h.

◆ secp256k1_ecmult_endo_split()

static SECP256K1_INLINE void secp256k1_ecmult_endo_split ( secp256k1_scalar s1,
secp256k1_scalar s2,
secp256k1_ge p1,
secp256k1_ge p2 
)
static

Definition at line 844 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_multi_batch_size_helper()

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

Definition at line 1016 of file ecmult_impl.h.

Here is the caller graph for this function:

◆ secp256k1_ecmult_multi_simple_var()

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

Definition at line 989 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_multi_var()

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

Definition at line 1035 of file ecmult_impl.h.

Here is the call graph for this function:

◆ secp256k1_ecmult_odd_multiples_table()

static void secp256k1_ecmult_odd_multiples_table ( int  n,
secp256k1_gej prej,
secp256k1_fe zr,
const secp256k1_gej a 
)
static

Fill a table 'prej' with precomputed odd multiples of a.

Prej will contain the values [1*a,3*a,...,(2*n-1)*a], so it space for n values. zr[0] will contain prej[0].z / a.z. The other zr[i] values = prej[i].z / prej[i-1].z. Prej's Z values are undefined, except for the last value.

Definition at line 85 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_odd_multiples_table_globalz_windowa()

static void secp256k1_ecmult_odd_multiples_table_globalz_windowa ( secp256k1_ge pre,
secp256k1_fe globalz,
const secp256k1_gej a 
)
static

Fill a table 'pre' with precomputed odd multiples of a.

There are two versions of this function:

  • secp256k1_ecmult_odd_multiples_table_globalz_windowa which brings its resulting point set to a single constant Z denominator, stores the X and Y coordinates as ge_storage points in pre, and stores the global Z in rz. It only operates on tables sized for WINDOW_A wnaf multiples.
  • secp256k1_ecmult_odd_multiples_table_storage_var, which converts its resulting point set to actually affine points, and stores those in pre. It operates on tables of any size.

To compute a*P + b*G, we compute a table for P using the first function, and for G using the second (which requires an inverse, but it only needs to happen once).

Definition at line 135 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_odd_multiples_table_storage_var()

static void secp256k1_ecmult_odd_multiples_table_storage_var ( const int  n,
secp256k1_ge_storage pre,
const secp256k1_gej a 
)
static

Definition at line 145 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_pippenger_batch()

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

Definition at line 869 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_pippenger_batch_single()

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

Definition at line 944 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_pippenger_wnaf()

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

Definition at line 715 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_strauss_batch()

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

Definition at line 582 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_strauss_batch_single()

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

Definition at line 621 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_strauss_wnaf()

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 
)
static

Definition at line 446 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_ecmult_wnaf()

static int secp256k1_ecmult_wnaf ( int *  wnaf,
int  len,
const secp256k1_scalar a,
int  w 
)
static

Convert a number to WNAF notation.

The number becomes represented by sum(2^i * wnaf[i], i=0..bits), with the following guarantees:

  • each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1)
  • two non-zero entries in wnaf are separated by at least w-1 zeroes.
  • the number of set values in wnaf is returned. This number is at most 256, and at most one more than the number of bits in the (absolute value) of the input.

Definition at line 377 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_pippenger_bucket_window()

static int secp256k1_pippenger_bucket_window ( size_t  n)
static

Returns optimal bucket_window (number of bits of a scalar represented by a set of buckets) for a given number of points.

Definition at line 796 of file ecmult_impl.h.

Here is the caller graph for this function:

◆ secp256k1_pippenger_bucket_window_inv()

static size_t secp256k1_pippenger_bucket_window_inv ( int  bucket_window)
static

Returns the maximum optimal number of points for a bucket_window.

Definition at line 825 of file ecmult_impl.h.

Here is the caller graph for this function:

◆ secp256k1_pippenger_max_points()

static size_t secp256k1_pippenger_max_points ( const secp256k1_callback error_callback,
secp256k1_scratch scratch 
)
static

Returns the maximum number of points in addition to G that can be used with a given scratch space.

The function ensures that fewer points may also be used.

Definition at line 953 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_pippenger_scratch_size()

static size_t secp256k1_pippenger_scratch_size ( size_t  n_points,
int  bucket_window 
)
static

Returns the scratch size required for a given number of points (excluding base point G) without considering alignment.

Definition at line 863 of file ecmult_impl.h.

Here is the caller graph for this function:

◆ secp256k1_strauss_max_points()

static size_t secp256k1_strauss_max_points ( const secp256k1_callback error_callback,
secp256k1_scratch scratch 
)
static

Definition at line 625 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ secp256k1_strauss_scratch_size()

static size_t secp256k1_strauss_scratch_size ( size_t  n_points)
static

Definition at line 577 of file ecmult_impl.h.

Here is the caller graph for this function:

◆ secp256k1_wnaf_fixed()

static int secp256k1_wnaf_fixed ( int *  wnaf,
const secp256k1_scalar s,
int  w 
)
static

Convert a number to WNAF notation.

The number becomes represented by sum(2^{wi} * wnaf[i], i=0..WNAF_SIZE(w)+1) - return_val. It has the following guarantees:

  • each wnaf[i] is either 0 or an odd integer between -(1 << w) and (1 << w)
  • the number of words set is always WNAF_SIZE(w)
  • the returned skew is 0 or 1

Definition at line 636 of file ecmult_impl.h.

Here is the call graph for this function:
Here is the caller graph for this function:

Variable Documentation

◆ SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE

const size_t SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE
static
Initial value:
=
+ ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G))
#define ECMULT_TABLE_SIZE(w)
The number of entries a table with precomputed multiples needs to have.
Definition: ecmult_impl.h:67
#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
#define ROUND_TO_ALIGN(size)
Definition: util.h:116

Definition at line 302 of file ecmult_impl.h.