ecmult_gen.go raw
1 package p256k1
2
3 // =============================================================================
4 // Phase 5: Generator Precomputation for GLV Optimization
5 // =============================================================================
6 //
7 // This file contains precomputed tables for the secp256k1 generator point G
8 // and its λ-transformed version λ*G. These tables enable very fast scalar
9 // multiplication of the generator point.
10 //
11 // The GLV approach splits a 256-bit scalar k into two ~128-bit scalars k1, k2
12 // such that k = k1 + k2*λ (mod n). Then k*G = k1*G + k2*(λ*G).
13 //
14 // We precompute odd multiples of G and λ*G:
15 // preGenG[i] = (2*i+1) * G for i = 0 to tableSize-1
16 // preGenLambdaG[i] = (2*i+1) * (λ*G) for i = 0 to tableSize-1
17 //
18 // Reference: libsecp256k1 ecmult_gen_impl.h
19
20 // Window size for generator multiplication
21 // Larger window = more precomputation but faster multiplication
22 // libsecp256k1 uses window 15 for ecmult (8192 entries) and comb with 352 points for ecmult_gen
23 // Window 8 is maximum due to wNAF int8 digit limit; 128 entries per table
24 const genWindowSize = 8
25 const genTableSize = 1 << (genWindowSize - 1) // 128 entries
26
27 // Precomputed tables for generator multiplication
28 // These are computed once at init() time
29 var (
30 // preGenG contains odd multiples of G: preGenG[i] = (2*i+1)*G
31 preGenG [genTableSize]GroupElementAffine
32
33 // preGenLambdaG contains odd multiples of λ*G: preGenLambdaG[i] = (2*i+1)*(λ*G)
34 preGenLambdaG [genTableSize]GroupElementAffine
35
36 // preGenBetaX contains β*x for each point in preGenG (for potential future optimization)
37 preGenBetaX [genTableSize]FieldElement
38
39 // genTablesInitialized tracks whether the tables have been computed
40 genTablesInitialized bool
41 )
42
43 // initGenTables computes the precomputed generator tables
44 // This is called automatically on first use
45 func initGenTables() {
46 if genTablesInitialized {
47 return
48 }
49
50 // Build odd multiples of G
51 var gJac GroupElementJacobian
52 gJac.setGE(&Generator)
53
54 var preJacG [genTableSize]GroupElementJacobian
55 preJacG[0] = gJac
56
57 // Compute 2*G
58 var twoG GroupElementJacobian
59 twoG.double(&gJac)
60
61 // Build odd multiples: preJacG[i] = (2*i+1)*G
62 for i := 1; i < genTableSize; i++ {
63 preJacG[i].addVar(&preJacG[i-1], &twoG)
64 }
65
66 // Batch normalize to affine
67 BatchNormalize(preGenG[:], preJacG[:])
68
69 // Compute λ*G
70 var lambdaG GroupElementAffine
71 lambdaG.mulLambda(&Generator)
72
73 // Build odd multiples of λ*G
74 var lambdaGJac GroupElementJacobian
75 lambdaGJac.setGE(&lambdaG)
76
77 var preJacLambdaG [genTableSize]GroupElementJacobian
78 preJacLambdaG[0] = lambdaGJac
79
80 // Compute 2*(λ*G)
81 var twoLambdaG GroupElementJacobian
82 twoLambdaG.double(&lambdaGJac)
83
84 // Build odd multiples: preJacLambdaG[i] = (2*i+1)*(λ*G)
85 for i := 1; i < genTableSize; i++ {
86 preJacLambdaG[i].addVar(&preJacLambdaG[i-1], &twoLambdaG)
87 }
88
89 // Batch normalize to affine
90 BatchNormalize(preGenLambdaG[:], preJacLambdaG[:])
91
92 // Precompute β*x for each point in preGenG
93 for i := 0; i < genTableSize; i++ {
94 if preGenG[i].isInfinity() {
95 preGenBetaX[i] = FieldElementZero
96 } else {
97 preGenBetaX[i].mul(&preGenG[i].x, &fieldBeta)
98 }
99 }
100
101 genTablesInitialized = true
102 }
103
104 // EnsureGenTablesInitialized ensures the generator tables are computed
105 // This is automatically called by ecmultGenGLV, but can be called explicitly
106 // during application startup to avoid first-use latency
107 func EnsureGenTablesInitialized() {
108 initGenTables()
109 }
110
111 // ecmultGenGLV computes r = k * G using precomputed tables and GLV endomorphism
112 // This is the fastest method for generator multiplication
113 func ecmultGenGLV(r *GroupElementJacobian, k *Scalar) {
114 if k.isZero() {
115 r.setInfinity()
116 return
117 }
118
119 // Ensure tables are initialized
120 initGenTables()
121
122 // Split scalar using GLV: k = k1 + k2*λ
123 var k1, k2 Scalar
124 scalarSplitLambda(&k1, &k2, k)
125
126 // Normalize k1 and k2 to be "low" (not high)
127 // If k1 is high, negate it and we'll negate the final contribution
128 neg1 := k1.isHigh()
129 if neg1 {
130 k1.negate(&k1)
131 }
132
133 neg2 := k2.isHigh()
134 if neg2 {
135 k2.negate(&k2)
136 }
137
138 // Convert to wNAF
139 var wnaf1, wnaf2 [257]int8
140
141 bits1 := k1.wNAF(&wnaf1, genWindowSize)
142 bits2 := k2.wNAF(&wnaf2, genWindowSize)
143
144 // Find maximum bit position
145 maxBits := bits1
146 if bits2 > maxBits {
147 maxBits = bits2
148 }
149
150 // Perform Strauss algorithm using precomputed tables
151 r.setInfinity()
152
153 for i := maxBits - 1; i >= 0; i-- {
154 // Double the result
155 if !r.isInfinity() {
156 r.double(r)
157 }
158
159 // Add contribution from k1 (using preGenG table)
160 if i < bits1 && wnaf1[i] != 0 {
161 var pt GroupElementAffine
162 n := int(wnaf1[i])
163
164 var idx int
165 if n > 0 {
166 idx = (n - 1) / 2
167 } else {
168 idx = (-n - 1) / 2
169 }
170
171 if idx < genTableSize {
172 pt = preGenG[idx]
173 // Negate if wNAF digit is negative
174 if n < 0 {
175 pt.negate(&pt)
176 }
177 // Negate if k1 was negated during normalization
178 if neg1 {
179 pt.negate(&pt)
180 }
181
182 if r.isInfinity() {
183 r.setGE(&pt)
184 } else {
185 r.addGE(r, &pt)
186 }
187 }
188 }
189
190 // Add contribution from k2 (using preGenLambdaG table)
191 if i < bits2 && wnaf2[i] != 0 {
192 var pt GroupElementAffine
193 n := int(wnaf2[i])
194
195 var idx int
196 if n > 0 {
197 idx = (n - 1) / 2
198 } else {
199 idx = (-n - 1) / 2
200 }
201
202 if idx < genTableSize {
203 pt = preGenLambdaG[idx]
204 // Negate if wNAF digit is negative
205 if n < 0 {
206 pt.negate(&pt)
207 }
208 // Negate if k2 was negated during normalization
209 if neg2 {
210 pt.negate(&pt)
211 }
212
213 if r.isInfinity() {
214 r.setGE(&pt)
215 } else {
216 r.addGE(r, &pt)
217 }
218 }
219 }
220 }
221 }
222
223
224 // ecmultGenSimple computes r = k * G using a simple approach without GLV
225 // This uses the precomputed table for G only, without scalar splitting
226 // Useful for comparison and as a fallback
227 func ecmultGenSimple(r *GroupElementJacobian, k *Scalar) {
228 if k.isZero() {
229 r.setInfinity()
230 return
231 }
232
233 // Ensure tables are initialized
234 initGenTables()
235
236 // Normalize scalar if it's high (has high bit set)
237 var kNorm Scalar
238 kNorm = *k
239 negResult := kNorm.isHigh()
240 if negResult {
241 kNorm.negate(&kNorm)
242 }
243
244 // Convert to wNAF
245 var wnaf [257]int8
246
247 bits := kNorm.wNAF(&wnaf, genWindowSize)
248
249 // Perform algorithm using precomputed table
250 r.setInfinity()
251
252 for i := bits - 1; i >= 0; i-- {
253 // Double the result
254 if !r.isInfinity() {
255 r.double(r)
256 }
257
258 // Add contribution
259 if wnaf[i] != 0 {
260 var pt GroupElementAffine
261 n := int(wnaf[i])
262
263 var idx int
264 if n > 0 {
265 idx = (n - 1) / 2
266 } else {
267 idx = (-n - 1) / 2
268 }
269
270 if idx < genTableSize {
271 pt = preGenG[idx]
272 if n < 0 {
273 pt.negate(&pt)
274 }
275
276 if r.isInfinity() {
277 r.setGE(&pt)
278 } else {
279 r.addGE(r, &pt)
280 }
281 }
282 }
283 }
284
285 // Negate result if we negated the scalar
286 if negResult {
287 r.negate(r)
288 }
289 }
290
291 // EcmultGenSimple is the public interface for simple generator multiplication
292 func EcmultGenSimple(r *GroupElementJacobian, k *Scalar) {
293 ecmultGenSimple(r, k)
294 }
295
296 // =============================================================================
297 // EcmultGenContext - Compatibility layer for existing codebase
298 // =============================================================================
299
300 // EcmultGenContext represents the generator multiplication context
301 // This wraps the precomputed tables for generator multiplication
302 type EcmultGenContext struct {
303 initialized bool
304 }
305
306 // NewEcmultGenContext creates a new generator multiplication context
307 // This initializes the precomputed tables if not already done
308 func NewEcmultGenContext() *EcmultGenContext {
309 initGenTables()
310 return &EcmultGenContext{
311 initialized: true,
312 }
313 }
314
315