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

p3_bn254/
bn254.rs
