Nova/src/poseidon.rs
src/poseidon.rsRaw
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::{U27, U32};
13use neptune::{
14 circuit::poseidon_hash,
15 poseidon::{Poseidon, PoseidonConstants},
16 Strength,
17};
18
19/// All Poseidon Constants that are used in Nova
20#[derive(Clone)]
21pub struct PoseidonConstantsCircuit<Scalar>
22where
23 Scalar: PrimeField,
24{
25 constants27: PoseidonConstants<Scalar, U27>,
26 constants32: PoseidonConstants<Scalar, U32>,
27}
28
29impl<Scalar> ROConstantsTrait<Scalar> for PoseidonConstantsCircuit<Scalar>
30where
31 Scalar: PrimeField + PrimeFieldBits,
32{
33 /// Generate Poseidon constants for the arities that Nova uses
34 #[allow(clippy::new_without_default)]
35 fn new() -> Self {
36 let constants27 = PoseidonConstants::<Scalar, U27>::new_with_strength(Strength::Standard);
37 let constants32 = PoseidonConstants::<Scalar, U32>::new_with_strength(Strength::Standard);
38 Self {
39 constants27,
40 constants32,
41 }
42 }
43}
44
45/// A Poseidon-based RO to use outside circuits
46pub struct PoseidonRO<Base, Scalar>
47where
48 Base: PrimeField + PrimeFieldBits,
49 Scalar: PrimeField + PrimeFieldBits,
50{
51 // Internal State
52 state: Vec<Base>,
53 // Constants for Poseidon
54 constants: PoseidonConstantsCircuit<Base>,
55 _p: PhantomData<Scalar>,
56}
57
58impl<Base, Scalar> ROTrait<Base, Scalar> for PoseidonRO<Base, Scalar>
59where
60 Base: PrimeField + PrimeFieldBits,
61 Scalar: PrimeField + PrimeFieldBits,
62{
63 type Constants = PoseidonConstantsCircuit<Base>;
64
65 fn new(constants: PoseidonConstantsCircuit<Base>) -> Self {
66 Self {
67 state: Vec::new(),
68 constants,
69 _p: PhantomData::default(),
70 }
71 }
72
73 /// Absorb a new number into the state of the oracle
74 fn absorb(&mut self, e: Base) {
75 self.state.push(e);
76 }
77
78 /// Compute a challenge by hashing the current state
79 fn squeeze(&self, num_bits: usize) -> Scalar {
80 let hash = match self.state.len() {
81 27 => {
82 Poseidon::<Base, U27>::new_with_preimage(&self.state, &self.constants.constants27).hash()
83 }
84 32 => {
85 Poseidon::<Base, U32>::new_with_preimage(&self.state, &self.constants.constants32).hash()
86 }
87 _ => {
88 panic!(
89 "Number of elements in the RO state does not match any of the arities used in Nova: {:?}",
90 self.state.len()
91 );
92 }
93 };
94
95 // Only return `num_bits`
96 let bits = hash.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}
118
119impl<Scalar> ROCircuitTrait<Scalar> for PoseidonROCircuit<Scalar>
120where
121 Scalar: PrimeField + PrimeFieldBits,
122{
123 type Constants = PoseidonConstantsCircuit<Scalar>;
124
125 /// Initialize the internal state and set the poseidon constants
126 fn new(constants: PoseidonConstantsCircuit<Scalar>) -> Self {
127 Self {
128 state: Vec::new(),
129 constants,
130 }
131 }
132
133 /// Absorb a new number into the state of the oracle
134 fn absorb(&mut self, e: AllocatedNum<Scalar>) {
135 self.state.push(e);
136 }
137
138 /// Compute a challenge by hashing the current state
139 fn squeeze<CS>(
140 &mut self,
141 mut cs: CS,
142 num_bits: usize,
143 ) -> Result<Vec<AllocatedBit>, SynthesisError>
144 where
145 CS: ConstraintSystem<Scalar>,
146 {
147 let hash = match self.state.len() {
148 27 => poseidon_hash(
149 cs.namespace(|| "Poseidon hash"),
150 self.state.clone(),
151 &self.constants.constants27,
152 )?,
153 32 => poseidon_hash(
154 cs.namespace(|| "Posideon hash"),
155 self.state.clone(),
156 &self.constants.constants32,
157 )?,
158 _ => {
159 panic!(
160 "Number of elements in the RO state does not match any of the arities used in Nova: {}",
161 self.state.len()
162 )
163 }
164 };
165
166 // return the hash as a vector of bits, truncated
167 Ok(
168 hash
169 .to_bits_le_strict(cs.namespace(|| "poseidon hash to boolean"))?
170 .iter()
171 .map(|boolean| match boolean {
172 Boolean::Is(ref x) => x.clone(),
173 _ => panic!("Wrong type of input. We should have never reached there"),
174 })
175 .collect::<Vec<AllocatedBit>>()[..num_bits]
176 .into(),
177 )
178 }
179}
180
181#[cfg(test)]
182mod tests {
183 use super::*;
184 type S = pasta_curves::pallas::Scalar;
185 type B = pasta_curves::vesta::Scalar;
186 type G = pasta_curves::pallas::Point;
187 use crate::{
188 bellperson::solver::SatisfyingAssignment, constants::NUM_CHALLENGE_BITS,
189 gadgets::utils::le_bits_to_num,
190 };
191 use ff::Field;
192 use rand::rngs::OsRng;
193
194 #[test]
195 fn test_poseidon_ro() {
196 // Check that the number computed inside the circuit is equal to the number computed outside the circuit
197 let mut csprng: OsRng = OsRng;
198 let constants = PoseidonConstantsCircuit::new();
199 let mut ro: PoseidonRO<S, B> = PoseidonRO::new(constants.clone());
200 let mut ro_gadget: PoseidonROCircuit<S> = PoseidonROCircuit::new(constants);
201 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
202 for i in 0..27 {
203 let num = S::random(&mut csprng);
204 ro.absorb(num);
205 let num_gadget =
206 AllocatedNum::alloc(cs.namespace(|| format!("data {}", i)), || Ok(num)).unwrap();
207 num_gadget
208 .inputize(&mut cs.namespace(|| format!("input {}", i)))
209 .unwrap();
210 ro_gadget.absorb(num_gadget);
211 }
212 let num = ro.squeeze(NUM_CHALLENGE_BITS);
213 let num2_bits = ro_gadget.squeeze(&mut cs, NUM_CHALLENGE_BITS).unwrap();
214 let num2 = le_bits_to_num(&mut cs, num2_bits).unwrap();
215 assert_eq!(num.to_repr(), num2.get_value().unwrap().to_repr());
216 }
217}