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       23266 :                            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       23266 :   fd_bn254_fp2_t * X = &t->X;
      14       23266 :   fd_bn254_fp2_t * Y = &t->Y;
      15       23266 :   fd_bn254_fp2_t * Z = &t->Z;
      16       23266 :   fd_bn254_fp_t const * x = &p->X;
      17       23266 :   fd_bn254_fp_t const * y = &p->Y;
      18       23266 :   fd_bn254_fp2_t a[1], b[1], c[1], d[1];
      19       23266 :   fd_bn254_fp2_t e[1], f[1], g[1], h[1];
      20       23266 :   fd_bn254_fp_t x3[1];
      21             :   /* A=X1*Y1/2 */
      22       23266 :   fd_bn254_fp2_mul( a, X, Y );
      23       23266 :   fd_bn254_fp2_halve( a, a );
      24             :   /* B=Y1^2 */
      25       23266 :   fd_bn254_fp2_sqr( b, Y );
      26             :   /* C=Z1^2 */
      27       23266 :   fd_bn254_fp2_sqr( c, Z );
      28             :   /* D=3C */
      29       23266 :   fd_bn254_fp2_add( d, c, c );
      30       23266 :   fd_bn254_fp2_add( d, d, c );
      31             :   /* E=b'*D */
      32       23266 :   fd_bn254_fp2_mul( e, d, fd_bn254_const_twist_b_mont );
      33             :   /* F=3E */
      34       23266 :   fd_bn254_fp2_add( f, e, e );
      35       23266 :   fd_bn254_fp2_add( f, f, e );
      36             :   /* G=(B+F)/2 */
      37       23266 :   fd_bn254_fp2_add( g, b, f );
      38       23266 :   fd_bn254_fp2_halve( g, g );
      39             :   /* H =(Y1+Z1)^2 − (B+C) */
      40       23266 :   fd_bn254_fp2_add( h, Y, Z );
      41       23266 :   fd_bn254_fp2_sqr( h, h );
      42       23266 :   fd_bn254_fp2_sub( h, h, b );
      43       23266 :   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       23266 :   fd_bn254_fp2_neg( &r->el[0].el[0], h );
      48       23266 :   fd_bn254_fp_mul( &r->el[0].el[0].el[0], &r->el[0].el[0].el[0], y );
      49       23266 :   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       23266 :   fd_bn254_fp2_set_zero( &r->el[0].el[1] );
      52             :   /* el[0][2] = 0 */
      53       23266 :   fd_bn254_fp2_set_zero( &r->el[0].el[2] );
      54             :   /* el[1][0] = (3 * X^2 * x) */
      55       23266 :   fd_bn254_fp2_sqr( &r->el[1].el[0], X );
      56       23266 :   fd_bn254_fp_add( x3, x, x );
      57       23266 :   fd_bn254_fp_add( x3, x3, x );
      58       23266 :   fd_bn254_fp_mul( &r->el[1].el[0].el[0], &r->el[1].el[0].el[0], x3 );
      59       23266 :   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       23266 :   fd_bn254_fp2_sub( &r->el[1].el[1], e, b );
      62             :   /* el[1][2] = 0 */
      63       23266 :   fd_bn254_fp2_set_zero( &r->el[1].el[2] );
      64             : 
      65             :   /* update t */
      66             :   /* X3 = A * (B−F) */
      67       23266 :   fd_bn254_fp2_sub( X, b, f );
      68       23266 :   fd_bn254_fp2_mul( X, X, a );
      69             :   /* Y3 = G^2 − 3*E^2 (reusing var c, d) */
      70       23266 :   fd_bn254_fp2_sqr( Y, g );
      71       23266 :   fd_bn254_fp2_sqr( c, e );
      72       23266 :   fd_bn254_fp2_add( d, c, c );
      73       23266 :   fd_bn254_fp2_add( d, d, c );
      74       23266 :   fd_bn254_fp2_sub( Y, Y, d );
      75             :   /* Z3 = B * H */
      76       23266 :   fd_bn254_fp2_mul( Z, b, h );
      77       23266 : }
      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        8747 :                                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        8747 :   fd_bn254_fp2_t * X = &t->X;
      91        8747 :   fd_bn254_fp2_t * Y = &t->Y;
      92        8747 :   fd_bn254_fp2_t * Z = &t->Z;
      93        8747 :   fd_bn254_fp2_t const * X2 = &q->X;
      94        8747 :   fd_bn254_fp2_t Y2[1];
      95        8747 :   fd_bn254_fp_t const * x = &p->X;
      96        8747 :   fd_bn254_fp_t const * y = &p->Y;
      97        8747 :   fd_bn254_fp2_t a[1], b[1], c[1], d[1];
      98        8747 :   fd_bn254_fp2_t e[1], f[1], g[1], h[1];
      99        8747 :   fd_bn254_fp2_t i[1], j[1], k[1];
     100        8747 :   fd_bn254_fp2_t o[1], l[1];
     101             : 
     102        8747 :   if( is_add ) {
     103        4009 :     fd_bn254_fp2_set( Y2, &q->Y );
     104        4738 :   } else {
     105        4738 :     fd_bn254_fp2_neg( Y2, &q->Y );
     106        4738 :   }
     107             : 
     108        8747 :   fd_bn254_fp2_mul( a, Y2, Z );
     109        8747 :   fd_bn254_fp2_mul( b, X2, Z );
     110        8747 :   fd_bn254_fp2_sub( o, Y, a );
     111        8747 :   fd_bn254_fp2_sub( l, X, b );
     112             : 
     113        8747 :   fd_bn254_fp2_mul( j, o, X2 );
     114        8747 :   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        8747 :   fd_bn254_fp_mul( &r->el[0].el[0].el[0], &l->el[0], y );
     120        8747 :   fd_bn254_fp_mul( &r->el[0].el[0].el[1], &l->el[1], y );
     121             :   /* el[0][1] = 0 */
     122        8747 :   fd_bn254_fp2_set_zero( &r->el[0].el[1] );
     123             :   /* el[0][2] = 0 */
     124        8747 :   fd_bn254_fp2_set_zero( &r->el[0].el[2] );
     125             :   /* el[1][0] = -(o * x), term in w */
     126        8747 :   fd_bn254_fp2_neg( &r->el[1].el[0], o );
     127        8747 :   fd_bn254_fp_mul( &r->el[1].el[0].el[0], &r->el[1].el[0].el[0], x );
     128        8747 :   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        8747 :   fd_bn254_fp2_sub( &r->el[1].el[1], j, k );
     131             :   /* el[1][2] = 0 */
     132        8747 :   fd_bn254_fp2_set_zero( &r->el[1].el[2] );
     133             : 
     134        8747 :   if( add_point ) {
     135        8022 :     fd_bn254_fp2_sqr( c, o );
     136        8022 :     fd_bn254_fp2_sqr( d, l );
     137        8022 :     fd_bn254_fp2_mul( e, d, l );
     138        8022 :     fd_bn254_fp2_mul( f, Z, c );
     139        8022 :     fd_bn254_fp2_mul( g, X, d );
     140        8022 :     fd_bn254_fp2_add( h, e, f );
     141        8022 :     fd_bn254_fp2_sub( h, h, g );
     142        8022 :     fd_bn254_fp2_sub( h, h, g );
     143        8022 :     fd_bn254_fp2_mul( i, Y, e );
     144             : 
     145             :     /* update t */
     146        8022 :     fd_bn254_fp2_mul( X, l, h );
     147        8022 :     fd_bn254_fp2_sub( Y, g, h );
     148        8022 :     fd_bn254_fp2_mul( Y, Y, o );
     149        8022 :     fd_bn254_fp2_sub( Y, Y, i );
     150        8022 :     fd_bn254_fp2_mul( Z, Z, e );
     151        8022 :   }
     152        8747 : }
     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          94 :                       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          94 :   const schar s[] = {
     162          94 :     0,  0,  0,  1,  0,  1,  0, -1,
     163          94 :     0,  0, -1,  0,  0,  0,  1,  0,
     164          94 :     0, -1,  0, -1,  0,  0,  0,  1,
     165          94 :     0, -1,  0,  0,  0,  0, -1,  0,
     166          94 :     0,  1,  0, -1,  0,  0,  1,  0,
     167          94 :     0,  0,  0,  0, -1,  0,  0, -1,
     168          94 :     0,  1,  0, -1,  0,  0,  0, -1,
     169          94 :     0, -1,  0,  0,  0,  1,  0, -1, /* 0, 1 */
     170          94 :   };
     171             : 
     172          94 :   fd_bn254_g2_t t[FD_BN254_PAIRING_BATCH_MAX], frob[1];
     173          94 :   fd_bn254_fp12_t l[1];
     174             : 
     175          94 :   fd_bn254_fp12_set_one( f );
     176         459 :   for ( ulong j=0; j<sz; j++ ) {
     177         365 :     fd_bn254_g2_set( &t[j], &q[j] );
     178         365 :   }
     179             : 
     180         459 :   for( ulong j=0; j<sz; j++ ) {
     181         365 :     fd_bn254_pairing_proj_dbl( l, &t[j], &p[j] );
     182         365 :     fd_bn254_fp12_mul_sparse( f, f, l );
     183         365 :   }
     184          94 :   fd_bn254_fp12_sqr( f, f );
     185             : 
     186         459 :   for( ulong j=0; j<sz; j++ ) {
     187         365 :     fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], 0, 0 ); /* do not change t */
     188         365 :     fd_bn254_fp12_mul_sparse( f, f, l );
     189             : 
     190         365 :     fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], 1, 1 );
     191         365 :     fd_bn254_fp12_mul_sparse( f, f, l );
     192         365 :   }
     193             : 
     194        5993 :   for( int i = 65-3; i>=0; i-- ) {
     195        5899 :     fd_bn254_fp12_sqr( f, f );
     196             : 
     197       28803 :     for( ulong j=0; j<sz; j++ ) {
     198       22904 :       fd_bn254_pairing_proj_dbl( l, &t[j], &p[j] );
     199       22904 :       fd_bn254_fp12_mul_sparse( f, f, l );
     200       22904 :     }
     201             : 
     202        5899 :     if( s[i] != 0 ) {
     203        9169 :       for( ulong j=0; j<sz; j++ ) {
     204        7292 :         fd_bn254_pairing_proj_add_sub( l, &t[j], &q[j], &p[j], s[i] > 0, 1 );
     205        7292 :         fd_bn254_fp12_mul_sparse( f, f, l );
     206        7292 :       }
     207        1877 :     }
     208        5899 :   }
     209             : 
     210         459 :   for( ulong j=0; j<sz; j++ ) {
     211         365 :     fd_bn254_g2_frob( frob, &q[j] ); /* frob(q) */
     212         365 :     fd_bn254_pairing_proj_add_sub( l, &t[j], frob, &p[j], 1, 1 );
     213         365 :     fd_bn254_fp12_mul_sparse( f, f, l );
     214             : 
     215         365 :     fd_bn254_g2_frob2( frob, &q[j] ); /* -frob^2(q) */
     216         365 :     fd_bn254_g2_neg( frob, frob );
     217         365 :     fd_bn254_pairing_proj_add_sub( l, &t[j], frob, &p[j], 1, 0 ); /* do not change t */
     218         365 :     fd_bn254_fp12_mul_sparse( f, f, l );
     219         365 :   }
     220          94 :   return f;
     221          94 : }