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