bench_ecmult.c (14605B)
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 "secp256k1.c" 9 #include "../include/secp256k1.h" 10 11 #include "util.h" 12 #include "hash_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 19 #define POINTS 32768 20 21 static void help(char **argv) { 22 printf("Benchmark EC multiplication algorithms\n"); 23 printf("\n"); 24 printf("Usage: %s <help|pippenger_wnaf|strauss_wnaf|simple>\n", argv[0]); 25 printf("The output shows the number of multiplied and summed points right after the\n"); 26 printf("function name. The letter 'g' indicates that one of the points is the generator.\n"); 27 printf("The benchmarks are divided by the number of points.\n"); 28 printf("\n"); 29 printf("default (ecmult_multi): picks pippenger_wnaf or strauss_wnaf depending on the\n"); 30 printf(" batch size\n"); 31 printf("pippenger_wnaf: for all batch sizes\n"); 32 printf("strauss_wnaf: for all batch sizes\n"); 33 printf("simple: multiply and sum each point individually\n"); 34 } 35 36 typedef struct { 37 /* Setup once in advance */ 38 haskellsecp256k1_v0_1_0_context* ctx; 39 haskellsecp256k1_v0_1_0_scratch_space* scratch; 40 haskellsecp256k1_v0_1_0_scalar* scalars; 41 haskellsecp256k1_v0_1_0_ge* pubkeys; 42 haskellsecp256k1_v0_1_0_gej* pubkeys_gej; 43 haskellsecp256k1_v0_1_0_scalar* seckeys; 44 haskellsecp256k1_v0_1_0_gej* expected_output; 45 haskellsecp256k1_v0_1_0_ecmult_multi_func ecmult_multi; 46 47 /* Changes per benchmark */ 48 size_t count; 49 int includes_g; 50 51 /* Changes per benchmark iteration, used to pick different scalars and pubkeys 52 * in each run. */ 53 size_t offset1; 54 size_t offset2; 55 56 /* Benchmark output. */ 57 haskellsecp256k1_v0_1_0_gej* output; 58 } bench_data; 59 60 /* Hashes x into [0, POINTS) twice and store the result in offset1 and offset2. */ 61 static void hash_into_offset(bench_data* data, size_t x) { 62 data->offset1 = (x * 0x537b7f6f + 0x8f66a481) % POINTS; 63 data->offset2 = (x * 0x7f6f537b + 0x6a1a8f49) % POINTS; 64 } 65 66 /* Check correctness of the benchmark by computing 67 * sum(outputs) ?= (sum(scalars_gen) + sum(seckeys)*sum(scalars))*G */ 68 static void bench_ecmult_teardown_helper(bench_data* data, size_t* seckey_offset, size_t* scalar_offset, size_t* scalar_gen_offset, int iters) { 69 int i; 70 haskellsecp256k1_v0_1_0_gej sum_output, tmp; 71 haskellsecp256k1_v0_1_0_scalar sum_scalars; 72 73 haskellsecp256k1_v0_1_0_gej_set_infinity(&sum_output); 74 haskellsecp256k1_v0_1_0_scalar_clear(&sum_scalars); 75 for (i = 0; i < iters; ++i) { 76 haskellsecp256k1_v0_1_0_gej_add_var(&sum_output, &sum_output, &data->output[i], NULL); 77 if (scalar_gen_offset != NULL) { 78 haskellsecp256k1_v0_1_0_scalar_add(&sum_scalars, &sum_scalars, &data->scalars[(*scalar_gen_offset+i) % POINTS]); 79 } 80 if (seckey_offset != NULL) { 81 haskellsecp256k1_v0_1_0_scalar s = data->seckeys[(*seckey_offset+i) % POINTS]; 82 haskellsecp256k1_v0_1_0_scalar_mul(&s, &s, &data->scalars[(*scalar_offset+i) % POINTS]); 83 haskellsecp256k1_v0_1_0_scalar_add(&sum_scalars, &sum_scalars, &s); 84 } 85 } 86 haskellsecp256k1_v0_1_0_ecmult_gen(&data->ctx->ecmult_gen_ctx, &tmp, &sum_scalars); 87 CHECK(haskellsecp256k1_v0_1_0_gej_eq_var(&tmp, &sum_output)); 88 } 89 90 static void bench_ecmult_setup(void* arg) { 91 bench_data* data = (bench_data*)arg; 92 /* Re-randomize offset to ensure that we're using different scalars and 93 * group elements in each run. */ 94 hash_into_offset(data, data->offset1); 95 } 96 97 static void bench_ecmult_gen(void* arg, int iters) { 98 bench_data* data = (bench_data*)arg; 99 int i; 100 101 for (i = 0; i < iters; ++i) { 102 haskellsecp256k1_v0_1_0_ecmult_gen(&data->ctx->ecmult_gen_ctx, &data->output[i], &data->scalars[(data->offset1+i) % POINTS]); 103 } 104 } 105 106 static void bench_ecmult_gen_teardown(void* arg, int iters) { 107 bench_data* data = (bench_data*)arg; 108 bench_ecmult_teardown_helper(data, NULL, NULL, &data->offset1, iters); 109 } 110 111 static void bench_ecmult_const(void* arg, int iters) { 112 bench_data* data = (bench_data*)arg; 113 int i; 114 115 for (i = 0; i < iters; ++i) { 116 haskellsecp256k1_v0_1_0_ecmult_const(&data->output[i], &data->pubkeys[(data->offset1+i) % POINTS], &data->scalars[(data->offset2+i) % POINTS]); 117 } 118 } 119 120 static void bench_ecmult_const_teardown(void* arg, int iters) { 121 bench_data* data = (bench_data*)arg; 122 bench_ecmult_teardown_helper(data, &data->offset1, &data->offset2, NULL, iters); 123 } 124 125 static void bench_ecmult_1p(void* arg, int iters) { 126 bench_data* data = (bench_data*)arg; 127 int i; 128 129 for (i = 0; i < iters; ++i) { 130 haskellsecp256k1_v0_1_0_ecmult(&data->output[i], &data->pubkeys_gej[(data->offset1+i) % POINTS], &data->scalars[(data->offset2+i) % POINTS], NULL); 131 } 132 } 133 134 static void bench_ecmult_1p_teardown(void* arg, int iters) { 135 bench_data* data = (bench_data*)arg; 136 bench_ecmult_teardown_helper(data, &data->offset1, &data->offset2, NULL, iters); 137 } 138 139 static void bench_ecmult_0p_g(void* arg, int iters) { 140 bench_data* data = (bench_data*)arg; 141 int i; 142 143 for (i = 0; i < iters; ++i) { 144 haskellsecp256k1_v0_1_0_ecmult(&data->output[i], NULL, &haskellsecp256k1_v0_1_0_scalar_zero, &data->scalars[(data->offset1+i) % POINTS]); 145 } 146 } 147 148 static void bench_ecmult_0p_g_teardown(void* arg, int iters) { 149 bench_data* data = (bench_data*)arg; 150 bench_ecmult_teardown_helper(data, NULL, NULL, &data->offset1, iters); 151 } 152 153 static void bench_ecmult_1p_g(void* arg, int iters) { 154 bench_data* data = (bench_data*)arg; 155 int i; 156 157 for (i = 0; i < iters/2; ++i) { 158 haskellsecp256k1_v0_1_0_ecmult(&data->output[i], &data->pubkeys_gej[(data->offset1+i) % POINTS], &data->scalars[(data->offset2+i) % POINTS], &data->scalars[(data->offset1+i) % POINTS]); 159 } 160 } 161 162 static void bench_ecmult_1p_g_teardown(void* arg, int iters) { 163 bench_data* data = (bench_data*)arg; 164 bench_ecmult_teardown_helper(data, &data->offset1, &data->offset2, &data->offset1, iters/2); 165 } 166 167 static void run_ecmult_bench(bench_data* data, int iters) { 168 char str[32]; 169 sprintf(str, "ecmult_gen"); 170 run_benchmark(str, bench_ecmult_gen, bench_ecmult_setup, bench_ecmult_gen_teardown, data, 10, iters); 171 sprintf(str, "ecmult_const"); 172 run_benchmark(str, bench_ecmult_const, bench_ecmult_setup, bench_ecmult_const_teardown, data, 10, iters); 173 /* ecmult with non generator point */ 174 sprintf(str, "ecmult_1p"); 175 run_benchmark(str, bench_ecmult_1p, bench_ecmult_setup, bench_ecmult_1p_teardown, data, 10, iters); 176 /* ecmult with generator point */ 177 sprintf(str, "ecmult_0p_g"); 178 run_benchmark(str, bench_ecmult_0p_g, bench_ecmult_setup, bench_ecmult_0p_g_teardown, data, 10, iters); 179 /* ecmult with generator and non-generator point. The reported time is per point. */ 180 sprintf(str, "ecmult_1p_g"); 181 run_benchmark(str, bench_ecmult_1p_g, bench_ecmult_setup, bench_ecmult_1p_g_teardown, data, 10, 2*iters); 182 } 183 184 static int bench_ecmult_multi_callback(haskellsecp256k1_v0_1_0_scalar* sc, haskellsecp256k1_v0_1_0_ge* ge, size_t idx, void* arg) { 185 bench_data* data = (bench_data*)arg; 186 if (data->includes_g) ++idx; 187 if (idx == 0) { 188 *sc = data->scalars[data->offset1]; 189 *ge = haskellsecp256k1_v0_1_0_ge_const_g; 190 } else { 191 *sc = data->scalars[(data->offset1 + idx) % POINTS]; 192 *ge = data->pubkeys[(data->offset2 + idx - 1) % POINTS]; 193 } 194 return 1; 195 } 196 197 static void bench_ecmult_multi(void* arg, int iters) { 198 bench_data* data = (bench_data*)arg; 199 200 int includes_g = data->includes_g; 201 int iter; 202 int count = data->count; 203 iters = iters / data->count; 204 205 for (iter = 0; iter < iters; ++iter) { 206 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); 207 data->offset1 = (data->offset1 + count) % POINTS; 208 data->offset2 = (data->offset2 + count - 1) % POINTS; 209 } 210 } 211 212 static void bench_ecmult_multi_setup(void* arg) { 213 bench_data* data = (bench_data*)arg; 214 hash_into_offset(data, data->count); 215 } 216 217 static void bench_ecmult_multi_teardown(void* arg, int iters) { 218 bench_data* data = (bench_data*)arg; 219 int iter; 220 iters = iters / data->count; 221 /* Verify the results in teardown, to avoid doing comparisons while benchmarking. */ 222 for (iter = 0; iter < iters; ++iter) { 223 haskellsecp256k1_v0_1_0_gej tmp; 224 haskellsecp256k1_v0_1_0_gej_add_var(&tmp, &data->output[iter], &data->expected_output[iter], NULL); 225 CHECK(haskellsecp256k1_v0_1_0_gej_is_infinity(&tmp)); 226 } 227 } 228 229 static void generate_scalar(uint32_t num, haskellsecp256k1_v0_1_0_scalar* scalar) { 230 haskellsecp256k1_v0_1_0_sha256 sha256; 231 unsigned char c[10] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0}; 232 unsigned char buf[32]; 233 int overflow = 0; 234 c[6] = num; 235 c[7] = num >> 8; 236 c[8] = num >> 16; 237 c[9] = num >> 24; 238 haskellsecp256k1_v0_1_0_sha256_initialize(&sha256); 239 haskellsecp256k1_v0_1_0_sha256_write(&sha256, c, sizeof(c)); 240 haskellsecp256k1_v0_1_0_sha256_finalize(&sha256, buf); 241 haskellsecp256k1_v0_1_0_scalar_set_b32(scalar, buf, &overflow); 242 CHECK(!overflow); 243 } 244 245 static void run_ecmult_multi_bench(bench_data* data, size_t count, int includes_g, int num_iters) { 246 char str[32]; 247 size_t iters = 1 + num_iters / count; 248 size_t iter; 249 250 data->count = count; 251 data->includes_g = includes_g; 252 253 /* Compute (the negation of) the expected results directly. */ 254 hash_into_offset(data, data->count); 255 for (iter = 0; iter < iters; ++iter) { 256 haskellsecp256k1_v0_1_0_scalar tmp; 257 haskellsecp256k1_v0_1_0_scalar total = data->scalars[(data->offset1++) % POINTS]; 258 size_t i = 0; 259 for (i = 0; i + 1 < count; ++i) { 260 haskellsecp256k1_v0_1_0_scalar_mul(&tmp, &data->seckeys[(data->offset2++) % POINTS], &data->scalars[(data->offset1++) % POINTS]); 261 haskellsecp256k1_v0_1_0_scalar_add(&total, &total, &tmp); 262 } 263 haskellsecp256k1_v0_1_0_scalar_negate(&total, &total); 264 haskellsecp256k1_v0_1_0_ecmult(&data->expected_output[iter], NULL, &haskellsecp256k1_v0_1_0_scalar_zero, &total); 265 } 266 267 /* Run the benchmark. */ 268 if (includes_g) { 269 sprintf(str, "ecmult_multi_%ip_g", (int)count - 1); 270 } else { 271 sprintf(str, "ecmult_multi_%ip", (int)count); 272 } 273 run_benchmark(str, bench_ecmult_multi, bench_ecmult_multi_setup, bench_ecmult_multi_teardown, data, 10, count * iters); 274 } 275 276 int main(int argc, char **argv) { 277 bench_data data; 278 int i, p; 279 size_t scratch_size; 280 281 int iters = get_iters(10000); 282 283 data.ecmult_multi = haskellsecp256k1_v0_1_0_ecmult_multi_var; 284 285 if (argc > 1) { 286 if(have_flag(argc, argv, "-h") 287 || have_flag(argc, argv, "--help") 288 || have_flag(argc, argv, "help")) { 289 help(argv); 290 return 0; 291 } else if(have_flag(argc, argv, "pippenger_wnaf")) { 292 printf("Using pippenger_wnaf:\n"); 293 data.ecmult_multi = haskellsecp256k1_v0_1_0_ecmult_pippenger_batch_single; 294 } else if(have_flag(argc, argv, "strauss_wnaf")) { 295 printf("Using strauss_wnaf:\n"); 296 data.ecmult_multi = haskellsecp256k1_v0_1_0_ecmult_strauss_batch_single; 297 } else if(have_flag(argc, argv, "simple")) { 298 printf("Using simple algorithm:\n"); 299 } else { 300 fprintf(stderr, "%s: unrecognized argument '%s'.\n\n", argv[0], argv[1]); 301 help(argv); 302 return 1; 303 } 304 } 305 306 data.ctx = haskellsecp256k1_v0_1_0_context_create(SECP256K1_CONTEXT_NONE); 307 scratch_size = haskellsecp256k1_v0_1_0_strauss_scratch_size(POINTS) + STRAUSS_SCRATCH_OBJECTS*16; 308 if (!have_flag(argc, argv, "simple")) { 309 data.scratch = haskellsecp256k1_v0_1_0_scratch_space_create(data.ctx, scratch_size); 310 } else { 311 data.scratch = NULL; 312 } 313 314 /* Allocate stuff */ 315 data.scalars = malloc(sizeof(haskellsecp256k1_v0_1_0_scalar) * POINTS); 316 data.seckeys = malloc(sizeof(haskellsecp256k1_v0_1_0_scalar) * POINTS); 317 data.pubkeys = malloc(sizeof(haskellsecp256k1_v0_1_0_ge) * POINTS); 318 data.pubkeys_gej = malloc(sizeof(haskellsecp256k1_v0_1_0_gej) * POINTS); 319 data.expected_output = malloc(sizeof(haskellsecp256k1_v0_1_0_gej) * (iters + 1)); 320 data.output = malloc(sizeof(haskellsecp256k1_v0_1_0_gej) * (iters + 1)); 321 322 /* Generate a set of scalars, and private/public keypairs. */ 323 haskellsecp256k1_v0_1_0_gej_set_ge(&data.pubkeys_gej[0], &haskellsecp256k1_v0_1_0_ge_const_g); 324 haskellsecp256k1_v0_1_0_scalar_set_int(&data.seckeys[0], 1); 325 for (i = 0; i < POINTS; ++i) { 326 generate_scalar(i, &data.scalars[i]); 327 if (i) { 328 haskellsecp256k1_v0_1_0_gej_double_var(&data.pubkeys_gej[i], &data.pubkeys_gej[i - 1], NULL); 329 haskellsecp256k1_v0_1_0_scalar_add(&data.seckeys[i], &data.seckeys[i - 1], &data.seckeys[i - 1]); 330 } 331 } 332 haskellsecp256k1_v0_1_0_ge_set_all_gej_var(data.pubkeys, data.pubkeys_gej, POINTS); 333 334 335 print_output_table_header_row(); 336 /* Initialize offset1 and offset2 */ 337 hash_into_offset(&data, 0); 338 run_ecmult_bench(&data, iters); 339 340 for (i = 1; i <= 8; ++i) { 341 run_ecmult_multi_bench(&data, i, 1, iters); 342 } 343 344 /* This is disabled with low count of iterations because the loop runs 77 times even with iters=1 345 * and the higher it goes the longer the computation takes(more points) 346 * So we don't run this benchmark with low iterations to prevent slow down */ 347 if (iters > 2) { 348 for (p = 0; p <= 11; ++p) { 349 for (i = 9; i <= 16; ++i) { 350 run_ecmult_multi_bench(&data, i << p, 1, iters); 351 } 352 } 353 } 354 355 if (data.scratch != NULL) { 356 haskellsecp256k1_v0_1_0_scratch_space_destroy(data.ctx, data.scratch); 357 } 358 haskellsecp256k1_v0_1_0_context_destroy(data.ctx); 359 free(data.scalars); 360 free(data.pubkeys); 361 free(data.pubkeys_gej); 362 free(data.seckeys); 363 free(data.output); 364 free(data.expected_output); 365 366 return(0); 367 }