src/bench_ecmult.c

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