p3_bn254/
bn254.rs

1use alloc::vec::Vec;
2use core::fmt::{Debug, Display, Formatter};
3use core::hash::{Hash, Hasher};
4use core::iter::{Product, Sum};
5use core::mem::transmute;
6use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
7use core::{array, fmt};
8
9use num_bigint::BigUint;
10use p3_field::integers::QuotientMap;
11use p3_field::op_assign_macros::{
12    impl_add_assign, impl_div_methods, impl_mul_methods, impl_sub_assign, ring_sum,
13};
14use p3_field::{
15    Field, InjectiveMonomial, Packable, PrimeCharacteristicRing, PrimeField, RawDataSerializable,
16    TwoAdicField, quotient_map_small_int,
17};
18use rand::Rng;
19use rand::distr::{Distribution, StandardUniform};
20use serde::{Deserialize, Deserializer, Serialize};
21
22use crate::helpers::{
23    gcd_inversion, halve_bn254, monty_mul, to_biguint, wrapping_add, wrapping_sub,
24};
25
26/// The BN254 prime represented as a little-endian array of 4-u64s.
27///
28/// Equal to: `21888242871839275222246405745257275088548364400416034343698204186575808495617`
29pub(crate) const BN254_PRIME: [u64; 4] = [
30    0x43e1f593f0000001,
31    0x2833e84879b97091,
32    0xb85045b68181585d,
33    0x30644e72e131a029,
34];
35
36// We use the Montgomery representation of the BN254 prime, with respect to the
37// constant 2^256.
38
39/// The value P^{-1} mod 2^64 where P is the BN254 prime.
40pub(crate) const BN254_MONTY_MU_64: u64 = 0x3d1e0a6c10000001;
41
42/// The square of the Montgomery constant `R = 2^256 mod P` for the BN254 field.
43///
44/// Elements of the BN254 field are represented in Montgomery form, by `aR mod P`
45/// This constant is equal to `R^2 mod P` and is useful for converting elements into Montgomery form.
46///
47/// Equal to: `944936681149208446651664254269745548490766851729442924617792859073125903783`
48pub(crate) const BN254_MONTY_R_SQ: [u64; 4] = [
49    0x1bb8e645ae216da7,
50    0x53fe3ab1e35c59e3,
51    0x8c49833d53bb8085,
52    0x0216d0b17f4e44a5,
53];
54
55/// The BN254 curve scalar field prime, defined as `F_P` where `P = 21888242871839275222246405745257275088548364400416034343698204186575808495617`.
56#[derive(Copy, Clone, Default, Eq, PartialEq)]
57#[must_use]
58pub struct Bn254 {
59    /// The MONTY form of the field element, a 254-bit integer less than `P` saved as a collection of u64's using a little-endian order.
60    pub(crate) value: [u64; 4],
61}
62
63impl Bn254 {
64    /// Create a new field element from any `[u64; 4]` in little-endian limb order.
65    ///
66    /// Any value is accepted and automatically reduced modulo P.
67    #[inline]
68    pub const fn new(value: [u64; 4]) -> Self {
69        Self::new_monty(monty_mul(BN254_MONTY_R_SQ, value))
70    }
71
72    /// Convert a `[[u64; 4]; N]` array to an array of field elements.
73    ///
74    /// Const version of `input.map(Bn254::new)`.
75    #[inline]
76    pub const fn new_array<const N: usize>(input: [[u64; 4]; N]) -> [Self; N] {
77        let mut output = [Self::ZERO; N];
78        let mut i = 0;
79        while i < N {
80            output[i] = Self::new(input[i]);
81            i += 1;
82        }
83        output
84    }
85
86    /// Creates a new BN254 field element from an array of 4 u64's.
87    ///
88    /// The array is assumed to correspond to a 254-bit integer less than P and is interpreted as
89    /// already being in Montgomery form.
90    #[inline]
91    pub(crate) const fn new_monty(value: [u64; 4]) -> Self {
92        Self { value }
93    }
94
95    #[inline]
96    #[allow(clippy::needless_pass_by_value)]
97    pub fn from_biguint(value: BigUint) -> Option<Self> {
98        let digits = value.to_u64_digits();
99        let num_dig = digits.len();
100
101        match num_dig {
102            0 => Some(Self::ZERO),
103            1..=4 => {
104                let mut inner = [0; 4];
105                inner[..num_dig].copy_from_slice(&digits);
106
107                // We don't need to check that the value is less than the prime as, provided
108                // the lhs entry of `monty_mul` is less than `P`, the result will be less than `P`.
109                // Adjust the value into Montgomery form by multiplying by `R^2` and doing a monty reduction.
110                Some(Self::new_monty(monty_mul(BN254_MONTY_R_SQ, inner)))
111            }
112            _ => None, // Too many digits for BN254
113        }
114    }
115
116    /// Converts the a byte array in little-endian order to a field element.
117    ///
118    /// Assumes the bytes correspond to the Montgomery form of the desired field element.
119    ///
120    /// Returns None if the byte array is not exactly 32 bytes long or if the value
121    /// represented by the byte array is not less than the BN254 prime.
122    #[inline]
123    pub(crate) fn from_bytes_monty(bytes: &[u8]) -> Option<Self> {
124        if bytes.len() != 32 {
125            return None;
126        }
127        let value: [u64; 4] = array::from_fn(|i| {
128            // Convert each 8 bytes to a u64 in little-endian order.
129            let start = i * 8;
130            let end = start + 8;
131            // This unwrap is safe due to the length check above.
132            u64::from_le_bytes(bytes[start..end].try_into().unwrap())
133        });
134        // Check if the value is less than the prime.
135        if value.iter().rev().cmp(BN254_PRIME.iter().rev()) == core::cmp::Ordering::Less {
136            Some(Self::new_monty(value))
137        } else {
138            None
139        }
140    }
141}
142
143impl Serialize for Bn254 {
144    /// Serializes to raw bytes, which correspond to the Montgomery representation of the field element.
145    #[inline]
146    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
147        serializer.serialize_bytes(&self.into_bytes())
148    }
149}
150
151impl<'de> Deserialize<'de> for Bn254 {
152    /// Deserializes from raw bytes, which correspond to the Montgomery representation of the field element.
153    /// Performs a check that the deserialized field element corresponds to a value less than the field modulus, and
154    /// returns an error otherwise.
155    #[inline]
156    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
157        let bytes: Vec<u8> = Deserialize::deserialize(d)?;
158
159        Self::from_bytes_monty(&bytes)
160            .ok_or_else(|| serde::de::Error::custom("Invalid field element"))
161    }
162}
163
164impl Packable for Bn254 {}
165
166impl Hash for Bn254 {
167    #[inline]
168    fn hash<H: Hasher>(&self, state: &mut H) {
169        for byte in self.value.as_ref() {
170            state.write_u64(*byte);
171        }
172    }
173}
174
175impl Ord for Bn254 {
176    #[inline]
177    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
178        self.value.iter().rev().cmp(other.value.iter().rev())
179    }
180}
181
182impl PartialOrd for Bn254 {
183    #[inline]
184    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
185        Some(self.cmp(other))
186    }
187}
188
189impl Display for Bn254 {
190    #[inline]
191    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
192        core::fmt::Display::fmt(&self.as_canonical_biguint(), f)
193    }
194}
195
196impl Debug for Bn254 {
197    #[inline]
198    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
199        core::fmt::Debug::fmt(&self.as_canonical_biguint(), f)
200    }
201}
202
203impl PrimeCharacteristicRing for Bn254 {
204    type PrimeSubfield = Self;
205
206    const ZERO: Self = Self::new_monty([0, 0, 0, 0]);
207
208    /// The Montgomery form of the BN254 field element 1.
209    ///
210    /// Equal to `2^256 mod P = 6350874878119819312338956282401532410528162663560392320966563075034087161851`
211    const ONE: Self = Self::new_monty([
212        0xac96341c4ffffffb,
213        0x36fc76959f60cd29,
214        0x666ea36f7879462e,
215        0x0e0a77c19a07df2f,
216    ]);
217
218    /// The Montgomery form of the BN254 field element 2.
219    ///
220    /// Equal to `2^257 mod P = 12701749756239638624677912564803064821056325327120784641933126150068174323702`
221    const TWO: Self = Self::new_monty([
222        0x592c68389ffffff6,
223        0x6df8ed2b3ec19a53,
224        0xccdd46def0f28c5c,
225        0x1c14ef83340fbe5e,
226    ]);
227
228    /// The Montgomery form of the BN254 field element -1.
229    ///
230    /// Equal to `-2^256 mod P = 15537367993719455909907449462855742678020201736855642022731641111541721333766`
231    const NEG_ONE: Self = Self::new_monty([
232        0x974bc177a0000006,
233        0xf13771b2da58a367,
234        0x51e1a2470908122e,
235        0x2259d6b14729c0fa,
236    ]);
237
238    #[inline]
239    fn from_prime_subfield(f: Self::PrimeSubfield) -> Self {
240        f
241    }
242
243    #[inline]
244    fn halve(&self) -> Self {
245        Self::new_monty(halve_bn254(self.value))
246    }
247}
248
249/// Degree of the smallest permutation polynomial for BN254.
250///
251/// As p - 1 is divisible by 2 and 3 the smallest choice for a degree D satisfying gcd(p - 1, D) = 1 is 5.
252impl InjectiveMonomial<5> for Bn254 {}
253
254// TODO: Implement PermutationMonomial<5> for Bn254Fr.
255// Not a priority given how slow (and unused) this will be.
256
257impl RawDataSerializable for Bn254 {
258    const NUM_BYTES: usize = 32;
259
260    #[allow(refining_impl_trait)]
261    #[inline]
262    fn into_bytes(self) -> [u8; 32] {
263        // The transmute here maps from [[u8; 8]; 4] to [u8; 32] so is clearly safe.
264        unsafe { transmute(self.value.map(|x| x.to_le_bytes())) }
265    }
266
267    #[inline]
268    fn into_u32_stream(input: impl IntoIterator<Item = Self>) -> impl IntoIterator<Item = u32> {
269        input.into_iter().flat_map(|x| {
270            x.value
271                .into_iter()
272                .flat_map(|digit| [digit as u32, (digit >> 32) as u32])
273        })
274    }
275
276    #[inline]
277    fn into_u64_stream(input: impl IntoIterator<Item = Self>) -> impl IntoIterator<Item = u64> {
278        input.into_iter().flat_map(|x| x.value)
279    }
280
281    #[inline]
282    fn into_parallel_byte_streams<const N: usize>(
283        input: impl IntoIterator<Item = [Self; N]>,
284    ) -> impl IntoIterator<Item = [u8; N]> {
285        input.into_iter().flat_map(|vector| {
286            let bytes = vector.map(|elem| elem.into_bytes());
287            (0..Self::NUM_BYTES).map(move |i| array::from_fn(|j| bytes[j][i]))
288        })
289    }
290
291    #[inline]
292    fn into_parallel_u32_streams<const N: usize>(
293        input: impl IntoIterator<Item = [Self; N]>,
294    ) -> impl IntoIterator<Item = [u32; N]> {
295        input.into_iter().flat_map(|vector| {
296            // The transmute here maps from [[u32; 2]; 4] to [u32; 8] so is clearly safe.
297            let u32s: [[u32; 8]; N] = vector
298                .map(|elem| unsafe { transmute(elem.value.map(|x| [x as u32, (x >> 32) as u32])) });
299            (0..(Self::NUM_BYTES / 4)).map(move |i| array::from_fn(|j| u32s[j][i]))
300        })
301    }
302
303    #[inline]
304    fn into_parallel_u64_streams<const N: usize>(
305        input: impl IntoIterator<Item = [Self; N]>,
306    ) -> impl IntoIterator<Item = [u64; N]> {
307        input.into_iter().flat_map(|vector| {
308            let u64s = vector.map(|elem| elem.value);
309            (0..(Self::NUM_BYTES / 8)).map(move |i| array::from_fn(|j| u64s[j][i]))
310        })
311    }
312}
313
314impl Field for Bn254 {
315    type Packing = Self;
316
317    /// The Montgomery form of the BN254 field element 5 which generates the multiplicative group.
318    ///
319    /// Can check this in SageMath by running:
320    /// ```SageMath
321    ///     BN254_prime = 21888242871839275222246405745257275088548364400416034343698204186575808495617
322    ///     BN254_field = GF(BN254_prime)
323    ///     BN254_field(5).multiplicative_order()
324    /// ```
325    ///
326    /// Equal to `9866131518759821339448375666750386964092448917385927261134611188594627313638`
327    const GENERATOR: Self = Self::new_monty([
328        0x1b0d0ef99fffffe6,
329        0xeaba68a3a32a913f,
330        0x47d8eb76d8dd0689,
331        0x15d0085520f5bbc3,
332    ]);
333
334    #[inline]
335    fn is_zero(&self) -> bool {
336        self.value.iter().all(|&x| x == 0)
337    }
338
339    #[inline]
340    fn try_inverse(&self) -> Option<Self> {
341        // TODO: This turns out to be a much slower than the Halo2 implementation used by FFBn254Fr. (Roughly 4x slower)
342        // That implementation makes use of an optimised extended Euclidean algorithm. It would be good
343        // to either implement that here or further improve the speed of multiplication to speed exponentiation
344        // based inversion up. Don't think it is super important for now though as inversion is rare and can mostly be
345        // batched.
346        (!self.is_zero()).then(|| Self::new_monty(gcd_inversion(self.value)))
347    }
348
349    /// `r = 21888242871839275222246405745257275088548364400416034343698204186575808495617`
350    #[inline]
351    fn order() -> BigUint {
352        to_biguint(BN254_PRIME)
353    }
354}
355
356quotient_map_small_int!(Bn254, u128, [u8, u16, u32, u64]);
357quotient_map_small_int!(Bn254, i128, [i8, i16, i32, i64]);
358
359impl QuotientMap<u128> for Bn254 {
360    /// Due to the size of the `BN254` prime, the input value is always canonical.
361    #[inline]
362    fn from_int(int: u128) -> Self {
363        // Need to convert into Monty form. As the monty reduction strips out a factor of `R`,
364        // we can do this by multiplying by `R^2` and doing a monty reduction.
365        // This may be able to be improved as some values are always 0 but the compiler is
366        // probably smart enough to work that out here?
367        let monty_form = monty_mul(BN254_MONTY_R_SQ, [int as u64, (int >> 64) as u64, 0, 0]);
368        Self::new_monty(monty_form)
369    }
370
371    /// Due to the size of the `BN254` prime, the input value is always canonical.
372    #[inline]
373    fn from_canonical_checked(int: u128) -> Option<Self> {
374        Some(Self::from_int(int))
375    }
376
377    /// Due to the size of the `BN254` prime, the input value is always canonical.
378    #[inline]
379    unsafe fn from_canonical_unchecked(int: u128) -> Self {
380        Self::from_int(int)
381    }
382}
383
384impl QuotientMap<i128> for Bn254 {
385    /// Due to the size of the `BN254` prime, the input value is always canonical.
386    #[inline]
387    fn from_int(int: i128) -> Self {
388        // Nothing better than just branching based on the sign of int.
389        if int >= 0 {
390            Self::from_int(int as u128)
391        } else {
392            -Self::from_int((-int) as u128)
393        }
394    }
395
396    /// Due to the size of the `BN254` prime, the input value is always canonical.
397    #[inline]
398    fn from_canonical_checked(int: i128) -> Option<Self> {
399        Some(Self::from_int(int))
400    }
401
402    /// Due to the size of the `BN254` prime, the input value is always canonical.
403    #[inline]
404    unsafe fn from_canonical_unchecked(int: i128) -> Self {
405        Self::from_int(int)
406    }
407}
408
409impl PrimeField for Bn254 {
410    #[inline]
411    fn as_canonical_biguint(&self) -> BigUint {
412        // `monty_mul` strips out a factor of `R` so multiplying by `1` converts a montgomery
413        // representation into a canonical representation.
414        let out_val = monty_mul(self.value, [1, 0, 0, 0]);
415        to_biguint(out_val)
416    }
417}
418
419impl Add for Bn254 {
420    type Output = Self;
421
422    #[inline]
423    fn add(self, rhs: Self) -> Self {
424        let lhs = self.value;
425        let rhs = rhs.value;
426
427        let (sum, overflow) = wrapping_add(lhs, rhs);
428
429        // As the inputs are < 2^254, the output is < 2^256 so the final carry flag should be false.
430        debug_assert!(!overflow);
431
432        // If output is bigger than BN254_PRIME, we should subtract BN254_PRIME from it.
433        // TODO: Can we avoid this subtraction in some cases? Might make things faster.
434        // Currently subtraction of Bn254 elements is faster than addition as we don't need to
435        // do both an addition and a subtraction in both cases.
436        let (sum_corr, underflow) = wrapping_sub(sum, BN254_PRIME);
437
438        if underflow {
439            Self::new_monty(sum)
440        } else {
441            Self::new_monty(sum_corr)
442        }
443    }
444}
445
446impl Sub for Bn254 {
447    type Output = Self;
448
449    #[inline]
450    fn sub(self, rhs: Self) -> Self {
451        let lhs = self.value;
452        let rhs = rhs.value;
453
454        let (mut sub, underflow) = wrapping_sub(lhs, rhs);
455
456        // if lhs < rhs, we need to add BN254_PRIME to the result.
457        if underflow {
458            (sub, _) = wrapping_add(sub, BN254_PRIME);
459        }
460
461        Self::new_monty(sub)
462    }
463}
464
465impl Neg for Bn254 {
466    type Output = Self;
467
468    #[inline]
469    fn neg(self) -> Self::Output {
470        Self::ZERO - self
471    }
472}
473
474impl Mul for Bn254 {
475    type Output = Self;
476
477    #[inline]
478    fn mul(self, rhs: Self) -> Self {
479        Self::new_monty(monty_mul(self.value, rhs.value))
480    }
481}
482
483impl_add_assign!(Bn254);
484impl_sub_assign!(Bn254);
485impl_mul_methods!(Bn254);
486ring_sum!(Bn254);
487impl_div_methods!(Bn254, Bn254);
488
489impl Distribution<Bn254> for StandardUniform {
490    #[inline]
491    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Bn254 {
492        // Simple implementation of rejection sampling:
493        loop {
494            let mut trial_element: [u8; 32] = rng.random();
495
496            // Set top 2 bits to 0 as bn254 is a 254-bit field.
497            // `from_bytes` expects little endian input, so we adjust byte 31:
498            trial_element[31] &= (1_u8 << 6) - 1;
499
500            let x = Bn254::from_bytes_monty(&trial_element);
501            if let Some(val) = x {
502                return val;
503            }
504        }
505    }
506}
507
508/// TWO_ADIC_GENERATOR is defined as `5^{P - 1 / 2^28}` where `P` is the BN254 prime.
509///
510/// It is equal to: 19103219067921713944291392827692070036145651957329286315305642004821462161904
511const TWO_ADIC_GENERATOR: [u64; 4] = [
512    0x636e735580d13d9c,
513    0xa22bf3742445ffd6,
514    0x56452ac01eb203d8,
515    0x1860ef942963f9e7,
516];
517
518impl TwoAdicField for Bn254 {
519    const TWO_ADICITY: usize = 28;
520
521    #[inline]
522    fn two_adic_generator(bits: usize) -> Self {
523        let mut omega = Self::new_monty(TWO_ADIC_GENERATOR);
524        for _ in bits..Self::TWO_ADICITY {
525            omega = omega.square();
526        }
527        omega
528    }
529}
530
531#[cfg(test)]
532mod tests {
533    use p3_field_testing::{test_field, test_field_json_serialization, test_prime_field};
534
535    use super::*;
536
537    type F = Bn254;
538
539    #[test]
540    fn test_bn254fr() {
541        let big_int_100 = BigUint::from(100u32);
542        let big_int_p = to_biguint(BN254_PRIME);
543        let big_int_2_256_min_1 = to_biguint([
544            0xffffffffffffffff,
545            0xffffffffffffffff,
546            0xffffffffffffffff,
547            0xffffffffffffffff,
548        ]);
549        let big_int_2_256_mod_p = to_biguint([
550            0xac96341c4ffffffb,
551            0x36fc76959f60cd29,
552            0x666ea36f7879462e,
553            0x0e0a77c19a07df2f,
554        ]);
555
556        let f_100 = F::from_biguint(big_int_100.clone()).unwrap();
557        assert_eq!(f_100.as_canonical_biguint(), BigUint::from(100u32));
558        assert_eq!(F::from_biguint(BigUint::ZERO), Some(F::ZERO));
559        for i in 0_u32..6_u32 {
560            assert_eq!(F::from_biguint(big_int_p.clone() * i), Some(F::ZERO));
561            assert_eq!(
562                F::from_biguint((big_int_100.clone() + big_int_p.clone()) * i),
563                Some(f_100 * F::from_int(i))
564            );
565        }
566        assert_eq!(F::from_biguint(big_int_p * 6_u32), None);
567        assert_eq!(
568            F::from_biguint(big_int_2_256_min_1).unwrap(),
569            F::NEG_ONE + F::from_biguint(big_int_2_256_mod_p).unwrap()
570        );
571
572        // Generator check
573        let expected_multiplicative_group_generator = F::from_u8(5);
574        assert_eq!(F::GENERATOR, expected_multiplicative_group_generator);
575        assert_eq!(F::GENERATOR.as_canonical_biguint(), BigUint::from(5u32));
576
577        let f_1 = F::ONE;
578        let f_2 = F::TWO;
579        let f_r_minus_1 = F::NEG_ONE;
580        let f_r_minus_2 = F::NEG_ONE + F::NEG_ONE;
581
582        test_field_json_serialization(&[f_100, f_1, f_2, f_r_minus_1, f_r_minus_2]);
583    }
584
585    const ZERO: Bn254 = Bn254::ZERO;
586    const ONE: Bn254 = Bn254::ONE;
587
588    // Get the prime factorization of the order of the multiplicative group.
589    // i.e. the prime factorization of P - 1.
590    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 10] {
591        [
592            (BigUint::from(2u8), 28),
593            (BigUint::from(3u8), 2),
594            (BigUint::from(13u8), 1),
595            (BigUint::from(29u8), 1),
596            (BigUint::from(983u16), 1),
597            (BigUint::from(11003u16), 1),
598            (BigUint::from(237073u32), 1),
599            (BigUint::from(405928799u32), 1),
600            (BigUint::from(1670836401704629u64), 1),
601            (BigUint::from(13818364434197438864469338081u128), 1),
602        ]
603    }
604    test_field!(
605        crate::Bn254,
606        &[super::ZERO],
607        &[super::ONE],
608        &super::multiplicative_group_prime_factorization()
609    );
610
611    test_prime_field!(crate::Bn254);
612}
p3_bn254/bn254.rs

p3_bn254/
bn254.rs
