Line data    Source code

       1             : #include "./fd_bn254_g2_inl.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_sparse( 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_sparse( 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_sparse( 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_sparse( 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_sparse( 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_sparse( 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_sparse( f, f, l );
     219         876 :   }
     220         387 :   return f;
     221         387 : }