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 56064 : 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 56064 : fd_bn254_fp2_t * X = &t->X;
14 56064 : fd_bn254_fp2_t * Y = &t->Y;
15 56064 : fd_bn254_fp2_t * Z = &t->Z;
16 56064 : fd_bn254_fp_t const * x = &p->X;
17 56064 : fd_bn254_fp_t const * y = &p->Y;
18 56064 : fd_bn254_fp2_t a[1], b[1], c[1], d[1];
19 56064 : fd_bn254_fp2_t e[1], f[1], g[1], h[1];
20 56064 : fd_bn254_fp_t x3[1];
21 : /* A=X1*Y1/2 */
22 56064 : fd_bn254_fp2_mul( a, X, Y );
23 56064 : fd_bn254_fp2_halve( a, a );
24 : /* B=Y1^2 */
25 56064 : fd_bn254_fp2_sqr( b, Y );
26 : /* C=Z1^2 */
27 56064 : fd_bn254_fp2_sqr( c, Z );
28 : /* D=3C */
29 56064 : fd_bn254_fp2_add( d, c, c );
30 56064 : fd_bn254_fp2_add( d, d, c );
31 : /* E=b'*D */
32 56064 : fd_bn254_fp2_mul( e, d, fd_bn254_const_twist_b_mont );
33 : /* F=3E */
34 56064 : fd_bn254_fp2_add( f, e, e );
35 56064 : fd_bn254_fp2_add( f, f, e );
36 : /* G=(B+F)/2 */
37 56064 : fd_bn254_fp2_add( g, b, f );
38 56064 : fd_bn254_fp2_halve( g, g );
39 : /* H =(Y1+Z1)^2 − (B+C) */
40 56064 : fd_bn254_fp2_add( h, Y, Z );
41 56064 : fd_bn254_fp2_sqr( h, h );
42 56064 : fd_bn254_fp2_sub( h, h, b );
43 56064 : 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 56064 : fd_bn254_fp2_neg( &r->el[0].el[0], h );
48 56064 : fd_bn254_fp_mul( &r->el[0].el[0].el[0], &r->el[0].el[0].el[0], y );
49 56064 : 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 56064 : fd_bn254_fp2_set_zero( &r->el[0].el[1] );
52 : /* el[0][2] = 0 */
53 56064 : fd_bn254_fp2_set_zero( &r->el[0].el[2] );
54 : /* el[1][0] = (3 * X^2 * x) */
55 56064 : fd_bn254_fp2_sqr( &r->el[1].el[0], X );
56 56064 : fd_bn254_fp_add( x3, x, x );
57 56064 : fd_bn254_fp_add( x3, x3, x );
58 56064 : fd_bn254_fp_mul( &r->el[1].el[0].el[0], &r->el[1].el[0].el[0], x3 );
59 56064 : 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 56064 : fd_bn254_fp2_sub( &r->el[1].el[1], e, b );
62 : /* el[1][2] = 0 */
63 56064 : fd_bn254_fp2_set_zero( &r->el[1].el[2] );
64 :
65 : /* update t */
66 : /* X3 = A * (B−F) */
67 56064 : fd_bn254_fp2_sub( X, b, f );
68 56064 : fd_bn254_fp2_mul( X, X, a );
69 : /* Y3 = G^2 − 3*E^2 (reusing var c, d) */
70 56064 : fd_bn254_fp2_sqr( Y, g );
71 56064 : fd_bn254_fp2_sqr( c, e );
72 56064 : fd_bn254_fp2_add( d, c, c );
73 56064 : fd_bn254_fp2_add( d, d, c );
74 56064 : fd_bn254_fp2_sub( Y, Y, d );
75 : /* Z3 = B * H */
76 56064 : fd_bn254_fp2_mul( Z, b, h );
77 56064 : }
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 21024 : 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 21024 : fd_bn254_fp2_t * X = &t->X;
91 21024 : fd_bn254_fp2_t * Y = &t->Y;
92 21024 : fd_bn254_fp2_t * Z = &t->Z;
93 21024 : fd_bn254_fp2_t const * X2 = &q->X;
94 21024 : fd_bn254_fp2_t Y2[1];
95 21024 : fd_bn254_fp_t const * x = &p->X;
96 21024 : fd_bn254_fp_t const * y = &p->Y;
97 21024 : fd_bn254_fp2_t a[1], b[1], c[1], d[1];
98 21024 : fd_bn254_fp2_t e[1], f[1], g[1], h[1];
99 21024 : fd_bn254_fp2_t i[1], j[1], k[1];
100 21024 : fd_bn254_fp2_t o[1], l[1];
101 :
102 21024 : if( is_add ) {
103 9636 : fd_bn254_fp2_set( Y2, &q->Y );
104 11388 : } else {
105 11388 : fd_bn254_fp2_neg( Y2, &q->Y );
106 11388 : }
107 :
108 21024 : fd_bn254_fp2_mul( a, Y2, Z );
109 21024 : fd_bn254_fp2_mul( b, X2, Z );
110 21024 : fd_bn254_fp2_sub( o, Y, a );
111 21024 : fd_bn254_fp2_sub( l, X, b );
112 :
113 21024 : fd_bn254_fp2_mul( j, o, X2 );
114 21024 : 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 21024 : fd_bn254_fp_mul( &r->el[0].el[0].el[0], &l->el[0], y );
120 21024 : fd_bn254_fp_mul( &r->el[0].el[0].el[1], &l->el[1], y );
121 : /* el[0][1] = 0 */
122 21024 : fd_bn254_fp2_set_zero( &r->el[0].el[1] );
123 : /* el[0][2] = 0 */
124 21024 : fd_bn254_fp2_set_zero( &r->el[0].el[2] );
125 : /* el[1][0] = -(o * x), term in w */
126 21024 : fd_bn254_fp2_neg( &r->el[1].el[0], o );
127 21024 : fd_bn254_fp_mul( &r->el[1].el[0].el[0], &r->el[1].el[0].el[0], x );
128 21024 : 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 21024 : fd_bn254_fp2_sub( &r->el[1].el[1], j, k );
131 : /* el[1][2] = 0 */
132 21024 : fd_bn254_fp2_set_zero( &r->el[1].el[2] );
133 :
134 21024 : if( add_point ) {
135 19272 : fd_bn254_fp2_sqr( c, o );
136 19272 : fd_bn254_fp2_sqr( d, l );
137 19272 : fd_bn254_fp2_mul( e, d, l );
138 19272 : fd_bn254_fp2_mul( f, Z, c );
139 19272 : fd_bn254_fp2_mul( g, X, d );
140 19272 : fd_bn254_fp2_add( h, e, f );
141 19272 : fd_bn254_fp2_sub( h, h, g );
142 19272 : fd_bn254_fp2_sub( h, h, g );
143 19272 : fd_bn254_fp2_mul( i, Y, e );
144 :
145 : /* update t */
146 19272 : fd_bn254_fp2_mul( X, l, h );
147 19272 : fd_bn254_fp2_sub( Y, g, h );
148 19272 : fd_bn254_fp2_mul( Y, Y, o );
149 19272 : fd_bn254_fp2_sub( Y, Y, i );
150 19272 : fd_bn254_fp2_mul( Z, Z, e );
151 19272 : }
152 21024 : }
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 387 : 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 387 : const schar s[] = {
162 387 : 0, 0, 0, 1, 0, 1, 0, -1,
163 387 : 0, 0, -1, 0, 0, 0, 1, 0,
164 387 : 0, -1, 0, -1, 0, 0, 0, 1,
165 387 : 0, -1, 0, 0, 0, 0, -1, 0,
166 387 : 0, 1, 0, -1, 0, 0, 1, 0,
167 387 : 0, 0, 0, 0, -1, 0, 0, -1,
168 387 : 0, 1, 0, -1, 0, 0, 0, -1,
169 387 : 0, -1, 0, 0, 0, 1, 0, -1, /* 0, 1 */
170 387 : };
171 :
172 387 : fd_bn254_g2_t t[FD_BN254_PAIRING_BATCH_MAX], frob[1];
173 387 : fd_bn254_fp12_t l[1];
174 :
175 387 : fd_bn254_fp12_set_one( f );
176 1263 : for ( ulong j=0; j<sz; j++ ) {
177 876 : fd_bn254_g2_set( &t[j], &q[j] );
178 876 : }
179 :
180 1263 : for( ulong j=0; j<sz; j++ ) {
181 876 : fd_bn254_pairing_proj_dbl( l, &t[j], &p[j] );
182 876 : fd_bn254_fp12_mul( f, f, l );
183 876 : }
184 387 : fd_bn254_fp12_sqr( f, f );
185 :
186 1263 : for( ulong j=0; j<sz; j++ ) {
187 876 : fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], 0, 0 ); /* do not change t */
188 876 : fd_bn254_fp12_mul( f, f, l );
189 :
190 876 : fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], 1, 1 );
191 876 : fd_bn254_fp12_mul( f, f, l );
192 876 : }
193 :
194 24768 : for( int i = 65-3; i>=0; i-- ) {
195 24381 : fd_bn254_fp12_sqr( f, f );
196 :
197 79569 : for( ulong j=0; j<sz; j++ ) {
198 55188 : fd_bn254_pairing_proj_dbl( l, &t[j], &p[j] );
199 55188 : fd_bn254_fp12_mul( f, f, l );
200 55188 : }
201 :
202 24381 : if( s[i] != 0 ) {
203 25260 : for( ulong j=0; j<sz; j++ ) {
204 17520 : fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], s[i] > 0, 1 );
205 17520 : fd_bn254_fp12_mul( f, f, l );
206 17520 : }
207 7740 : }
208 24381 : }
209 :
210 1263 : for( ulong j=0; j<sz; j++ ) {
211 876 : fd_bn254_g2_frob( frob, &q[j] ); /* frob(q) */
212 876 : fd_bn254_pairing_proj_add_sub( l, &t[j], frob, &p[j], 1, 1 );
213 876 : fd_bn254_fp12_mul( f, f, l );
214 :
215 876 : fd_bn254_g2_frob2( frob, &q[j] ); /* -frob^2(q) */
216 876 : fd_bn254_g2_neg( frob, frob );
217 876 : fd_bn254_pairing_proj_add_sub( l, &t[j], frob, &p[j], 1, 0 ); /* do not change t */
218 876 : fd_bn254_fp12_mul( f, f, l );
219 876 : }
220 387 : return f;
221 387 : }
222 :
223 : fd_bn254_fp12_t *
224 : fd_bn254_fp12_pow_x( fd_bn254_fp12_t * restrict r,
225 2070 : 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 2070 : fd_bn254_fp12_t t[7];
228 2070 : fd_bn254_fp12_sqr_fast( &t[3], a );
229 2070 : fd_bn254_fp12_sqr_fast( &t[5], &t[3] );
230 2070 : fd_bn254_fp12_sqr_fast( r, &t[5] );
231 2070 : fd_bn254_fp12_sqr_fast( &t[0], r );
232 2070 : fd_bn254_fp12_mul ( &t[2], &t[0], a );
233 2070 : fd_bn254_fp12_mul ( &t[0], &t[2], &t[3] );
234 2070 : fd_bn254_fp12_mul ( &t[1], &t[0], a );
235 2070 : fd_bn254_fp12_mul ( &t[4], &t[2], r );
236 2070 : fd_bn254_fp12_sqr_fast( &t[6], &t[2] );
237 2070 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[0] );
238 2070 : fd_bn254_fp12_mul ( &t[0], &t[1], &t[3] );
239 14490 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[6], &t[6] );
240 2070 : fd_bn254_fp12_mul ( &t[5], &t[5], &t[6] );
241 2070 : fd_bn254_fp12_mul ( &t[5], &t[5], &t[4] );
242 16560 : for( int i=0; i<7; i++ ) fd_bn254_fp12_sqr_fast( &t[5], &t[5] );
243 2070 : fd_bn254_fp12_mul ( &t[4], &t[4], &t[5] );
244 18630 : for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[4], &t[4] );
245 2070 : fd_bn254_fp12_mul ( &t[4], &t[4], &t[0] );
246 2070 : fd_bn254_fp12_mul ( &t[3], &t[3], &t[4] );
247 14490 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[3], &t[3] );
248 2070 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[3] );
249 18630 : for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
250 2070 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[0] );
251 14490 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
252 2070 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[0] );
253 22770 : for( int i=0; i<10; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
254 2070 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[2] );
255 14490 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[1], &t[1] );
256 2070 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[1] );
257 2070 : fd_bn254_fp12_mul ( r, r, &t[0] );
258 2070 : return r;
259 2070 : }
260 :
261 : fd_bn254_fp12_t *
262 : fd_bn254_final_exp( fd_bn254_fp12_t * r,
263 690 : fd_bn254_fp12_t * const x ) {
264 : /* https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/pairing.go#L62 */
265 690 : fd_bn254_fp12_t t[5], s[1];
266 690 : fd_bn254_fp12_conj ( &t[0], x ); /* x^(p^6) */
267 690 : fd_bn254_fp12_inv ( &t[1], x ); /* x^(-1) */
268 690 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[1] ); /* x^(p^6-1) */
269 690 : fd_bn254_fp12_frob2( &t[2], &t[0] ); /* x^(p^6-1)(p^2) */
270 690 : 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 690 : fd_bn254_fp12_pow_x ( &t[0], s );
274 690 : fd_bn254_fp12_conj ( &t[0], &t[0] );
275 690 : fd_bn254_fp12_sqr_fast( &t[0], &t[0] );
276 690 : fd_bn254_fp12_sqr_fast( &t[1], &t[0] );
277 690 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[0] );
278 :
279 690 : fd_bn254_fp12_pow_x ( &t[2], &t[1] );
280 690 : fd_bn254_fp12_conj ( &t[2], &t[2] );
281 690 : fd_bn254_fp12_conj ( &t[3], &t[1] );
282 690 : fd_bn254_fp12_mul ( &t[1], &t[2], &t[3] );
283 :
284 690 : fd_bn254_fp12_sqr_fast( &t[3], &t[2] );
285 690 : fd_bn254_fp12_pow_x ( &t[4], &t[3] );
286 690 : fd_bn254_fp12_mul ( &t[4], &t[1], &t[4] );
287 690 : fd_bn254_fp12_mul ( &t[3], &t[0], &t[4] );
288 690 : fd_bn254_fp12_mul ( &t[0], &t[2], &t[4] );
289 690 : fd_bn254_fp12_mul ( &t[0], &t[0], s );
290 :
291 690 : fd_bn254_fp12_frob ( &t[2], &t[3] );
292 690 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[2] );
293 690 : fd_bn254_fp12_frob2 ( &t[2], &t[4] );
294 690 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[2] );
295 :
296 690 : fd_bn254_fp12_conj ( &t[2], s );
297 690 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[3] );
298 : // fd_bn254_fp12_frob3 ( &t[2], &t[2] );
299 690 : fd_bn254_fp12_frob2 ( &t[2], &t[2] );
300 690 : fd_bn254_fp12_frob ( &t[2], &t[2] );
301 690 : fd_bn254_fp12_mul ( r, &t[0], &t[2] );
302 690 : return r;
303 690 : }
|
