#include <string.h>
#include <stdint.h>
#include "util.h"
#include "group.h"
#include "scalar.h"
#include "ecmult.h"
#include "precomputed_ecmult.h"

Include dependency graph for ecmult_impl.h:

This graph shows which files directly or indirectly include 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	WNAF_BITS 128
	Larger values for ECMULT_WINDOW_SIZE result in possibly better performance at the cost of an exponentially larger precomputed table. More...

#define	WNAF_SIZE_BITS(bits, w) CEIL_DIV(bits, w)

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

#define	PIPPENGER_SCRATCH_OBJECTS 6

#define	STRAUSS_SCRATCH_OBJECTS 5

#define	PIPPENGER_MAX_BUCKET_WINDOW 12

#define	ECMULT_PIPPENGER_THRESHOLD 88

#define	ECMULT_MAX_POINTS_PER_BATCH 5000000

Typedefs
typedef int(*	secp256k1_ecmult_multi_func) (const secp256k1_callback error_callback, secp256k1_scratch , secp256k1_gej , const secp256k1_scalar , secp256k1_ecmult_multi_callback cb, void *, size_t)

Functions
static void	secp256k1_ecmult_odd_multiples_table (int n, secp256k1_ge pre_a, secp256k1_fe zr, secp256k1_fe z, const secp256k1_gej a)
	Fill a table 'pre_a' with precomputed odd multiples of a. More...

static SECP256K1_INLINE void	secp256k1_ecmult_table_verify (int n, int w)

static SECP256K1_INLINE void	secp256k1_ecmult_table_get_ge (secp256k1_ge r, const secp256k1_ge pre, int n, int w)

static SECP256K1_INLINE void	secp256k1_ecmult_table_get_ge_lambda (secp256k1_ge r, const secp256k1_ge pre, const secp256k1_fe *x, int n, int w)

static SECP256K1_INLINE void	secp256k1_ecmult_table_get_ge_storage (secp256k1_ge r, const secp256k1_ge_storage pre, int n, int w)

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 struct secp256k1_strauss_state state, secp256k1_gej r, size_t num, const secp256k1_gej a, const secp256k1_scalar na, const secp256k1_scalar *ng)

static void	secp256k1_ecmult (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, 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, 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, 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, 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 (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, secp256k1_scratch scratch, secp256k1_gej r, const secp256k1_scalar inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n)

Macro Definition Documentation

◆ ECMULT_MAX_POINTS_PER_BATCH

#define ECMULT_MAX_POINTS_PER_BATCH 5000000

Definition at line 57 of file ecmult_impl.h.

◆ ECMULT_PIPPENGER_THRESHOLD

#define ECMULT_PIPPENGER_THRESHOLD 88

Definition at line 55 of file ecmult_impl.h.

◆ PIPPENGER_MAX_BUCKET_WINDOW

#define PIPPENGER_MAX_BUCKET_WINDOW 12

Definition at line 52 of file ecmult_impl.h.

◆ PIPPENGER_SCRATCH_OBJECTS

#define PIPPENGER_SCRATCH_OBJECTS 6

Definition at line 49 of file ecmult_impl.h.

◆ STRAUSS_SCRATCH_OBJECTS

#define STRAUSS_SCRATCH_OBJECTS 5

Definition at line 50 of file ecmult_impl.h.

◆ WINDOW_A

#define WINDOW_A 5

Definition at line 32 of file ecmult_impl.h.

◆ WNAF_BITS

#define WNAF_BITS 128

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_SIZE

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

Definition at line 46 of file ecmult_impl.h.

◆ WNAF_SIZE_BITS

#define WNAF_SIZE_BITS	(	bits,
		w
	)	CEIL_DIV(bits, w)

Definition at line 45 of file ecmult_impl.h.

Typedef Documentation

◆ secp256k1_ecmult_multi_func

typedef int(* secp256k1_ecmult_multi_func) (const secp256k1_callback *error_callback, secp256k1_scratch *, secp256k1_gej *, const secp256k1_scalar *, secp256k1_ecmult_multi_callback cb, void *, size_t)

Definition at line 806 of file ecmult_impl.h.

Function Documentation

◆ secp256k1_ecmult()

static void secp256k1_ecmult	(	secp256k1_gej *	r,
		const secp256k1_gej *	a,
		const secp256k1_scalar *	na,
		const secp256k1_scalar *	ng
	)

static

