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