p3_bn254_fr/
lib.rs

1//! The scalar field of the BN254 curve, defined as `F_r` where `r = 21888242871839275222246405745257275088548364400416034343698204186575808495617`.
2#![no_std]
3
4mod poseidon2;
5
6extern crate alloc;
7
8use alloc::vec::Vec;
9use core::fmt::{Debug, Display, Formatter};
10use core::hash::{Hash, Hasher};
11use core::iter::{Product, Sum};
12use core::ops::{Add, AddAssign, Div, Mul, MulAssign, Neg, Sub, SubAssign};
13use core::{array, fmt, stringify};
14
15pub use halo2curves::bn256::Fr as FFBn254Fr;
16use halo2curves::ff::{Field as FFField, PrimeField as FFPrimeField};
17use halo2curves::serde::SerdeObject;
18use num_bigint::BigUint;
19use p3_field::integers::QuotientMap;
20use p3_field::{
21    Field, InjectiveMonomial, Packable, PrimeCharacteristicRing, PrimeField, RawDataSerializable,
22    TwoAdicField, quotient_map_small_int,
23};
24pub use poseidon2::Poseidon2Bn254;
25use rand::Rng;
26use rand::distr::{Distribution, StandardUniform};
27use serde::{Deserialize, Deserializer, Serialize};
28
29/// The BN254 curve scalar field prime, defined as `F_r` where `r = 21888242871839275222246405745257275088548364400416034343698204186575808495617`.
30#[derive(Copy, Clone, Default, Eq, PartialEq)]
31pub struct Bn254Fr {
32    pub(crate) value: FFBn254Fr,
33}
34
35impl Bn254Fr {
36    pub(crate) const fn new(value: FFBn254Fr) -> Self {
37        Self { value }
38    }
39}
40
41impl Serialize for Bn254Fr {
42    /// Serializes to raw bytes, which are typically of the Montgomery representation of the field element.
43    // See https://github.com/privacy-scaling-explorations/halo2curves/blob/d34e9e46f7daacd194739455de3b356ca6c03206/derive/src/field/mod.rs#L493
44    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
45        let bytes = self.value.to_raw_bytes();
46        serializer.serialize_bytes(&bytes)
47    }
48}
49
50impl<'de> Deserialize<'de> for Bn254Fr {
51    /// Deserializes from raw bytes, which are typically of the Montgomery representation of the field element.
52    /// Performs a check that the deserialized field element corresponds to a value less than the field modulus, and
53    /// returns error otherwise.
54    // See https://github.com/privacy-scaling-explorations/halo2curves/blob/d34e9e46f7daacd194739455de3b356ca6c03206/derive/src/field/mod.rs#L485
55    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
56        let bytes: Vec<u8> = Deserialize::deserialize(d)?;
57
58        FFBn254Fr::from_raw_bytes(&bytes)
59            .map(Self::new)
60            .ok_or_else(|| serde::de::Error::custom("Invalid field element"))
61    }
62}
63
64impl Packable for Bn254Fr {}
65
66impl Hash for Bn254Fr {
67    fn hash<H: Hasher>(&self, state: &mut H) {
68        for byte in self.value.to_repr().as_ref() {
69            state.write_u8(*byte);
70        }
71    }
72}
73
74impl Ord for Bn254Fr {
75    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
76        self.value.cmp(&other.value)
77    }
78}
79
80impl PartialOrd for Bn254Fr {
81    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
82        Some(self.cmp(other))
83    }
84}
85
86impl Display for Bn254Fr {
87    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
88        self.value.fmt(f)
89    }
90}
91
92impl Debug for Bn254Fr {
93    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
94        Debug::fmt(&self.value, f)
95    }
96}
97
98impl PrimeCharacteristicRing for Bn254Fr {
99    type PrimeSubfield = Self;
100
101    const ZERO: Self = Self::new(FFBn254Fr::ZERO);
102    const ONE: Self = Self::new(FFBn254Fr::ONE);
103    const TWO: Self = Self::new(FFBn254Fr::from_raw([2u64, 0, 0, 0]));
104
105    // r - 1 = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000000
106    const NEG_ONE: Self = Self::new(FFBn254Fr::from_raw([
107        0x43e1f593f0000000,
108        0x2833e84879b97091,
109        0xb85045b68181585d,
110        0x30644e72e131a029,
111    ]));
112
113    #[inline]
114    fn from_prime_subfield(f: Self::PrimeSubfield) -> Self {
115        f
116    }
117}
118
119/// Degree of the smallest permutation polynomial for BN254.
120///
121/// As p - 1 is divisible by 2 and 3 the smallest choice for a degree D satisfying gcd(p - 1, D) = 1 is 5.
122impl InjectiveMonomial<5> for Bn254Fr {}
123
124// TODO: Implement PermutationMonomial<5> for Bn254Fr.
125// Not a priority given how slow (and unused) this will be.
126
127impl RawDataSerializable for Bn254Fr {
128    const NUM_BYTES: usize = 32;
129
130    #[allow(refining_impl_trait)]
131    #[inline]
132    fn into_bytes(self) -> [u8; 32] {
133        // TODO: Would be better to use to_raw_bytes() but I'm unsure if that has a uniqueness guarantee.
134        self.value.to_repr().into()
135    }
136
137    #[inline]
138    fn into_u32_stream(input: impl IntoIterator<Item = Self>) -> impl IntoIterator<Item = u32> {
139        // TODO: Might be a way to use iter_u32_digits and save an allocation.
140        // Currently switching it in causes rust to throw an error about referencing temporary values.
141        // Also we don't need as_canonical_biguint, (e.g. as_unique_biguint would be fine if it existed).
142        // This comment also applies to `into_u64_stream` as well as `into_parallel_u32_streams` and `into_parallel_u64_streams`.
143        input
144            .into_iter()
145            .flat_map(|x| x.as_canonical_biguint().to_u32_digits())
146    }
147
148    #[inline]
149    fn into_u64_stream(input: impl IntoIterator<Item = Self>) -> impl IntoIterator<Item = u64> {
150        input
151            .into_iter()
152            .flat_map(|x| x.as_canonical_biguint().to_u64_digits())
153    }
154
155    #[inline]
156    fn into_parallel_byte_streams<const N: usize>(
157        input: impl IntoIterator<Item = [Self; N]>,
158    ) -> impl IntoIterator<Item = [u8; N]> {
159        input.into_iter().flat_map(|vector| {
160            let bytes = vector.map(|elem| elem.into_bytes());
161            (0..Self::NUM_BYTES).map(move |i| array::from_fn(|j| bytes[j][i]))
162        })
163    }
164
165    #[inline]
166    fn into_parallel_u32_streams<const N: usize>(
167        input: impl IntoIterator<Item = [Self; N]>,
168    ) -> impl IntoIterator<Item = [u32; N]> {
169        input.into_iter().flat_map(|vector| {
170            let u32s = vector.map(|elem| elem.as_canonical_biguint().to_u32_digits());
171            (0..(Self::NUM_BYTES / 4)).map(move |i| array::from_fn(|j| u32s[j][i]))
172        })
173    }
174
175    #[inline]
176    fn into_parallel_u64_streams<const N: usize>(
177        input: impl IntoIterator<Item = [Self; N]>,
178    ) -> impl IntoIterator<Item = [u64; N]> {
179        input.into_iter().flat_map(|vector| {
180            let u64s = vector.map(|elem| elem.as_canonical_biguint().to_u64_digits());
181            (0..(Self::NUM_BYTES / 8)).map(move |i| array::from_fn(|j| u64s[j][i]))
182        })
183    }
184}
185
186impl Field for Bn254Fr {
187    type Packing = Self;
188
189    // generator is 5
190    const GENERATOR: Self = Self::new(FFBn254Fr::from_raw([5u64, 0, 0, 0]));
191
192    fn is_zero(&self) -> bool {
193        self.value.is_zero().into()
194    }
195
196    fn try_inverse(&self) -> Option<Self> {
197        let inverse = self.value.invert();
198
199        if inverse.is_some().into() {
200            Some(Self::new(inverse.unwrap()))
201        } else {
202            None
203        }
204    }
205
206    /// r = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
207    fn order() -> BigUint {
208        BigUint::from_slice(&[
209            0xf0000001, 0x43e1f593, 0x79b97091, 0x2833e848, 0x8181585d, 0xb85045b6, 0xe131a029,
210            0x30644e72,
211        ])
212    }
213}
214
215quotient_map_small_int!(Bn254Fr, u128, [u8, u16, u32, u64]);
216quotient_map_small_int!(Bn254Fr, i128, [i8, i16, i32, i64]);
217
218impl QuotientMap<u128> for Bn254Fr {
219    /// Due to the size of the `BN254` prime, the input value is always canonical.
220    #[inline]
221    fn from_int(int: u128) -> Self {
222        Self::new(FFBn254Fr::from_raw([int as u64, (int >> 64) as u64, 0, 0]))
223    }
224
225    /// Due to the size of the `BN254` prime, the input value is always canonical.
226    #[inline]
227    fn from_canonical_checked(int: u128) -> Option<Self> {
228        Some(Self::from_int(int))
229    }
230
231    /// Due to the size of the `BN254` prime, the input value is always canonical.
232    #[inline]
233    unsafe fn from_canonical_unchecked(int: u128) -> Self {
234        Self::from_int(int)
235    }
236}
237
238impl QuotientMap<i128> for Bn254Fr {
239    /// Due to the size of the `BN254` prime, the input value is always canonical.
240    #[inline]
241    fn from_int(int: i128) -> Self {
242        // Nothing better than just branching based on the sign of int.
243        if int >= 0 {
244            Self::from_int(int as u128)
245        } else {
246            -Self::from_int((-int) as u128)
247        }
248    }
249
250    /// Due to the size of the `BN254` prime, the input value is always canonical.
251    #[inline]
252    fn from_canonical_checked(int: i128) -> Option<Self> {
253        Some(Self::from_int(int))
254    }
255
256    /// Due to the size of the `BN254` prime, the input value is always canonical.
257    #[inline]
258    unsafe fn from_canonical_unchecked(int: i128) -> Self {
259        Self::from_int(int)
260    }
261}
262
263impl PrimeField for Bn254Fr {
264    fn as_canonical_biguint(&self) -> BigUint {
265        let repr = self.value.to_repr();
266        let le_bytes = repr.as_ref();
267        BigUint::from_bytes_le(le_bytes)
268    }
269}
270
271impl Add for Bn254Fr {
272    type Output = Self;
273
274    fn add(self, rhs: Self) -> Self {
275        Self::new(self.value + rhs.value)
276    }
277}
278
279impl AddAssign for Bn254Fr {
280    fn add_assign(&mut self, rhs: Self) {
281        self.value += rhs.value;
282    }
283}
284
285impl Sum for Bn254Fr {
286    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
287        iter.reduce(|x, y| x + y).unwrap_or(Self::ZERO)
288    }
289}
290
291impl Sub for Bn254Fr {
292    type Output = Self;
293
294    fn sub(self, rhs: Self) -> Self {
295        Self::new(self.value.sub(rhs.value))
296    }
297}
298
299impl SubAssign for Bn254Fr {
300    fn sub_assign(&mut self, rhs: Self) {
301        self.value -= rhs.value;
302    }
303}
304
305impl Neg for Bn254Fr {
306    type Output = Self;
307
308    fn neg(self) -> Self::Output {
309        self * Self::NEG_ONE
310    }
311}
312
313impl Mul for Bn254Fr {
314    type Output = Self;
315
316    fn mul(self, rhs: Self) -> Self {
317        Self::new(self.value * rhs.value)
318    }
319}
320
321impl MulAssign for Bn254Fr {
322    fn mul_assign(&mut self, rhs: Self) {
323        self.value *= rhs.value;
324    }
325}
326
327impl Product for Bn254Fr {
328    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
329        iter.reduce(|x, y| x * y).unwrap_or(Self::ONE)
330    }
331}
332
333impl Div for Bn254Fr {
334    type Output = Self;
335
336    #[allow(clippy::suspicious_arithmetic_impl)]
337    fn div(self, rhs: Self) -> Self {
338        self * rhs.inverse()
339    }
340}
341
342impl Distribution<Bn254Fr> for StandardUniform {
343    #[inline]
344    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Bn254Fr {
345        // Simple implementation of rejection sampling:
346        loop {
347            let mut trial_element: [u8; 32] = rng.random();
348
349            // Set top 2 bits to 0 as bn254 is a 254-bit field.
350            // `from_bytes` expects little endian input, so we adjust byte 31:
351            trial_element[31] &= (1_u8 << 6) - 1;
352
353            let x = FFBn254Fr::from_bytes(&trial_element);
354            if x.is_some().into() {
355                // x.unwrap() is safe because x.is_some() is true
356                return Bn254Fr::new(x.unwrap());
357            }
358        }
359    }
360}
361
362impl TwoAdicField for Bn254Fr {
363    const TWO_ADICITY: usize = FFBn254Fr::S as usize;
364
365    fn two_adic_generator(bits: usize) -> Self {
366        let mut omega = FFBn254Fr::ROOT_OF_UNITY;
367        for _ in bits..Self::TWO_ADICITY {
368            omega = omega.square();
369        }
370        Self::new(omega)
371    }
372}
373
374#[cfg(test)]
375mod tests {
376    use p3_field_testing::{test_field, test_prime_field};
377
378    use super::*;
379
380    type F = Bn254Fr;
381
382    #[test]
383    fn test_bn254fr() {
384        let f = F::new(FFBn254Fr::from_u128(100));
385        assert_eq!(f.as_canonical_biguint(), BigUint::from(100u32));
386
387        let f = F::new(FFBn254Fr::from_str_vartime(&F::order().to_str_radix(10)).unwrap());
388        assert!(f.is_zero());
389
390        // Generator check
391        let expected_multiplicative_group_generator = F::new(FFBn254Fr::from_u128(5));
392        assert_eq!(F::GENERATOR, expected_multiplicative_group_generator);
393        assert_eq!(F::GENERATOR.as_canonical_biguint(), BigUint::from(5u32));
394
395        let f_1 = F::ONE;
396        let f_2 = F::TWO;
397        let f_r_minus_1 = F::NEG_ONE;
398        let f_r_minus_2 = F::NEG_ONE + F::NEG_ONE;
399
400        let f_serialized = serde_json::to_string(&f).unwrap();
401        let f_deserialized: F = serde_json::from_str(&f_serialized).unwrap();
402        assert_eq!(f, f_deserialized);
403
404        let f_1_serialized = serde_json::to_string(&f_1).unwrap();
405        let f_1_deserialized: F = serde_json::from_str(&f_1_serialized).unwrap();
406        let f_1_serialized_again = serde_json::to_string(&f_1_deserialized).unwrap();
407        let f_1_deserialized_again: F = serde_json::from_str(&f_1_serialized_again).unwrap();
408        assert_eq!(f_1, f_1_deserialized);
409        assert_eq!(f_1, f_1_deserialized_again);
410
411        let f_2_serialized = serde_json::to_string(&f_2).unwrap();
412        let f_2_deserialized: F = serde_json::from_str(&f_2_serialized).unwrap();
413        assert_eq!(f_2, f_2_deserialized);
414
415        let f_r_minus_1_serialized = serde_json::to_string(&f_r_minus_1).unwrap();
416        let f_r_minus_1_deserialized: F = serde_json::from_str(&f_r_minus_1_serialized).unwrap();
417        assert_eq!(f_r_minus_1, f_r_minus_1_deserialized);
418
419        let f_r_minus_2_serialized = serde_json::to_string(&f_r_minus_2).unwrap();
420        let f_r_minus_2_deserialized: F = serde_json::from_str(&f_r_minus_2_serialized).unwrap();
421        assert_eq!(f_r_minus_2, f_r_minus_2_deserialized);
422    }
423
424    const ZERO: Bn254Fr = Bn254Fr::ZERO;
425    const ONE: Bn254Fr = Bn254Fr::ONE;
426
427    // Get the prime factorization of the order of the multiplicative group.
428    // i.e. the prime factorization of P - 1.
429    fn multiplicative_group_prime_factorization() -> [(BigUint, u32); 10] {
430        [
431            (BigUint::from(2u8), 28),
432            (BigUint::from(3u8), 2),
433            (BigUint::from(13u8), 1),
434            (BigUint::from(29u8), 1),
435            (BigUint::from(983u16), 1),
436            (BigUint::from(11003u16), 1),
437            (BigUint::from(237073u32), 1),
438            (BigUint::from(405928799u32), 1),
439            (BigUint::from(1670836401704629u64), 1),
440            (BigUint::from(13818364434197438864469338081u128), 1),
441        ]
442    }
443    test_field!(
444        crate::Bn254Fr,
445        &[super::ZERO],
446        &[super::ONE],
447        &super::multiplicative_group_prime_factorization()
448    );
449
450    test_prime_field!(crate::Bn254Fr);
451}
p3_bn254_fr/lib.rs

p3_bn254_fr/
lib.rs
