zzstoatzz.io
this repo has no description
1const std = @import("std");
2const jacobian_mod = @import("jacobian.zig");
3const JacobianPoint = jacobian_mod.JacobianPoint;
4const AffinePoint = jacobian_mod.AffinePoint;
5const endo = @import("endo.zig");
6const affine_mod = @import("affine.zig");
7const Secp256k1 = std.crypto.ecc.Secp256k1;
8
9/// Build a precomputation table: [identity, p, 2p, 3p, ..., count*p].
10/// Uses Jacobian arithmetic for efficient computation.
11pub fn precompute(p: AffinePoint, comptime count: usize) [1 + count]JacobianPoint {
12 var pc: [1 + count]JacobianPoint = undefined;
13 pc[0] = JacobianPoint.identity;
14 pc[1] = JacobianPoint.fromAffine(p);
15 var i: usize = 2;
16 while (i <= count) : (i += 1) {
17 pc[i] = if (i % 2 == 0) pc[i / 2].dbl() else pc[i - 1].addMixed(p);
18 }
19 return pc;
20}
21
22/// Apply the endomorphism to each entry in an affine precompute table.
23/// phi(n*P) = n*phi(P), so transforming the table gives a valid table for phi(P).
24pub fn phiTableAffine(comptime n: usize, table: [n]AffinePoint) [n]AffinePoint {
25 var result: [n]AffinePoint = undefined;
26 for (0..n) |i| {
27 result[i] = endo.phiAffine(table[i]);
28 }
29 return result;
30}
31
32/// Apply the endomorphism to each entry in a Jacobian precompute table.
33pub fn phiTableJacobian(comptime n: usize, table: [n]JacobianPoint) [n]JacobianPoint {
34 var result: [n]JacobianPoint = undefined;
35 for (0..n) |i| {
36 result[i] = endo.phiJacobian(table[i]);
37 }
38 return result;
39}
40
41/// Encode a scalar into a signed 4-bit windowed representation.
42/// Returns 65 digits in [-8, 8], suitable for use with a 9-entry precompute table.
43/// For half-sized scalars (128-bit), digits 33-64 are zero.
44pub fn slide(s: [32]u8) [2 * 32 + 1]i8 {
45 var e: [2 * 32 + 1]i8 = undefined;
46 for (s, 0..) |x, i| {
47 e[i * 2 + 0] = @as(i8, @as(u4, @truncate(x)));
48 e[i * 2 + 1] = @as(i8, @as(u4, @truncate(x >> 4)));
49 }
50 var carry: i8 = 0;
51 for (e[0..64]) |*x| {
52 x.* += carry;
53 carry = (x.* + 8) >> 4;
54 x.* -= carry * 16;
55 }
56 e[64] = carry;
57 return e;
58}
59
60test "precompute table correctness" {
61 const G = Secp256k1.basePoint;
62 const g_affine = G.affineCoordinates();
63 const g26 = AffinePoint.fromStdlib(g_affine);
64
65 const table = precompute(g26, 8);
66
67 // table[0] should be identity
68 try std.testing.expect(table[0].z.isZero());
69
70 // table[1] should be G — compare via toProjective
71 const t1_affine = table[1].toProjective().affineCoordinates();
72 try std.testing.expect(t1_affine.x.equivalent(g_affine.x));
73 try std.testing.expect(t1_affine.y.equivalent(g_affine.y));
74
75 // table[2] should be 2G
76 const t2_affine = table[2].toProjective().affineCoordinates();
77 const stdlib_2g = G.dbl().affineCoordinates();
78 try std.testing.expect(t2_affine.x.equivalent(stdlib_2g.x));
79 try std.testing.expect(t2_affine.y.equivalent(stdlib_2g.y));
80
81 // table[3] should be 3G = 2G + G
82 const t3_affine = table[3].toProjective().affineCoordinates();
83 const stdlib_3g = G.dbl().add(G).affineCoordinates();
84 try std.testing.expect(t3_affine.x.equivalent(stdlib_3g.x));
85 try std.testing.expect(t3_affine.y.equivalent(stdlib_3g.y));
86}
87
88test "slide produces valid digits" {
89 // Test with a known scalar
90 var s: [32]u8 = undefined;
91 std.mem.writeInt(u256, &s, 12345678, .little);
92 const digits = slide(s);
93
94 // All digits should be in [-8, 8]
95 for (digits) |d| {
96 try std.testing.expect(d >= -8 and d <= 8);
97 }
98
99 // Reconstruct the value and verify
100 var reconstructed: i512 = 0;
101 var power: i512 = 1;
102 for (digits) |d| {
103 reconstructed += @as(i512, d) * power;
104 power *= 16;
105 }
106 try std.testing.expectEqual(@as(i512, 12345678), reconstructed);
107}