Definition at line 349 of file ecmult_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 629 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 788 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	(	secp256k1_gej *	r,
		const secp256k1_scalar *	inp_g_sc,
		secp256k1_ecmult_multi_callback	cb,
		void *	cbdata,
		size_t	n_points
	)

static

Definition at line 763 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,
		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 807 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_ge *	pre_a,
		secp256k1_fe *	zr,
		secp256k1_fe *	z,
		const secp256k1_gej *	a
	)

static

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

pre_a will contain [1*a,3*a,...,(2*n-1)*a], so it needs space for n group elements. zr needs space for n field elements.

Although pre_a is an array of _ge rather than _gej, it actually represents elements in Jacobian coordinates with their z coordinates omitted. The omitted z-coordinates can be recovered using z and zr. Using the notation z(b) to represent the omitted z coordinate of b:

z(pre_a[n-1]) = 'z'
z(pre_a[i-1]) = z(pre_a[i]) / zr[i] for n > i > 0

Lastly the zr[0] value, which isn't used above, is set so that:

a.z = z(pre_a[0]) / zr[0]

Definition at line 73 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,
		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 654 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,
		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 718 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 500 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,
		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 366 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,
		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 406 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 struct secp256k1_strauss_state *	state,
		secp256k1_gej *	r,
		size_t	num,
		const secp256k1_gej *	a,
		const secp256k1_scalar *	na,
		const secp256k1_scalar *	ng
	)

static

Definition at line 237 of file ecmult_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ secp256k1_ecmult_table_get_ge()

static SECP256K1_INLINE void secp256k1_ecmult_table_get_ge	(	secp256k1_ge *	r,
		const secp256k1_ge *	pre,
		int	n,
		int	w
	)

static

Definition at line 125 of file ecmult_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ secp256k1_ecmult_table_get_ge_lambda()

static SECP256K1_INLINE void secp256k1_ecmult_table_get_ge_lambda	(	secp256k1_ge *	r,
		const secp256k1_ge *	pre,
		const secp256k1_fe *	x,
		int	n,
		int	w
	)

static

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_table_get_ge_storage()

static SECP256K1_INLINE void secp256k1_ecmult_table_get_ge_storage	(	secp256k1_ge *	r,
		const secp256k1_ge_storage *	pre,
		int	n,
		int	w
	)

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_table_verify()

static SECP256K1_INLINE void secp256k1_ecmult_table_verify	(	int	n,
		int	w
	)

static

Definition at line 117 of file ecmult_impl.h.

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 162 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 581 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 610 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 727 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 648 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 410 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 361 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 421 of file ecmult_impl.h.

Here is the call graph for this function:

Here is the caller graph for this function:

Classes

Macros

Typedefs

Functions

Macro Definition Documentation

◆ ECMULT_MAX_POINTS_PER_BATCH

◆ ECMULT_PIPPENGER_THRESHOLD

◆ PIPPENGER_MAX_BUCKET_WINDOW

◆ PIPPENGER_SCRATCH_OBJECTS

◆ STRAUSS_SCRATCH_OBJECTS

◆ WINDOW_A

◆ WNAF_BITS

◆ WNAF_SIZE

◆ WNAF_SIZE_BITS

Typedef Documentation

◆ secp256k1_ecmult_multi_func

Function Documentation

◆ secp256k1_ecmult()

◆ secp256k1_ecmult_endo_split()

◆ secp256k1_ecmult_multi_batch_size_helper()

◆ secp256k1_ecmult_multi_simple_var()

◆ secp256k1_ecmult_multi_var()

◆ secp256k1_ecmult_odd_multiples_table()

◆ secp256k1_ecmult_pippenger_batch()

◆ secp256k1_ecmult_pippenger_batch_single()

◆ secp256k1_ecmult_pippenger_wnaf()

◆ secp256k1_ecmult_strauss_batch()

◆ secp256k1_ecmult_strauss_batch_single()

◆ secp256k1_ecmult_strauss_wnaf()

◆ secp256k1_ecmult_table_get_ge()

◆ secp256k1_ecmult_table_get_ge_lambda()

◆ secp256k1_ecmult_table_get_ge_storage()

◆ secp256k1_ecmult_table_verify()

◆ secp256k1_ecmult_wnaf()

◆ secp256k1_pippenger_bucket_window()

◆ secp256k1_pippenger_bucket_window_inv()

◆ secp256k1_pippenger_max_points()

◆ secp256k1_pippenger_scratch_size()

◆ secp256k1_strauss_max_points()

◆ secp256k1_strauss_scratch_size()

◆ secp256k1_wnaf_fixed()