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