Line data    Source code

       1             : #ifndef HEADER_fd_src_ballet_bn254_fd_bn254_scalar_h
       2             : #define HEADER_fd_src_ballet_bn254_fd_bn254_scalar_h
       3             : 
       4             : /* Implementation of the BN254 scalar field, based on fiat-crypto.
       5             : 
       6             :    This covers 2 main use cases:
       7             :    - scalar validation, used e.g. in BN254 point scalar mul
       8             :    - scalar arithmetic, used e.g. to compute Poseidon hash
       9             : 
      10             :    The primary consumer is Firedancer VM (Solana syscalls).
      11             :    Therefore, input is little endian and already aligned. */
      12             : 
      13             : #include "../fd_ballet_base.h"
      14             : #include "../bigint/fd_uint256.h"
      15             : #include "../../third_party/fiat-crypto/bn254_scalar_64.c"
      16             : 
      17             : /* The implementation is based on fiat-crypto.
      18             :    Unfortunately mul is dramatically slow on gcc, so we reimplemented
      19             :    it in ballet/bigint/uint256_mul.h, based on uint128.
      20             :    When uint128 is not available we fall back on fiat-crypto. */
      21             : #define USE_FIAT_CRYPTO_MUL !FD_HAS_INT128
      22             : 
      23             : /* fd_bn254_scalar represents a scalar as a buffer of 32 bytes,
      24             :    or equivalently (on little endian platforms) an array of 4 ulong. */
      25             : typedef fd_uint256_t fd_bn254_scalar_t;
      26             : 
      27             : /* const r, used to validate a scalar field element.
      28             :    NOT Montgomery.
      29             :    0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001 */
      30             : static const fd_bn254_scalar_t fd_bn254_const_r[1] = {{{
      31             :   0x43e1f593f0000001, 0x2833e84879b97091, 0xb85045b68181585d, 0x30644e72e131a029,
      32             : }}};
      33             : 
      34             : /* const 1/r for CIOS mul */
      35             : static const ulong fd_bn254_const_r_inv = 0xC2E1F593EFFFFFFFUL;
      36             : 
      37             : FD_PROTOTYPES_BEGIN
      38             : 
      39             : /* fd_bn254_scalar_validate validates that the input scalar s
      40             :    is between 0 and r-1, included.
      41             :    This function works on 32-byte input buffer with no memory
      42             :    copies (assuming both platform and input are little endian). */
      43             : static inline int
      44       75531 : fd_bn254_scalar_validate( fd_bn254_scalar_t const * s ) {
      45       75531 :   return fd_uint256_cmp( s, fd_bn254_const_r ) < 0;
      46       75531 : }
      47             : 
      48             : static inline fd_bn254_scalar_t *
      49             : fd_bn254_scalar_add( fd_bn254_scalar_t *       r,
      50             :                      fd_bn254_scalar_t const * a,
      51    17521440 :                      fd_bn254_scalar_t const * b ) {
      52    17521440 :   fiat_bn254_scalar_add( r->limbs, a->limbs, b->limbs );
      53    17521440 :   return r;
      54    17521440 : }
      55             : 
      56             : #if USE_FIAT_CRYPTO_MUL
      57             : 
      58             : static inline fd_bn254_scalar_t *
      59             : fd_bn254_scalar_mul( fd_bn254_scalar_t *       r,
      60             :                      fd_bn254_scalar_t const * a,
      61             :                      fd_bn254_scalar_t const * b ) {
      62             :   fiat_bn254_scalar_mul( r->limbs, a->limbs, b->limbs );
      63             :   return r;
      64             : }
      65             : 
      66             : static inline fd_bn254_scalar_t *
      67             : fd_bn254_scalar_sqr( fd_bn254_scalar_t *       r,
      68             :                      fd_bn254_scalar_t const * a ) {
      69             :   fiat_bn254_scalar_square( r->limbs, a->limbs );
      70             :   return r;
      71             : }
      72             : 
      73             : static inline fd_bn254_scalar_t *
      74             : fd_bn254_scalar_from_mont( fd_bn254_scalar_t *       r,
      75             :                            fd_bn254_scalar_t const * a ) {
      76             :   fiat_bn254_scalar_from_montgomery( r->limbs, a->limbs );
      77             :   return r;
      78             : }
      79             : 
      80             : static inline fd_bn254_scalar_t *
      81             : fd_bn254_scalar_to_mont( fd_bn254_scalar_t *       r,
      82             :                          fd_bn254_scalar_t const * a ) {
      83             :   fiat_bn254_scalar_to_montgomery( r->limbs, a->limbs );
      84             :   return r;
      85             : }
      86             : 
      87             : #else
      88             : 
      89             : FD_UINT256_FP_MUL_IMPL(fd_bn254_scalar, fd_bn254_const_r, fd_bn254_const_r_inv)
      90             : 
      91             : static inline fd_bn254_scalar_t *
      92             : fd_bn254_scalar_sqr( fd_bn254_scalar_t *       r,
      93     3267168 :                      fd_bn254_scalar_t const * a ) {
      94     3267168 :   return fd_bn254_scalar_mul( r, a, a );
      95     3267168 : }
      96             : 
      97             : /* Montgomery conversions via scalar_mul rather than fiat's
      98             :    from/to_montgomery (their literal limbs are slow to compile). */
      99             : 
     100             : /* const 1. NOT Montgomery. mul(a, 1) = a*R^-1 = from_mont(a). */
     101             : static const fd_bn254_scalar_t fd_bn254_scalar_const_one[1] = {{{
     102             :   0x1UL, 0x0UL, 0x0UL, 0x0UL,
     103             : }}};
     104             : 
     105             : /* const R^2 mod r, R=2^256. mul(a, R^2) = a*R = to_mont(a).
     106             :    0x0216d0b17f4e44a58c49833d53bb808553fe3ab1e35c59e31bb8e645ae216da7 */
     107             : static const fd_bn254_scalar_t fd_bn254_scalar_const_rr[1] = {{{
     108             :   0x1bb8e645ae216da7, 0x53fe3ab1e35c59e3, 0x8c49833d53bb8085, 0x0216d0b17f4e44a5,
     109             : }}};
     110             : 
     111             : static inline fd_bn254_scalar_t *
     112             : fd_bn254_scalar_from_mont( fd_bn254_scalar_t *       r,
     113       15093 :                            fd_bn254_scalar_t const * a ) {
     114       15093 :   return fd_bn254_scalar_mul( r, a, fd_bn254_scalar_const_one );
     115       15093 : }
     116             : 
     117             : static inline fd_bn254_scalar_t *
     118             : fd_bn254_scalar_to_mont( fd_bn254_scalar_t *       r,
     119       75531 :                          fd_bn254_scalar_t const * a ) {
     120       75531 :   return fd_bn254_scalar_mul( r, a, fd_bn254_scalar_const_rr );
     121       75531 : }
     122             : 
     123             : #endif
     124             : 
     125             : FD_PROTOTYPES_END
     126             : 
     127             : #endif /* HEADER_fd_src_ballet_bn254_fd_bn254_scalar_h */