decaf377/fields/fr/
arkworks.rs

1use super::Fr;
2use ark_ff::{BigInt, Field, PrimeField, SqrtPrecomputation};
3use ark_ff::{BigInteger, FftField};
4use ark_serialize::{
5    CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
6    CanonicalSerializeWithFlags, Compress, EmptyFlags, Flags, SerializationError, Valid, Validate,
7};
8use ark_std::{rand, str::FromStr, string::ToString, One, Zero};
9use core::convert::TryInto;
10use core::{
11    fmt::{Display, Formatter},
12    iter,
13};
14
15impl PrimeField for Fr {
16    /// A `BigInteger` type that can represent elements of this field.
17    type BigInt = BigInt<4>;
18
19    /// The Decaf377 scalar field modulus `r` = 0x4aad957a68b2955982d1347970dec005293a3afc43c8afeb95aee9ac33fd9ff
20    const MODULUS: Self::BigInt = ark_ff::BigInt(Self::MODULUS_LIMBS);
21
22    /// The value `(p - 1)/ 2`.
23    const MODULUS_MINUS_ONE_DIV_TWO: Self::BigInt = BigInt(Self::MODULUS_MINUS_ONE_DIV_TWO_LIMBS);
24
25    /// The size of the modulus in bits.
26    const MODULUS_BIT_SIZE: u32 = Self::MODULUS_BIT_SIZE;
27
28    /// The trace of the field is defined as the smallest integer `t` such that by
29    /// `2^s * t = p - 1`, and `t` is coprime to 2.
30    const TRACE: Self::BigInt = BigInt(Self::TRACE_LIMBS);
31
32    /// The value `(t - 1)/ 2`.
33    const TRACE_MINUS_ONE_DIV_TWO: Self::BigInt = BigInt(Self::TRACE_MINUS_ONE_DIV_TWO_LIMBS);
34
35    fn from_bigint(repr: Self::BigInt) -> Option<Self> {
36        if repr >= Fr::MODULUS {
37            None
38        } else {
39            // Assuming BigInt is little endian
40            Some(Self::from_le_limbs(repr.0))
41        }
42    }
43
44    fn into_bigint(self) -> Self::BigInt {
45        BigInt(self.to_le_limbs())
46    }
47
48    fn from_be_bytes_mod_order(bytes: &[u8]) -> Self {
49        let mut bytes_copy = bytes.to_vec();
50        bytes_copy.reverse();
51        Self::from_le_bytes_mod_order(&bytes_copy)
52    }
53
54    fn from_le_bytes_mod_order(bytes: &[u8]) -> Self {
55        Self::from_le_bytes_mod_order(bytes)
56    }
57}
58
59impl Field for Fr {
60    type BasePrimeField = Self;
61    type BasePrimeFieldIter = iter::Once<Self::BasePrimeField>;
62
63    const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>> = Some(SqrtPrecomputation::Case3Mod4 {
64        modulus_plus_one_div_four: &[
65            12562434535201961600,
66            1487569876998365887,
67            7353046484906113792,
68            84080023168010837,
69        ],
70    });
71
72    const ZERO: Self = Self::ZERO;
73
74    // Montomgery representation of one
75    const ONE: Self = Self::ONE;
76
77    fn extension_degree() -> u64 {
78        1
79    }
80
81    fn to_base_prime_field_elements(&self) -> Self::BasePrimeFieldIter {
82        iter::once(*self)
83    }
84
85    fn from_base_prime_field_elems(elems: &[Self::BasePrimeField]) -> Option<Self> {
86        if elems.len() != (Self::extension_degree() as usize) {
87            return None;
88        }
89        Some(elems[0])
90    }
91
92    fn from_base_prime_field(elem: Self::BasePrimeField) -> Self {
93        elem
94    }
95
96    fn double(&self) -> Self {
97        self.add(self)
98    }
99
100    fn double_in_place(&mut self) -> &mut Self {
101        *self = self.add(self);
102        self
103    }
104
105    fn neg_in_place(&mut self) -> &mut Self {
106        *self = Self::ZERO.sub(self);
107        self
108    }
109
110    fn from_random_bytes_with_flags<F: ark_serialize::Flags>(bytes: &[u8]) -> Option<(Self, F)> {
111        Some((Self::from_le_bytes_mod_order(bytes), F::default()))
112    }
113
114    fn legendre(&self) -> ark_ff::LegendreSymbol {
115        use ark_ff::LegendreSymbol::*;
116
117        if self.is_zero() {
118            return Zero;
119        }
120        if self.pow(&Self::MODULUS_MINUS_ONE_DIV_TWO.0).is_one() {
121            return QuadraticResidue;
122        }
123        return QuadraticNonResidue;
124    }
125
126    fn square(&self) -> Self {
127        self.square()
128    }
129
130    fn square_in_place(&mut self) -> &mut Self {
131        *self = self.square();
132        self
133    }
134
135    fn inverse(&self) -> Option<Self> {
136        self.inverse()
137    }
138
139    fn inverse_in_place(&mut self) -> Option<&mut Self> {
140        if let Some(inverse) = self.inverse() {
141            *self = inverse;
142            Some(self)
143        } else {
144            None
145        }
146    }
147
148    fn frobenius_map_in_place(&mut self, _power: usize) {
149        // Because this is a prime field, we don't need to do anything,
150        // the automorphism is trivial.
151    }
152
153    fn characteristic() -> &'static [u64] {
154        &Self::MODULUS_LIMBS
155    }
156}
157
158impl FftField for Fr {
159    const GENERATOR: Self = Self::MULTIPLICATIVE_GENERATOR;
160    const TWO_ADICITY: u32 = Self::TWO_ADICITY;
161    const TWO_ADIC_ROOT_OF_UNITY: Self = Self::TWO_ADIC_ROOT_OF_UNITY;
162    const SMALL_SUBGROUP_BASE: Option<u32> = None;
163    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
164    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = None;
165}
166
167impl Zero for Fr {
168    #[inline]
169    fn zero() -> Self {
170        Fr::ZERO
171    }
172
173    #[inline]
174    fn is_zero(&self) -> bool {
175        *self == Fr::ZERO
176    }
177}
178
179impl One for Fr {
180    #[inline]
181    fn one() -> Self {
182        Fr::ONE
183    }
184
185    #[inline]
186    fn is_one(&self) -> bool {
187        *self == Fr::ONE
188    }
189}
190impl CanonicalDeserializeWithFlags for Fr {
191    fn deserialize_with_flags<R: ark_std::io::Read, F: Flags>(
192        mut reader: R,
193    ) -> Result<(Self, F), SerializationError> {
194        // Enough for the field element + 8 bits of flags. The last byte may or may not contain flags.
195        let mut bytes = [0u8; (Self::MODULUS_BIT_SIZE as usize + 7) / 8];
196
197        let expected_len = (Self::MODULUS_BIT_SIZE as usize + F::BIT_SIZE + 7) / 8;
198        reader.read_exact(&mut bytes[..expected_len])?;
199        let flags = F::from_u8_remove_flags(&mut bytes[bytes.len() - 1])
200            .ok_or(SerializationError::UnexpectedFlags)?;
201        // Then, convert the bytes to limbs, to benefit from the canonical check we have for
202        // bigint.
203        let mut limbs = [0u64; 4];
204        for (limb, chunk) in limbs.iter_mut().zip(bytes[..32].chunks_exact(8)) {
205            *limb = u64::from_le_bytes(chunk.try_into().expect("chunk will have the right size"));
206        }
207        let out = Self::from_bigint(BigInt(limbs)).ok_or(SerializationError::InvalidData)?;
208        Ok((out, flags))
209    }
210}
211
212impl Valid for Fr {
213    fn check(&self) -> Result<(), SerializationError> {
214        Ok(())
215    }
216}
217
218impl CanonicalDeserialize for Fr {
219    fn deserialize_with_mode<R: ark_std::io::Read>(
220        reader: R,
221        _compress: Compress,
222        validate: Validate,
223    ) -> Result<Self, SerializationError> {
224        let (out, _) = Self::deserialize_with_flags::<R, EmptyFlags>(reader)?;
225        match validate {
226            Validate::Yes => out.check(),
227            Validate::No => Ok(()),
228        }?;
229        Ok(out)
230    }
231}
232
233impl CanonicalSerialize for Fr {
234    #[inline]
235    fn serialize_with_mode<W: ark_std::io::Write>(
236        &self,
237        writer: W,
238        _compress: Compress,
239    ) -> Result<(), SerializationError> {
240        self.serialize_with_flags(writer, EmptyFlags)
241    }
242
243    #[inline]
244    fn serialized_size(&self, _compress: Compress) -> usize {
245        self.serialized_size_with_flags::<EmptyFlags>()
246    }
247}
248
249impl CanonicalSerializeWithFlags for Fr {
250    fn serialize_with_flags<W: ark_std::io::Write, F: Flags>(
251        &self,
252        mut writer: W,
253        flags: F,
254    ) -> Result<(), SerializationError> {
255        // Arkworks imposes this constraint
256        if F::BIT_SIZE > 8 {
257            return Err(SerializationError::NotEnoughSpace);
258        }
259
260        // We can't just write the bytes out, because the last byte might be masked by flags.
261        let mut bytes = self.to_bytes_le();
262        // Either the flags fit into the last byte...
263        if bytes.len() == self.serialized_size_with_flags::<F>() {
264            // In which case we have to mask the last byte
265            bytes[bytes.len() - 1] |= flags.u8_bitmask();
266            writer.write_all(&bytes)?;
267        } else {
268            // Or else we create a new byte
269            writer.write_all(&bytes)?;
270            writer.write_all(&[flags.u8_bitmask()])?;
271        }
272        Ok(())
273    }
274
275    fn serialized_size_with_flags<F: Flags>(&self) -> usize {
276        (Self::MODULUS_BIT_SIZE as usize + F::BIT_SIZE + 7) / 8
277    }
278}
279
280impl ark_std::rand::distributions::Distribution<Fr> for ark_std::rand::distributions::Standard {
281    fn sample<R: rand::prelude::Rng + ?Sized>(&self, rng: &mut R) -> Fr {
282        loop {
283            let mut repr: [u64; 4] = rng.sample(ark_std::rand::distributions::Standard);
284            let shave_bits = 64 * 4 - (Fr::MODULUS_BIT_SIZE as usize);
285            // Mask away the unused bits at the beginning.
286            let mask = if shave_bits == 64 {
287                0
288            } else {
289                u64::MAX >> shave_bits
290            };
291
292            if let Some(val) = repr.last_mut() {
293                *val &= mask
294            }
295
296            if let Some(small_enough) = Fr::from_bigint(BigInt(repr)) {
297                return small_enough;
298            }
299        }
300    }
301}
302
303impl Display for Fr {
304    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
305        let string = self.into_bigint().to_string();
306        write!(f, "{}", string.trim_start_matches('0'))
307    }
308}
309
310impl FromStr for Fr {
311    type Err = ();
312
313    fn from_str(s: &str) -> Result<Self, Self::Err> {
314        ark_std::dbg!(&s);
315        // CANDO: a more efficient method accumulating into 64 bits first.
316        let mut acc = Self::zero();
317
318        let ten = Self::from(10u8);
319
320        for c in s.chars() {
321            match c.to_digit(10) {
322                Some(c) => {
323                    acc = ten * acc + Self::from(u64::from(c));
324                }
325                None => {
326                    return Err(());
327                }
328            }
329        }
330        Ok(acc)
331    }
332}
333
334impl From<num_bigint::BigUint> for Fr {
335    #[inline]
336    fn from(val: num_bigint::BigUint) -> Fr {
337        Fr::from_le_bytes_mod_order(&val.to_bytes_le())
338    }
339}
340
341impl From<Fr> for num_bigint::BigUint {
342    #[inline(always)]
343    fn from(other: Fr) -> Self {
344        other.into_bigint().into()
345    }
346}
347
348impl From<Fr> for BigInt<4> {
349    #[inline(always)]
350    fn from(fr: Fr) -> Self {
351        fr.into_bigint()
352    }
353}
354
355impl From<BigInt<4>> for Fr {
356    /// Converts `Self::BigInteger` into `Self`
357    #[inline(always)]
358    fn from(int: BigInt<4>) -> Self {
359        Fr::from_le_bytes_mod_order(&int.to_bytes_le())
360    }
361}
362
363#[cfg(test)]
364mod tests {
365    use super::*;
366    extern crate alloc;
367    use alloc::{format, vec::Vec};
368    use proptest::prelude::*;
369
370    prop_compose! {
371        // Technically this might overflow, but we won't miss any values,
372        // just return 0 if you overflow when consuming.
373        fn arb_fr_limbs()(
374            z0 in 0..u64::MAX,
375            z1 in 0..u64::MAX,
376            z2 in 0..u64::MAX,
377            z3 in 0..336320092672043349u64
378        ) -> [u64; 4] {
379            [z0, z1, z2, z3]
380        }
381    }
382
383    prop_compose! {
384        fn arb_fr()(a in arb_fr_limbs()) -> Fr {
385            // Will be fine because of the bounds in the arb_fr_limbs
386            Fr::from_bigint(BigInt(a)).unwrap_or(Fr::zero())
387        }
388    }
389
390    prop_compose! {
391        fn arb_nonzero_fr()(a in arb_fr()) -> Fr {
392            if a == Fr::zero() { Fr::one() } else { a }
393        }
394    }
395
396    proptest! {
397        #[test]
398        fn test_addition_commutative(a in arb_fr(), b in arb_fr()) {
399            assert_eq!(a + b, b + a);
400        }
401    }
402
403    proptest! {
404        #[test]
405        fn test_addition_associative(a in arb_fr(), b in arb_fr(), c in arb_fr()) {
406            assert_eq!(a + (b + c), (a + b) + c);
407        }
408    }
409
410    proptest! {
411        #[test]
412        fn test_add_zero_identity(a in arb_fr()) {
413            let zero = Fr::zero();
414
415            assert_eq!(a + zero, a);
416            assert_eq!(zero + a, a);
417        }
418    }
419
420    proptest! {
421        #[test]
422        fn test_subtract_self_is_zero(a in arb_fr()) {
423            let zero = Fr::zero();
424
425            assert_eq!(a - a, zero);
426        }
427    }
428
429    proptest! {
430        #[test]
431        fn test_doubling_is_just_addition(a in arb_fr()) {
432            let two = Fr::from(2u64);
433
434            assert_eq!(two * a, a + a);
435            assert_eq!(a.double(), a + a);
436            assert_eq!(*(a.clone().double_in_place()), a + a);
437        }
438    }
439
440    proptest! {
441        #[test]
442        fn test_adding_negation(a in arb_fr()) {
443            assert_eq!(a + -a, Fr::ZERO)
444        }
445    }
446
447    proptest! {
448        #[test]
449        fn test_multiplication_commutative(a in arb_fr(), b in arb_fr()) {
450            assert_eq!(a * b, b * a);
451        }
452    }
453
454    proptest! {
455        #[test]
456        fn test_multiplication_associative(a in arb_fr(), b in arb_fr(), c in arb_fr()) {
457            assert_eq!(a * (b * c), (a * b) * c);
458        }
459    }
460
461    proptest! {
462        #[test]
463        fn test_multiplication_distributive(a in arb_fr(), b in arb_fr(), c in arb_fr()) {
464            assert_eq!(a * (b + c), a * b + a * c);
465        }
466    }
467
468    proptest! {
469        #[test]
470        fn test_multiply_one_identity(a in arb_fr()) {
471            assert_eq!(a * Fr::ONE, a);
472            assert_eq!(Fr::ONE * a, a);
473        }
474    }
475
476    proptest! {
477        #[test]
478        fn test_multiply_minus_one_is_negation(a in arb_fr()) {
479            let minus_one = -Fr::ONE;
480
481            assert_eq!(a * minus_one, a.neg());
482        }
483    }
484
485    proptest! {
486        #[test]
487        fn test_square_is_multiply(a in arb_fr()) {
488            assert_eq!(a.square(), a * a);
489            assert_eq!(*(a.clone().square_in_place()), a * a);
490        }
491    }
492
493    proptest! {
494        #[test]
495        fn test_inverse(a in arb_nonzero_fr()) {
496            assert_eq!(a * a.inverse().unwrap(), Fr::ONE);
497            assert_eq!(a * *(a.clone().inverse_in_place().unwrap()), Fr::ONE);
498        }
499    }
500
501    fn naive_inverse(a: Fr) -> Fr {
502        a.pow(&(-Fr::from(2u64)).into_bigint().0)
503    }
504
505    proptest! {
506        #[test]
507        fn test_inverse_vs_naive_inverse(a in arb_nonzero_fr()) {
508            assert_eq!(a.inverse().unwrap(), naive_inverse(a));
509        }
510    }
511
512    proptest! {
513        #[test]
514        fn test_sqrt(a in arb_fr()) {
515            match a.sqrt() {
516                Some(x) => assert_eq!(x * x, a),
517                None => {}
518            }
519        }
520    }
521
522    proptest! {
523        #[test]
524        fn test_into_bigint_monomorphism(a in arb_fr()) {
525            let as_bigint = a.into_bigint();
526            let roundtrip = Fr::from_bigint(as_bigint);
527
528            assert_eq!(Some(a), roundtrip);
529        }
530    }
531
532    proptest! {
533        #[test]
534        fn test_conversion_to_bytes_via_bigint(a in arb_fr()) {
535            let way1 = a.to_bytes_le();
536            let way2 = a.into_bigint().to_bytes_le();
537            assert_eq!(way1.as_slice(), way2.as_slice());
538        }
539    }
540
541    proptest! {
542        #[test]
543        fn test_legendre_symbol(a in arb_nonzero_fr()) {
544            assert_eq!((a * a).legendre(), ark_ff::LegendreSymbol::QuadraticResidue);
545        }
546    }
547
548    proptest! {
549        #[test]
550        fn test_canonical_serialize_monomorphism(a in arb_fr()) {
551            let mut bytes: Vec<u8> = Vec::new();
552            let roundtrip = a.serialize_compressed(&mut bytes).and_then(|_| Fr::deserialize_compressed(&*bytes));
553            assert!(roundtrip.is_ok());
554            assert_eq!(*roundtrip.as_ref().clone().unwrap(), a);
555        }
556    }
557
558    fn naive_from_le_bytes_mod_order(bytes: &[u8]) -> Fr {
559        let mut acc = Fr::zero();
560        let mut insert = Fr::one();
561        for byte in bytes {
562            for i in 0..8 {
563                if (byte >> i) & 1 == 1 {
564                    acc += insert;
565                }
566                insert.double_in_place();
567            }
568        }
569        acc
570    }
571
572    proptest! {
573        #[test]
574        fn test_from_le_bytes_mod_order_vs_naive(bytes in any::<[u8; 80]>()) {
575            let way1 = Fr::from_le_bytes_mod_order(&bytes);
576            let way2 = naive_from_le_bytes_mod_order(&bytes);
577            assert_eq!(way1, way2);
578        }
579    }
580
581    proptest! {
582        #[test]
583        fn test_from_str(a in arb_fr()) {
584            let x = <Fr as PrimeField>::BigInt::from(a);
585            assert_eq!(Ok(a), Fr::from_str(&format!("{}", x)));
586        }
587    }
588
589    #[test]
590    fn test_from_le_bytes_mod_order_examples() {
591        let p_plus_1_bytes: [u8; 32] = [
592            0, 218, 63, 195, 154, 238, 90, 185, 254, 138, 60, 196, 175, 163, 147, 82, 0, 236, 13,
593            151, 71, 19, 45, 152, 85, 41, 139, 166, 87, 217, 170, 4,
594        ];
595        let bytes_for_1 = {
596            let mut out = [0u8; 32];
597            out[0] = 1;
598            out
599        };
600        assert_eq!(Fr::from_le_bytes_mod_order(&p_plus_1_bytes), Fr::one());
601        assert_eq!(
602            Fr::from_le_bytes_mod_order(&p_plus_1_bytes).to_bytes_le(),
603            bytes_for_1
604        );
605    }
606
607    #[test]
608    fn test_addition_examples() {
609        let z1: Fr = BigInt([1, 1, 1, 1]).into();
610        let z2: Fr = BigInt([2, 2, 2, 2]).into();
611        let z3: Fr = BigInt([3, 3, 3, 3]).into();
612
613        assert_eq!(z3, z1 + z2);
614    }
615
616    #[test]
617    fn test_subtraction_examples() {
618        let mut z1: Fr = BigInt([1, 1, 1, 1]).into();
619        z1 -= z1;
620
621        assert_eq!(z1, Fr::ZERO);
622    }
623
624    #[test]
625    fn test_small_multiplication_examples() {
626        let z1: Fr = BigInt([1, 0, 0, 0]).into();
627        let z2: Fr = BigInt([2, 0, 0, 0]).into();
628        let z3: Fr = BigInt([3, 0, 0, 0]).into();
629
630        assert_eq!(z1 + z1, z1 * z2);
631        assert_eq!(z1 + z1 + z1, z1 * z3);
632    }
633
634    #[test]
635    fn test_2192_times_zero() {
636        let two192: Fr = BigInt([0, 0, 0, 1]).into();
637        assert_eq!(two192 * Fr::zero(), Fr::ZERO);
638    }
639
640    #[test]
641    fn test_minus_one_squared() {
642        let minus_one = Fr::zero() - Fr::one();
643        assert_eq!(minus_one.square(), Fr::ONE);
644    }
645
646    #[test]
647    fn test_modulus_from_le_bytes_mod_order() {
648        // Field modulus - 1 in non-montgomery form that satisfies the fiat-crypto preconditions (< m)
649        let modulus_minus_one: Fr = BigInt([
650            13356249993388743166,
651            5950279507993463550,
652            10965441865914903552,
653            336320092672043349,
654        ])
655        .into();
656
657        assert_eq!(modulus_minus_one, -Fr::one());
658    }
659}
decaf377/fields/fr/arkworks.rs

decaf377/fields/fr/
arkworks.rs
