Bitcoin Core  21.99.0
P2P Digital Currency
bench_ecmult.c
Go to the documentation of this file.
1 /***********************************************************************
2  * Copyright (c) 2017 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
5  ***********************************************************************/
6 #include <stdio.h>
7 
8 #include "include/secp256k1.h"
9 
10 #include "util.h"
11 #include "hash_impl.h"
12 #include "field_impl.h"
13 #include "group_impl.h"
14 #include "scalar_impl.h"
15 #include "ecmult_impl.h"
16 #include "bench.h"
17 #include "secp256k1.c"
18 
19 #define POINTS 32768
20 
21 typedef struct {
22  /* Setup once in advance */
30 
31  /* Changes per test */
32  size_t count;
34 
35  /* Changes per test iteration */
36  size_t offset1;
37  size_t offset2;
38 
39  /* Test output. */
41 } bench_data;
42 
43 static int bench_callback(secp256k1_scalar* sc, secp256k1_ge* ge, size_t idx, void* arg) {
44  bench_data* data = (bench_data*)arg;
45  if (data->includes_g) ++idx;
46  if (idx == 0) {
47  *sc = data->scalars[data->offset1];
49  } else {
50  *sc = data->scalars[(data->offset1 + idx) % POINTS];
51  *ge = data->pubkeys[(data->offset2 + idx - 1) % POINTS];
52  }
53  return 1;
54 }
55 
56 static void bench_ecmult(void* arg, int iters) {
57  bench_data* data = (bench_data*)arg;
58 
59  int includes_g = data->includes_g;
60  int iter;
61  int count = data->count;
62  iters = iters / data->count;
63 
64  for (iter = 0; iter < iters; ++iter) {
65  data->ecmult_multi(&data->ctx->error_callback, &data->ctx->ecmult_ctx, data->scratch, &data->output[iter], data->includes_g ? &data->scalars[data->offset1] : NULL, bench_callback, arg, count - includes_g);
66  data->offset1 = (data->offset1 + count) % POINTS;
67  data->offset2 = (data->offset2 + count - 1) % POINTS;
68  }
69 }
70 
71 static void bench_ecmult_setup(void* arg) {
72  bench_data* data = (bench_data*)arg;
73  data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS;
74  data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS;
75 }
76 
77 static void bench_ecmult_teardown(void* arg, int iters) {
78  bench_data* data = (bench_data*)arg;
79  int iter;
80  iters = iters / data->count;
81  /* Verify the results in teardown, to avoid doing comparisons while benchmarking. */
82  for (iter = 0; iter < iters; ++iter) {
83  secp256k1_gej tmp;
84  secp256k1_gej_add_var(&tmp, &data->output[iter], &data->expected_output[iter], NULL);
86  }
87 }
88 
89 static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) {
91  unsigned char c[11] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0};
92  unsigned char buf[32];
93  int overflow = 0;
94  c[6] = num;
95  c[7] = num >> 8;
96  c[8] = num >> 16;
97  c[9] = num >> 24;
99  secp256k1_sha256_write(&sha256, c, sizeof(c));
101  secp256k1_scalar_set_b32(scalar, buf, &overflow);
102  CHECK(!overflow);
103 }
104 
105 static void run_test(bench_data* data, size_t count, int includes_g, int num_iters) {
106  char str[32];
107  static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
108  size_t iters = 1 + num_iters / count;
109  size_t iter;
110 
111  data->count = count;
112  data->includes_g = includes_g;
113 
114  /* Compute (the negation of) the expected results directly. */
115  data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS;
116  data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS;
117  for (iter = 0; iter < iters; ++iter) {
118  secp256k1_scalar tmp;
119  secp256k1_scalar total = data->scalars[(data->offset1++) % POINTS];
120  size_t i = 0;
121  for (i = 0; i + 1 < count; ++i) {
122  secp256k1_scalar_mul(&tmp, &data->seckeys[(data->offset2++) % POINTS], &data->scalars[(data->offset1++) % POINTS]);
123  secp256k1_scalar_add(&total, &total, &tmp);
124  }
125  secp256k1_scalar_negate(&total, &total);
126  secp256k1_ecmult(&data->ctx->ecmult_ctx, &data->expected_output[iter], NULL, &zero, &total);
127  }
128 
129  /* Run the benchmark. */
130  sprintf(str, includes_g ? "ecmult_%ig" : "ecmult_%i", (int)count);
132 }
133 
134 int main(int argc, char **argv) {
135  bench_data data;
136  int i, p;
137  secp256k1_gej* pubkeys_gej;
138  size_t scratch_size;
139 
140  int iters = get_iters(10000);
141 
144  data.scratch = secp256k1_scratch_space_create(data.ctx, scratch_size);
146 
147  if (argc > 1) {
148  if(have_flag(argc, argv, "pippenger_wnaf")) {
149  printf("Using pippenger_wnaf:\n");
151  } else if(have_flag(argc, argv, "strauss_wnaf")) {
152  printf("Using strauss_wnaf:\n");
154  } else if(have_flag(argc, argv, "simple")) {
155  printf("Using simple algorithm:\n");
158  data.scratch = NULL;
159  } else {
160  fprintf(stderr, "%s: unrecognized argument '%s'.\n", argv[0], argv[1]);
161  fprintf(stderr, "Use 'pippenger_wnaf', 'strauss_wnaf', 'simple' or no argument to benchmark a combined algorithm.\n");
162  return 1;
163  }
164  }
165 
166  /* Allocate stuff */
167  data.scalars = malloc(sizeof(secp256k1_scalar) * POINTS);
168  data.seckeys = malloc(sizeof(secp256k1_scalar) * POINTS);
169  data.pubkeys = malloc(sizeof(secp256k1_ge) * POINTS);
170  data.expected_output = malloc(sizeof(secp256k1_gej) * (iters + 1));
171  data.output = malloc(sizeof(secp256k1_gej) * (iters + 1));
172 
173  /* Generate a set of scalars, and private/public keypairs. */
174  pubkeys_gej = malloc(sizeof(secp256k1_gej) * POINTS);
175  secp256k1_gej_set_ge(&pubkeys_gej[0], &secp256k1_ge_const_g);
176  secp256k1_scalar_set_int(&data.seckeys[0], 1);
177  for (i = 0; i < POINTS; ++i) {
178  generate_scalar(i, &data.scalars[i]);
179  if (i) {
180  secp256k1_gej_double_var(&pubkeys_gej[i], &pubkeys_gej[i - 1], NULL);
181  secp256k1_scalar_add(&data.seckeys[i], &data.seckeys[i - 1], &data.seckeys[i - 1]);
182  }
183  }
184  secp256k1_ge_set_all_gej_var(data.pubkeys, pubkeys_gej, POINTS);
185  free(pubkeys_gej);
186 
187  for (i = 1; i <= 8; ++i) {
188  run_test(&data, i, 1, iters);
189  }
190 
191  /* This is disabled with low count of iterations because the loop runs 77 times even with iters=1
192  * and the higher it goes the longer the computation takes(more points)
193  * So we don't run this benchmark with low iterations to prevent slow down */
194  if (iters > 2) {
195  for (p = 0; p <= 11; ++p) {
196  for (i = 9; i <= 16; ++i) {
197  run_test(&data, i << p, 1, iters);
198  }
199  }
200  }
201 
202  if (data.scratch != NULL) {
204  }
206  free(data.scalars);
207  free(data.pubkeys);
208  free(data.seckeys);
209  free(data.output);
210  free(data.expected_output);
211 
212  return(0);
213 }
secp256k1_scalar_negate
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
count
static int count
Definition: tests.c:41
SECP256K1_CONTEXT_VERIFY
#define SECP256K1_CONTEXT_VERIFY
Flags to pass to secp256k1_context_create, secp256k1_context_preallocated_size, and secp256k1_context...
Definition: secp256k1.h:170
secp256k1_scratch_space_create
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT secp256k1_scratch_space * secp256k1_scratch_space_create(const secp256k1_context *ctx, size_t size) SECP256K1_ARG_NONNULL(1)
Create a secp256k1 scratch space object.
Definition: secp256k1.c:221
bench_data::offset2
size_t offset2
Definition: bench_ecmult.c:37
bench_ecmult_teardown
static void bench_ecmult_teardown(void *arg, int iters)
Definition: bench_ecmult.c:77
field_impl.h
SECP256K1_CONTEXT_SIGN
#define SECP256K1_CONTEXT_SIGN
Definition: secp256k1.h:171
bench_data::expected_output
secp256k1_gej * expected_output
Definition: bench_ecmult.c:28
secp256k1_context_struct
Definition: secp256k1.c:69
bench_data::output
secp256k1_gej * output
Definition: bench_ecmult.c:40
POINTS
#define POINTS
Definition: bench_ecmult.c:19
group_impl.h
tinyformat::printf
void printf(const char *fmt, const Args &... args)
Format list of arguments to std::cout, according to the given format string.
Definition: tinyformat.h:1079
sha256
Internal SHA-256 implementation.
Definition: sha256.cpp:46
ecmult_impl.h
bench_ecmult_setup
static void bench_ecmult_setup(void *arg)
Definition: bench_ecmult.c:71
SECP256K1_SCALAR_CONST
#define SECP256K1_SCALAR_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: scalar_4x64.h:17
secp256k1_scratch_space_struct
Definition: scratch.h:12
util.h
bench.h
secp256k1_sha256
Definition: hash.h:13
secp256k1_context_destroy
SECP256K1_API void secp256k1_context_destroy(secp256k1_context *ctx)
Destroy a secp256k1 context object (created in dynamically allocated memory).
Definition: secp256k1.c:196
secp256k1_scratch_space_destroy
SECP256K1_API void secp256k1_scratch_space_destroy(const secp256k1_context *ctx, secp256k1_scratch_space *scratch) SECP256K1_ARG_NONNULL(1)
Destroy a secp256k1 scratch space.
Definition: secp256k1.c:226
secp256k1_context_create
SECP256K1_API secp256k1_context * secp256k1_context_create(unsigned int flags) SECP256K1_WARN_UNUSED_RESULT
Create a secp256k1 context object (in dynamically allocated memory).
Definition: secp256k1.c:152
secp256k1_scalar_add
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
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)
Definition: ecmult_impl.h:621
secp256k1_scalar
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
STRAUSS_SCRATCH_OBJECTS
#define STRAUSS_SCRATCH_OBJECTS
Definition: ecmult_impl.h:71
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)
Double multiply: R = na*A + ng*G.
secp256k1_ge_const_g
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
secp256k1.h
secp256k1_gej
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:23
run_benchmark
void run_benchmark(char *name, void(*benchmark)(void *, int), void(*setup)(void *), void(*teardown)(void *, int), void *data, int count, int iter)
Definition: bench.h:76
bench_data::count
size_t count
Definition: bench_ecmult.c:32
bench_data::ecmult_multi
secp256k1_ecmult_multi_func ecmult_multi
Definition: bench_ecmult.c:29
secp256k1_sha256_write
static void secp256k1_sha256_write(secp256k1_sha256 *hash, const unsigned char *data, size_t size)
bench_data::offset1
size_t offset1
Definition: bench_ecmult.c:36
secp256k1.c
bench_data::scalars
secp256k1_scalar * scalars
Definition: bench_ecmult.c:25
secp256k1_sha256_finalize
static void secp256k1_sha256_finalize(secp256k1_sha256 *hash, unsigned char *out32)
secp256k1_context_struct::ecmult_ctx
secp256k1_ecmult_context ecmult_ctx
Definition: secp256k1.c:70
hash_impl.h
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)
Definition: ecmult_impl.h:944
secp256k1_sha256_initialize
static void secp256k1_sha256_initialize(secp256k1_sha256 *hash)
get_iters
int get_iters(int default_iters)
Definition: bench.h:124
bench_data::scratch
secp256k1_scratch_space * scratch
Definition: bench_ecmult.c:24
secp256k1_context_struct::error_callback
secp256k1_callback error_callback
Definition: secp256k1.c:73
secp256k1_gej_add_var
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.
bench_data::seckeys
secp256k1_scalar * seckeys
Definition: bench_ecmult.c:27
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)
Multi-multiply: R = inp_g_sc * G + sum_i ni * Ai.
bench_ecmult
static void bench_ecmult(void *arg, int iters)
Definition: bench_ecmult.c:56
bench_callback
static int bench_callback(secp256k1_scalar *sc, secp256k1_ge *ge, size_t idx, void *arg)
Definition: bench_ecmult.c:43
secp256k1_ge_set_all_gej_var
static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Set a batch of group elements equal to the inputs given in jacobian coordinates.
bench_data
Definition: bench_ecmult.c:21
scalar_impl.h
secp256k1_gej_double_var
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Set r equal to the double of a.
bench_data::includes_g
int includes_g
Definition: bench_ecmult.c:33
bench_data::ctx
secp256k1_context * ctx
Definition: bench_ecmult.c:23
secp256k1_scalar_mul
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Multiply two scalars (modulo the group order).
secp256k1_gej_is_infinity
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Check whether a group element is the point at infinity.
secp256k1_strauss_scratch_size
static size_t secp256k1_strauss_scratch_size(size_t n_points)
Definition: ecmult_impl.h:577
secp256k1_ecmult_multi_func
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: ecmult_impl.h:1034
generate_scalar
static void generate_scalar(uint32_t num, secp256k1_scalar *scalar)
Definition: bench_ecmult.c:89
main
int main(int argc, char **argv)
Definition: bench_ecmult.c:134
CHECK
#define CHECK(cond)
Definition: util.h:53
secp256k1_scalar_set_b32
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow)
Set a scalar from a big endian byte array.
bench_data::pubkeys
secp256k1_ge * pubkeys
Definition: bench_ecmult.c:26
secp256k1_ge
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:13
have_flag
int have_flag(int argc, char **argv, char *flag)
Definition: bench.h:109
secp256k1_scalar_set_int
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
run_test
static void run_test(bench_data *data, size_t count, int includes_g, int num_iters)
Definition: bench_ecmult.c:105
secp256k1_gej_set_ge
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.