Line data Source code
1 : #include "./fd_bn254.h"
2 :
3 : /* Pairing */
4 :
5 : static inline void
6 : fd_bn254_pairing_proj_dbl( fd_bn254_fp12_t * r,
7 : fd_bn254_g2_t * t,
8 16128 : fd_bn254_g1_t const * p ) {
9 : /* https://eprint.iacr.org/2012/408, Sec 4.2.
10 : See also: https://eprint.iacr.org/2013/722, Sec. 4.3, Eq. (11).
11 : https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/pairing.go#L302
12 : Note: this can be optimized by precomputing 3x, -y and probably more. */
13 16128 : fd_bn254_fp2_t * X = &t->X;
14 16128 : fd_bn254_fp2_t * Y = &t->Y;
15 16128 : fd_bn254_fp2_t * Z = &t->Z;
16 16128 : fd_bn254_fp_t const * x = &p->X;
17 16128 : fd_bn254_fp_t const * y = &p->Y;
18 16128 : fd_bn254_fp2_t a[1], b[1], c[1], d[1];
19 16128 : fd_bn254_fp2_t e[1], f[1], g[1], h[1];
20 16128 : fd_bn254_fp_t x3[1];
21 : /* A=X1*Y1/2 */
22 16128 : fd_bn254_fp2_mul( a, X, Y );
23 16128 : fd_bn254_fp2_halve( a, a );
24 : /* B=Y1^2 */
25 16128 : fd_bn254_fp2_sqr( b, Y );
26 : /* C=Z1^2 */
27 16128 : fd_bn254_fp2_sqr( c, Z );
28 : /* D=3C */
29 16128 : fd_bn254_fp2_add( d, c, c );
30 16128 : fd_bn254_fp2_add( d, d, c );
31 : /* E=b'*D */
32 16128 : fd_bn254_fp2_mul( e, d, fd_bn254_const_twist_b_mont );
33 : /* F=3E */
34 16128 : fd_bn254_fp2_add( f, e, e );
35 16128 : fd_bn254_fp2_add( f, f, e );
36 : /* G=(B+F)/2 */
37 16128 : fd_bn254_fp2_add( g, b, f );
38 16128 : fd_bn254_fp2_halve( g, g );
39 : /* H =(Y1+Z1)^2 − (B+C) */
40 16128 : fd_bn254_fp2_add( h, Y, Z );
41 16128 : fd_bn254_fp2_sqr( h, h );
42 16128 : fd_bn254_fp2_sub( h, h, b );
43 16128 : fd_bn254_fp2_sub( h, h, c );
44 :
45 : /* g(P) = (H * -y) + (X^2 * 3 * x)w + (E−B)w^3. */
46 : /* el[0][0] = -(H * y) */
47 16128 : fd_bn254_fp2_neg( &r->el[0].el[0], h );
48 16128 : fd_bn254_fp_mul( &r->el[0].el[0].el[0], &r->el[0].el[0].el[0], y );
49 16128 : fd_bn254_fp_mul( &r->el[0].el[0].el[1], &r->el[0].el[0].el[1], y );
50 : /* el[0][1] = 0 */
51 16128 : fd_bn254_fp2_set_zero( &r->el[0].el[1] );
52 : /* el[0][2] = 0 */
53 16128 : fd_bn254_fp2_set_zero( &r->el[0].el[2] );
54 : /* el[1][0] = (3 * X^2 * x) */
55 16128 : fd_bn254_fp2_sqr( &r->el[1].el[0], X );
56 16128 : fd_bn254_fp_add( x3, x, x );
57 16128 : fd_bn254_fp_add( x3, x3, x );
58 16128 : fd_bn254_fp_mul( &r->el[1].el[0].el[0], &r->el[1].el[0].el[0], x3 );
59 16128 : fd_bn254_fp_mul( &r->el[1].el[0].el[1], &r->el[1].el[0].el[1], x3 );
60 : /* el[1][0] = (E−B) */
61 16128 : fd_bn254_fp2_sub( &r->el[1].el[1], e, b );
62 : /* el[1][2] = 0 */
63 16128 : fd_bn254_fp2_set_zero( &r->el[1].el[2] );
64 :
65 : /* update t */
66 : /* X3 = A * (B−F) */
67 16128 : fd_bn254_fp2_sub( X, b, f );
68 16128 : fd_bn254_fp2_mul( X, X, a );
69 : /* Y3 = G^2 − 3*E^2 (reusing var c, d) */
70 16128 : fd_bn254_fp2_sqr( Y, g );
71 16128 : fd_bn254_fp2_sqr( c, e );
72 16128 : fd_bn254_fp2_add( d, c, c );
73 16128 : fd_bn254_fp2_add( d, d, c );
74 16128 : fd_bn254_fp2_sub( Y, Y, d );
75 : /* Z3 = B * H */
76 16128 : fd_bn254_fp2_mul( Z, b, h );
77 16128 : }
78 :
79 : static inline void
80 : fd_bn254_pairing_proj_add_sub( fd_bn254_fp12_t * r,
81 : fd_bn254_g2_t * t,
82 : fd_bn254_g2_t const * q,
83 : fd_bn254_g1_t const * p,
84 : int is_add,
85 6048 : int add_point ) {
86 : /* https://eprint.iacr.org/2012/408, Sec 4.2.
87 : See also: https://eprint.iacr.org/2013/722, Sec. 4.3, Eq. (12, 13).
88 : https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/pairing.go#L343
89 : Note: this can be optimized by precomputing -x and probably more. */
90 6048 : fd_bn254_fp2_t * X = &t->X;
91 6048 : fd_bn254_fp2_t * Y = &t->Y;
92 6048 : fd_bn254_fp2_t * Z = &t->Z;
93 6048 : fd_bn254_fp2_t const * X2 = &q->X;
94 6048 : fd_bn254_fp2_t Y2[1];
95 6048 : fd_bn254_fp_t const * x = &p->X;
96 6048 : fd_bn254_fp_t const * y = &p->Y;
97 6048 : fd_bn254_fp2_t a[1], b[1], c[1], d[1];
98 6048 : fd_bn254_fp2_t e[1], f[1], g[1], h[1];
99 6048 : fd_bn254_fp2_t i[1], j[1], k[1];
100 6048 : fd_bn254_fp2_t o[1], l[1];
101 :
102 6048 : if( is_add ) {
103 2772 : fd_bn254_fp2_set( Y2, &q->Y );
104 3276 : } else {
105 3276 : fd_bn254_fp2_neg( Y2, &q->Y );
106 3276 : }
107 :
108 6048 : fd_bn254_fp2_mul( a, Y2, Z );
109 6048 : fd_bn254_fp2_mul( b, X2, Z );
110 6048 : fd_bn254_fp2_sub( o, Y, a );
111 6048 : fd_bn254_fp2_sub( l, X, b );
112 :
113 6048 : fd_bn254_fp2_mul( j, o, X2 );
114 6048 : fd_bn254_fp2_mul( k, l, Y2 );
115 : // fd_bn254_fp2_sub( j, j, k );
116 :
117 : /* g(P) */
118 : /* el[0][0] = (l * y) */
119 6048 : fd_bn254_fp_mul( &r->el[0].el[0].el[0], &l->el[0], y );
120 6048 : fd_bn254_fp_mul( &r->el[0].el[0].el[1], &l->el[1], y );
121 : /* el[0][1] = 0 */
122 6048 : fd_bn254_fp2_set_zero( &r->el[0].el[1] );
123 : /* el[0][2] = 0 */
124 6048 : fd_bn254_fp2_set_zero( &r->el[0].el[2] );
125 : /* el[1][0] = -(o * x), term in w */
126 6048 : fd_bn254_fp2_neg( &r->el[1].el[0], o );
127 6048 : fd_bn254_fp_mul( &r->el[1].el[0].el[0], &r->el[1].el[0].el[0], x );
128 6048 : fd_bn254_fp_mul( &r->el[1].el[0].el[1], &r->el[1].el[0].el[1], x );
129 : /* el[1][1] = j-k */
130 6048 : fd_bn254_fp2_sub( &r->el[1].el[1], j, k );
131 : /* el[1][2] = 0 */
132 6048 : fd_bn254_fp2_set_zero( &r->el[1].el[2] );
133 :
134 6048 : if( add_point ) {
135 5544 : fd_bn254_fp2_sqr( c, o );
136 5544 : fd_bn254_fp2_sqr( d, l );
137 5544 : fd_bn254_fp2_mul( e, d, l );
138 5544 : fd_bn254_fp2_mul( f, Z, c );
139 5544 : fd_bn254_fp2_mul( g, X, d );
140 5544 : fd_bn254_fp2_add( h, e, f );
141 5544 : fd_bn254_fp2_sub( h, h, g );
142 5544 : fd_bn254_fp2_sub( h, h, g );
143 5544 : fd_bn254_fp2_mul( i, Y, e );
144 :
145 : /* update t */
146 5544 : fd_bn254_fp2_mul( X, l, h );
147 5544 : fd_bn254_fp2_sub( Y, g, h );
148 5544 : fd_bn254_fp2_mul( Y, Y, o );
149 5544 : fd_bn254_fp2_sub( Y, Y, i );
150 5544 : fd_bn254_fp2_mul( Z, Z, e );
151 5544 : }
152 6048 : }
153 :
154 : fd_bn254_fp12_t *
155 : fd_bn254_miller_loop( fd_bn254_fp12_t * f,
156 : fd_bn254_g1_t const p[],
157 : fd_bn254_g2_t const q[],
158 156 : ulong sz ) {
159 : /* https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/pairing.go#L121 */
160 : //TODO use more efficient muls
161 156 : const schar s[] = {
162 156 : 0, 0, 0, 1, 0, 1, 0, -1,
163 156 : 0, 0, -1, 0, 0, 0, 1, 0,
164 156 : 0, -1, 0, -1, 0, 0, 0, 1,
165 156 : 0, -1, 0, 0, 0, 0, -1, 0,
166 156 : 0, 1, 0, -1, 0, 0, 1, 0,
167 156 : 0, 0, 0, 0, -1, 0, 0, -1,
168 156 : 0, 1, 0, -1, 0, 0, 0, -1,
169 156 : 0, -1, 0, 0, 0, 1, 0, -1, /* 0, 1 */
170 156 : };
171 :
172 156 : fd_bn254_g2_t t[FD_BN254_PAIRING_BATCH_MAX], frob[1];
173 156 : fd_bn254_fp12_t l[1];
174 :
175 156 : fd_bn254_fp12_set_one( f );
176 408 : for ( ulong j=0; j<sz; j++ ) {
177 252 : fd_bn254_g2_set( &t[j], &q[j] );
178 252 : }
179 :
180 408 : for( ulong j=0; j<sz; j++ ) {
181 252 : fd_bn254_pairing_proj_dbl( l, &t[j], &p[j] );
182 252 : fd_bn254_fp12_mul( f, f, l );
183 252 : }
184 156 : fd_bn254_fp12_sqr( f, f );
185 :
186 408 : for( ulong j=0; j<sz; j++ ) {
187 252 : fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], 0, 0 ); /* do not change t */
188 252 : fd_bn254_fp12_mul( f, f, l );
189 :
190 252 : fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], 1, 1 );
191 252 : fd_bn254_fp12_mul( f, f, l );
192 252 : }
193 :
194 9984 : for( int i = 65-3; i>=0; i-- ) {
195 9828 : fd_bn254_fp12_sqr( f, f );
196 :
197 25704 : for( ulong j=0; j<sz; j++ ) {
198 15876 : fd_bn254_pairing_proj_dbl( l, &t[j], &p[j] );
199 15876 : fd_bn254_fp12_mul( f, f, l );
200 15876 : }
201 :
202 9828 : if( s[i] != 0 ) {
203 8160 : for( ulong j=0; j<sz; j++ ) {
204 5040 : fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], s[i] > 0, 1 );
205 5040 : fd_bn254_fp12_mul( f, f, l );
206 5040 : }
207 3120 : }
208 9828 : }
209 :
210 408 : for( ulong j=0; j<sz; j++ ) {
211 252 : fd_bn254_g2_frob( frob, &q[j] ); /* frob(q) */
212 252 : fd_bn254_pairing_proj_add_sub( l, &t[j], frob, &p[j], 1, 1 );
213 252 : fd_bn254_fp12_mul( f, f, l );
214 :
215 252 : fd_bn254_g2_frob2( frob, &q[j] ); /* -frob^2(q) */
216 252 : fd_bn254_g2_neg( frob, frob );
217 252 : fd_bn254_pairing_proj_add_sub( l, &t[j], frob, &p[j], 1, 0 ); /* do not change t */
218 252 : fd_bn254_fp12_mul( f, f, l );
219 252 : }
220 156 : return f;
221 156 : }
222 :
223 : fd_bn254_fp12_t *
224 : fd_bn254_fp12_pow_x( fd_bn254_fp12_t * restrict r,
225 792 : fd_bn254_fp12_t const * a ) {
226 : /* https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/internal/fptower/e12_pairing.go#L16 */
227 792 : fd_bn254_fp12_t t[7];
228 792 : fd_bn254_fp12_sqr_fast( &t[3], a );
229 792 : fd_bn254_fp12_sqr_fast( &t[5], &t[3] );
230 792 : fd_bn254_fp12_sqr_fast( r, &t[5] );
231 792 : fd_bn254_fp12_sqr_fast( &t[0], r );
232 792 : fd_bn254_fp12_mul ( &t[2], &t[0], a );
233 792 : fd_bn254_fp12_mul ( &t[0], &t[2], &t[3] );
234 792 : fd_bn254_fp12_mul ( &t[1], &t[0], a );
235 792 : fd_bn254_fp12_mul ( &t[4], &t[2], r );
236 792 : fd_bn254_fp12_sqr_fast( &t[6], &t[2] );
237 792 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[0] );
238 792 : fd_bn254_fp12_mul ( &t[0], &t[1], &t[3] );
239 5544 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[6], &t[6] );
240 792 : fd_bn254_fp12_mul ( &t[5], &t[5], &t[6] );
241 792 : fd_bn254_fp12_mul ( &t[5], &t[5], &t[4] );
242 6336 : for( int i=0; i<7; i++ ) fd_bn254_fp12_sqr_fast( &t[5], &t[5] );
243 792 : fd_bn254_fp12_mul ( &t[4], &t[4], &t[5] );
244 7128 : for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[4], &t[4] );
245 792 : fd_bn254_fp12_mul ( &t[4], &t[4], &t[0] );
246 792 : fd_bn254_fp12_mul ( &t[3], &t[3], &t[4] );
247 5544 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[3], &t[3] );
248 792 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[3] );
249 7128 : for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
250 792 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[0] );
251 5544 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
252 792 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[0] );
253 8712 : for( int i=0; i<10; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
254 792 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[2] );
255 5544 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[1], &t[1] );
256 792 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[1] );
257 792 : fd_bn254_fp12_mul ( r, r, &t[0] );
258 792 : return r;
259 792 : }
260 :
261 : fd_bn254_fp12_t *
262 : fd_bn254_final_exp( fd_bn254_fp12_t * r,
263 264 : fd_bn254_fp12_t * const x ) {
264 : /* https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/pairing.go#L62 */
265 264 : fd_bn254_fp12_t t[5], s[1];
266 264 : fd_bn254_fp12_conj ( &t[0], x ); /* x^(p^6) */
267 264 : fd_bn254_fp12_inv ( &t[1], x ); /* x^(-1) */
268 264 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[1] ); /* x^(p^6-1) */
269 264 : fd_bn254_fp12_frob2( &t[2], &t[0] ); /* x^(p^6-1)(p^2) */
270 264 : fd_bn254_fp12_mul ( s, &t[0], &t[2] ); /* x^(p^6-1)(p^2+1) */
271 : /* Fast chain, https://eprint.iacr.org/2015/192, Alg. 10.
272 : Variant of https://eprint.iacr.org/2010/354, Alg. 31. */
273 264 : fd_bn254_fp12_pow_x ( &t[0], s );
274 264 : fd_bn254_fp12_conj ( &t[0], &t[0] );
275 264 : fd_bn254_fp12_sqr_fast( &t[0], &t[0] );
276 264 : fd_bn254_fp12_sqr_fast( &t[1], &t[0] );
277 264 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[0] );
278 :
279 264 : fd_bn254_fp12_pow_x ( &t[2], &t[1] );
280 264 : fd_bn254_fp12_conj ( &t[2], &t[2] );
281 264 : fd_bn254_fp12_conj ( &t[3], &t[1] );
282 264 : fd_bn254_fp12_mul ( &t[1], &t[2], &t[3] );
283 :
284 264 : fd_bn254_fp12_sqr_fast( &t[3], &t[2] );
285 264 : fd_bn254_fp12_pow_x ( &t[4], &t[3] );
286 264 : fd_bn254_fp12_mul ( &t[4], &t[1], &t[4] );
287 264 : fd_bn254_fp12_mul ( &t[3], &t[0], &t[4] );
288 264 : fd_bn254_fp12_mul ( &t[0], &t[2], &t[4] );
289 264 : fd_bn254_fp12_mul ( &t[0], &t[0], s );
290 :
291 264 : fd_bn254_fp12_frob ( &t[2], &t[3] );
292 264 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[2] );
293 264 : fd_bn254_fp12_frob2 ( &t[2], &t[4] );
294 264 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[2] );
295 :
296 264 : fd_bn254_fp12_conj ( &t[2], s );
297 264 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[3] );
298 : // fd_bn254_fp12_frob3 ( &t[2], &t[2] );
299 264 : fd_bn254_fp12_frob2 ( &t[2], &t[2] );
300 264 : fd_bn254_fp12_frob ( &t[2], &t[2] );
301 264 : fd_bn254_fp12_mul ( r, &t[0], &t[2] );
302 264 : return r;
303 264 : }
|
