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