nova_snark/provider/
poseidon.rs

1//! Poseidon Constants and Poseidon-based RO used in Nova
2use crate::{
3  frontend::{
4    gadgets::poseidon::{
5      Elt, IOPattern, PoseidonConstants, Simplex, Sponge, SpongeAPI, SpongeCircuit, SpongeOp,
6      SpongeTrait, Strength,
7    },
8    num::AllocatedNum,
9    AllocatedBit, Boolean, ConstraintSystem, SynthesisError,
10  },
11  traits::{ROCircuitTrait, ROTrait},
12};
13use ff::{PrimeField, PrimeFieldBits};
14use generic_array::typenum::U24;
15use serde::{Deserialize, Serialize};
16
17/// All Poseidon Constants that are used in Nova
18#[derive(Clone, PartialEq, Serialize, Deserialize)]
19pub struct PoseidonConstantsCircuit<Scalar: PrimeField>(PoseidonConstants<Scalar, U24>);
20
21impl<Scalar: PrimeField> Default for PoseidonConstantsCircuit<Scalar> {
22  /// Generate Poseidon constants
23  fn default() -> Self {
24    Self(Sponge::<Scalar, U24>::api_constants(Strength::Standard))
25  }
26}
27
28/// A Poseidon-based RO to use outside circuits
29#[derive(Serialize, Deserialize)]
30pub struct PoseidonRO<Base: PrimeField> {
31  // internal State
32  state: Vec<Base>,
33  constants: PoseidonConstantsCircuit<Base>,
34}
35
36impl<Base> ROTrait<Base> for PoseidonRO<Base>
37where
38  Base: PrimeField + PrimeFieldBits + Serialize + for<'de> Deserialize<'de>,
39{
40  type CircuitRO = PoseidonROCircuit<Base>;
41  type Constants = PoseidonConstantsCircuit<Base>;
42
43  fn new(constants: PoseidonConstantsCircuit<Base>) -> Self {
44    Self {
45      state: Vec::new(),
46      constants,
47    }
48  }
49
50  /// Absorb a new number into the state of the oracle
51  fn absorb(&mut self, e: Base) {
52    self.state.push(e);
53  }
54
55  /// Compute a challenge by hashing the current state
56  fn squeeze(&mut self, num_bits: usize, start_with_one: bool) -> Base {
57    let mut sponge = Sponge::new_with_constants(&self.constants.0, Simplex);
58    let acc = &mut ();
59    let parameter = IOPattern(vec![
60      SpongeOp::Absorb(self.state.len() as u32),
61      SpongeOp::Squeeze(1u32),
62    ]);
63
64    sponge.start(parameter, None, acc);
65    SpongeAPI::absorb(&mut sponge, self.state.len() as u32, &self.state, acc);
66    let hash = SpongeAPI::squeeze(&mut sponge, 1, acc);
67    sponge.finish(acc).unwrap();
68
69    // reset the state to only contain the squeezed value
70    self.state = vec![hash[0]];
71
72    // Only return `num_bits`
73    let bits = hash[0].to_le_bits();
74    let mut res = Base::ZERO;
75    let mut coeff = Base::ONE;
76    for bit in bits[..num_bits].into_iter() {
77      if *bit {
78        res += coeff;
79      }
80      coeff += coeff;
81    }
82    // If start_with_one, force MSB (bit num_bits-1) to 1
83    if start_with_one {
84      // coeff is now 2^num_bits; we need 2^(num_bits-1)
85      let msb_coeff = coeff * Base::from(2u64).invert().unwrap();
86      // Check if MSB is not already set
87      if !bits[num_bits - 1] {
88        res += msb_coeff;
89      }
90    }
91    res
92  }
93}
94
95/// A Poseidon-based RO gadget to use inside the verifier circuit.
96#[derive(Serialize, Deserialize)]
97pub struct PoseidonROCircuit<Scalar: PrimeField> {
98  // Internal state
99  state: Vec<AllocatedNum<Scalar>>,
100  constants: PoseidonConstantsCircuit<Scalar>,
101}
102
103impl<Scalar> ROCircuitTrait<Scalar> for PoseidonROCircuit<Scalar>
104where
105  Scalar: PrimeField + PrimeFieldBits + Serialize + for<'de> Deserialize<'de>,
106{
107  type NativeRO = PoseidonRO<Scalar>;
108  type Constants = PoseidonConstantsCircuit<Scalar>;
109
110  /// Initialize the internal state and set the poseidon constants
111  fn new(constants: PoseidonConstantsCircuit<Scalar>) -> Self {
112    Self {
113      state: Vec::new(),
114      constants,
115    }
116  }
117
118  /// Absorb a new number into the state of the oracle
119  fn absorb(&mut self, e: &AllocatedNum<Scalar>) {
120    self.state.push(e.clone());
121  }
122
123  /// Compute a challenge by hashing the current state
124  fn squeeze<CS: ConstraintSystem<Scalar>>(
125    &mut self,
126    mut cs: CS,
127    num_bits: usize,
128    start_with_one: bool,
129  ) -> Result<Vec<AllocatedBit>, SynthesisError> {
130    let parameter = IOPattern(vec![
131      SpongeOp::Absorb(self.state.len() as u32),
132      SpongeOp::Squeeze(1u32),
133    ]);
134    let mut ns = cs.namespace(|| "ns");
135
136    let hash = {
137      let mut sponge = SpongeCircuit::new_with_constants(&self.constants.0, Simplex);
138      let acc = &mut ns;
139
140      sponge.start(parameter, None, acc);
141      SpongeAPI::absorb(
142        &mut sponge,
143        self.state.len() as u32,
144        &(0..self.state.len())
145          .map(|i| Elt::Allocated(self.state[i].clone()))
146          .collect::<Vec<Elt<Scalar>>>(),
147        acc,
148      );
149
150      let output = SpongeAPI::squeeze(&mut sponge, 1, acc);
151      sponge.finish(acc).unwrap();
152      output
153    };
154
155    let hash = Elt::ensure_allocated(&hash[0], &mut ns.namespace(|| "ensure allocated"))?;
156
157    // reset the state to only contain the squeezed value
158    self.state = vec![hash.clone()];
159
160    // return the hash as a vector of bits, truncated
161    let mut bits: Vec<AllocatedBit> = hash
162      .to_bits_le_strict(ns.namespace(|| "poseidon hash to boolean"))?
163      .iter()
164      .map(|boolean| match boolean {
165        Boolean::Is(ref x) => x.clone(),
166        _ => panic!("Wrong type of input. We should have never reached there"),
167      })
168      .collect::<Vec<AllocatedBit>>()[..num_bits]
169      .to_vec();
170
171    if start_with_one {
172      let msb_idx = num_bits - 1;
173      bits[msb_idx] = AllocatedBit::alloc(ns.namespace(|| "set msb to 1"), Some(true))?;
174      ns.enforce(
175        || "check bits[msb] = 1",
176        |lc| lc + bits[msb_idx].get_variable(),
177        |lc| lc + CS::one(),
178        |lc| lc + CS::one(),
179      );
180    }
181
182    Ok(bits)
183  }
184
185  fn squeeze_scalar<CS: ConstraintSystem<Scalar>>(
186    &mut self,
187    mut cs: CS,
188  ) -> Result<AllocatedNum<Scalar>, SynthesisError> {
189    let parameter = IOPattern(vec![
190      SpongeOp::Absorb(self.state.len() as u32),
191      SpongeOp::Squeeze(1u32),
192    ]);
193    let mut ns = cs.namespace(|| "ns");
194
195    let hash = {
196      let mut sponge = SpongeCircuit::new_with_constants(&self.constants.0, Simplex);
197      let acc = &mut ns;
198
199      sponge.start(parameter, None, acc);
200      SpongeAPI::absorb(
201        &mut sponge,
202        self.state.len() as u32,
203        &(0..self.state.len())
204          .map(|i| Elt::Allocated(self.state[i].clone()))
205          .collect::<Vec<Elt<Scalar>>>(),
206        acc,
207      );
208
209      let output = SpongeAPI::squeeze(&mut sponge, 1, acc);
210      sponge.finish(acc).unwrap();
211      output
212    };
213
214    let hash = Elt::ensure_allocated(&hash[0], &mut ns.namespace(|| "ensure allocated"))?;
215
216    // reset the state to only contain the squeezed value
217    self.state = vec![hash.clone()];
218
219    Ok(hash)
220  }
221}
222
223#[cfg(test)]
224mod tests {
225  use super::*;
226  use crate::{
227    constants::NUM_CHALLENGE_BITS,
228    frontend::solver::SatisfyingAssignment,
229    gadgets::utils::le_bits_to_num,
230    provider::{
231      Bn256EngineKZG, GrumpkinEngine, PallasEngine, Secp256k1Engine, Secq256k1Engine, VestaEngine,
232    },
233    traits::Engine,
234  };
235  use ff::Field;
236  use rand::rngs::OsRng;
237
238  fn test_poseidon_ro_with<E: Engine>() {
239    // Check that the number computed inside the circuit is equal to the number computed outside the circuit
240    let mut csprng: OsRng = OsRng;
241    let constants = PoseidonConstantsCircuit::<E::Scalar>::default();
242    let num_absorbs = 32;
243    let mut ro: PoseidonRO<E::Scalar> = PoseidonRO::new(constants.clone());
244    let mut ro_gadget: PoseidonROCircuit<E::Scalar> = PoseidonROCircuit::new(constants);
245    let mut cs = SatisfyingAssignment::<E>::new();
246    for i in 0..num_absorbs {
247      let num = E::Scalar::random(&mut csprng);
248      ro.absorb(num);
249      let num_gadget = AllocatedNum::alloc_infallible(cs.namespace(|| format!("data {i}")), || num);
250      num_gadget
251        .inputize(&mut cs.namespace(|| format!("input {i}")))
252        .unwrap();
253      ro_gadget.absorb(&num_gadget);
254    }
255    let num = ro.squeeze(NUM_CHALLENGE_BITS, false);
256    let num2_bits = ro_gadget
257      .squeeze(&mut cs, NUM_CHALLENGE_BITS, false)
258      .unwrap();
259    let num2 = le_bits_to_num(&mut cs, &num2_bits).unwrap();
260    assert_eq!(num, num2.get_value().unwrap());
261  }
262
263  #[test]
264  fn test_poseidon_ro() {
265    test_poseidon_ro_with::<PallasEngine>();
266    test_poseidon_ro_with::<VestaEngine>();
267    test_poseidon_ro_with::<Bn256EngineKZG>();
268    test_poseidon_ro_with::<GrumpkinEngine>();
269    test_poseidon_ro_with::<Secp256k1Engine>();
270    test_poseidon_ro_with::<Secq256k1Engine>();
271  }
272}
nova_snark/provider/poseidon.rs

nova_snark/provider/
poseidon.rs
