Bitcoin Core 29.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#include <stdlib.h>
8
9#include "secp256k1.c"
10#include "../include/secp256k1.h"
11
12#include "util.h"
13#include "hash_impl.h"
14#include "field_impl.h"
15#include "group_impl.h"
16#include "scalar_impl.h"
17#include "ecmult_impl.h"
18#include "bench.h"
19
20#define POINTS 32768
21
22static void help(char **argv) {
23 printf("Benchmark EC multiplication algorithms\n");
24 printf("\n");
25 printf("Usage: %s <help|pippenger_wnaf|strauss_wnaf|simple>\n", argv[0]);
26 printf("The output shows the number of multiplied and summed points right after the\n");
27 printf("function name. The letter 'g' indicates that one of the points is the generator.\n");
28 printf("The benchmarks are divided by the number of points.\n");
29 printf("\n");
30 printf("default (ecmult_multi): picks pippenger_wnaf or strauss_wnaf depending on the\n");
31 printf(" batch size\n");
32 printf("pippenger_wnaf: for all batch sizes\n");
33 printf("strauss_wnaf: for all batch sizes\n");
34 printf("simple: multiply and sum each point individually\n");
35}
36
37typedef struct {
38 /* Setup once in advance */
47
48 /* Changes per benchmark */
49 size_t count;
51
52 /* Changes per benchmark iteration, used to pick different scalars and pubkeys
53 * in each run. */
54 size_t offset1;
55 size_t offset2;
56
57 /* Benchmark output. */
60
61/* Hashes x into [0, POINTS) twice and store the result in offset1 and offset2. */
62static void hash_into_offset(bench_data* data, size_t x) {
63 data->offset1 = (x * 0x537b7f6f + 0x8f66a481) % POINTS;
64 data->offset2 = (x * 0x7f6f537b + 0x6a1a8f49) % POINTS;
65}
66
67/* Check correctness of the benchmark by computing
68 * sum(outputs) ?= (sum(scalars_gen) + sum(seckeys)*sum(scalars))*G */
69static void bench_ecmult_teardown_helper(bench_data* data, size_t* seckey_offset, size_t* scalar_offset, size_t* scalar_gen_offset, int iters) {
70 int i;
71 secp256k1_gej sum_output, tmp;
72 secp256k1_scalar sum_scalars;
73
74 secp256k1_gej_set_infinity(&sum_output);
75 secp256k1_scalar_set_int(&sum_scalars, 0);
76 for (i = 0; i < iters; ++i) {
77 secp256k1_gej_add_var(&sum_output, &sum_output, &data->output[i], NULL);
78 if (scalar_gen_offset != NULL) {
79 secp256k1_scalar_add(&sum_scalars, &sum_scalars, &data->scalars[(*scalar_gen_offset+i) % POINTS]);
80 }
81 if (seckey_offset != NULL) {
82 secp256k1_scalar s = data->seckeys[(*seckey_offset+i) % POINTS];
83 secp256k1_scalar_mul(&s, &s, &data->scalars[(*scalar_offset+i) % POINTS]);
84 secp256k1_scalar_add(&sum_scalars, &sum_scalars, &s);
85 }
86 }
87 secp256k1_ecmult_gen(&data->ctx->ecmult_gen_ctx, &tmp, &sum_scalars);
88 CHECK(secp256k1_gej_eq_var(&tmp, &sum_output));
89}
90
91static void bench_ecmult_setup(void* arg) {
92 bench_data* data = (bench_data*)arg;
93 /* Re-randomize offset to ensure that we're using different scalars and
94 * group elements in each run. */
95 hash_into_offset(data, data->offset1);
96}
97
98static void bench_ecmult_gen(void* arg, int iters) {
99 bench_data* data = (bench_data*)arg;
100 int i;
101
102 for (i = 0; i < iters; ++i) {
103 secp256k1_ecmult_gen(&data->ctx->ecmult_gen_ctx, &data->output[i], &data->scalars[(data->offset1+i) % POINTS]);
104 }
105}
106
107static void bench_ecmult_gen_teardown(void* arg, int iters) {
108 bench_data* data = (bench_data*)arg;
109 bench_ecmult_teardown_helper(data, NULL, NULL, &data->offset1, iters);
110}
111
112static void bench_ecmult_const(void* arg, int iters) {
113 bench_data* data = (bench_data*)arg;
114 int i;
115
116 for (i = 0; i < iters; ++i) {
117 secp256k1_ecmult_const(&data->output[i], &data->pubkeys[(data->offset1+i) % POINTS], &data->scalars[(data->offset2+i) % POINTS]);
118 }
119}
120
121static void bench_ecmult_const_teardown(void* arg, int iters) {
122 bench_data* data = (bench_data*)arg;
123 bench_ecmult_teardown_helper(data, &data->offset1, &data->offset2, NULL, iters);
124}
125
126static void bench_ecmult_1p(void* arg, int iters) {
127 bench_data* data = (bench_data*)arg;
128 int i;
129
130 for (i = 0; i < iters; ++i) {
131 secp256k1_ecmult(&data->output[i], &data->pubkeys_gej[(data->offset1+i) % POINTS], &data->scalars[(data->offset2+i) % POINTS], NULL);
132 }
133}
134
135static void bench_ecmult_1p_teardown(void* arg, int iters) {
136 bench_data* data = (bench_data*)arg;
137 bench_ecmult_teardown_helper(data, &data->offset1, &data->offset2, NULL, iters);
138}
139
140static void bench_ecmult_0p_g(void* arg, int iters) {
141 bench_data* data = (bench_data*)arg;
142 int i;
143
144 for (i = 0; i < iters; ++i) {
145 secp256k1_ecmult(&data->output[i], NULL, &secp256k1_scalar_zero, &data->scalars[(data->offset1+i) % POINTS]);
146 }
147}
148
149static void bench_ecmult_0p_g_teardown(void* arg, int iters) {
150 bench_data* data = (bench_data*)arg;
151 bench_ecmult_teardown_helper(data, NULL, NULL, &data->offset1, iters);
152}
153
154static void bench_ecmult_1p_g(void* arg, int iters) {
155 bench_data* data = (bench_data*)arg;
156 int i;
157
158 for (i = 0; i < iters/2; ++i) {
159 secp256k1_ecmult(&data->output[i], &data->pubkeys_gej[(data->offset1+i) % POINTS], &data->scalars[(data->offset2+i) % POINTS], &data->scalars[(data->offset1+i) % POINTS]);
160 }
161}
162
163static void bench_ecmult_1p_g_teardown(void* arg, int iters) {
164 bench_data* data = (bench_data*)arg;
165 bench_ecmult_teardown_helper(data, &data->offset1, &data->offset2, &data->offset1, iters/2);
166}
167
168static void run_ecmult_bench(bench_data* data, int iters) {
169 char str[32];
170 sprintf(str, "ecmult_gen");
172 sprintf(str, "ecmult_const");
174 /* ecmult with non generator point */
175 sprintf(str, "ecmult_1p");
177 /* ecmult with generator point */
178 sprintf(str, "ecmult_0p_g");
180 /* ecmult with generator and non-generator point. The reported time is per point. */
181 sprintf(str, "ecmult_1p_g");
183}
184
185static int bench_ecmult_multi_callback(secp256k1_scalar* sc, secp256k1_ge* ge, size_t idx, void* arg) {
186 bench_data* data = (bench_data*)arg;
187 if (data->includes_g) ++idx;
188 if (idx == 0) {
189 *sc = data->scalars[data->offset1];
191 } else {
192 *sc = data->scalars[(data->offset1 + idx) % POINTS];
193 *ge = data->pubkeys[(data->offset2 + idx - 1) % POINTS];
194 }
195 return 1;
196}
197
198static void bench_ecmult_multi(void* arg, int iters) {
199 bench_data* data = (bench_data*)arg;
200
201 int includes_g = data->includes_g;
202 int iter;
203 int count = data->count;
204 iters = iters / data->count;
205
206 for (iter = 0; iter < iters; ++iter) {
207 data->ecmult_multi(&data->ctx->error_callback, data->scratch, &data->output[iter], data->includes_g ? &data->scalars[data->offset1] : NULL, bench_ecmult_multi_callback, arg, count - includes_g);
208 data->offset1 = (data->offset1 + count) % POINTS;
209 data->offset2 = (data->offset2 + count - 1) % POINTS;
210 }
211}
212
213static void bench_ecmult_multi_setup(void* arg) {
214 bench_data* data = (bench_data*)arg;
215 hash_into_offset(data, data->count);
216}
217
218static void bench_ecmult_multi_teardown(void* arg, int iters) {
219 bench_data* data = (bench_data*)arg;
220 int iter;
221 iters = iters / data->count;
222 /* Verify the results in teardown, to avoid doing comparisons while benchmarking. */
223 for (iter = 0; iter < iters; ++iter) {
224 secp256k1_gej tmp;
225 secp256k1_gej_add_var(&tmp, &data->output[iter], &data->expected_output[iter], NULL);
227 }
228}
229
230static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) {
232 unsigned char c[10] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0};
233 unsigned char buf[32];
234 int overflow = 0;
235 c[6] = num;
236 c[7] = num >> 8;
237 c[8] = num >> 16;
238 c[9] = num >> 24;
240 secp256k1_sha256_write(&sha256, c, sizeof(c));
242 secp256k1_scalar_set_b32(scalar, buf, &overflow);
243 CHECK(!overflow);
244}
245
246static void run_ecmult_multi_bench(bench_data* data, size_t count, int includes_g, int num_iters) {
247 char str[32];
248 size_t iters = 1 + num_iters / count;
249 size_t iter;
250
251 data->count = count;
252 data->includes_g = includes_g;
253
254 /* Compute (the negation of) the expected results directly. */
255 hash_into_offset(data, data->count);
256 for (iter = 0; iter < iters; ++iter) {
258 secp256k1_scalar total = data->scalars[(data->offset1++) % POINTS];
259 size_t i = 0;
260 for (i = 0; i + 1 < count; ++i) {
261 secp256k1_scalar_mul(&tmp, &data->seckeys[(data->offset2++) % POINTS], &data->scalars[(data->offset1++) % POINTS]);
262 secp256k1_scalar_add(&total, &total, &tmp);
263 }
264 secp256k1_scalar_negate(&total, &total);
265 secp256k1_ecmult(&data->expected_output[iter], NULL, &secp256k1_scalar_zero, &total);
266 }
267
268 /* Run the benchmark. */
269 if (includes_g) {
270 sprintf(str, "ecmult_multi_%ip_g", (int)count - 1);
271 } else {
272 sprintf(str, "ecmult_multi_%ip", (int)count);
273 }
275}
276
277int main(int argc, char **argv) {
279 int i, p;
280 size_t scratch_size;
281
282 int iters = get_iters(10000);
283
284 data.ecmult_multi = secp256k1_ecmult_multi_var;
285
286 if (argc > 1) {
287 if(have_flag(argc, argv, "-h")
288 || have_flag(argc, argv, "--help")
289 || have_flag(argc, argv, "help")) {
290 help(argv);
291 return EXIT_SUCCESS;
292 } else if(have_flag(argc, argv, "pippenger_wnaf")) {
293 printf("Using pippenger_wnaf:\n");
295 } else if(have_flag(argc, argv, "strauss_wnaf")) {
296 printf("Using strauss_wnaf:\n");
298 } else if(have_flag(argc, argv, "simple")) {
299 printf("Using simple algorithm:\n");
300 } else {
301 fprintf(stderr, "%s: unrecognized argument '%s'.\n\n", argv[0], argv[1]);
302 help(argv);
303 return EXIT_FAILURE;
304 }
305 }
306
309 if (!have_flag(argc, argv, "simple")) {
310 data.scratch = secp256k1_scratch_space_create(data.ctx, scratch_size);
311 } else {
312 data.scratch = NULL;
313 }
314
315 /* Allocate stuff */
316 data.scalars = malloc(sizeof(secp256k1_scalar) * POINTS);
317 data.seckeys = malloc(sizeof(secp256k1_scalar) * POINTS);
318 data.pubkeys = malloc(sizeof(secp256k1_ge) * POINTS);
319 data.pubkeys_gej = malloc(sizeof(secp256k1_gej) * POINTS);
320 data.expected_output = malloc(sizeof(secp256k1_gej) * (iters + 1));
321 data.output = malloc(sizeof(secp256k1_gej) * (iters + 1));
322
323 /* Generate a set of scalars, and private/public keypairs. */
325 secp256k1_scalar_set_int(&data.seckeys[0], 1);
326 for (i = 0; i < POINTS; ++i) {
327 generate_scalar(i, &data.scalars[i]);
328 if (i) {
329 secp256k1_gej_double_var(&data.pubkeys_gej[i], &data.pubkeys_gej[i - 1], NULL);
330 secp256k1_scalar_add(&data.seckeys[i], &data.seckeys[i - 1], &data.seckeys[i - 1]);
331 }
332 }
333 secp256k1_ge_set_all_gej_var(data.pubkeys, data.pubkeys_gej, POINTS);
334
335
337 /* Initialize offset1 and offset2 */
339 run_ecmult_bench(&data, iters);
340
341 for (i = 1; i <= 8; ++i) {
342 run_ecmult_multi_bench(&data, i, 1, iters);
343 }
344
345 /* This is disabled with low count of iterations because the loop runs 77 times even with iters=1
346 * and the higher it goes the longer the computation takes(more points)
347 * So we don't run this benchmark with low iterations to prevent slow down */
348 if (iters > 2) {
349 for (p = 0; p <= 11; ++p) {
350 for (i = 9; i <= 16; ++i) {
351 run_ecmult_multi_bench(&data, i << p, 1, iters);
352 }
353 }
354 }
355
356 if (data.scratch != NULL) {
358 }
360 free(data.scalars);
361 free(data.pubkeys);
362 free(data.pubkeys_gej);
363 free(data.seckeys);
364 free(data.output);
365 free(data.expected_output);
366
367 return EXIT_SUCCESS;
368}
static void bench_ecmult_const(void *arg, int iters)
Definition: bench_ecmult.c:112
static void bench_ecmult_gen_teardown(void *arg, int iters)
Definition: bench_ecmult.c:107
static int bench_ecmult_multi_callback(secp256k1_scalar *sc, secp256k1_ge *ge, size_t idx, void *arg)
Definition: bench_ecmult.c:185
static void bench_ecmult_teardown_helper(bench_data *data, size_t *seckey_offset, size_t *scalar_offset, size_t *scalar_gen_offset, int iters)
Definition: bench_ecmult.c:69
int main(int argc, char **argv)
Definition: bench_ecmult.c:277
static void bench_ecmult_setup(void *arg)
Definition: bench_ecmult.c:91
static void bench_ecmult_gen(void *arg, int iters)
Definition: bench_ecmult.c:98
static void generate_scalar(uint32_t num, secp256k1_scalar *scalar)
Definition: bench_ecmult.c:230
static void bench_ecmult_const_teardown(void *arg, int iters)
Definition: bench_ecmult.c:121
static void bench_ecmult_multi_setup(void *arg)
Definition: bench_ecmult.c:213
static void bench_ecmult_1p_g_teardown(void *arg, int iters)
Definition: bench_ecmult.c:163
static void bench_ecmult_1p(void *arg, int iters)
Definition: bench_ecmult.c:126
static void bench_ecmult_1p_teardown(void *arg, int iters)
Definition: bench_ecmult.c:135
static void bench_ecmult_multi(void *arg, int iters)
Definition: bench_ecmult.c:198
static void hash_into_offset(bench_data *data, size_t x)
Definition: bench_ecmult.c:62
static void help(char **argv)
Definition: bench_ecmult.c:22
static void bench_ecmult_0p_g_teardown(void *arg, int iters)
Definition: bench_ecmult.c:149
static void run_ecmult_bench(bench_data *data, int iters)
Definition: bench_ecmult.c:168
static void bench_ecmult_1p_g(void *arg, int iters)
Definition: bench_ecmult.c:154
static void bench_ecmult_0p_g(void *arg, int iters)
Definition: bench_ecmult.c:140
static void bench_ecmult_multi_teardown(void *arg, int iters)
Definition: bench_ecmult.c:218
#define POINTS
Definition: bench_ecmult.c:20
static void run_ecmult_multi_bench(bench_data *data, size_t count, int includes_g, int num_iters)
Definition: bench_ecmult.c:246
return EXIT_SUCCESS
static void run_benchmark(char *name, void(*benchmark)(void *), void(*setup)(void *), void(*teardown)(void *), void *data, int count, int iter)
Definition: bench.c:26
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)
Multi-multiply: R = inp_g_sc * G + sum_i ni * Ai.
static void secp256k1_ecmult(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_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, const secp256k1_scalar *q)
Multiply: R = q*A (in constant-time for q)
static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *a)
Multiply with the generator: R = a*G.
#define STRAUSS_SCRATCH_OBJECTS
Definition: ecmult_impl.h:50
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)
Definition: ecmult_impl.h:406
static size_t secp256k1_strauss_scratch_size(size_t n_points)
Definition: ecmult_impl.h:361
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)
Definition: ecmult_impl.h:718
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: ecmult_impl.h:806
static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b)
Check two group elements (jacobian) for equality in variable time.
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_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_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_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Set group elements r[0:len] (affine) equal to group elements a[0:len] (jacobian).
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 const secp256k1_ge secp256k1_ge_const_g
Definition: group_impl.h:72
#define CHECK(cond)
Unconditional failure on condition failure.
Definition: util.h:35
Internal SHA-256 implementation.
Definition: sha256.cpp:68
void printf(FormatStringCheck< sizeof...(Args)> fmt, const Args &... args)
Format list of arguments to std::cout, according to the given format string.
Definition: tinyformat.h:1096
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow)
Set a scalar from a big endian byte array.
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Multiply two scalars (modulo the group order).
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
static const secp256k1_scalar secp256k1_scalar_zero
Definition: scalar_impl.h:28
static int get_iters(int default_iters)
Definition: bench.h:170
static void print_output_table_header_row(void)
Definition: bench.h:179
static int have_flag(int argc, char **argv, char *flag)
Definition: bench.h:132
static void secp256k1_sha256_initialize(secp256k1_sha256 *hash)
static void secp256k1_sha256_finalize(secp256k1_sha256 *hash, unsigned char *out32)
static void secp256k1_sha256_write(secp256k1_sha256 *hash, const unsigned char *data, size_t size)
static void secp256k1_scratch_space_destroy(const secp256k1_context *ctx, secp256k1_scratch_space *scratch)
Definition: secp256k1.c:228
static secp256k1_scratch_space * secp256k1_scratch_space_create(const secp256k1_context *ctx, size_t max_size)
Definition: secp256k1.c:223
SECP256K1_API void secp256k1_context_destroy(secp256k1_context *ctx) SECP256K1_ARG_NONNULL(1)
Destroy a secp256k1 context object (created in dynamically allocated memory).
Definition: secp256k1.c:187
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:141
#define SECP256K1_CONTEXT_NONE
Context flags to pass to secp256k1_context_create, secp256k1_context_preallocated_size,...
Definition: secp256k1.h:202
secp256k1_scalar * seckeys
Definition: bench_ecmult.c:44
secp256k1_gej * output
Definition: bench_ecmult.c:58
secp256k1_gej * pubkeys_gej
Definition: bench_ecmult.c:43
size_t offset2
Definition: bench_ecmult.c:55
secp256k1_ecmult_multi_func ecmult_multi
Definition: bench_ecmult.c:46
int includes_g
Definition: bench_ecmult.c:50
size_t offset1
Definition: bench_ecmult.c:54
secp256k1_scratch_space * scratch
Definition: bench_ecmult.c:40
secp256k1_ge * pubkeys
Definition: bench_ecmult.c:42
size_t count
Definition: bench_ecmult.c:49
secp256k1_scalar * scalars
Definition: bench_ecmult.c:41
secp256k1_gej * expected_output
Definition: bench_ecmult.c:45
A group element in affine coordinates on the secp256k1 curve, or occasionally on an isomorphic curve ...
Definition: group.h:16
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:28
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
static int count