LCOV - code coverage report
Current view: top level - ballet/bn254 - fd_bn254_g2_check.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 114 133 85.7 %
Date: 2026-11-15 04:25:17 Functions: 4 4 100.0 %

          Line data    Source code
       1             : #include "./fd_bn254_g2_inl.h"
       2             : #include "./fd_bn254_glv.h"
       3             : 
       4             : /* G2 scalar mul and deserialization. */
       5             : 
       6             : /* fd_bn254_g2_scalar_mul computes r = [s]P.
       7             :    p must be in affine form (p->Z == 1).
       8             :    The result is in projective coordinates over Fp2. */
       9             : fd_bn254_g2_t *
      10             : fd_bn254_g2_scalar_mul( fd_bn254_g2_t *           r,
      11             :                         fd_bn254_g2_t const *     p,
      12        1524 :                         fd_bn254_scalar_t const * s ) {
      13        1524 :   if( FD_UNLIKELY( fd_uint256_is_zero( s ) || fd_bn254_g2_is_zero( p ) ) ) {
      14          18 :     return fd_bn254_g2_set_zero( r );
      15          18 :   }
      16             : 
      17        1506 :   ulong b1[ 3 ], b2[ 2 ];
      18        1506 :   fd_bn254_glv_sxg3( b1, s, g1_const_g2 );
      19        1506 :   fd_bn254_glv_sxg2( b2, s, g2_const );
      20             : 
      21             :   /* k1 = s - b1*N_C - b2*N_B (may be negative for G2) */
      22        1506 :   fd_uint256_t k1_abs[1];
      23        1506 :   int k1_neg = 0;
      24        1506 :   {
      25        1506 :     ulong p_nc[ 4 ];
      26             :     /* b2*nb will produce at most 3 limbs, so we want the 4th zeroed for the addition. */
      27        1506 :     ulong p_nb[ 4 ] = {0};
      28        1506 :     ulong    t[ 4 ];
      29        1506 :     fd_bn254_glv_mul3x2( p_nc, b1, nc );
      30        1506 :     fd_bn254_glv_mul2x1( p_nb, b2, nb );
      31        1506 :     fd_bn254_glv_add4( t, p_nc, p_nb );
      32        1506 :     ulong borrow = fd_bn254_glv_sub4( k1_abs->limbs, s->limbs, t );
      33        1506 :     if( borrow ) {
      34           0 :       k1_neg = 1;
      35           0 :       fd_bn254_glv_negate4( k1_abs->limbs );
      36           0 :     }
      37        1506 :   }
      38             : 
      39             :   /* k2 = b2*N_A - b1*N_B (usually negative for G2) */
      40        1506 :   fd_uint256_t k2_abs[1];
      41        1506 :   int k2_neg = 0;
      42        1506 :   {
      43        1506 :     ulong pos[ 4 ], neg[ 4 ];
      44        1506 :     fd_bn254_glv_mul2x2( pos, b2, na );
      45        1506 :     fd_bn254_glv_mul3x1( neg, b1, nb );
      46        1506 :     ulong borrow = fd_bn254_glv_sub4( k2_abs->limbs, pos, neg );
      47        1506 :     if( borrow ) {
      48         306 :       k2_neg = 1;
      49         306 :       fd_bn254_glv_negate4( k2_abs->limbs );
      50         306 :     }
      51        1506 :   }
      52             : 
      53             :   /* pt1 = P, pt2 = phi(P) = (beta * P.x, P.y).
      54             :      If k1 < 0, negate pt1. If k2 < 0, negate pt2. */
      55        1506 :   fd_bn254_g2_t pt1[1], pt2[1];
      56        1506 :   fd_bn254_g2_set( pt1, p );
      57        1506 :   fd_bn254_fp_mul( &pt2->X.el[0], &p->X.el[0], fd_bn254_const_beta_mont );
      58        1506 :   fd_bn254_fp_mul( &pt2->X.el[1], &p->X.el[1], fd_bn254_const_beta_mont );
      59        1506 :   fd_bn254_fp2_set( &pt2->Y, &p->Y );
      60        1506 :   fd_bn254_fp2_set_one( &pt2->Z );
      61        1506 :   if( k1_neg ) {
      62           0 :     fd_bn254_fp2_neg( &pt1->Y, &pt1->Y );
      63           0 :   }
      64        1506 :   if( k2_neg ) {
      65         306 :     fd_bn254_fp2_neg( &pt2->Y, &pt2->Y );
      66         306 :   }
      67             : 
      68        1506 :   fd_bn254_g2_t pt12[1];
      69        1506 :   fd_bn254_g2_affine_add( pt12, pt1, pt2 );
      70             : 
      71             :   /* Shamir's trick: simultaneous double-and-add on k1, k2. */
      72        1506 :   int i = 255;
      73      272952 :   for( ; i>=0; i-- ) {
      74      272952 :     int k1b = !!fd_uint256_bit( k1_abs, i );
      75      272952 :     int k2b = !!fd_uint256_bit( k2_abs, i );
      76      272952 :     if( k1b || k2b ) {
      77        1506 :       fd_bn254_g2_set( r, ( k1b && k2b ) ? pt12 : ( k1b ? pt1 : pt2 ) );
      78        1506 :       break;
      79        1506 :     }
      80      272952 :   }
      81        1506 :   if( FD_UNLIKELY( i<0 ) ) {
      82           0 :     return fd_bn254_g2_set_zero( r );
      83           0 :   }
      84      114090 :   for( i--; i >= 0; i-- ) {
      85      112584 :     fd_bn254_g2_dbl( r, r );
      86      112584 :     int k1b = !!fd_uint256_bit( k1_abs, i );
      87      112584 :     int k2b = !!fd_uint256_bit( k2_abs, i );
      88      112584 :     if( k1b && k2b ) {
      89        8874 :       fd_bn254_g2_add_mixed( r, r, pt12 );
      90      103710 :     } else if( k1b ) {
      91       41724 :       fd_bn254_g2_add_mixed( r, r, pt1 );
      92       61986 :     } else if( k2b ) {
      93        8262 :       fd_bn254_g2_add_mixed( r, r, pt2 );
      94        8262 :     }
      95      112584 :   }
      96             : 
      97        1506 :   return r;
      98        1506 : }
      99             : 
     100             : /* fd_bn254_g2_frombytes_internal extracts (x, y) and performs basic checks.
     101             :    This is used by fd_bn254_g2_compress() and fd_bn254_g2_frombytes_check_subgroup(). */
     102             : fd_bn254_g2_t *
     103             : fd_bn254_g2_frombytes_internal( fd_bn254_g2_t * p,
     104             :                                 uchar const     in[128],
     105       91368 :                                 int             big_endian ) {
     106             :   /* Special case: all zeros => point at infinity */
     107       91368 :   const uchar zero[128] = { 0 };
     108       91368 :   if( FD_UNLIKELY( fd_memeq( in, zero, 128 ) ) ) {
     109          39 :     return fd_bn254_g2_set_zero( p );
     110          39 :   }
     111             : 
     112             :   /* Check x < p */
     113       91329 :   if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->X, &in[0], big_endian, NULL, NULL ) ) ) {
     114           0 :     return NULL;
     115           0 :   }
     116             : 
     117             :   /* Check flags and y < p */
     118       91329 :   int is_inf, is_neg;
     119       91329 :   if( FD_UNLIKELY( !fd_bn254_fp2_frombytes_nm( &p->Y, &in[64], big_endian, &is_inf, &is_neg ) ) ) {
     120           0 :     return NULL;
     121           0 :   }
     122             : 
     123       91329 :   if( FD_UNLIKELY( is_inf ) ) {
     124           6 :     return fd_bn254_g2_set_zero( p );
     125           6 :   }
     126             : 
     127       91323 :   fd_bn254_fp2_set_one( &p->Z );
     128       91323 :   return p;
     129       91329 : }
     130             : 
     131             : /* fd_bn254_g2_frombytes_check_eq_only performs frombytes, checks the curve
     132             :    equation, but does NOT check subgroup membership. */
     133             : fd_bn254_g2_t *
     134             : fd_bn254_g2_frombytes_check_eq_only( fd_bn254_g2_t * p,
     135             :                                      uchar const     in[128],
     136       61266 :                                      int             big_endian ) {
     137       61266 :   if( FD_UNLIKELY( !fd_bn254_g2_frombytes_internal( p, in, big_endian ) ) ) {
     138           0 :     return NULL;
     139           0 :   }
     140       61266 :   if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
     141          36 :     return p;
     142          36 :   }
     143             : 
     144       61230 :   fd_bn254_fp2_to_mont( &p->X, &p->X );
     145       61230 :   fd_bn254_fp2_to_mont( &p->Y, &p->Y );
     146       61230 :   fd_bn254_fp2_set_one( &p->Z );
     147             : 
     148             :   /* Check that y^2 = x^3 + b */
     149       61230 :   fd_bn254_fp2_t y2[1], x3b[1];
     150       61230 :   fd_bn254_fp2_sqr( y2, &p->Y );
     151       61230 :   fd_bn254_fp2_sqr( x3b, &p->X );
     152       61230 :   fd_bn254_fp2_mul( x3b, x3b, &p->X );
     153       61230 :   fd_bn254_fp2_add( x3b, x3b, fd_bn254_const_twist_b_mont );
     154       61230 :   if( FD_UNLIKELY( !fd_bn254_fp2_eq( y2, x3b ) ) ) {
     155           0 :     return NULL;
     156           0 :   }
     157       61230 :   return p;
     158       61230 : }
     159             : 
     160             : /* fd_bn254_g2_frombytes_check_subgroup performs frombytes AND checks subgroup membership. */
     161             : fd_bn254_g2_t *
     162             : fd_bn254_g2_frombytes_check_subgroup( fd_bn254_g2_t * p,
     163             :                                       uchar const     in[128],
     164        1206 :                                       int             big_endian ) {
     165        1206 :   if( FD_UNLIKELY( fd_bn254_g2_frombytes_check_eq_only( p, in, big_endian )==NULL ) ) {
     166           0 :     return NULL;
     167           0 :   }
     168        1206 :   if( FD_UNLIKELY( fd_bn254_g2_is_zero( p ) ) ) {
     169          12 :     return p;
     170          12 :   }
     171             : 
     172             :   /* G2 does NOT have prime order, so we have to check group membership. */
     173             : 
     174             :   /* We use the fast subgroup membership check, that requires a single 64-bit scalar mul.
     175             :      https://eprint.iacr.org/2022/348, Sec 3.1.
     176             :      [r]P == 0 <==> [x+1]P + ψ([x]P) + ψ²([x]P) = ψ³([2x]P)
     177             :      See also: https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/g2.go#L404
     178             : 
     179             :      For reference, the following also work:
     180             : 
     181             :      1) very slow: 256-bit scalar mul
     182             : 
     183             :      fd_bn254_g2_t r[1];
     184             :      fd_bn254_g2_scalar_mul( r, p, fd_bn254_const_r );
     185             :      if( !fd_bn254_g2_is_zero( r ) ) return NULL;
     186             : 
     187             :      2) slow: 128-bit scalar mul
     188             : 
     189             :      fd_bn254_g2_t a[1], b[1];
     190             :      const fd_bn254_scalar_t six_x_sqr[1] = {{{ 0xf83e9682e87cfd46, 0x6f4d8248eeb859fb, 0x0, 0x0, }}};
     191             :      fd_bn254_g2_scalar_mul( a, p, six_x_sqr );
     192             :      fd_bn254_g2_frob( b, p );
     193             :      if( !fd_bn254_g2_eq( a, b ) ) return NULL; */
     194             : 
     195        1194 :   fd_bn254_g2_t xp[1], l[1], psi[1], r[1];
     196        1194 :   fd_bn254_g2_scalar_mul( xp, p, fd_bn254_const_x ); /* 64-bit */
     197        1194 :   fd_bn254_g2_add_mixed( l, xp, p );
     198             : 
     199             :   /* l will not be equal to psi unless p==0 */
     200        1194 :   fd_bn254_g2_frob( psi, xp );
     201        1194 :   fd_bn254_g2_add( l, l, psi );
     202             : 
     203        1194 :   fd_bn254_g2_frob2( psi, xp ); /* faster than frob( psi, psi ) */
     204        1194 :   fd_bn254_g2_add( l, l, psi );
     205             : 
     206        1194 :   fd_bn254_g2_frob( psi, psi );
     207        1194 :   fd_bn254_g2_dbl( r, psi );
     208        1194 :   if( FD_UNLIKELY( !fd_bn254_g2_eq( l, r ) ) ) {
     209           0 :     return NULL;
     210           0 :   }
     211        1194 :   return p;
     212        1194 : }

Generated by: LCOV version 1.14