Bitcoin Core  27.99.0
P2P Digital Currency
ecmult_gen_compute_table_impl.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Copyright (c) Pieter Wuille, Gregory Maxwell, Peter Dettman *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
5  ***********************************************************************/
6 
7 #ifndef SECP256K1_ECMULT_GEN_COMPUTE_TABLE_IMPL_H
8 #define SECP256K1_ECMULT_GEN_COMPUTE_TABLE_IMPL_H
9 
11 #include "group_impl.h"
12 #include "field_impl.h"
13 #include "scalar_impl.h"
14 #include "ecmult_gen.h"
15 #include "util.h"
16 
17 static void secp256k1_ecmult_gen_compute_table(secp256k1_ge_storage* table, const secp256k1_ge* gen, int blocks, int teeth, int spacing) {
18  size_t points = ((size_t)1) << (teeth - 1);
19  size_t points_total = points * blocks;
20  secp256k1_ge* prec = checked_malloc(&default_error_callback, points_total * sizeof(*prec));
21  secp256k1_gej* ds = checked_malloc(&default_error_callback, teeth * sizeof(*ds));
22  secp256k1_gej* vs = checked_malloc(&default_error_callback, points_total * sizeof(*vs));
23  secp256k1_gej u;
24  size_t vs_pos = 0;
25  secp256k1_scalar half;
26  int block, i;
27 
28  VERIFY_CHECK(points_total > 0);
29 
30  /* u is the running power of two times gen we're working with, initially gen/2. */
33  for (i = 255; i >= 0; --i) {
34  /* Use a very simple multiplication ladder to avoid dependency on ecmult. */
35  secp256k1_gej_double_var(&u, &u, NULL);
36  if (secp256k1_scalar_get_bits_limb32(&half, i, 1)) {
37  secp256k1_gej_add_ge_var(&u, &u, gen, NULL);
38  }
39  }
40 #ifdef VERIFY
41  {
42  /* Verify that u*2 = gen. */
43  secp256k1_gej double_u;
44  secp256k1_gej_double_var(&double_u, &u, NULL);
45  VERIFY_CHECK(secp256k1_gej_eq_ge_var(&double_u, gen));
46  }
47 #endif
48 
49  for (block = 0; block < blocks; ++block) {
50  int tooth;
51  /* Here u = 2^(block*teeth*spacing) * gen/2. */
54  for (tooth = 0; tooth < teeth; ++tooth) {
55  /* Here u = 2^((block*teeth + tooth)*spacing) * gen/2. */
56  /* Make sum = sum(2^((block*teeth + t)*spacing), t=0..tooth) * gen/2. */
57  secp256k1_gej_add_var(&sum, &sum, &u, NULL);
58  /* Make u = 2^((block*teeth + tooth)*spacing + 1) * gen/2. */
59  secp256k1_gej_double_var(&u, &u, NULL);
60  /* Make ds[tooth] = u = 2^((block*teeth + tooth)*spacing + 1) * gen/2. */
61  ds[tooth] = u;
62  /* Make u = 2^((block*teeth + tooth + 1)*spacing) * gen/2, unless at the end. */
63  if (block + tooth != blocks + teeth - 2) {
64  int bit_off;
65  for (bit_off = 1; bit_off < spacing; ++bit_off) {
66  secp256k1_gej_double_var(&u, &u, NULL);
67  }
68  }
69  }
70  /* Now u = 2^((block*teeth + teeth)*spacing) * gen/2
71  * = 2^((block+1)*teeth*spacing) * gen/2 */
72 
73  /* Next, compute the table entries for block number block in Jacobian coordinates.
74  * The entries will occupy vs[block*points + i] for i=0..points-1.
75  * We start by computing the first (i=0) value corresponding to all summed
76  * powers of two times G being negative. */
77  secp256k1_gej_neg(&vs[vs_pos++], &sum);
78  /* And then teeth-1 times "double" the range of i values for which the table
79  * is computed: in each iteration, double the table by taking an existing
80  * table entry and adding ds[tooth]. */
81  for (tooth = 0; tooth < teeth - 1; ++tooth) {
82  size_t stride = ((size_t)1) << tooth;
83  size_t index;
84  for (index = 0; index < stride; ++index, ++vs_pos) {
85  secp256k1_gej_add_var(&vs[vs_pos], &vs[vs_pos - stride], &ds[tooth], NULL);
86  }
87  }
88  }
89  VERIFY_CHECK(vs_pos == points_total);
90 
91  /* Convert all points simultaneously from secp256k1_gej to secp256k1_ge. */
92  secp256k1_ge_set_all_gej_var(prec, vs, points_total);
93  /* Convert all points from secp256k1_ge to secp256k1_ge_storage output. */
94  for (block = 0; block < blocks; ++block) {
95  size_t index;
96  for (index = 0; index < points; ++index) {
97  VERIFY_CHECK(!secp256k1_ge_is_infinity(&prec[block * points + index]));
98  secp256k1_ge_to_storage(&table[block * points + index], &prec[block * points + index]);
99  }
100  }
101 
102  /* Free memory. */
103  free(vs);
104  free(ds);
105  free(prec);
106 }
107 
108 #endif /* SECP256K1_ECMULT_GEN_COMPUTE_TABLE_IMPL_H */
static void secp256k1_ecmult_gen_compute_table(secp256k1_ge_storage *table, const secp256k1_ge *gen, int blocks, int teeth, int spacing)
volatile double sum
Definition: examples.cpp:10
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Set r equal to the double of a.
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Set a group element (jacobian) equal to the point at infinity.
static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr)
Set r equal to the sum of a and b (with b given in affine coordinates).
static int secp256k1_gej_eq_ge_var(const secp256k1_gej *a, const secp256k1_ge *b)
Check two group elements (jacobian and affine) for equality in variable time.
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.
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Check whether a group element is the point at infinity.
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_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Convert a group element to the storage type.
static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a)
Set r equal to the inverse of a (i.e., mirrored around the X axis)
static void secp256k1_scalar_half(secp256k1_scalar *r, const secp256k1_scalar *a)
Multiply a scalar with the multiplicative inverse of 2.
static uint32_t secp256k1_scalar_get_bits_limb32(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
Access bits (1 < count <= 32) from a scalar.
static const secp256k1_scalar secp256k1_scalar_one
Definition: scalar_impl.h:27
static SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition: util.h:156
static const secp256k1_callback default_error_callback
Definition: util.h:111
#define VERIFY_CHECK(cond)
Definition: util.h:153
A group element in affine coordinates on the secp256k1 curve, or occasionally on an isomorphic curve ...
Definition: group.h:16
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:28
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13