Update libsecp256k1 subtree to latest master

1 files changed, 79 insertions, 55 deletions

diff --git a/src/secp256k1/src/ecmult_gen_compute_table_impl.h b/src/secp256k1/src/ecmult_gen_compute_table_impl.h
index dfbacdbfde..6aa8d84082 100644
--- a/src/secp256k1/src/ecmult_gen_compute_table_impl.h
+++ b/src/secp256k1/src/ecmult_gen_compute_table_impl.h
@@ -1,5 +1,5 @@
 /***********************************************************************
- * Copyright (c) 2013, 2014, 2015 Pieter Wuille, Gregory Maxwell       *
+ * Copyright (c) Pieter Wuille, Gregory Maxwell, Peter Dettman         *
  * Distributed under the MIT software license, see the accompanying    *
  * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
  ***********************************************************************/
@@ -10,74 +10,98 @@
 #include "ecmult_gen_compute_table.h"
 #include "group_impl.h"
 #include "field_impl.h"
+#include "scalar_impl.h"
 #include "ecmult_gen.h"
 #include "util.h"
 
-static void secp256k1_ecmult_gen_compute_table(secp256k1_ge_storage* table, const secp256k1_ge* gen, int bits) {
-    int g = ECMULT_GEN_PREC_G(bits);
-    int n = ECMULT_GEN_PREC_N(bits);
+static void secp256k1_ecmult_gen_compute_table(secp256k1_ge_storage* table, const secp256k1_ge* gen, int blocks, int teeth, int spacing) {
+    size_t points = ((size_t)1) << (teeth - 1);
+    size_t points_total = points * blocks;
+    secp256k1_ge* prec = checked_malloc(&default_error_callback, points_total * sizeof(*prec));
+    secp256k1_gej* ds = checked_malloc(&default_error_callback, teeth * sizeof(*ds));
+    secp256k1_gej* vs = checked_malloc(&default_error_callback, points_total * sizeof(*vs));
+    secp256k1_gej u;
+    size_t vs_pos = 0;
+    secp256k1_scalar half;
+    int block, i;
 
-    secp256k1_ge* prec = checked_malloc(&default_error_callback, n * g * sizeof(*prec));
-    secp256k1_gej gj;
-    secp256k1_gej nums_gej;
-    int i, j;
+    VERIFY_CHECK(points_total > 0);
 
-    VERIFY_CHECK(g > 0);
-    VERIFY_CHECK(n > 0);
-
-    /* get the generator */
-    secp256k1_gej_set_ge(&gj, gen);
-
-    /* Construct a group element with no known corresponding scalar (nothing up my sleeve). */
+    /* u is the running power of two times gen we're working with, initially gen/2. */
+    secp256k1_scalar_half(&half, &secp256k1_scalar_one);
+    secp256k1_gej_set_infinity(&u);
+    for (i = 255; i >= 0; --i) {
+        /* Use a very simple multiplication ladder to avoid dependency on ecmult. */
+        secp256k1_gej_double_var(&u, &u, NULL);
+        if (secp256k1_scalar_get_bits_limb32(&half, i, 1)) {
+            secp256k1_gej_add_ge_var(&u, &u, gen, NULL);
+        }
+    }
+#ifdef VERIFY
     {
-        static const unsigned char nums_b32[33] = "The scalar for this x is unknown";
-        secp256k1_fe nums_x;
-        secp256k1_ge nums_ge;
-        int r;
-        r = secp256k1_fe_set_b32_limit(&nums_x, nums_b32);
-        (void)r;
-        VERIFY_CHECK(r);
-        r = secp256k1_ge_set_xo_var(&nums_ge, &nums_x, 0);
-        (void)r;
-        VERIFY_CHECK(r);
-        secp256k1_gej_set_ge(&nums_gej, &nums_ge);
-        /* Add G to make the bits in x uniformly distributed. */
-        secp256k1_gej_add_ge_var(&nums_gej, &nums_gej, gen, NULL);
+        /* Verify that u*2 = gen. */
+        secp256k1_gej double_u;
+        secp256k1_gej_double_var(&double_u, &u, NULL);
+        VERIFY_CHECK(secp256k1_gej_eq_ge_var(&double_u, gen));
     }
+#endif
 
-    /* compute prec. */
-    {
-        secp256k1_gej gbase;
-        secp256k1_gej numsbase;
-        secp256k1_gej* precj = checked_malloc(&default_error_callback, n * g * sizeof(*precj));  /* Jacobian versions of prec. */
-        gbase = gj; /* PREC_G^j * G */
-        numsbase = nums_gej; /* 2^j * nums. */
-        for (j = 0; j < n; j++) {
-            /* Set precj[j*PREC_G .. j*PREC_G+(PREC_G-1)] to (numsbase, numsbase + gbase, ..., numsbase + (PREC_G-1)*gbase). */
-            precj[j*g] = numsbase;
-            for (i = 1; i < g; i++) {
-                secp256k1_gej_add_var(&precj[j*g + i], &precj[j*g + i - 1], &gbase, NULL);
+    for (block = 0; block < blocks; ++block) {
+        int tooth;
+        /* Here u = 2^(block*teeth*spacing) * gen/2. */
+        secp256k1_gej sum;
+        secp256k1_gej_set_infinity(&sum);
+        for (tooth = 0; tooth < teeth; ++tooth) {
+            /* Here u = 2^((block*teeth + tooth)*spacing) * gen/2. */
+            /* Make sum = sum(2^((block*teeth + t)*spacing), t=0..tooth) * gen/2. */
+            secp256k1_gej_add_var(&sum, &sum, &u, NULL);
+            /* Make u = 2^((block*teeth + tooth)*spacing + 1) * gen/2. */
+            secp256k1_gej_double_var(&u, &u, NULL);
+            /* Make ds[tooth] = u = 2^((block*teeth + tooth)*spacing + 1) * gen/2. */
+            ds[tooth] = u;
+            /* Make u = 2^((block*teeth + tooth + 1)*spacing) * gen/2, unless at the end. */
+            if (block + tooth != blocks + teeth - 2) {
+                int bit_off;
+                for (bit_off = 1; bit_off < spacing; ++bit_off) {
+                    secp256k1_gej_double_var(&u, &u, NULL);
+                }
             }
-            /* Multiply gbase by PREC_G. */
-            for (i = 0; i < bits; i++) {
-                secp256k1_gej_double_var(&gbase, &gbase, NULL);
-            }
-            /* Multiply numbase by 2. */
-            secp256k1_gej_double_var(&numsbase, &numsbase, NULL);
-            if (j == n - 2) {
-                /* In the last iteration, numsbase is (1 - 2^j) * nums instead. */
-                secp256k1_gej_neg(&numsbase, &numsbase);
-                secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej, NULL);
+        }
+        /* Now u = 2^((block*teeth + teeth)*spacing) * gen/2
+         *       = 2^((block+1)*teeth*spacing) * gen/2       */
+
+        /* Next, compute the table entries for block number block in Jacobian coordinates.
+         * The entries will occupy vs[block*points + i] for i=0..points-1.
+         * We start by computing the first (i=0) value corresponding to all summed
+         * powers of two times G being negative. */
+        secp256k1_gej_neg(&vs[vs_pos++], &sum);
+        /* And then teeth-1 times "double" the range of i values for which the table
+         * is computed: in each iteration, double the table by taking an existing
+         * table entry and adding ds[tooth]. */
+        for (tooth = 0; tooth < teeth - 1; ++tooth) {
+            size_t stride = ((size_t)1) << tooth;
+            size_t index;
+            for (index = 0; index < stride; ++index, ++vs_pos) {
+                secp256k1_gej_add_var(&vs[vs_pos], &vs[vs_pos - stride], &ds[tooth], NULL);
             }
         }
-        secp256k1_ge_set_all_gej_var(prec, precj, n * g);
-        free(precj);
     }
-    for (j = 0; j < n; j++) {
-        for (i = 0; i < g; i++) {
-            secp256k1_ge_to_storage(&table[j*g + i], &prec[j*g + i]);
+    VERIFY_CHECK(vs_pos == points_total);
+
+    /* Convert all points simultaneously from secp256k1_gej to secp256k1_ge. */
+    secp256k1_ge_set_all_gej_var(prec, vs, points_total);
+    /* Convert all points from secp256k1_ge to secp256k1_ge_storage output. */
+    for (block = 0; block < blocks; ++block) {
+        size_t index;
+        for (index = 0; index < points; ++index) {
+            VERIFY_CHECK(!secp256k1_ge_is_infinity(&prec[block * points + index]));
+            secp256k1_ge_to_storage(&table[block * points + index], &prec[block * points + index]);
         }
     }
+
+    /* Free memory. */
+    free(vs);
+    free(ds);
     free(prec);
 }