mina_poseidon/
sponge.rs

1extern crate alloc;
2use crate::{
3    constants::SpongeConstants,
4    poseidon::{ArithmeticSponge, ArithmeticSpongeParams, Sponge},
5};
6use alloc::{vec, vec::Vec};
7use ark_ec::models::short_weierstrass::{Affine, SWCurveConfig};
8use ark_ff::{BigInteger, Field, One, PrimeField, Zero};
9
10/// Abstracts a sponge operating on a base field `Fq` of the curve
11/// `G`. The parameter `Fr` is modelling the scalar field of the
12/// curve.
13pub trait FqSponge<Fq: Field, G, Fr> {
14    /// Creates a new sponge.
15    fn new(p: &'static ArithmeticSpongeParams<Fq>) -> Self;
16
17    /// Absorbs a base field element. This operation is the most
18    /// straightforward and calls the underlying sponge directly.
19    fn absorb_fq(&mut self, x: &[Fq]);
20
21    /// Absorbs a base field point, that is a pair of `Fq` elements.
22    /// In the case of the point to infinity, the values `(0, 0)` are absorbed.
23    fn absorb_g(&mut self, g: &[G]);
24
25    /// Absorbs an element of the scalar field `Fr` --- it is done
26    /// by converting the element to the base field first.
27    fn absorb_fr(&mut self, x: &[Fr]);
28
29    /// Squeeze out a base field challenge. This operation is the most
30    /// direct and calls the underlying sponge.
31    fn challenge_fq(&mut self) -> Fq;
32
33    /// Squeeze out a challenge in the scalar field. Implemented by
34    /// squeezing out base points and then converting them to a scalar
35    /// field element using binary representation.
36    fn challenge(&mut self) -> Fr;
37
38    /// Returns a base field digest by squeezing the underlying sponge directly.
39    fn digest_fq(self) -> Fq;
40
41    /// Returns a scalar field digest using the binary representation technique.
42    fn digest(self) -> Fr;
43}
44
45pub const CHALLENGE_LENGTH_IN_LIMBS: usize = 2;
46
47const HIGH_ENTROPY_LIMBS: usize = 2;
48
49// TODO: move to a different file / module
50/// A challenge which is used as a scalar on a group element in the verifier
51#[derive(Clone, Debug)]
52pub struct ScalarChallenge<F>(pub F);
53
54pub fn endo_coefficient<F: PrimeField>() -> F {
55    let p_minus_1_over_3 = (F::zero() - F::one()) / F::from(3u64);
56
57    F::GENERATOR.pow(p_minus_1_over_3.into_bigint().as_ref())
58}
59
60fn get_bit(limbs_lsb: &[u64], i: u64) -> u64 {
61    let limb = i / 64;
62    let j = i % 64;
63    (limbs_lsb[limb as usize] >> j) & 1
64}
65
66impl<F: PrimeField> ScalarChallenge<F> {
67    pub fn to_field_with_length(&self, length_in_bits: usize, endo_coeff: &F) -> F {
68        let rep = self.0.into_bigint();
69        let r = rep.as_ref();
70
71        let mut a: F = 2_u64.into();
72        let mut b: F = 2_u64.into();
73
74        let one = F::one();
75        let neg_one = -one;
76
77        for i in (0..(length_in_bits as u64 / 2)).rev() {
78            a.double_in_place();
79            b.double_in_place();
80
81            let r_2i = get_bit(r, 2 * i);
82            let s = if r_2i == 0 { &neg_one } else { &one };
83
84            if get_bit(r, 2 * i + 1) == 0 {
85                b += s;
86            } else {
87                a += s;
88            }
89        }
90
91        a * endo_coeff + b
92    }
93
94    pub fn to_field(&self, endo_coeff: &F) -> F {
95        let length_in_bits = 64 * CHALLENGE_LENGTH_IN_LIMBS;
96        self.to_field_with_length(length_in_bits, endo_coeff)
97    }
98}
99
100#[derive(Clone)]
101pub struct DefaultFqSponge<P: SWCurveConfig, SC: SpongeConstants> {
102    pub sponge: ArithmeticSponge<P::BaseField, SC>,
103    pub last_squeezed: Vec<u64>,
104}
105
106pub struct DefaultFrSponge<Fr: Field, SC: SpongeConstants> {
107    pub sponge: ArithmeticSponge<Fr, SC>,
108    pub last_squeezed: Vec<u64>,
109}
110
111fn pack<B: BigInteger>(limbs_lsb: &[u64]) -> B {
112    let mut res: B = 0u64.into();
113    for &x in limbs_lsb.iter().rev() {
114        res.muln(64);
115        res.add_with_carry(&x.into());
116    }
117    res
118}
119
120impl<Fr: PrimeField, SC: SpongeConstants> DefaultFrSponge<Fr, SC> {
121    pub fn squeeze(&mut self, num_limbs: usize) -> Fr {
122        if self.last_squeezed.len() >= num_limbs {
123            let last_squeezed = self.last_squeezed.clone();
124            let (limbs, remaining) = last_squeezed.split_at(num_limbs);
125            self.last_squeezed = remaining.to_vec();
126            Fr::from(pack::<Fr::BigInt>(limbs))
127        } else {
128            let x = self.sponge.squeeze().into_bigint();
129            self.last_squeezed
130                .extend(&x.as_ref()[0..HIGH_ENTROPY_LIMBS]);
131            self.squeeze(num_limbs)
132        }
133    }
134}
135
136impl<P: SWCurveConfig, SC: SpongeConstants> DefaultFqSponge<P, SC>
137where
138    P::BaseField: PrimeField,
139    <P::BaseField as PrimeField>::BigInt: Into<<P::ScalarField as PrimeField>::BigInt>,
140{
141    pub fn squeeze_limbs(&mut self, num_limbs: usize) -> Vec<u64> {
142        if self.last_squeezed.len() >= num_limbs {
143            let last_squeezed = self.last_squeezed.clone();
144            let (limbs, remaining) = last_squeezed.split_at(num_limbs);
145            self.last_squeezed = remaining.to_vec();
146            limbs.to_vec()
147        } else {
148            let x = self.sponge.squeeze().into_bigint();
149            self.last_squeezed
150                .extend(&x.as_ref()[0..HIGH_ENTROPY_LIMBS]);
151            self.squeeze_limbs(num_limbs)
152        }
153    }
154
155    pub fn squeeze_field(&mut self) -> P::BaseField {
156        self.last_squeezed = vec![];
157        self.sponge.squeeze()
158    }
159
160    pub fn squeeze(&mut self, num_limbs: usize) -> P::ScalarField {
161        P::ScalarField::from_bigint(pack(&self.squeeze_limbs(num_limbs)))
162            .expect("internal representation was not a valid field element")
163    }
164}
165
166impl<P: SWCurveConfig, SC: SpongeConstants> FqSponge<P::BaseField, Affine<P>, P::ScalarField>
167    for DefaultFqSponge<P, SC>
168where
169    P::BaseField: PrimeField,
170    <P::BaseField as PrimeField>::BigInt: Into<<P::ScalarField as PrimeField>::BigInt>,
171{
172    fn new(params: &'static ArithmeticSpongeParams<P::BaseField>) -> DefaultFqSponge<P, SC> {
173        let sponge = ArithmeticSponge::new(params);
174        DefaultFqSponge {
175            sponge,
176            last_squeezed: vec![],
177        }
178    }
179
180    fn absorb_g(&mut self, g: &[Affine<P>]) {
181        self.last_squeezed = vec![];
182        for g in g.iter() {
183            if g.infinity {
184                // absorb a fake point (0, 0)
185                let zero = P::BaseField::zero();
186                self.sponge.absorb(&[zero]);
187                self.sponge.absorb(&[zero]);
188            } else {
189                self.sponge.absorb(&[g.x]);
190                self.sponge.absorb(&[g.y]);
191            }
192        }
193    }
194
195    fn absorb_fq(&mut self, x: &[P::BaseField]) {
196        self.last_squeezed = vec![];
197
198        for fe in x {
199            self.sponge.absorb(&[*fe])
200        }
201    }
202
203    fn absorb_fr(&mut self, x: &[P::ScalarField]) {
204        self.last_squeezed = vec![];
205
206        x.iter().for_each(|x| {
207            let bits = x.into_bigint().to_bits_le();
208
209            // absorb
210            if <P::ScalarField as PrimeField>::MODULUS
211                < <P::BaseField as PrimeField>::MODULUS.into()
212            {
213                let fe = P::BaseField::from_bigint(
214                    <P::BaseField as PrimeField>::BigInt::from_bits_le(&bits),
215                )
216                .expect("padding code has a bug");
217                self.sponge.absorb(&[fe]);
218            } else {
219                let low_bit = if bits[0] {
220                    P::BaseField::one()
221                } else {
222                    P::BaseField::zero()
223                };
224
225                let high_bits = P::BaseField::from_bigint(
226                    <P::BaseField as PrimeField>::BigInt::from_bits_le(&bits[1..bits.len()]),
227                )
228                .expect("padding code has a bug");
229
230                self.sponge.absorb(&[high_bits]);
231                self.sponge.absorb(&[low_bit]);
232            }
233        });
234    }
235
236    fn digest(mut self) -> P::ScalarField {
237        let x: <P::BaseField as PrimeField>::BigInt = self.squeeze_field().into_bigint();
238        // Returns zero for values that are too large.
239        // This means that there is a bias for the value zero (in one of the curve).
240        // An attacker could try to target that seed, in order to predict the challenges u and v produced by the Fr-Sponge.
241        // This would allow the attacker to mess with the result of the aggregated evaluation proof.
242        // Previously the attacker's odds were 1/q, now it's (q-p)/q.
243        // Since log2(q-p) ~ 86 and log2(q) ~ 254 the odds of a successful attack are negligible.
244        P::ScalarField::from_bigint(x.into()).unwrap_or_else(P::ScalarField::zero)
245    }
246
247    fn digest_fq(mut self) -> P::BaseField {
248        self.squeeze_field()
249    }
250
251    fn challenge(&mut self) -> P::ScalarField {
252        self.squeeze(CHALLENGE_LENGTH_IN_LIMBS)
253    }
254
255    fn challenge_fq(&mut self) -> P::BaseField {
256        self.squeeze_field()
257    }
258}
259
260//
261// OCaml types
262//
263
264#[cfg(feature = "ocaml_types")]
265pub mod caml {
266    use super::*;
267
268    extern crate alloc;
269    use alloc::{
270        format,
271        string::{String, ToString},
272    };
273
274    //
275    // ScalarChallenge<F> <-> CamlScalarChallenge<CamlF>
276    //
277
278    #[derive(Debug, Clone, ocaml::IntoValue, ocaml::FromValue, ocaml_gen::Struct)]
279    pub struct CamlScalarChallenge<CamlF>(pub CamlF);
280
281    impl<F, CamlF> From<ScalarChallenge<F>> for CamlScalarChallenge<CamlF>
282    where
283        CamlF: From<F>,
284    {
285        fn from(sc: ScalarChallenge<F>) -> Self {
286            Self(sc.0.into())
287        }
288    }
289
290    impl<F, CamlF> From<CamlScalarChallenge<CamlF>> for ScalarChallenge<F>
291    where
292        CamlF: Into<F>,
293    {
294        fn from(caml_sc: CamlScalarChallenge<CamlF>) -> Self {
295            Self(caml_sc.0.into())
296        }
297    }
298}
mina_poseidon/sponge.rs

mina_poseidon/
sponge.rs
