trace_double_test.go raw
1 package avx
2
3 import (
4 "encoding/hex"
5 "fmt"
6 "testing"
7 )
8
9 func TestGeneratorConstants(t *testing.T) {
10 // Verify the generator X and Y constants
11 expectedGx := "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798"
12 expectedGy := "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8"
13
14 gx := Generator.X.Bytes()
15 gy := Generator.Y.Bytes()
16
17 t.Logf("Generator X: %x", gx)
18 t.Logf("Expected X: %s", expectedGx)
19 t.Logf("Generator Y: %x", gy)
20 t.Logf("Expected Y: %s", expectedGy)
21
22 // They should match
23 if expectedGx != fmt.Sprintf("%x", gx) {
24 t.Error("Generator X mismatch")
25 }
26 if expectedGy != fmt.Sprintf("%x", gy) {
27 t.Error("Generator Y mismatch")
28 }
29
30 // Verify G is on the curve
31 if !Generator.IsOnCurve() {
32 t.Error("Generator should be on curve")
33 }
34
35 // Let me test squaring and multiplication more carefully
36 // Y² should equal X³ + 7
37 var y2, x2, x3, seven, rhs FieldElement
38 y2.Sqr(&Generator.Y)
39 x2.Sqr(&Generator.X)
40 x3.Mul(&x2, &Generator.X)
41 seven.N[0].Lo = 7
42 rhs.Add(&x3, &seven)
43
44 t.Logf("Y² = %x", y2.Bytes())
45 t.Logf("X³ + 7 = %x", rhs.Bytes())
46
47 if !y2.Equal(&rhs) {
48 t.Error("Y² != X³ + 7 for generator")
49 }
50 }
51
52 func TestTraceDouble(t *testing.T) {
53 // Test the point doubling step by step
54 var g JacobianPoint
55 g.FromAffine(&Generator)
56
57 t.Logf("Input G:")
58 t.Logf(" X = %x", g.X.Bytes())
59 t.Logf(" Y = %x", g.Y.Bytes())
60 t.Logf(" Z = %x", g.Z.Bytes())
61
62 // Standard Jacobian doubling for y²=x³+b (secp256k1 has a=0):
63 // M = 3*X₁²
64 // S = 4*X₁*Y₁²
65 // T = 8*Y₁⁴
66 // X₃ = M² - 2*S
67 // Y₃ = M*(S - X₃) - T
68 // Z₃ = 2*Y₁*Z₁
69
70 var y2, m, x2, s, t_val, x3, y3, z3, tmp FieldElement
71
72 // Y² = Y₁²
73 y2.Sqr(&g.Y)
74 t.Logf("Y² = %x", y2.Bytes())
75
76 // M = 3*X²
77 x2.Sqr(&g.X)
78 t.Logf("X² = %x", x2.Bytes())
79 m.MulInt(&x2, 3)
80 t.Logf("M = 3*X² = %x", m.Bytes())
81
82 // S = 4*X₁*Y₁²
83 s.Mul(&g.X, &y2)
84 t.Logf("X*Y² = %x", s.Bytes())
85 s.MulInt(&s, 4)
86 t.Logf("S = 4*X*Y² = %x", s.Bytes())
87
88 // T = 8*Y₁⁴
89 t_val.Sqr(&y2)
90 t.Logf("Y⁴ = %x", t_val.Bytes())
91 t_val.MulInt(&t_val, 8)
92 t.Logf("T = 8*Y⁴ = %x", t_val.Bytes())
93
94 // X₃ = M² - 2*S
95 x3.Sqr(&m)
96 t.Logf("M² = %x", x3.Bytes())
97 tmp.Double(&s)
98 t.Logf("2*S = %x", tmp.Bytes())
99 x3.Sub(&x3, &tmp)
100 t.Logf("X₃ = M² - 2*S = %x", x3.Bytes())
101
102 // Y₃ = M*(S - X₃) - T
103 tmp.Sub(&s, &x3)
104 t.Logf("S - X₃ = %x", tmp.Bytes())
105 y3.Mul(&m, &tmp)
106 t.Logf("M*(S-X₃) = %x", y3.Bytes())
107 y3.Sub(&y3, &t_val)
108 t.Logf("Y₃ = M*(S-X₃) - T = %x", y3.Bytes())
109
110 // Z₃ = 2*Y₁*Z₁
111 z3.Mul(&g.Y, &g.Z)
112 z3.Double(&z3)
113 t.Logf("Z₃ = 2*Y*Z = %x", z3.Bytes())
114
115 // Now convert to affine
116 var doubled JacobianPoint
117 doubled.X = x3
118 doubled.Y = y3
119 doubled.Z = z3
120 doubled.Infinity = false
121
122 var affineResult AffinePoint
123 doubled.ToAffine(&affineResult)
124 t.Logf("Affine result (correct formula):")
125 t.Logf(" X = %x", affineResult.X.Bytes())
126 t.Logf(" Y = %x", affineResult.Y.Bytes())
127
128 // Expected 2G
129 expectedX := "c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5"
130 expectedY := "1ae168fea63dc339a3c58419466ceae1061b7c24a6b3e36e3b4d04f7a8f63301"
131 t.Logf("Expected:")
132 t.Logf(" X = %s", expectedX)
133 t.Logf(" Y = %s", expectedY)
134
135 // Verify by computing 2G using the existing Double method
136 var doubled2 JacobianPoint
137 doubled2.Double(&g)
138 var affine2 AffinePoint
139 doubled2.ToAffine(&affine2)
140 t.Logf("Current Double method result:")
141 t.Logf(" X = %x", affine2.X.Bytes())
142 t.Logf(" Y = %x", affine2.Y.Bytes())
143
144 // Compare results
145 expectedXBytes, _ := hex.DecodeString(expectedX)
146 expectedYBytes, _ := hex.DecodeString(expectedY)
147
148 if fmt.Sprintf("%x", affineResult.X.Bytes()) == expectedX &&
149 fmt.Sprintf("%x", affineResult.Y.Bytes()) == expectedY {
150 t.Logf("Correct formula produces expected result!")
151 } else {
152 t.Logf("Even correct formula doesn't match - problem elsewhere")
153 }
154
155 _ = expectedXBytes
156 _ = expectedYBytes
157
158 // Verify the result is on the curve
159 t.Logf("Result is on curve: %v", affineResult.IsOnCurve())
160
161 // Compute y² for the computed result
162 var verifyY2, verifyX2, verifyX3, verifySeven, verifyRhs FieldElement
163 verifyY2.Sqr(&affineResult.Y)
164 verifyX2.Sqr(&affineResult.X)
165 verifyX3.Mul(&verifyX2, &affineResult.X)
166 verifySeven.N[0].Lo = 7
167 verifyRhs.Add(&verifyX3, &verifySeven)
168 t.Logf("Computed y² = %x", verifyY2.Bytes())
169 t.Logf("Computed x³+7 = %x", verifyRhs.Bytes())
170 t.Logf("y² == x³+7: %v", verifyY2.Equal(&verifyRhs))
171
172 // Now test with the expected Y value
173 var expectedYField, expectedY2Field FieldElement
174 expectedYField.SetBytes(expectedYBytes)
175 expectedY2Field.Sqr(&expectedYField)
176 t.Logf("Expected Y² = %x", expectedY2Field.Bytes())
177 t.Logf("Expected Y² == x³+7: %v", expectedY2Field.Equal(&verifyRhs))
178
179 // Maybe I have the negative Y - let's check the negation
180 var negY FieldElement
181 negY.Negate(&affineResult.Y)
182 t.Logf("Negated computed Y = %x", negY.Bytes())
183
184 // Also check if the expected value is valid at all
185 // The expected 2G should be:
186 // X = c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
187 // Y = 1ae168fea63dc339a3c58419466ceae1061b7c24a6b3e36e3b4d04f7a8f63301
188 // Let me verify this is correct by computing y² directly
189 t.Log("--- Verifying expected 2G values ---")
190 var expXField FieldElement
191 expXField.SetBytes(expectedXBytes)
192
193 // Compute x³ + 7 for the expected X
194 var expX2, expX3, expRhs FieldElement
195 expX2.Sqr(&expXField)
196 expX3.Mul(&expX2, &expXField)
197 var seven2 FieldElement
198 seven2.N[0].Lo = 7
199 expRhs.Add(&expX3, &seven2)
200 t.Logf("For expected X, x³+7 = %x", expRhs.Bytes())
201
202 // Compute sqrt
203 var sqrtY FieldElement
204 if sqrtY.Sqrt(&expRhs) {
205 t.Logf("sqrt(x³+7) = %x", sqrtY.Bytes())
206 var negSqrtY FieldElement
207 negSqrtY.Negate(&sqrtY)
208 t.Logf("-sqrt(x³+7) = %x", negSqrtY.Bytes())
209 }
210 }
211
212 func TestDebugPointAdd(t *testing.T) {
213 // Compute 3G two ways: (1) G + 2G and (2) 3*G via scalar mult
214 var g, twoG, threeGAdd JacobianPoint
215 var affine3GAdd, affine3GSM AffinePoint
216
217 g.FromAffine(&Generator)
218 twoG.Double(&g)
219 threeGAdd.Add(&twoG, &g)
220 threeGAdd.ToAffine(&affine3GAdd)
221
222 t.Logf("2G (Jacobian):")
223 t.Logf(" X = %x", twoG.X.Bytes())
224 t.Logf(" Y = %x", twoG.Y.Bytes())
225 t.Logf(" Z = %x", twoG.Z.Bytes())
226
227 t.Logf("3G via Add (affine):")
228 t.Logf(" X = %x", affine3GAdd.X.Bytes())
229 t.Logf(" Y = %x", affine3GAdd.Y.Bytes())
230 t.Logf(" On curve: %v", affine3GAdd.IsOnCurve())
231
232 // Now via scalar mult
233 var three Scalar
234 three.D[0].Lo = 3
235 var threeGSM JacobianPoint
236 threeGSM.ScalarMult(&g, &three)
237 threeGSM.ToAffine(&affine3GSM)
238
239 t.Logf("3G via ScalarMult (affine):")
240 t.Logf(" X = %x", affine3GSM.X.Bytes())
241 t.Logf(" Y = %x", affine3GSM.Y.Bytes())
242 t.Logf(" On curve: %v", affine3GSM.IsOnCurve())
243
244 // Compute expected 3G using Python
245 // This should be:
246 // X = f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
247 // Y = 388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
248 t.Logf("Equal: %v", affine3GAdd.Equal(&affine3GSM))
249 }
250
251 func TestAVX2Operations(t *testing.T) {
252 // Test that AVX2 assembly produces same results as Go code
253 if !hasAVX2() {
254 t.Skip("AVX2 not available")
255 }
256
257 // Test field addition
258 var a, b, resultGo, resultAVX FieldElement
259 a.N[0].Lo = 0x123456789ABCDEF0
260 a.N[0].Hi = 0xFEDCBA9876543210
261 a.N[1].Lo = 0x1111111111111111
262 a.N[1].Hi = 0x2222222222222222
263
264 b.N[0].Lo = 0x0FEDCBA987654321
265 b.N[0].Hi = 0x123456789ABCDEF0
266 b.N[1].Lo = 0x3333333333333333
267 b.N[1].Hi = 0x4444444444444444
268
269 resultGo.Add(&a, &b)
270 FieldAddAVX2(&resultAVX, &a, &b)
271
272 if !resultGo.Equal(&resultAVX) {
273 t.Errorf("FieldAddAVX2 mismatch:\n Go: %x\n AVX2: %x", resultGo.Bytes(), resultAVX.Bytes())
274 }
275
276 // Test field subtraction
277 resultGo.Sub(&a, &b)
278 FieldSubAVX2(&resultAVX, &a, &b)
279
280 if !resultGo.Equal(&resultAVX) {
281 t.Errorf("FieldSubAVX2 mismatch:\n Go: %x\n AVX2: %x", resultGo.Bytes(), resultAVX.Bytes())
282 }
283
284 // Test field multiplication
285 resultGo.Mul(&a, &b)
286 FieldMulAVX2(&resultAVX, &a, &b)
287
288 if !resultGo.Equal(&resultAVX) {
289 t.Errorf("FieldMulAVX2 mismatch:\n Go: %x\n AVX2: %x", resultGo.Bytes(), resultAVX.Bytes())
290 }
291
292 // Test scalar addition
293 var sa, sb, sResultGo, sResultAVX Scalar
294 sa.D[0].Lo = 0x123456789ABCDEF0
295 sa.D[0].Hi = 0xFEDCBA9876543210
296 sa.D[1].Lo = 0x1111111111111111
297 sa.D[1].Hi = 0x2222222222222222
298
299 sb.D[0].Lo = 0x0FEDCBA987654321
300 sb.D[0].Hi = 0x123456789ABCDEF0
301 sb.D[1].Lo = 0x3333333333333333
302 sb.D[1].Hi = 0x4444444444444444
303
304 sResultGo.Add(&sa, &sb)
305 ScalarAddAVX2(&sResultAVX, &sa, &sb)
306
307 if !sResultGo.Equal(&sResultAVX) {
308 t.Errorf("ScalarAddAVX2 mismatch:\n Go: %x\n AVX2: %x", sResultGo.Bytes(), sResultAVX.Bytes())
309 }
310
311 // Test scalar multiplication
312 sResultGo.Mul(&sa, &sb)
313 ScalarMulAVX2(&sResultAVX, &sa, &sb)
314
315 if !sResultGo.Equal(&sResultAVX) {
316 t.Errorf("ScalarMulAVX2 mismatch:\n Go: %x\n AVX2: %x", sResultGo.Bytes(), sResultAVX.Bytes())
317 }
318
319 t.Logf("Field and Scalar Add/Sub AVX2 operations match Go implementations")
320 }
321
322 func TestDebugScalarMult(t *testing.T) {
323 // Test 2*G via scalar mult
324 var g, twoGDouble, twoGSM JacobianPoint
325 var affineDouble, affineSM AffinePoint
326
327 g.FromAffine(&Generator)
328
329 // Via doubling
330 twoGDouble.Double(&g)
331 twoGDouble.ToAffine(&affineDouble)
332
333 // Via scalar mult (k=2)
334 var two Scalar
335 two.D[0].Lo = 2
336
337 // Print the bytes of k=2
338 twoBytes := two.Bytes()
339 t.Logf("k=2 bytes: %x", twoBytes[:])
340
341 twoGSM.ScalarMult(&g, &two)
342 twoGSM.ToAffine(&affineSM)
343
344 t.Logf("2G via Double (affine):")
345 t.Logf(" X = %x", affineDouble.X.Bytes())
346 t.Logf(" Y = %x", affineDouble.Y.Bytes())
347 t.Logf(" On curve: %v", affineDouble.IsOnCurve())
348
349 t.Logf("2G via ScalarMult (affine):")
350 t.Logf(" X = %x", affineSM.X.Bytes())
351 t.Logf(" Y = %x", affineSM.Y.Bytes())
352 t.Logf(" On curve: %v", affineSM.IsOnCurve())
353
354 t.Logf("Equal: %v", affineDouble.Equal(&affineSM))
355
356 // Manual scalar mult for k=2
357 // Binary: 10 (2 bits)
358 // Start with p = infinity
359 // bit 1: p = 2*infinity = infinity, then p = p + G = G
360 // bit 0: p = 2*G, no add
361 // Result should be 2G
362
363 var p JacobianPoint
364 p.SetInfinity()
365
366 // Process bit 1 (the high bit of 2)
367 p.Double(&p)
368 t.Logf("After double of infinity: IsInfinity=%v", p.IsInfinity())
369 p.Add(&p, &g)
370 t.Logf("After add G: IsInfinity=%v", p.IsInfinity())
371
372 var affineP AffinePoint
373 p.ToAffine(&affineP)
374 t.Logf("After first iteration (should be G):")
375 t.Logf(" X = %x", affineP.X.Bytes())
376 t.Logf(" Y = %x", affineP.Y.Bytes())
377 t.Logf(" Equal to G: %v", affineP.Equal(&Generator))
378
379 // Process bit 0
380 p.Double(&p)
381 p.ToAffine(&affineP)
382 t.Logf("After second iteration (should be 2G):")
383 t.Logf(" X = %x", affineP.X.Bytes())
384 t.Logf(" Y = %x", affineP.Y.Bytes())
385 t.Logf(" On curve: %v", affineP.IsOnCurve())
386 t.Logf(" Equal to Double result: %v", affineP.Equal(&affineDouble))
387
388 // Test: does doubling G into a fresh variable work?
389 var fresh JacobianPoint
390 var freshAffine AffinePoint
391 fresh.Double(&g)
392 fresh.ToAffine(&freshAffine)
393 t.Logf("Fresh Double(g):")
394 t.Logf(" X = %x", freshAffine.X.Bytes())
395 t.Logf(" Y = %x", freshAffine.Y.Bytes())
396 t.Logf(" On curve: %v", freshAffine.IsOnCurve())
397
398 // Test: what about p.Double(p) when p == g?
399 var pCopy JacobianPoint
400 pCopy = p // now p is already set to some value
401 pCopy.FromAffine(&Generator)
402 t.Logf("Before in-place double, pCopy X: %x", pCopy.X.Bytes())
403 pCopy.Double(&pCopy)
404 var pCopyAffine AffinePoint
405 pCopy.ToAffine(&pCopyAffine)
406 t.Logf("After in-place Double(&pCopy):")
407 t.Logf(" X = %x", pCopyAffine.X.Bytes())
408 t.Logf(" Y = %x", pCopyAffine.Y.Bytes())
409 t.Logf(" On curve: %v", pCopyAffine.IsOnCurve())
410 }
411