p3_bn254_fr/
lib.rs

Help
1//! The scalar field of the BN254 curve, defined as `F_r` where `r = 21888242871839275222246405745257275088548364400416034343698204186575808495617`.
2
3mod poseidon2;
4
5use core::fmt;
6use core::fmt::{Debug, Display, Formatter};
7use core::hash::{Hash, Hasher};
8use core::iter::{Product, Sum};
9use core::ops::{Add, AddAssign, Div, Mul, MulAssign, Neg, Sub, SubAssign};
10
11use ff::{Field as FFField, PrimeField as FFPrimeField};
12pub use halo2curves::bn256::Fr as FFBn254Fr;
13use halo2curves::serde::SerdeObject;
14use num_bigint::BigUint;
15use p3_field::{Field, FieldAlgebra, Packable, PrimeField, TwoAdicField};
16pub use poseidon2::Poseidon2Bn254;
17use rand::distributions::{Distribution, Standard};
18use rand::Rng;
19use serde::{Deserialize, Deserializer, Serialize};
20
21/// The BN254 curve scalar field prime, defined as `F_r` where `r = 21888242871839275222246405745257275088548364400416034343698204186575808495617`.
22#[derive(Copy, Clone, Default, Eq, PartialEq)]
23pub struct Bn254Fr {
24    pub value: FFBn254Fr,
25}
26
27impl Bn254Fr {
28    pub(crate) const fn new(value: FFBn254Fr) -> Self {
29        Self { value }
30    }
31}
32
33impl Serialize for Bn254Fr {
34    /// Serializes to raw bytes, which are typically of the Montgomery representation of the field element.
35    // See https://github.com/privacy-scaling-explorations/halo2curves/blob/d34e9e46f7daacd194739455de3b356ca6c03206/derive/src/field/mod.rs#L493
36    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
37        let bytes = self.value.to_raw_bytes();
38        serializer.serialize_bytes(&bytes)
39    }
40}
41
42impl<'de> Deserialize<'de> for Bn254Fr {
43    /// Deserializes from raw bytes, which are typically of the Montgomery representation of the field element.
44    /// Performs a check that the deserialized field element corresponds to a value less than the field modulus, and
45    /// returns error otherwise.
46    // See https://github.com/privacy-scaling-explorations/halo2curves/blob/d34e9e46f7daacd194739455de3b356ca6c03206/derive/src/field/mod.rs#L485
47    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
48        let bytes: Vec<u8> = Deserialize::deserialize(d)?;
49
50        let value = FFBn254Fr::from_raw_bytes(&bytes);
51
52        value
53            .map(Self::new)
54            .ok_or(serde::de::Error::custom("Invalid field element"))
55    }
56}
57
58impl Packable for Bn254Fr {}
59
60impl Hash for Bn254Fr {
61    fn hash<H: Hasher>(&self, state: &mut H) {
62        for byte in self.value.to_repr().as_ref().iter() {
63            state.write_u8(*byte);
64        }
65    }
66}
67
68impl Ord for Bn254Fr {
69    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
70        self.value.cmp(&other.value)
71    }
72}
73
74impl PartialOrd for Bn254Fr {
75    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
76        Some(self.cmp(other))
77    }
78}
79
80impl Display for Bn254Fr {
81    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
82        <FFBn254Fr as Debug>::fmt(&self.value, f)
83    }
84}
85
86impl Debug for Bn254Fr {
87    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
88        Debug::fmt(&self.value, f)
89    }
90}
91
92impl FieldAlgebra for Bn254Fr {
93    type F = Self;
94
95    const ZERO: Self = Self::new(FFBn254Fr::ZERO);
96    const ONE: Self = Self::new(FFBn254Fr::ONE);
97    const TWO: Self = Self::new(FFBn254Fr::from_raw([2u64, 0, 0, 0]));
98
99    // r - 1 = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000000
100    const NEG_ONE: Self = Self::new(FFBn254Fr::from_raw([
101        0x43e1f593f0000000,
102        0x2833e84879b97091,
103        0xb85045b68181585d,
104        0x30644e72e131a029,
105    ]));
106
107    #[inline]
108    fn from_f(f: Self::F) -> Self {
109        f
110    }
111
112    fn from_canonical_u8(n: u8) -> Self {
113        Self::new(FFBn254Fr::from(n as u64))
114    }
115
116    fn from_canonical_u16(n: u16) -> Self {
117        Self::new(FFBn254Fr::from(n as u64))
118    }
119
120    fn from_canonical_u32(n: u32) -> Self {
121        Self::new(FFBn254Fr::from(n as u64))
122    }
123
124    fn from_canonical_u64(n: u64) -> Self {
125        Self::new(FFBn254Fr::from(n))
126    }
127
128    fn from_canonical_usize(n: usize) -> Self {
129        Self::new(FFBn254Fr::from(n as u64))
130    }
131
132    fn from_wrapped_u32(n: u32) -> Self {
133        Self::new(FFBn254Fr::from(n as u64))
134    }
135
136    fn from_wrapped_u64(n: u64) -> Self {
137        Self::new(FFBn254Fr::from(n))
138    }
139}
140
141impl Field for Bn254Fr {
142    type Packing = Self;
143
144    // generator is 5
145    const GENERATOR: Self = Self::new(FFBn254Fr::from_raw([5u64, 0, 0, 0]));
146
147    fn is_zero(&self) -> bool {
148        self.value.is_zero().into()
149    }
150
151    fn try_inverse(&self) -> Option<Self> {
152        let inverse = self.value.invert();
153
154        if inverse.is_some().into() {
155            Some(Self::new(inverse.unwrap()))
156        } else {
157            None
158        }
159    }
160
161    /// r = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
162    fn order() -> BigUint {
163        BigUint::new(vec![
164            0xf0000001, 0x43e1f593, 0x79b97091, 0x2833e848, 0x8181585d, 0xb85045b6, 0xe131a029,
165            0x30644e72,
166        ])
167    }
168
169    fn multiplicative_group_factors() -> Vec<(BigUint, usize)> {
170        vec![
171            (BigUint::from(2u8), 28),
172            (BigUint::from(3u8), 2),
173            (BigUint::from(13u8), 1),
174            (BigUint::from(29u8), 1),
175            (BigUint::from(983u16), 1),
176            (BigUint::from(11003u16), 1),
177            (BigUint::from(237073u32), 1),
178            (BigUint::from(405928799u32), 1),
179            (BigUint::from(1670836401704629u64), 1),
180            (BigUint::from(13818364434197438864469338081u128), 1),
181        ]
182    }
183}
184
185impl PrimeField for Bn254Fr {
186    fn as_canonical_biguint(&self) -> BigUint {
187        let repr = self.value.to_repr();
188        let le_bytes = repr.as_ref();
189        BigUint::from_bytes_le(le_bytes)
190    }
191}
192
193impl Add for Bn254Fr {
194    type Output = Self;
195
196    fn add(self, rhs: Self) -> Self {
197        Self::new(self.value + rhs.value)
198    }
199}
200
201impl AddAssign for Bn254Fr {
202    fn add_assign(&mut self, rhs: Self) {
203        self.value += rhs.value;
204    }
205}
206
207impl Sum for Bn254Fr {
208    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
209        iter.reduce(|x, y| x + y).unwrap_or(Self::ZERO)
210    }
211}
212
213impl Sub for Bn254Fr {
214    type Output = Self;
215
216    fn sub(self, rhs: Self) -> Self {
217        Self::new(self.value.sub(rhs.value))
218    }
219}
220
221impl SubAssign for Bn254Fr {
222    fn sub_assign(&mut self, rhs: Self) {
223        self.value -= rhs.value;
224    }
225}
226
227impl Neg for Bn254Fr {
228    type Output = Self;
229
230    fn neg(self) -> Self::Output {
231        self * Self::NEG_ONE
232    }
233}
234
235impl Mul for Bn254Fr {
236    type Output = Self;
237
238    fn mul(self, rhs: Self) -> Self {
239        Self::new(self.value * rhs.value)
240    }
241}
242
243impl MulAssign for Bn254Fr {
244    fn mul_assign(&mut self, rhs: Self) {
245        self.value *= rhs.value;
246    }
247}
248
249impl Product for Bn254Fr {
250    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
251        iter.reduce(|x, y| x * y).unwrap_or(Self::ONE)
252    }
253}
254
255impl Div for Bn254Fr {
256    type Output = Self;
257
258    #[allow(clippy::suspicious_arithmetic_impl)]
259    fn div(self, rhs: Self) -> Self {
260        self * rhs.inverse()
261    }
262}
263
264impl Distribution<Bn254Fr> for Standard {
265    #[inline]
266    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Bn254Fr {
267        Bn254Fr::new(FFBn254Fr::random(rng))
268    }
269}
270
271impl TwoAdicField for Bn254Fr {
272    const TWO_ADICITY: usize = FFBn254Fr::S as usize;
273
274    fn two_adic_generator(bits: usize) -> Self {
275        let mut omega = FFBn254Fr::ROOT_OF_UNITY;
276        for _ in bits..Self::TWO_ADICITY {
277            omega = omega.square();
278        }
279        Self::new(omega)
280    }
281}
282
283#[cfg(test)]
284mod tests {
285    use num_traits::One;
286    use p3_field_testing::test_field;
287
288    use super::*;
289
290    type F = Bn254Fr;
291
292    #[test]
293    fn test_bn254fr() {
294        let f = F::new(FFBn254Fr::from_u128(100));
295        assert_eq!(f.as_canonical_biguint(), BigUint::new(vec![100]));
296
297        let f = F::from_canonical_u64(0);
298        assert!(f.is_zero());
299
300        let f = F::new(FFBn254Fr::from_str_vartime(&F::order().to_str_radix(10)).unwrap());
301        assert!(f.is_zero());
302
303        assert_eq!(F::GENERATOR.as_canonical_biguint(), BigUint::new(vec![5]));
304
305        let f_1 = F::new(FFBn254Fr::from_u128(1));
306        let f_1_copy = F::new(FFBn254Fr::from_u128(1));
307
308        let expected_result = F::ZERO;
309        assert_eq!(f_1 - f_1_copy, expected_result);
310
311        let expected_result = F::new(FFBn254Fr::from_u128(2));
312        assert_eq!(f_1 + f_1_copy, expected_result);
313
314        let f_2 = F::new(FFBn254Fr::from_u128(2));
315        let expected_result = F::new(FFBn254Fr::from_u128(3));
316        assert_eq!(f_1 + f_1_copy * f_2, expected_result);
317
318        let expected_result = F::new(FFBn254Fr::from_u128(5));
319        assert_eq!(f_1 + f_2 * f_2, expected_result);
320
321        let f_r_minus_1 = F::new(
322            FFBn254Fr::from_str_vartime(&(F::order() - BigUint::one()).to_str_radix(10)).unwrap(),
323        );
324        let expected_result = F::ZERO;
325        assert_eq!(f_1 + f_r_minus_1, expected_result);
326
327        let f_r_minus_2 = F::new(
328            FFBn254Fr::from_str_vartime(&(F::order() - BigUint::new(vec![2])).to_str_radix(10))
329                .unwrap(),
330        );
331        let expected_result = F::new(
332            FFBn254Fr::from_str_vartime(&(F::order() - BigUint::new(vec![3])).to_str_radix(10))
333                .unwrap(),
334        );
335        assert_eq!(f_r_minus_1 + f_r_minus_2, expected_result);
336
337        let expected_result = F::new(FFBn254Fr::from_u128(1));
338        assert_eq!(f_r_minus_1 - f_r_minus_2, expected_result);
339
340        let expected_result = f_r_minus_1;
341        assert_eq!(f_r_minus_2 - f_r_minus_1, expected_result);
342
343        let expected_result = f_r_minus_2;
344        assert_eq!(f_r_minus_1 - f_1, expected_result);
345
346        let expected_result = F::new(FFBn254Fr::from_u128(3));
347        assert_eq!(f_2 * f_2 - f_1, expected_result);
348
349        // Generator check
350        let expected_multiplicative_group_generator = F::new(FFBn254Fr::from_u128(5));
351        assert_eq!(F::GENERATOR, expected_multiplicative_group_generator);
352
353        let f_serialized = serde_json::to_string(&f).unwrap();
354        let f_deserialized: F = serde_json::from_str(&f_serialized).unwrap();
355        assert_eq!(f, f_deserialized);
356
357        let f_1_serialized = serde_json::to_string(&f_1).unwrap();
358        let f_1_deserialized: F = serde_json::from_str(&f_1_serialized).unwrap();
359        let f_1_serialized_again = serde_json::to_string(&f_1_deserialized).unwrap();
360        let f_1_deserialized_again: F = serde_json::from_str(&f_1_serialized_again).unwrap();
361        assert_eq!(f_1, f_1_deserialized);
362        assert_eq!(f_1, f_1_deserialized_again);
363
364        let f_2_serialized = serde_json::to_string(&f_2).unwrap();
365        let f_2_deserialized: F = serde_json::from_str(&f_2_serialized).unwrap();
366        assert_eq!(f_2, f_2_deserialized);
367
368        let f_r_minus_1_serialized = serde_json::to_string(&f_r_minus_1).unwrap();
369        let f_r_minus_1_deserialized: F = serde_json::from_str(&f_r_minus_1_serialized).unwrap();
370        assert_eq!(f_r_minus_1, f_r_minus_1_deserialized);
371
372        let f_r_minus_2_serialized = serde_json::to_string(&f_r_minus_2).unwrap();
373        let f_r_minus_2_deserialized: F = serde_json::from_str(&f_r_minus_2_serialized).unwrap();
374        assert_eq!(f_r_minus_2, f_r_minus_2_deserialized);
375    }
376
377    test_field!(crate::Bn254Fr);
378}
p3_bn254_fr/lib.rs

p3_bn254_fr/
lib.rs
