Nova/src/poseidon.rs
src/poseidon.rsRaw
1//! Poseidon Constants and Poseidon-based RO used in Nova
2use super::{
3 constants::{NUM_CHALLENGE_BITS, NUM_HASH_BITS},
4 traits::{HashFuncConstantsTrait, HashFuncTrait},
5};
6use bellperson::{
7 gadgets::{
8 boolean::{AllocatedBit, Boolean},
9 num::AllocatedNum,
10 },
11 ConstraintSystem, SynthesisError,
12};
13use core::marker::PhantomData;
14use ff::{PrimeField, PrimeFieldBits};
15use generic_array::typenum::{U27, U32};
16use neptune::{
17 circuit::poseidon_hash,
18 poseidon::{Poseidon, PoseidonConstants},
19 Strength,
20};
21
22/// All Poseidon Constants that are used in Nova
23#[derive(Clone)]
24pub struct ROConstantsCircuit<Scalar>
25where
26 Scalar: PrimeField,
27{
28 constants27: PoseidonConstants<Scalar, U27>,
29 constants32: PoseidonConstants<Scalar, U32>,
30}
31
32impl<Scalar> HashFuncConstantsTrait<Scalar> for ROConstantsCircuit<Scalar>
33where
34 Scalar: PrimeField + PrimeFieldBits,
35{
36 /// Generate Poseidon constants for the arities that Nova uses
37 #[allow(clippy::new_without_default)]
38 fn new() -> Self {
39 let constants27 = PoseidonConstants::<Scalar, U27>::new_with_strength(Strength::Strengthened);
40 let constants32 = PoseidonConstants::<Scalar, U32>::new_with_strength(Strength::Strengthened);
41 Self {
42 constants27,
43 constants32,
44 }
45 }
46}
47
48/// A Poseidon-based RO to use outside circuits
49pub struct PoseidonRO<Base, Scalar>
50where
51 Base: PrimeField + PrimeFieldBits,
52 Scalar: PrimeField + PrimeFieldBits,
53{
54 // Internal State
55 state: Vec<Base>,
56 // Constants for Poseidon
57 constants: ROConstantsCircuit<Base>,
58 _p: PhantomData<Scalar>,
59}
60
61impl<Base, Scalar> PoseidonRO<Base, Scalar>
62where
63 Base: PrimeField + PrimeFieldBits,
64 Scalar: PrimeField + PrimeFieldBits,
65{
66 fn hash_inner(&self) -> Base {
67 match self.state.len() {
68 27 => {
69 Poseidon::<Base, U27>::new_with_preimage(&self.state, &self.constants.constants27).hash()
70 }
71 32 => {
72 Poseidon::<Base, U32>::new_with_preimage(&self.state, &self.constants.constants32).hash()
73 }
74 _ => {
75 panic!(
76 "Number of elements in the RO state does not match any of the arities used in Nova: {:?}",
77 self.state.len()
78 );
79 }
80 }
81 }
82}
83
84impl<Base, Scalar> HashFuncTrait<Base, Scalar> for PoseidonRO<Base, Scalar>
85where
86 Base: PrimeField + PrimeFieldBits,
87 Scalar: PrimeField + PrimeFieldBits,
88{
89 type Constants = ROConstantsCircuit<Base>;
90
91 fn new(constants: ROConstantsCircuit<Base>) -> Self {
92 Self {
93 state: Vec::new(),
94 constants,
95 _p: PhantomData::default(),
96 }
97 }
98
99 /// Absorb a new number into the state of the oracle
100 fn absorb(&mut self, e: Base) {
101 self.state.push(e);
102 }
103
104 /// Compute a challenge by hashing the current state
105 fn get_challenge(&self) -> Scalar {
106 let hash = self.hash_inner();
107 // Only keep NUM_CHALLENGE_BITS bits
108 let bits = hash.to_le_bits();
109 let mut res = Scalar::zero();
110 let mut coeff = Scalar::one();
111 for bit in bits[0..NUM_CHALLENGE_BITS].into_iter() {
112 if *bit {
113 res += coeff;
114 }
115 coeff += coeff;
116 }
117 res
118 }
119
120 fn get_hash(&self) -> Scalar {
121 let hash = self.hash_inner();
122 // Only keep NUM_HASH_BITS bits
123 let bits = hash.to_le_bits();
124 let mut res = Scalar::zero();
125 let mut coeff = Scalar::one();
126 for bit in bits[0..NUM_HASH_BITS].into_iter() {
127 if *bit {
128 res += coeff;
129 }
130 coeff += coeff;
131 }
132 res
133 }
134}
135
136/// A Poseidon-based RO gadget to use inside the verifier circuit.
137pub struct PoseidonROGadget<Scalar>
138where
139 Scalar: PrimeField + PrimeFieldBits,
140{
141 // Internal state
142 state: Vec<AllocatedNum<Scalar>>,
143 constants: ROConstantsCircuit<Scalar>,
144}
145
146impl<Scalar> PoseidonROGadget<Scalar>
147where
148 Scalar: PrimeField + PrimeFieldBits,
149{
150 /// Initialize the internal state and set the poseidon constants
151 pub fn new(constants: ROConstantsCircuit<Scalar>) -> Self {
152 Self {
153 state: Vec::new(),
154 constants,
155 }
156 }
157
158 /// Absorb a new number into the state of the oracle
159 pub fn absorb(&mut self, e: AllocatedNum<Scalar>) {
160 self.state.push(e);
161 }
162
163 fn hash_inner<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
164 where
165 CS: ConstraintSystem<Scalar>,
166 {
167 let out = match self.state.len() {
168 27 => poseidon_hash(
169 cs.namespace(|| "Poseidon hash"),
170 self.state.clone(),
171 &self.constants.constants27,
172 )?,
173 32 => poseidon_hash(
174 cs.namespace(|| "Posideon hash"),
175 self.state.clone(),
176 &self.constants.constants32,
177 )?,
178 _ => {
179 panic!(
180 "Number of elements in the RO state does not match any of the arities used in Nova: {}",
181 self.state.len()
182 )
183 }
184 };
185
186 // return the hash as a vector of bits
187 Ok(
188 out
189 .to_bits_le_strict(cs.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(),
196 )
197 }
198
199 /// Compute a challenge by hashing the current state
200 pub fn get_challenge<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
201 where
202 CS: ConstraintSystem<Scalar>,
203 {
204 let bits = self.hash_inner(cs.namespace(|| "hash"))?;
205 Ok(bits[..NUM_CHALLENGE_BITS].into())
206 }
207
208 pub fn get_hash<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
209 where
210 CS: ConstraintSystem<Scalar>,
211 {
212 let bits = self.hash_inner(cs.namespace(|| "hash"))?;
213 Ok(bits[..NUM_HASH_BITS].into())
214 }
215}
216
217#[cfg(test)]
218mod tests {
219 use super::*;
220 type S = pasta_curves::pallas::Scalar;
221 type B = pasta_curves::vesta::Scalar;
222 type G = pasta_curves::pallas::Point;
223 use crate::{bellperson::solver::SatisfyingAssignment, gadgets::utils::le_bits_to_num};
224 use ff::Field;
225 use rand::rngs::OsRng;
226
227 #[test]
228 fn test_poseidon_ro() {
229 // Check that the number computed inside the circuit is equal to the number computed outside the circuit
230 let mut csprng: OsRng = OsRng;
231 let constants = ROConstantsCircuit::new();
232 let mut ro: PoseidonRO<S, B> = PoseidonRO::new(constants.clone());
233 let mut ro_gadget: PoseidonROGadget<S> = PoseidonROGadget::new(constants);
234 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
235 for i in 0..27 {
236 let num = S::random(&mut csprng);
237 ro.absorb(num);
238 let num_gadget =
239 AllocatedNum::alloc(cs.namespace(|| format!("data {}", i)), || Ok(num)).unwrap();
240 let _ = num_gadget
241 .inputize(&mut cs.namespace(|| format!("input {}", i)))
242 .unwrap();
243 ro_gadget.absorb(num_gadget);
244 }
245 let num = ro.get_challenge();
246 let num2_bits = ro_gadget.get_challenge(&mut cs).unwrap();
247 let num2 = le_bits_to_num(&mut cs, num2_bits).unwrap();
248 assert_eq!(num.to_repr(), num2.get_value().unwrap().to_repr());
249 }
250}