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