Line data Source code
1 : #ifndef HEADER_fd_src_ballet_bn254_fd_bn254_glv_h
2 : #define HEADER_fd_src_ballet_bn254_fd_bn254_glv_h
3 :
4 : /* Included by fd_bn254_g1.c and fd_bn254_g2.c, should not be used elsewhere. */
5 :
6 : #include "./fd_bn254_internal.h"
7 :
8 : /* Rundown of the BN254 GLV implementation:
9 :
10 : Context: https://bitcointalk.org/index.php?topic=3238.msg45565#msg45565
11 :
12 : BN254 is a "pairing-friendly" curve E: y^2 = x^3 + 3 over a prime field
13 : Fp, where:
14 : p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
15 :
16 : The group G1 = E(Fp) has prime order:
17 : r = 21888242871839275222246405745257275088548364400416034343698204186575808495617
18 :
19 : A naive approach to scalar multiplication, [s]P, requires ~256 doublings
20 : and ~128 additions (double-and-add) in the worst case. The GLV method
21 : takes advantage of an easy to compute endomorphism to cut this roughly
22 : in half.
23 :
24 : For BN254, there exists a cube root of unity beta in Fp such that:
25 : phi: (x, y) -> (beta * x, y)
26 : is an endomorphism of E.
27 : That is, if point P = (x, y) is on the curve, then phi(P) = (beta * x, y)
28 : is also on the curve, since (beta*x)^3 = beta^3 * x^3) = x^3,
29 : so the curve equation is preserved.
30 :
31 : phi satisfies phi(P) = [lambda]P where lambda is a cube root of unity
32 : modulo r (the group order we defined above^):
33 : lambda = 4407920970296243842393367215006156084916469457145843978461
34 : (a root of X^2 + X + 1 = 0 mod r)
35 :
36 : Computing phi(P) = (beta * x, y) costs just one FP multiplication, but
37 : is equivalent to a full scalar multiplication by the ~254-bit scalar lambda.
38 :
39 : We want to "decompose" the input scalar in a way where a majority of the
40 : effort is re-used by the lambda computation, leaving the remaining operations
41 : smaller and faster to perform. Given a scalar s, we want to find small
42 : k1, k2 (each ~128-bit) such that:
43 : s = k1 + k2 * lambda (mod r)
44 : Then: [s]P = [k1]P + [k2](lambda * P) = [k1]P + [k2]phi(P).
45 :
46 : Using the "Straus-Shamir trick", https://pmc.ncbi.nlm.nih.gov/articles/PMC9028562/#app1-sensors-22-03083,
47 : this requires only ~128 doublings + ~128 additions instead of ~256 doublings.
48 :
49 : To decompose the scalar, we have a 2-dimensional lattice
50 : L = { (a, b) in Z^2 : a + b*lambda = 0 (mod r) }
51 :
52 : A reduced basis of L is given by three magnitudes:
53 : N_A = 147946756881789319000765030803803410728 (~128 bits, 2 limbs)
54 : N_B = 9931322734385697763 (~64 bits, 1 limb)
55 : N_C = 147946756881789319010696353538189108491 (~128 bits, 2 limbs)
56 :
57 : These are arranged differently depending on the group.
58 : G1:
59 : | +N_A +N_B |
60 : | -N_B +N_C |
61 : G2:
62 : | -N_C -N_B |
63 : | +N_B -N_A |
64 :
65 : We avoid big integer divisions by r using Babai's algorithm with
66 : precomputed fixed-point inverses:
67 : b1 = (s * g1) >> 256, where for group:
68 : G1: g1 = round(2^256 * N_C / r)
69 : G2: g1 = round(2^256 * N_A / r)
70 : b2 = (s * g2) >> 256 g2 = round(2^256 * N_B / r), 66-bit, 2 limbs)
71 :
72 : Then:
73 : G1: k1 = s - b1*N_A - b2*N_B, k2 = b1*N_B - b2*N_C
74 : G2: k1 = s - b1*N_C - b2*N_B, k2 = b2*N_A - b1*N_B
75 :
76 : For G1, k1 >= 0 always, k2 may be negative.
77 : For G2, both k1 and k2 may be negative. */
78 :
79 : /* Const definitions live in fd_bn254_g1.c. */
80 :
81 : /* beta in Montgomery form.
82 : 0x30644e72e131a0295e6dd9e7e0acccb0c28f069fbb966e3de4bd44e5607cfd48 */
83 : extern const fd_bn254_fp_t fd_bn254_const_beta_mont[1];
84 :
85 : /* Lattice constants, see glv.py */
86 : extern const ulong na[ 2 ];
87 : extern const ulong nb[ 1 ];
88 : extern const ulong nc[ 2 ];
89 :
90 : /* g2 = round(2^256 * N_B / r), 66-bit (2 limbs). Same for G1 and G2. */
91 : extern const ulong g2_const[ 2 ];
92 :
93 : /* Multiply 4-limb scalar s by a 3-limb constant g.
94 : Returns top 3 limbs. */
95 : static inline void
96 : fd_bn254_glv_sxg3( ulong out[ 3 ],
97 : fd_bn254_scalar_t const * s,
98 31629 : ulong const g[ 3 ] ) {
99 31629 : uint128 s0 = s->limbs[0];
100 31629 : uint128 s1 = s->limbs[1];
101 31629 : uint128 s2 = s->limbs[2];
102 31629 : uint128 s3 = s->limbs[3];
103 31629 : uint128 acc;
104 31629 : acc = s0 * g[ 0 ];
105 31629 : acc = s1 * g[ 0 ] + s0 * g[ 1 ] + (ulong)(acc >> 64);
106 31629 : acc = s2 * g[ 0 ] + s1 * g[ 1 ] + s0 * g[ 2 ] + (ulong)(acc >> 64);
107 31629 : acc = s3 * g[ 0 ] + s2 * g[ 1 ] + s1 * g[ 2 ] + (ulong)(acc >> 64);
108 31629 : acc = s3 * g[ 1 ] + s2 * g[ 2 ] + (ulong)(acc >> 64); out[ 0 ] = (ulong)acc;
109 31629 : acc = s3 * g[ 2 ] + (ulong)(acc >> 64); out[ 1 ] = (ulong)acc;
110 31629 : acc = (ulong)(acc >> 64); out[ 2 ] = (ulong)acc;
111 31629 : }
112 :
113 : /* Same, but for a 2-limb constant g. */
114 : static inline void
115 : fd_bn254_glv_sxg2( ulong out[ 2 ],
116 : fd_bn254_scalar_t const * s,
117 31629 : ulong const g[ 2 ] ) {
118 31629 : uint128 s0 = s->limbs[0];
119 31629 : uint128 s1 = s->limbs[1];
120 31629 : uint128 s2 = s->limbs[2];
121 31629 : uint128 s3 = s->limbs[3];
122 31629 : uint128 acc;
123 31629 : acc = s0 * g[ 0 ];
124 31629 : acc = s1 * g[ 0 ] + s0 * g[ 1 ] + (ulong)(acc >> 64);
125 31629 : acc = s2 * g[ 0 ] + s1 * g[ 1 ] + (ulong)(acc >> 64);
126 31629 : acc = s3 * g[ 0 ] + s2 * g[ 1 ] + (ulong)(acc >> 64);
127 31629 : acc = s3 * g[ 1 ] + (ulong)(acc >> 64); out[ 0 ] = (ulong)acc;
128 31629 : acc = (ulong)(acc >> 64); out[ 1 ] = (ulong)acc;
129 31629 : }
130 :
131 : /* Multiply 3-limb a by 2-limb n, store low 4 limbs into out. */
132 : static inline void
133 : fd_bn254_glv_mul3x2( ulong out[ 4 ],
134 : ulong const a[ 3 ],
135 31629 : ulong const n[ 2 ] ) {
136 31629 : uint128 acc;
137 31629 : acc = (uint128)a[ 0 ] * n[ 0 ]; out[ 0 ] = (ulong)acc;
138 31629 : acc = (uint128)a[ 1 ] * n[ 0 ] + (uint128)a[ 0 ] * n[ 1 ] + (ulong)(acc >> 64); out[ 1 ] = (ulong)acc;
139 31629 : acc = (uint128)a[ 2 ] * n[ 0 ] + (uint128)a[ 1 ] * n[ 1 ] + (ulong)(acc >> 64); out[ 2 ] = (ulong)acc;
140 31629 : acc = (uint128)a[ 2 ] * n[ 1 ] + (ulong)(acc >> 64); out[ 3 ] = (ulong)acc;
141 31629 : }
142 :
143 : /* Multiply 3-limb by 1-limb, store into 4-limb. */
144 : static inline void
145 : fd_bn254_glv_mul3x1( ulong out[ 4 ],
146 : ulong const a[ 3 ],
147 31629 : ulong const n[ 1 ] ) {
148 31629 : uint128 acc;
149 31629 : acc = (uint128)a[ 0 ] * n[ 0 ]; out[ 0 ] = (ulong)acc;
150 31629 : acc = (uint128)a[ 1 ] * n[ 0 ] + (ulong)(acc >> 64); out[ 1 ] = (ulong)acc;
151 31629 : acc = (uint128)a[ 2 ] * n[ 0 ] + (ulong)(acc >> 64); out[ 2 ] = (ulong)acc;
152 31629 : acc = (ulong)(acc >> 64); out[ 3 ] = (ulong)acc;
153 31629 : }
154 :
155 : /* Multiply 2-limb by 2-limb, store into 4-limb. */
156 : static inline void
157 : fd_bn254_glv_mul2x2( ulong out[ 4 ],
158 : ulong const a[ 2 ],
159 31629 : ulong const n[ 2 ] ) {
160 31629 : uint128 acc;
161 31629 : acc = (uint128)a[ 0 ] * n[ 0 ]; out[ 0 ] = (ulong)acc;
162 31629 : acc = (uint128)a[ 1 ] * n[ 0 ] + (uint128)a[ 0 ] * n[ 1 ] + (ulong)(acc >> 64); out[ 1 ] = (ulong)acc;
163 31629 : acc = (uint128)a[ 1 ] * n[ 1 ] + (ulong)(acc >> 64); out[ 2 ] = (ulong)acc;
164 31629 : acc = (ulong)(acc >> 64); out[ 3 ] = (ulong)acc;
165 31629 : }
166 :
167 : /* Multiply 2-limb by 1-limb, stores 3-limbs. */
168 : static inline void
169 : fd_bn254_glv_mul2x1( ulong out[ 3 ],
170 : ulong const a[ 2 ],
171 31629 : ulong const n[ 1 ] ) {
172 31629 : uint128 acc;
173 31629 : acc = (uint128)a[ 0 ] * n[ 0 ]; out[ 0 ] = (ulong)acc;
174 31629 : acc = (uint128)a[ 1 ] * n[ 0 ] + (ulong)(acc >> 64); out[ 1 ] = (ulong)acc;
175 31629 : acc = (ulong)(acc >> 64); out[ 2 ] = (ulong)acc;
176 31629 : }
177 :
178 : /* 4-limb addition: out = a + b. Returns carry. */
179 : static inline ulong
180 : fd_bn254_glv_add4( ulong out[ 4 ],
181 : ulong const a[ 4 ],
182 31629 : ulong const b[ 4 ] ) {
183 31629 : ulong carry = 0;
184 158145 : for( int j = 0; j < 4; j++ ) {
185 126516 : uint128 acc = (uint128)a[ j ] + b[ j ] + carry;
186 126516 : out[ j ] = (ulong)acc;
187 126516 : carry = (ulong)(acc >> 64);
188 126516 : }
189 31629 : return carry;
190 31629 : }
191 :
192 : /* 4-limb subtraction: out = a - b. Returns borrow (1 if a < b). */
193 : static inline ulong
194 : fd_bn254_glv_sub4( ulong out[ 4 ],
195 : ulong const a[ 4 ],
196 63258 : ulong const b[ 4 ] ) {
197 63258 : ulong borrow = 0;
198 316290 : for( int j = 0; j < 4; j++ ) {
199 253032 : ulong av = a[ j ];
200 253032 : ulong bv = b[ j ];
201 253032 : ulong diff = av - bv - borrow;
202 253032 : borrow = ( av < bv || (borrow && av == bv) ) ? 1UL : 0UL;
203 253032 : out[ j ] = diff;
204 253032 : }
205 63258 : return borrow;
206 63258 : }
207 :
208 : /* Two's complement negation of a 4-limb value in-place. */
209 : static inline void
210 306 : fd_bn254_glv_negate4( ulong v[ 4 ] ) {
211 306 : ulong carry = 1;
212 1530 : for( int j = 0; j < 4; j++ ) {
213 1224 : uint128 sum = (uint128)(~v[ j ]) + carry;
214 1224 : v[ j ] = (ulong)sum;
215 1224 : carry = (ulong)(sum >> 64);
216 1224 : }
217 306 : }
218 :
219 : #endif /* HEADER_fd_src_ballet_bn254_fd_bn254_glv_h */
|
