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 */
25 secp256k1_context* ctx;
26 secp256k1_scratch_space* scratch;
27 secp256k1_scalar* scalars;
28 secp256k1_ge* pubkeys;
29 secp256k1_scalar* seckeys;
30 secp256k1_gej* expected_output;
31 secp256k1_ecmult_multi_func ecmult_multi;
32
33 /* Changes per test */
34 size_t count;
35 int includes_g;
36
37 /* Changes per test iteration */
38 size_t offset1;
39 size_t offset2;
40
41 /* Test output. */
42 secp256k1_gej* output;
43 } bench_data;
44
bench_callback(secp256k1_scalar * sc,secp256k1_ge * ge,size_t idx,void * arg)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];
50 *ge = secp256k1_ge_const_g;
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
bench_ecmult(void * arg)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
bench_ecmult_setup(void * arg)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
bench_ecmult_teardown(void * arg)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);
87 CHECK(secp256k1_gej_is_infinity(&tmp));
88 }
89 }
90
generate_scalar(uint32_t num,secp256k1_scalar * scalar)91 static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) {
92 secp256k1_sha256 sha256;
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;
100 secp256k1_sha256_initialize(&sha256);
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
run_test(bench_data * data,size_t count,int includes_g)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
main(int argc,char ** argv)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
142 data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);
143 scratch_size = secp256k1_strauss_scratch_size(POINTS) + STRAUSS_SCRATCH_OBJECTS*16;
144 data.scratch = secp256k1_scratch_space_create(data.ctx, scratch_size);
145 data.ecmult_multi = secp256k1_ecmult_multi_var;
146
147 if (argc > 1) {
148 if(have_flag(argc, argv, "pippenger_wnaf")) {
149 printf("Using pippenger_wnaf:\n");
150 data.ecmult_multi = secp256k1_ecmult_pippenger_batch_single;
151 } else if(have_flag(argc, argv, "strauss_wnaf")) {
152 printf("Using strauss_wnaf:\n");
153 data.ecmult_multi = secp256k1_ecmult_strauss_batch_single;
154 } else if(have_flag(argc, argv, "simple")) {
155 printf("Using simple algorithm:\n");
156 data.ecmult_multi = secp256k1_ecmult_multi_var;
157 secp256k1_scratch_space_destroy(data.scratch);
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 }
196 secp256k1_context_destroy(data.ctx);
197 if (data.scratch != NULL) {
198 secp256k1_scratch_space_destroy(data.scratch);
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 }
208