zzstoatzz.io
this repo has no description
1const std = @import("std");
2const Secp256k1 = std.crypto.ecc.Secp256k1;
3const Fe = @import("field.zig").Fe;
4const jacobian_mod = @import("jacobian.zig");
5const JacobianPoint = jacobian_mod.JacobianPoint;
6const AffinePoint = jacobian_mod.AffinePoint;
7
8/// Batch-convert Jacobian points to affine using Montgomery's trick.
9/// Uses 1 field inversion + 3*(n-1) field multiplications.
10/// For Jacobian: x_affine = X * Z^{-2}, y_affine = Y * Z^{-3}.
11pub fn batchToAffine(comptime n: usize, points: [n]JacobianPoint) [n]AffinePoint {
12 // Replace zero Z with one to keep products invertible
13 var zs: [n]Fe = undefined;
14 for (0..n) |i| {
15 zs[i] = if (points[i].z.isZero()) Fe.one else points[i].z;
16 }
17
18 // Forward: accumulate Z products
19 var products: [n]Fe = undefined;
20 products[0] = zs[0];
21 for (1..n) |i| {
22 products[i] = products[i - 1].mul(zs[i]);
23 }
24
25 // Invert total product
26 var inv = products[n - 1].invert();
27
28 // Backward: recover individual Z inverses and convert to affine
29 // For Jacobian: x = X * zinv², y = Y * zinv³
30 var result: [n]AffinePoint = undefined;
31 var i: usize = n - 1;
32 while (true) {
33 const z_inv = if (i > 0) inv.mul(products[i - 1]) else inv;
34 if (i > 0) inv = inv.mul(zs[i]);
35
36 if (points[i].z.isZero()) {
37 result[i] = AffinePoint.identity;
38 } else {
39 const z_inv2 = z_inv.sq();
40 const z_inv3 = z_inv2.mul(z_inv);
41 result[i] = .{
42 .x = points[i].x.mul(z_inv2),
43 .y = points[i].y.mul(z_inv3),
44 };
45 }
46
47 if (i == 0) break;
48 i -= 1;
49 }
50
51 return result;
52}
53
54/// Build a byte-indexed precomputed table for scalar multiplication.
55/// table[i][j] = j * 256^i * base, stored as AffinePoint.
56/// 32 subtables × 256 entries = full 256-bit scalar coverage.
57/// table[i][0] is the identity element (unused in lookups).
58pub fn buildByteTable(base: Secp256k1) [32][256]AffinePoint {
59 @setEvalBranchQuota(100_000_000);
60
61 // Phase 1: compute all 32*256 points in Jacobian Fe
62 var flat: [32 * 256]JacobianPoint = undefined;
63
64 var cur_base_affine = AffinePoint.fromStdlib(base.affineCoordinates());
65 for (0..32) |sub| {
66 flat[sub * 256] = JacobianPoint.identity;
67 flat[sub * 256 + 1] = JacobianPoint.fromAffine(cur_base_affine);
68 for (2..256) |j| {
69 flat[sub * 256 + j] = flat[sub * 256 + j - 1].addMixed(cur_base_affine);
70 }
71 if (sub < 31) {
72 // next subtable base = 256 * current base (8 doublings)
73 var next = JacobianPoint.fromAffine(cur_base_affine);
74 next = next.dbl().dbl().dbl().dbl().dbl().dbl().dbl().dbl();
75 // convert back to affine for next iteration
76 const next_batch = batchToAffine(1, .{next});
77 cur_base_affine = next_batch[0];
78 }
79 }
80
81 // Phase 2: batch convert to affine
82 const affine_flat = batchToAffine(32 * 256, flat);
83
84 // Reshape to [32][256]
85 var result: [32][256]AffinePoint = undefined;
86 for (0..32) |sub| {
87 for (0..256) |j| {
88 result[sub][j] = affine_flat[sub * 256 + j];
89 }
90 }
91 return result;
92}
93
94test "batchToAffine matches individual conversion" {
95 const G = Secp256k1.basePoint;
96 const g_affine = G.affineCoordinates();
97 const g26 = AffinePoint.fromStdlib(g_affine);
98 const StdAffineCoordinates = @TypeOf(g_affine);
99
100 const j_id = JacobianPoint.identity;
101 const j_g = JacobianPoint.fromAffine(g26);
102 const j_2g = j_g.dbl();
103 const j_3g = j_2g.addMixed(g26);
104
105 const points = [_]JacobianPoint{ j_id, j_g, j_2g, j_3g };
106 const result = batchToAffine(4, points);
107
108 // Identity
109 try std.testing.expect(result[0].x.isZero());
110
111 // G — compare via stdlib
112 const result_g = StdAffineCoordinates{
113 .x = result[1].x.toStdlib(),
114 .y = result[1].y.toStdlib(),
115 };
116 try std.testing.expect(result_g.x.equivalent(g_affine.x));
117 try std.testing.expect(result_g.y.equivalent(g_affine.y));
118
119 // 2G
120 const g2_affine = G.dbl().affineCoordinates();
121 const result_2g = StdAffineCoordinates{
122 .x = result[2].x.toStdlib(),
123 .y = result[2].y.toStdlib(),
124 };
125 try std.testing.expect(result_2g.x.equivalent(g2_affine.x));
126 try std.testing.expect(result_2g.y.equivalent(g2_affine.y));
127
128 // 3G
129 const g3_affine = G.dbl().add(G).affineCoordinates();
130 const result_3g = StdAffineCoordinates{
131 .x = result[3].x.toStdlib(),
132 .y = result[3].y.toStdlib(),
133 };
134 try std.testing.expect(result_3g.x.equivalent(g3_affine.x));
135 try std.testing.expect(result_3g.y.equivalent(g3_affine.y));
136}