Bitcoin Core  0.19.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 #define ITERS 10000
22 
23 typedef struct {
24  /* Setup once in advance */
32 
33  /* Changes per test */
34  size_t count;
36 
37  /* Changes per test iteration */
38  size_t offset1;
39  size_t offset2;
40 
41  /* Test output. */
43 } bench_data;
44 
45 static int bench_callback(secp256k1_scalar* sc, secp256k1_ge* ge, size_t idx, void* arg) {
46  bench_data* data = (bench_data*)arg;
47  if (data->includes_g) ++idx;
48  if (idx == 0) {
49  *sc = data->scalars[data->offset1];
51  } else {
52  *sc = data->scalars[(data->offset1 + idx) % POINTS];
53  *ge = data->pubkeys[(data->offset2 + idx - 1) % POINTS];
54  }
55  return 1;
56 }
57 
58 static void bench_ecmult(void* arg) {
59  bench_data* data = (bench_data*)arg;
60 
61  size_t count = data->count;
62  int includes_g = data->includes_g;
63  size_t iters = 1 + ITERS / count;
64  size_t iter;
65 
66  for (iter = 0; iter < iters; ++iter) {
67  data->ecmult_multi(&data->ctx->ecmult_ctx, data->scratch, &data->output[iter], data->includes_g ? &data->scalars[data->offset1] : NULL, bench_callback, arg, count - includes_g);
68  data->offset1 = (data->offset1 + count) % POINTS;
69  data->offset2 = (data->offset2 + count - 1) % POINTS;
70  }
71 }
72 
73 static void bench_ecmult_setup(void* arg) {
74  bench_data* data = (bench_data*)arg;
75  data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS;
76  data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS;
77 }
78 
79 static void bench_ecmult_teardown(void* arg) {
80  bench_data* data = (bench_data*)arg;
81  size_t iters = 1 + ITERS / data->count;
82  size_t iter;
83  /* Verify the results in teardown, to avoid doing comparisons while benchmarking. */
84  for (iter = 0; iter < iters; ++iter) {
85  secp256k1_gej tmp;
86  secp256k1_gej_add_var(&tmp, &data->output[iter], &data->expected_output[iter], NULL);
88  }
89 }
90 
91 static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) {
93  unsigned char c[11] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0};
94  unsigned char buf[32];
95  int overflow = 0;
96  c[6] = num;
97  c[7] = num >> 8;
98  c[8] = num >> 16;
99  c[9] = num >> 24;
101  secp256k1_sha256_write(&sha256, c, sizeof(c));
102  secp256k1_sha256_finalize(&sha256, buf);
103  secp256k1_scalar_set_b32(scalar, buf, &overflow);
104  CHECK(!overflow);
105 }
106 
107 static void run_test(bench_data* data, size_t count, int includes_g) {
108  char str[32];
109  static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
110  size_t iters = 1 + ITERS / count;
111  size_t iter;
112 
113  data->count = count;
114  data->includes_g = includes_g;
115 
116  /* Compute (the negation of) the expected results directly. */
117  data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS;
118  data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS;
119  for (iter = 0; iter < iters; ++iter) {
120  secp256k1_scalar tmp;
121  secp256k1_scalar total = data->scalars[(data->offset1++) % POINTS];
122  size_t i = 0;
123  for (i = 0; i + 1 < count; ++i) {
124  secp256k1_scalar_mul(&tmp, &data->seckeys[(data->offset2++) % POINTS], &data->scalars[(data->offset1++) % POINTS]);
125  secp256k1_scalar_add(&total, &total, &tmp);
126  }
127  secp256k1_scalar_negate(&total, &total);
128  secp256k1_ecmult(&data->ctx->ecmult_ctx, &data->expected_output[iter], NULL, &zero, &total);
129  }
130 
131  /* Run the benchmark. */
132  sprintf(str, includes_g ? "ecmult_%ig" : "ecmult_%i", (int)count);
133  run_benchmark(str, bench_ecmult, bench_ecmult_setup, bench_ecmult_teardown, data, 10, count * (1 + ITERS / count));
134 }
135 
136 int main(int argc, char **argv) {
137  bench_data data;
138  int i, p;
139  secp256k1_gej* pubkeys_gej;
140  size_t scratch_size;
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);
189  }
190 
191  for (p = 0; p <= 11; ++p) {
192  for (i = 9; i <= 16; ++i) {
193  run_test(&data, i << p, 1);
194  }
195  }
197  if (data.scratch != NULL) {
199  }
200  free(data.scalars);
201  free(data.pubkeys);
202  free(data.seckeys);
203  free(data.output);
204  free(data.expected_output);
205 
206  return(0);
207 }
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:34
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:30
secp256k1_scalar * scalars
Definition: bench_ecmult.c:27
static int secp256k1_ecmult_pippenger_batch_single(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:1042
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.
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:168
size_t offset2
Definition: bench_ecmult.c:39
static void bench_ecmult(void *arg)
Definition: bench_ecmult.c:58
#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.
Definition: secp256k1.c:101
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
void run_benchmark(char *name, void(*benchmark)(void *), void(*setup)(void *), void(*teardown)(void *), void *data, int count, int iter)
Definition: bench.h:34
secp256k1_scratch_space * scratch
Definition: bench_ecmult.c:26
secp256k1_ecmult_multi_func ecmult_multi
Definition: bench_ecmult.c:31
static int bench_callback(secp256k1_scalar *sc, secp256k1_ge *ge, size_t idx, void *arg)
Definition: bench_ecmult.c:45
secp256k1_scalar * seckeys
Definition: bench_ecmult.c:29
#define SECP256K1_SCALAR_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: scalar_4x64.h:17
static void bench_ecmult_teardown(void *arg)
Definition: bench_ecmult.c:79
static void run_test(bench_data *data, size_t count, int includes_g)
Definition: bench_ecmult.c:107
secp256k1_ecmult_context ecmult_ctx
Definition: secp256k1.c:53
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
static int secp256k1_ecmult_multi_var(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 size_t secp256k1_strauss_scratch_size(size_t n_points)
Definition: ecmult_impl.h:620
#define CHECK(cond)
Definition: util.h:52
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
#define STRAUSS_SCRATCH_OBJECTS
Definition: ecmult_impl.h:58
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:91
secp256k1_context * ctx
Definition: bench_ecmult.c:25
#define SECP256K1_CONTEXT_VERIFY
Flags to pass to secp256k1_context_create.
Definition: secp256k1.h:167
static int secp256k1_ecmult_strauss_batch_single(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:669
secp256k1_ge * pubkeys
Definition: bench_ecmult.c:28
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:136
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
Internal SHA-256 implementation.
Definition: sha256.cpp:46
secp256k1_gej * output
Definition: bench_ecmult.c:42
static int count
Definition: tests.c:45
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.
size_t offset1
Definition: bench_ecmult.c:38
int includes_g
Definition: bench_ecmult.c:35
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(secp256k1_scratch_space *scratch)
Destroy a secp256k1 scratch space.
Definition: secp256k1.c:134
int(* secp256k1_ecmult_multi_func)(const secp256k1_ecmult_context *, secp256k1_scratch *, secp256k1_gej *, const secp256k1_scalar *, secp256k1_ecmult_multi_callback cb, void *, size_t)
Definition: ecmult_impl.h:1134
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT secp256k1_scratch_space * secp256k1_scratch_space_create(const secp256k1_context *ctx, size_t max_size) SECP256K1_ARG_NONNULL(1)
Create a secp256k1 scratch space object.
Definition: secp256k1.c:129
int have_flag(int argc, char **argv, char *flag)
Definition: bench.h:67
SECP256K1_API secp256k1_context * secp256k1_context_create(unsigned int flags) SECP256K1_WARN_UNUSED_RESULT
Create a secp256k1 context object.
Definition: secp256k1.c:67
static void secp256k1_sha256_finalize(secp256k1_sha256 *hash, unsigned char *out32)
static void bench_ecmult_setup(void *arg)
Definition: bench_ecmult.c:73
#define ITERS
Definition: bench_ecmult.c:21