sonobe_primitives/transcripts/griffin/
sponge.rs

1//! Implementation of transcript traits for Griffin sponge.
2
3use ark_crypto_primitives::sponge::DuplexSpongeMode;
4use ark_ff::PrimeField;
5use ark_r1cs_std::fields::{FieldVar, fp::FpVar};
6use ark_relations::gr1cs::SynthesisError;
7use ark_std::sync::Arc;
8
9use crate::transcripts::{
10    AbsorbableVar, Transcript, TranscriptGadget,
11    griffin::{Griffin, GriffinGadget, GriffinParams},
12};
13
14/// [`GriffinSponge`] is a duplex sponge built on the Griffin permutation.
15///
16/// The implementation mirrors arkworks' [`ark_crypto_primitives::sponge::poseidon::PoseidonSponge`].
17#[derive(Clone)]
18pub struct GriffinSponge<F: PrimeField> {
19    params: Arc<GriffinParams<F>>,
20    state: Vec<F>,
21    mode: DuplexSpongeMode,
22}
23
24impl<F: PrimeField> GriffinSponge<F> {
25    fn permute(&mut self) {
26        Griffin::permute(&self.params, &mut self.state);
27    }
28
29    // Absorbs everything in elements, this does not end in an absorption.
30    fn absorb_internal(&mut self, mut rate_start_index: usize, elements: &[F]) {
31        let mut remaining_elements = elements;
32
33        loop {
34            // if we can finish in this call
35            if rate_start_index + remaining_elements.len() <= self.params.rate {
36                for (i, element) in remaining_elements.iter().enumerate() {
37                    self.state[self.params.capacity + i + rate_start_index] += element;
38                }
39                self.mode = DuplexSpongeMode::Absorbing {
40                    next_absorb_index: rate_start_index + remaining_elements.len(),
41                };
42
43                return;
44            }
45            // otherwise absorb (rate - rate_start_index) elements
46            let num_elements_absorbed = self.params.rate - rate_start_index;
47            for (i, element) in remaining_elements
48                .iter()
49                .enumerate()
50                .take(num_elements_absorbed)
51            {
52                self.state[self.params.capacity + i + rate_start_index] += element;
53            }
54            self.permute();
55            // the input elements got truncated by num elements absorbed
56            remaining_elements = &remaining_elements[num_elements_absorbed..];
57            rate_start_index = 0;
58        }
59    }
60
61    // Squeeze |output| many elements. This does not end in a squeeze
62    fn squeeze_internal(&mut self, mut rate_start_index: usize, output: &mut [F]) {
63        let mut output_remaining = output;
64        loop {
65            // if we can finish in this call
66            if rate_start_index + output_remaining.len() <= self.params.rate {
67                output_remaining.clone_from_slice(
68                    &self.state[self.params.capacity + rate_start_index
69                        ..(self.params.capacity + output_remaining.len() + rate_start_index)],
70                );
71                self.mode = DuplexSpongeMode::Squeezing {
72                    next_squeeze_index: rate_start_index + output_remaining.len(),
73                };
74                return;
75            }
76            // otherwise squeeze (rate - rate_start_index) elements
77            let num_elements_squeezed = self.params.rate - rate_start_index;
78            output_remaining[..num_elements_squeezed].clone_from_slice(
79                &self.state[self.params.capacity + rate_start_index
80                    ..(self.params.capacity + num_elements_squeezed + rate_start_index)],
81            );
82
83            // Repeat with updated output slices
84            output_remaining = &mut output_remaining[num_elements_squeezed..];
85            // Unless we are done with squeezing in this call, permute.
86            if !output_remaining.is_empty() {
87                self.permute();
88            }
89
90            rate_start_index = 0;
91        }
92    }
93}
94
95/// [`GriffinSpongeVar`] is the in-circuit variable of [`GriffinSponge`].
96///
97/// The implementation mirrors arkworks' [`ark_crypto_primitives::sponge::poseidon::constraints::PoseidonSpongeVar`].
98#[derive(Clone)]
99pub struct GriffinSpongeVar<F: PrimeField> {
100    params: Arc<GriffinParams<F>>,
101    state: Vec<FpVar<F>>,
102    mode: DuplexSpongeMode,
103}
104
105impl<F: PrimeField> GriffinSpongeVar<F> {
106    fn permute(&mut self) -> Result<(), SynthesisError> {
107        self.state = GriffinGadget::permute(&self.params, &self.state)?;
108        Ok(())
109    }
110
111    fn absorb_internal(
112        &mut self,
113        mut rate_start_index: usize,
114        elements: &[FpVar<F>],
115    ) -> Result<(), SynthesisError> {
116        let mut remaining_elements = elements;
117        loop {
118            // if we can finish in this call
119            if rate_start_index + remaining_elements.len() <= self.params.rate {
120                for (i, element) in remaining_elements.iter().enumerate() {
121                    self.state[self.params.capacity + i + rate_start_index] += element;
122                }
123                self.mode = DuplexSpongeMode::Absorbing {
124                    next_absorb_index: rate_start_index + remaining_elements.len(),
125                };
126
127                return Ok(());
128            }
129            // otherwise absorb (rate - rate_start_index) elements
130            let num_elements_absorbed = self.params.rate - rate_start_index;
131            for (i, element) in remaining_elements
132                .iter()
133                .enumerate()
134                .take(num_elements_absorbed)
135            {
136                self.state[self.params.capacity + i + rate_start_index] += element;
137            }
138            self.permute()?;
139            // the input elements got truncated by num elements absorbed
140            remaining_elements = &remaining_elements[num_elements_absorbed..];
141            rate_start_index = 0;
142        }
143    }
144
145    // Squeeze |output| many elements. This does not end in a squeeze
146    fn squeeze_internal(
147        &mut self,
148        mut rate_start_index: usize,
149        output: &mut [FpVar<F>],
150    ) -> Result<(), SynthesisError> {
151        let mut remaining_output = output;
152        loop {
153            // if we can finish in this call
154            if rate_start_index + remaining_output.len() <= self.params.rate {
155                remaining_output.clone_from_slice(
156                    &self.state[self.params.capacity + rate_start_index
157                        ..(self.params.capacity + remaining_output.len() + rate_start_index)],
158                );
159                self.mode = DuplexSpongeMode::Squeezing {
160                    next_squeeze_index: rate_start_index + remaining_output.len(),
161                };
162                return Ok(());
163            }
164            // otherwise squeeze (rate - rate_start_index) elements
165            let num_elements_squeezed = self.params.rate - rate_start_index;
166            remaining_output[..num_elements_squeezed].clone_from_slice(
167                &self.state[self.params.capacity + rate_start_index
168                    ..(self.params.capacity + num_elements_squeezed + rate_start_index)],
169            );
170
171            // Repeat with updated output slices and rate start index
172            remaining_output = &mut remaining_output[num_elements_squeezed..];
173
174            // Unless we are done with squeezing in this call, permute.
175            if !remaining_output.is_empty() {
176                self.permute()?;
177            }
178            rate_start_index = 0;
179        }
180    }
181}
182
183impl<F: PrimeField> Transcript<F> for GriffinSponge<F> {
184    type Config = Arc<GriffinParams<F>>;
185    type Gadget = GriffinSpongeVar<F>;
186
187    fn new(parameters: Arc<GriffinParams<F>>) -> Self {
188        let state = vec![F::zero(); parameters.rate + parameters.capacity];
189        let mode = DuplexSpongeMode::Absorbing {
190            next_absorb_index: 0,
191        };
192
193        Self {
194            params: parameters.clone(),
195            state,
196            mode,
197        }
198    }
199
200    fn add_field_elements(&mut self, elems: &[F]) -> &mut Self {
201        if elems.is_empty() {
202            return self;
203        }
204
205        match self.mode {
206            DuplexSpongeMode::Absorbing { next_absorb_index } => {
207                let mut absorb_index = next_absorb_index;
208                if absorb_index == self.params.rate {
209                    self.permute();
210                    absorb_index = 0;
211                }
212                self.absorb_internal(absorb_index, elems);
213            }
214            DuplexSpongeMode::Squeezing {
215                next_squeeze_index: _,
216            } => {
217                self.absorb_internal(0, elems);
218            }
219        };
220        self
221    }
222
223    fn get_field_elements(&mut self, num_elements: usize) -> Vec<F> {
224        let mut squeezed_elems = vec![F::zero(); num_elements];
225        match self.mode {
226            DuplexSpongeMode::Absorbing {
227                next_absorb_index: _,
228            } => {
229                self.permute();
230                self.squeeze_internal(0, &mut squeezed_elems);
231            }
232            DuplexSpongeMode::Squeezing { next_squeeze_index } => {
233                let mut squeeze_index = next_squeeze_index;
234                if squeeze_index == self.params.rate {
235                    self.permute();
236                    squeeze_index = 0;
237                }
238                self.squeeze_internal(squeeze_index, &mut squeezed_elems);
239            }
240        };
241
242        squeezed_elems
243    }
244}
245
246impl<F: PrimeField> TranscriptGadget<F> for GriffinSpongeVar<F> {
247    type Config = Arc<GriffinParams<F>>;
248    type Widget = GriffinSponge<F>;
249
250    fn new(parameters: Arc<GriffinParams<F>>) -> Self
251    where
252        Self: Sized,
253    {
254        let zero = FpVar::<F>::zero();
255        let state = vec![zero; parameters.rate + parameters.capacity];
256        let mode = DuplexSpongeMode::Absorbing {
257            next_absorb_index: 0,
258        };
259
260        Self {
261            params: parameters.clone(),
262            state,
263            mode,
264        }
265    }
266
267    fn add<A: AbsorbableVar<F>>(&mut self, input: &A) -> Result<&mut Self, SynthesisError> {
268        let input = {
269            let mut result = Vec::new();
270            input.absorb_into(&mut result)?;
271            result
272        };
273
274        if input.is_empty() {
275            return Ok(self);
276        }
277
278        match self.mode {
279            DuplexSpongeMode::Absorbing { next_absorb_index } => {
280                let mut absorb_index = next_absorb_index;
281                if absorb_index == self.params.rate {
282                    self.permute()?;
283                    absorb_index = 0;
284                }
285                self.absorb_internal(absorb_index, input.as_slice())?;
286            }
287            DuplexSpongeMode::Squeezing {
288                next_squeeze_index: _,
289            } => {
290                self.absorb_internal(0, input.as_slice())?;
291            }
292        };
293
294        Ok(self)
295    }
296
297    fn get_field_elements(&mut self, num_elements: usize) -> Result<Vec<FpVar<F>>, SynthesisError> {
298        let zero = FpVar::zero();
299        let mut squeezed_elems = vec![zero; num_elements];
300        match self.mode {
301            DuplexSpongeMode::Absorbing {
302                next_absorb_index: _,
303            } => {
304                self.permute()?;
305                self.squeeze_internal(0, &mut squeezed_elems)?;
306            }
307            DuplexSpongeMode::Squeezing { next_squeeze_index } => {
308                let mut squeeze_index = next_squeeze_index;
309                if squeeze_index == self.params.rate {
310                    self.permute()?;
311                    squeeze_index = 0;
312                }
313                self.squeeze_internal(squeeze_index, &mut squeezed_elems)?;
314            }
315        };
316
317        Ok(squeezed_elems)
318    }
319}
320
321#[cfg(test)]
322mod tests {
323    use ark_bn254::{Fq, Fr, G1Projective as G1, g1::Config};
324    use ark_ff::UniformRand;
325    use ark_r1cs_std::{
326        GR1CSVar, alloc::AllocVar, fields::fp::FpVar,
327        groups::curves::short_weierstrass::ProjectiveVar,
328    };
329    use ark_relations::gr1cs::ConstraintSystem;
330    use ark_std::{error::Error, rand::thread_rng};
331    #[cfg(all(target_arch = "wasm32", target_os = "unknown"))]
332    use wasm_bindgen_test::wasm_bindgen_test as test;
333
334    use super::*;
335    use crate::algebra::group::emulated::EmulatedAffineVar;
336
337    #[test]
338    fn test_challenge_field_element() -> Result<(), Box<dyn Error>> {
339        // Create a transcript outside of the circuit
340        let config = Arc::new(GriffinParams::<Fr>::new(3, 5, 12));
341        let mut tr = GriffinSponge::<Fr>::new(config.clone());
342        tr.add(&Fr::from(42_u32));
343        let c = tr.challenge_field_element();
344
345        // Create a transcript inside of the circuit
346        let cs = ConstraintSystem::<Fr>::new_ref();
347        let mut tr_var = GriffinSpongeVar::<Fr>::new(config);
348        let v = FpVar::<Fr>::new_witness(cs.clone(), || Ok(Fr::from(42_u32)))?;
349        tr_var.add(&v)?;
350        let c_var = tr_var.challenge_field_element()?;
351
352        // Assert that in-circuit and out-of-circuit transcripts return the same
353        // challenge
354        assert_eq!(c, c_var.value()?);
355        Ok(())
356    }
357
358    #[test]
359    fn test_challenge_bits() -> Result<(), Box<dyn Error>> {
360        let nbits = 128;
361
362        // Create a transcript outside of the circuit
363        let config = Arc::new(GriffinParams::<Fq>::new(3, 5, 12));
364        let mut tr = GriffinSponge::<Fq>::new(config.clone());
365        tr.add(&Fq::from(42_u32));
366        let c = tr.challenge_bits(nbits);
367
368        // Create a transcript inside of the circuit
369        let cs = ConstraintSystem::<Fq>::new_ref();
370        let mut tr_var = GriffinSpongeVar::<Fq>::new(config);
371        let v = FpVar::<Fq>::new_witness(cs.clone(), || Ok(Fq::from(42_u32)))?;
372        tr_var.add(&v)?;
373        let c_var = tr_var.challenge_bits(nbits)?;
374
375        // Assert that in-circuit and out-of-circuit transcripts return the same
376        // challenge
377        assert_eq!(c, c_var.value()?);
378        Ok(())
379    }
380
381    #[test]
382    fn test_absorb_canonical_point() -> Result<(), Box<dyn Error>> {
383        // Create a transcript outside of the circuit
384        let config = Arc::new(GriffinParams::<Fq>::new(3, 5, 12));
385        let mut tr = GriffinSponge::<Fq>::new(config.clone());
386        let rng = &mut thread_rng();
387
388        let p = G1::rand(rng);
389        tr.add(&p);
390        let c = tr.challenge_field_element();
391
392        // Create a transcript inside of the circuit
393        let cs = ConstraintSystem::<Fq>::new_ref();
394        let mut tr_var = GriffinSpongeVar::<Fq>::new(config);
395        let p_var = ProjectiveVar::<Config, FpVar<Fq>>::new_witness(cs, || Ok(p))?;
396        tr_var.add(&p_var)?;
397        let c_var = tr_var.challenge_field_element()?;
398
399        // Assert that in-circuit and out-of-circuit transcripts return the same
400        // challenge
401        assert_eq!(c, c_var.value()?);
402        Ok(())
403    }
404
405    #[test]
406    fn test_absorb_emulated_point() -> Result<(), Box<dyn Error>> {
407        // Create a transcript outside of the circuit
408        let config = Arc::new(GriffinParams::<Fr>::new(3, 5, 12));
409        let mut tr = GriffinSponge::<Fr>::new(config.clone());
410        let rng = &mut thread_rng();
411
412        let p = G1::rand(rng);
413        tr.add(&p);
414        let c = tr.challenge_field_element();
415
416        // Create a transcript inside of the circuit
417        let cs = ConstraintSystem::<Fr>::new_ref();
418        let mut tr_var = GriffinSpongeVar::<Fr>::new(config);
419        let p_var = EmulatedAffineVar::new_witness(cs, || Ok(p))?;
420        tr_var.add(&p_var)?;
421        let c_var = tr_var.challenge_field_element()?;
422
423        // Assert that in-circuit and out-of-circuit transcripts return the same
424        // challenge
425        assert_eq!(c, c_var.value()?);
426        Ok(())
427    }
428}
sonobe_primitives/transcripts/griffin/sponge.rs

sonobe_primitives/transcripts/griffin/
sponge.rs
