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