soroban_sdk/crypto/
bn254.rs

1#[cfg(not(target_family = "wasm"))]
2use crate::xdr::ScVal;
3use crate::{
4    crypto::utils::BigInt,
5    env::internal::{self, BytesObject, U256Val},
6    impl_bytesn_repr_without_from_bytes,
7    unwrap::{UnwrapInfallible, UnwrapOptimized},
8    Bytes, BytesN, ConversionError, Env, IntoVal, TryFromVal, Val, Vec, U256,
9};
10use core::{
11    cmp::Ordering,
12    fmt::Debug,
13    ops::{Add, Mul, Neg},
14};
15
16pub const BN254_FP_SERIALIZED_SIZE: usize = 32; // Size in bytes of a serialized Bn254Fp element in BN254. The field modulus is 254 bits, requiring 32 bytes (256 bits).
17pub const BN254_G1_SERIALIZED_SIZE: usize = BN254_FP_SERIALIZED_SIZE * 2; // Size in bytes of a serialized G1 element in BN254. Each coordinate (X, Y) is 32 bytes.
18pub const BN254_G2_SERIALIZED_SIZE: usize = BN254_G1_SERIALIZED_SIZE * 2; // Size in bytes of a serialized G2 element in BN254. Each coordinate (X, Y) is 64 bytes (2 Bn254Fp elements per coordinate).
19
20/// Bn254 provides access to curve and pairing operations on the BN254
21/// (also known as alt_bn128) curve.
22pub struct Bn254 {
23    env: Env,
24}
25
26/// `Bn254G1Affine` is a point in the G1 group (subgroup defined over the base field
27/// `Fq` with prime order `q =
28/// 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47`) of the
29/// BN254 elliptic curve
30///
31/// # Serialization (Ethereum-compatible format):
32/// - The 64 bytes represent the **uncompressed encoding** of a point in G1
33/// - Format: `be_bytes(X) || be_bytes(Y)` where `||` denotes concatenation
34/// - X and Y are curve coordinates, each a 32-byte big-endian Bn254Fp field element
35/// - The two flag bits (bits 0x80 and 0x40 of the first byte) must be unset
36/// - The point at infinity is encoded as 64 zero bytes
37/// - Points must be on the curve (no subgroup check required for G1)
38#[derive(Clone)]
39#[repr(transparent)]
40pub struct Bn254G1Affine(BytesN<BN254_G1_SERIALIZED_SIZE>);
41
42/// `Bn254G2Affine` is a point in the G2 group (subgroup defined over the quadratic
43/// extension field `Fq2`) of the BN254 elliptic curve
44///
45/// # Serialization (Ethereum-compatible format):
46/// - The 128 bytes represent the **uncompressed encoding** of a point in G2
47/// - Format: `be_bytes(X) || be_bytes(Y)` where each coordinate is an Fp2
48/// element (64 bytes) - Fp2 element encoding: `be_bytes(c1) || be_bytes(c0)`
49/// where:
50///   - c0 is the real component (32-byte big-endian Bn254Fp element)
51///   - c1 is the imaginary component (32-byte big-endian Bn254Fp element)
52/// - The two flag bits (bits 0x80 and 0x40 of the first byte) must be unset
53/// - The point at infinity is encoded as 128 zero bytes
54/// - Points must be on the curve AND in the correct subgroup
55#[derive(Clone)]
56#[repr(transparent)]
57pub struct Bn254G2Affine(BytesN<BN254_G2_SERIALIZED_SIZE>);
58
59/// `Fr` represents an element in the BN254 scalar field, which is a prime field
60/// of order `r =
61/// 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001`. The
62/// struct is internally represented with a `U256`, all arithmetic operations
63/// follow modulo `r`.
64#[derive(Clone)]
65#[repr(transparent)]
66pub struct Fr(U256);
67
68/// `Bn254Fp` represents an element of the base field `Bn254Fp` of the BN254 elliptic curve
69///
70/// # Serialization:
71/// - The 32 bytes represent the **big-endian encoding** of an element in the
72///   field `Bn254Fp`. The value is serialized as a big-endian integer.
73#[derive(Clone)]
74#[repr(transparent)]
75pub struct Bn254Fp(BytesN<BN254_FP_SERIALIZED_SIZE>);
76
77impl_bytesn_repr_without_from_bytes!(Bn254G1Affine, BN254_G1_SERIALIZED_SIZE);
78impl_bytesn_repr_without_from_bytes!(Bn254G2Affine, BN254_G2_SERIALIZED_SIZE);
79impl_bytesn_repr_without_from_bytes!(Bn254Fp, BN254_FP_SERIALIZED_SIZE);
80
81// BN254 base field modulus p in big-endian bytes.
82// p = 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47
83const BN254_FP_MODULUS_BE: [u8; BN254_FP_SERIALIZED_SIZE] = [
84    0x30, 0x64, 0x4e, 0x72, 0xe1, 0x31, 0xa0, 0x29, 0xb8, 0x50, 0x45, 0xb6, 0x81, 0x81, 0x58, 0x5d,
85    0x97, 0x81, 0x6a, 0x91, 0x68, 0x71, 0xca, 0x8d, 0x3c, 0x20, 0x8c, 0x16, 0xd8, 0x7c, 0xfd, 0x47,
86];
87
88fn validate_bn254_fp(bytes: &[u8; BN254_FP_SERIALIZED_SIZE]) {
89    if bytes >= &BN254_FP_MODULUS_BE {
90        sdk_panic!("Bn254: Invalid Fp");
91    }
92}
93
94impl Bn254G1Affine {
95    pub fn from_bytes(bytes: BytesN<BN254_G1_SERIALIZED_SIZE>) -> Self {
96        Self(bytes)
97    }
98}
99
100impl Bn254G2Affine {
101    pub fn from_bytes(bytes: BytesN<BN254_G2_SERIALIZED_SIZE>) -> Self {
102        Self(bytes)
103    }
104}
105
106impl Bn254Fp {
107    pub fn from_bytes(bytes: BytesN<BN254_FP_SERIALIZED_SIZE>) -> Self {
108        validate_bn254_fp(&bytes.to_array());
109        Self(bytes)
110    }
111}
112
113impl Bn254G1Affine {
114    pub fn env(&self) -> &Env {
115        self.0.env()
116    }
117}
118
119impl Bn254Fp {
120    pub fn env(&self) -> &Env {
121        self.0.env()
122    }
123
124    // `Bn254Fp` represents an element in the base field of the BN254 elliptic curve.
125    // For an element a ∈ Bn254Fp, its negation `-a` is defined as:
126    //   a + (-a) = 0 (mod p)
127    // where `p` is the field modulus, and to make a valid point coordinate on the
128    // curve, `a` also must be within the field range (i.e., 0 ≤ a < p).
129    fn checked_neg(&self) -> Option<Bn254Fp> {
130        let fq_bigint: BigInt<4> = (&self.0).into();
131        if fq_bigint.is_zero() {
132            return Some(self.clone());
133        }
134
135        //BN254 base field modulus
136        const BN254_MODULUS: [u64; 4] = [
137            4332616871279656263,
138            10917124144477883021,
139            13281191951274694749,
140            3486998266802970665,
141        ];
142        let mut res = BigInt(BN254_MODULUS);
143
144        // Compute modulus - value
145        let borrow = res.sub_with_borrow(&fq_bigint);
146        if borrow {
147            return None;
148        }
149
150        let mut bytes = [0u8; BN254_FP_SERIALIZED_SIZE];
151        res.copy_into_array(&mut bytes);
152        Some(Bn254Fp::from_array(self.env(), &bytes))
153    }
154}
155
156impl Neg for &Bn254Fp {
157    type Output = Bn254Fp;
158
159    fn neg(self) -> Self::Output {
160        match self.checked_neg() {
161            Some(v) => v,
162            None => sdk_panic!("invalid input - Bn254Fp is larger than the field modulus"),
163        }
164    }
165}
166
167impl Neg for Bn254Fp {
168    type Output = Bn254Fp;
169
170    fn neg(self) -> Self::Output {
171        (&self).neg()
172    }
173}
174
175impl Add for Bn254G1Affine {
176    type Output = Bn254G1Affine;
177
178    fn add(self, rhs: Self) -> Self::Output {
179        self.env().crypto().bn254().g1_add(&self, &rhs)
180    }
181}
182
183impl Mul<Fr> for Bn254G1Affine {
184    type Output = Bn254G1Affine;
185
186    fn mul(self, rhs: Fr) -> Self::Output {
187        self.env().crypto().bn254().g1_mul(&self, &rhs)
188    }
189}
190
191// Bn254G1Affine represents a point (X, Y) on the BN254 curve where X, Y ∈ Fr
192// Negation of (X, Y) is defined as (X, -Y)
193impl Neg for &Bn254G1Affine {
194    type Output = Bn254G1Affine;
195
196    fn neg(self) -> Self::Output {
197        let mut inner: Bytes = (&self.0).into();
198        let y = Bn254Fp::try_from_val(
199            inner.env(),
200            inner.slice(BN254_FP_SERIALIZED_SIZE as u32..).as_val(),
201        )
202        .unwrap_optimized();
203        let neg_y = -y;
204        inner.copy_from_slice(BN254_FP_SERIALIZED_SIZE as u32, &neg_y.to_array());
205        Bn254G1Affine::from_bytes(
206            BytesN::try_from_val(inner.env(), inner.as_val()).unwrap_optimized(),
207        )
208    }
209}
210
211impl Neg for Bn254G1Affine {
212    type Output = Bn254G1Affine;
213
214    fn neg(self) -> Self::Output {
215        (&self).neg()
216    }
217}
218
219impl Bn254G2Affine {
220    pub fn env(&self) -> &Env {
221        self.0.env()
222    }
223}
224
225impl Fr {
226    pub fn env(&self) -> &Env {
227        self.0.env()
228    }
229
230    pub fn from_u256(value: U256) -> Self {
231        value.into()
232    }
233
234    pub fn to_u256(&self) -> U256 {
235        self.0.clone()
236    }
237
238    pub fn as_u256(&self) -> &U256 {
239        &self.0
240    }
241
242    pub fn from_bytes(bytes: BytesN<32>) -> Self {
243        U256::from_be_bytes(bytes.env(), bytes.as_ref()).into()
244    }
245
246    pub fn to_bytes(&self) -> BytesN<32> {
247        self.as_u256().to_be_bytes().try_into().unwrap_optimized()
248    }
249
250    pub fn as_val(&self) -> &Val {
251        self.0.as_val()
252    }
253
254    pub fn to_val(&self) -> Val {
255        self.0.to_val()
256    }
257}
258
259// BN254 scalar field modulus r in big-endian bytes.
260// r = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
261const BN254_FR_MODULUS_BE: [u8; 32] = [
262    0x30, 0x64, 0x4e, 0x72, 0xe1, 0x31, 0xa0, 0x29, 0xb8, 0x50, 0x45, 0xb6, 0x81, 0x81, 0x58, 0x5d,
263    0x28, 0x33, 0xe8, 0x48, 0x79, 0xb9, 0x70, 0x91, 0x43, 0xe1, 0xf5, 0x93, 0xf0, 0x00, 0x00, 0x01,
264];
265
266fn fr_modulus(env: &Env) -> U256 {
267    U256::from_be_bytes(env, &Bytes::from_array(env, &BN254_FR_MODULUS_BE))
268}
269
270impl From<U256> for Fr {
271    fn from(value: U256) -> Self {
272        // Keep all Fr construction paths canonical by reducing modulo r here.
273        // Constructors and deserialization paths should route through this impl.
274        // Skip the expensive rem_euclid when value is already canonical (< r),
275        // which is always the case for host-returned arithmetic results.
276        let modulus = fr_modulus(value.env());
277        if value >= modulus {
278            Self(value.rem_euclid(&modulus))
279        } else {
280            Self(value)
281        }
282    }
283}
284
285impl From<&Fr> for U256Val {
286    fn from(value: &Fr) -> Self {
287        value.as_u256().into()
288    }
289}
290
291impl TryFromVal<Env, Val> for Fr {
292    type Error = ConversionError;
293
294    fn try_from_val(env: &Env, val: &Val) -> Result<Self, Self::Error> {
295        let u = U256::try_from_val(env, val)?;
296        Ok(u.into())
297    }
298}
299
300impl TryFromVal<Env, Fr> for Val {
301    type Error = ConversionError;
302
303    fn try_from_val(_env: &Env, fr: &Fr) -> Result<Self, Self::Error> {
304        Ok(fr.to_val())
305    }
306}
307
308impl TryFromVal<Env, &Fr> for Val {
309    type Error = ConversionError;
310
311    fn try_from_val(_env: &Env, fr: &&Fr) -> Result<Self, Self::Error> {
312        Ok(fr.to_val())
313    }
314}
315
316#[cfg(not(target_family = "wasm"))]
317impl From<&Fr> for ScVal {
318    fn from(v: &Fr) -> Self {
319        Self::from(&v.0)
320    }
321}
322
323#[cfg(not(target_family = "wasm"))]
324impl From<Fr> for ScVal {
325    fn from(v: Fr) -> Self {
326        (&v).into()
327    }
328}
329
330impl Eq for Fr {}
331
332impl PartialEq for Fr {
333    fn eq(&self, other: &Self) -> bool {
334        self.as_u256().partial_cmp(other.as_u256()) == Some(core::cmp::Ordering::Equal)
335    }
336}
337
338impl Debug for Fr {
339    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
340        write!(f, "Fr({:?})", self.as_u256())
341    }
342}
343
344impl Bn254 {
345    pub(crate) fn new(env: &Env) -> Bn254 {
346        Bn254 { env: env.clone() }
347    }
348
349    pub fn env(&self) -> &Env {
350        &self.env
351    }
352
353    /// Adds two points `p0` and `p1` in G1.
354    pub fn g1_add(&self, p0: &Bn254G1Affine, p1: &Bn254G1Affine) -> Bn254G1Affine {
355        let env = self.env();
356        let bin =
357            internal::Env::bn254_g1_add(env, p0.to_object(), p1.to_object()).unwrap_infallible();
358        unsafe { Bn254G1Affine::from_bytes(BytesN::unchecked_new(env.clone(), bin)) }
359    }
360
361    /// Multiplies a point `p0` in G1 by a scalar.
362    pub fn g1_mul(&self, p0: &Bn254G1Affine, scalar: &Fr) -> Bn254G1Affine {
363        let env = self.env();
364        let bin =
365            internal::Env::bn254_g1_mul(env, p0.to_object(), scalar.into()).unwrap_infallible();
366        unsafe { Bn254G1Affine::from_bytes(BytesN::unchecked_new(env.clone(), bin)) }
367    }
368
369    // pairing
370
371    /// Performs a multi-pairing check between vectors of points in G1 and G2.
372    ///
373    /// This function computes the pairing for each pair of points in the
374    /// provided vectors `vp1` (G1 points) and `vp2` (G2 points) and verifies if
375    /// the product of all pairings is equal to 1 in the target group Bn254Fp.
376    ///
377    /// # Returns:
378    /// - `true` if the pairing check holds (i.e., the product of pairings equals 1),
379    ///   otherwise `false`.
380    ///
381    /// # Panics:
382    /// - If the lengths of `vp1` and `vp2` are not equal or if they are empty.
383    pub fn pairing_check(&self, vp1: Vec<Bn254G1Affine>, vp2: Vec<Bn254G2Affine>) -> bool {
384        let env = self.env();
385        internal::Env::bn254_multi_pairing_check(env, vp1.into(), vp2.into())
386            .unwrap_infallible()
387            .into()
388    }
389}
390
391#[cfg(test)]
392mod test {
393    use super::*;
394    use crate::bytesn;
395
396    #[test]
397    fn test_g1affine_to_val() {
398        let env = Env::default();
399
400        let g1 = Bn254G1Affine::from_bytes(BytesN::from_array(&env, &[1; 64]));
401        let val: Val = g1.clone().into_val(&env);
402        let rt: Bn254G1Affine = val.into_val(&env);
403
404        assert_eq!(g1, rt);
405    }
406
407    #[test]
408    fn test_ref_g1affine_to_val() {
409        let env = Env::default();
410
411        let g1 = Bn254G1Affine::from_bytes(BytesN::from_array(&env, &[1; 64]));
412        let val: Val = (&g1).into_val(&env);
413        let rt: Bn254G1Affine = val.into_val(&env);
414
415        assert_eq!(g1, rt);
416    }
417
418    #[test]
419    fn test_double_ref_g1affine_to_val() {
420        let env = Env::default();
421
422        let g1 = Bn254G1Affine::from_bytes(BytesN::from_array(&env, &[1; 64]));
423        let val: Val = (&&g1).into_val(&env);
424        let rt: Bn254G1Affine = val.into_val(&env);
425
426        assert_eq!(g1, rt);
427    }
428
429    #[test]
430    fn test_fr_to_val() {
431        let env = Env::default();
432
433        let fr = Fr::from_bytes(BytesN::from_array(&env, &[1; 32]));
434        let val: Val = fr.clone().into_val(&env);
435        let rt: Fr = val.into_val(&env);
436
437        assert_eq!(fr, rt);
438    }
439
440    #[test]
441    fn test_ref_fr_to_val() {
442        let env = Env::default();
443
444        let fr = Fr::from_bytes(BytesN::from_array(&env, &[1; 32]));
445        let val: Val = (&fr).into_val(&env);
446        let rt: Fr = val.into_val(&env);
447
448        assert_eq!(fr, rt);
449    }
450
451    #[test]
452    fn test_double_ref_fr_to_val() {
453        let env = Env::default();
454
455        let fr = Fr::from_bytes(BytesN::from_array(&env, &[1; 32]));
456        let val: Val = (&&fr).into_val(&env);
457        let rt: Fr = val.into_val(&env);
458
459        assert_eq!(fr, rt);
460    }
461
462    #[test]
463    fn test_fr_eq_both_unreduced() {
464        // Both inputs are user-provided unreduced values representing the same field element
465        let env = Env::default();
466        let r = fr_modulus(&env);
467        let one = U256::from_u32(&env, 1);
468
469        let a = Fr::from_u256(r.add(&one)); // r+1 ≡ 1 (mod r)
470        let b = Fr::from_u256(one.clone()); // 1
471        assert_eq!(a, b);
472
473        // Both unreduced by different multiples of r
474        let two_r_plus_one = r.add(&r).add(&one);
475        let c = Fr::from_u256(two_r_plus_one); // 2r+1 ≡ 1 (mod r)
476        assert_eq!(a, c);
477        assert_eq!(b, c);
478    }
479
480    #[test]
481    fn test_fr_eq_unreduced_vs_zero() {
482        // value == r should reduce to 0
483        let env = Env::default();
484        let r = fr_modulus(&env);
485        let zero = U256::from_u32(&env, 0);
486
487        let a = Fr::from_u256(r);
488        let b = Fr::from_u256(zero);
489        assert_eq!(a, b);
490    }
491
492    #[test]
493    fn test_fr_reduced_value_unchanged() {
494        // value < r should be preserved as-is
495        let env = Env::default();
496        let r = fr_modulus(&env);
497        let val = r.sub(&U256::from_u32(&env, 1)); // r-1
498
499        let fr = Fr::from_u256(val.clone());
500        assert_eq!(fr.to_u256(), val);
501
502        // small values
503        let fr42 = Fr::from_u256(U256::from_u32(&env, 42));
504        assert_eq!(fr42.to_u256(), U256::from_u32(&env, 42));
505    }
506
507    #[test]
508    fn test_fr_from_bytes_reduces() {
509        // from_bytes should also reduce since it goes through From<U256>
510        let env = Env::default();
511        let one_fr = Fr::from_u256(U256::from_u32(&env, 1));
512
513        // BN254 r+1 as big-endian bytes
514        let fr_from_bytes = Fr::from_bytes(bytesn!(
515            &env,
516            0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000002
517        ));
518        assert_eq!(fr_from_bytes, one_fr);
519    }
520
521    #[test]
522    fn test_fr_try_from_val_reduces() {
523        // TryFromVal<Env, Val> path must also reduce
524        let env = Env::default();
525        let r = fr_modulus(&env);
526        let one = U256::from_u32(&env, 1);
527
528        // Create an unreduced U256 value (r+1), convert to Val, then to Fr
529        let unreduced_u256 = r.add(&one);
530        let val: Val = unreduced_u256.into_val(&env);
531        let fr_from_val: Fr = val.into_val(&env);
532        let fr_one = Fr::from_u256(one);
533        assert_eq!(fr_from_val, fr_one);
534    }
535
536    #[test]
537    fn test_fr_u256_into_reduces() {
538        // Direct From<U256>::from / .into() path must reduce
539        let env = Env::default();
540        let r = fr_modulus(&env);
541        let one = U256::from_u32(&env, 1);
542
543        let fr: Fr = r.add(&one).into(); // r+1 via .into()
544        let fr_one: Fr = one.into();
545        assert_eq!(fr, fr_one);
546    }
547
548    // Bn254Fp validation tests
549
550    #[test]
551    fn test_bn254_fp_max_valid_accepted() {
552        let env = Env::default();
553        // p - 1 (last byte 0x46 instead of 0x47)
554        let mut p_minus_1 = BN254_FP_MODULUS_BE;
555        p_minus_1[BN254_FP_SERIALIZED_SIZE - 1] -= 1;
556        let _ = Bn254Fp::from_array(&env, &p_minus_1);
557    }
558
559    #[test]
560    #[should_panic(expected = "Bn254: Invalid Fp")]
561    fn test_bn254_fp_at_modulus_panics() {
562        let env = Env::default();
563        let _ = Bn254Fp::from_array(&env, &BN254_FP_MODULUS_BE);
564    }
565
566    #[test]
567    #[should_panic(expected = "Bn254: Invalid Fp")]
568    fn test_bn254_fp_above_modulus_panics() {
569        let env = Env::default();
570        let mut above = BN254_FP_MODULUS_BE;
571        above[BN254_FP_SERIALIZED_SIZE - 1] += 1; // p + 1
572        let _ = Bn254Fp::from_array(&env, &above);
573    }
574
575    #[test]
576    fn test_bn254_fp_from_bytes_validates() {
577        let env = Env::default();
578        // Zero should be valid
579        let _ = Bn254Fp::from_bytes(BytesN::from_array(&env, &[0u8; BN254_FP_SERIALIZED_SIZE]));
580    }
581
582    #[test]
583    #[should_panic(expected = "Bn254: Invalid Fp")]
584    fn test_bn254_fp_from_bytes_rejects_modulus() {
585        let env = Env::default();
586        let _ = Bn254Fp::from_bytes(BytesN::from_array(&env, &BN254_FP_MODULUS_BE));
587    }
588
589    #[test]
590    #[should_panic(expected = "Bn254: Invalid Fp")]
591    fn test_bn254_fp_try_from_val_rejects_modulus() {
592        let env = Env::default();
593        let bytes = BytesN::from_array(&env, &BN254_FP_MODULUS_BE);
594        let val: Val = bytes.into_val(&env);
595        let _: Bn254Fp = val.into_val(&env);
596    }
597
598    #[test]
599    fn test_bn254_fp_modulus_matches_arkworks() {
600        use ark_bn254::Fq;
601        use ark_ff::{BigInteger, PrimeField};
602
603        let be_bytes = Fq::MODULUS.to_bytes_be();
604        assert_eq!(
605            be_bytes.as_slice(),
606            &BN254_FP_MODULUS_BE,
607            "BN254 Fp modulus does not match arkworks"
608        );
609    }
610
611    #[test]
612    fn test_bn254_fr_modulus_matches_arkworks() {
613        use ark_bn254::Fr as ArkFr;
614        use ark_ff::{BigInteger, PrimeField};
615
616        let be_bytes = ArkFr::MODULUS.to_bytes_be();
617        assert_eq!(
618            be_bytes.as_slice(),
619            &BN254_FR_MODULUS_BE,
620            "BN254 Fr modulus does not match arkworks"
621        );
622    }
623}
soroban_sdk/crypto/bn254.rs

soroban_sdk/crypto/
bn254.rs
