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::{HashFuncCircuitTrait, 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 PoseidonConstantsCircuit<Scalar>
25where
26 Scalar: PrimeField,
27{
28 constants27: PoseidonConstants<Scalar, U27>,
29 constants32: PoseidonConstants<Scalar, U32>,
30}
31
32impl<Scalar> HashFuncConstantsTrait<Scalar> for PoseidonConstantsCircuit<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::Standard);
40 let constants32 = PoseidonConstants::<Scalar, U32>::new_with_strength(Strength::Standard);
41 Self {
42 constants27,
43 constants32,
44 }
45 }
46}
47
48/// A Poseidon-based RO to use outside circuits
49pub struct PoseidonHashFunc<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: PoseidonConstantsCircuit<Base>,
58 _p: PhantomData<Scalar>,
59}
60
61impl<Base, Scalar> PoseidonHashFunc<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 PoseidonHashFunc<Base, Scalar>
85where
86 Base: PrimeField + PrimeFieldBits,
87 Scalar: PrimeField + PrimeFieldBits,
88{
89 type Constants = PoseidonConstantsCircuit<Base>;
90
91 fn new(constants: PoseidonConstantsCircuit<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 PoseidonHashFuncCircuit<Scalar>
138where
139 Scalar: PrimeField + PrimeFieldBits,
140{
141 // Internal state
142 state: Vec<AllocatedNum<Scalar>>,
143 constants: PoseidonConstantsCircuit<Scalar>,
144}
145
146impl<Scalar> PoseidonHashFuncCircuit<Scalar>
147where
148 Scalar: PrimeField + PrimeFieldBits,
149{
150 fn hash_inner<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
151 where
152 CS: ConstraintSystem<Scalar>,
153 {
154 let out = match self.state.len() {
155 27 => poseidon_hash(
156 cs.namespace(|| "Poseidon hash"),
157 self.state.clone(),
158 &self.constants.constants27,
159 )?,
160 32 => poseidon_hash(
161 cs.namespace(|| "Posideon hash"),
162 self.state.clone(),
163 &self.constants.constants32,
164 )?,
165 _ => {
166 panic!(
167 "Number of elements in the RO state does not match any of the arities used in Nova: {}",
168 self.state.len()
169 )
170 }
171 };
172
173 // return the hash as a vector of bits
174 Ok(
175 out
176 .to_bits_le_strict(cs.namespace(|| "poseidon hash to boolean"))?
177 .iter()
178 .map(|boolean| match boolean {
179 Boolean::Is(ref x) => x.clone(),
180 _ => panic!("Wrong type of input. We should have never reached there"),
181 })
182 .collect(),
183 )
184 }
185}
186
187impl<Scalar> HashFuncCircuitTrait<Scalar> for PoseidonHashFuncCircuit<Scalar>
188where
189 Scalar: PrimeField + PrimeFieldBits,
190{
191 type Constants = PoseidonConstantsCircuit<Scalar>;
192
193 /// Initialize the internal state and set the poseidon constants
194 fn new(constants: PoseidonConstantsCircuit<Scalar>) -> Self {
195 Self {
196 state: Vec::new(),
197 constants,
198 }
199 }
200
201 /// Absorb a new number into the state of the oracle
202 fn absorb(&mut self, e: AllocatedNum<Scalar>) {
203 self.state.push(e);
204 }
205
206 /// Compute a challenge by hashing the current state
207 fn get_challenge<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
208 where
209 CS: ConstraintSystem<Scalar>,
210 {
211 let bits = self.hash_inner(cs.namespace(|| "hash"))?;
212 Ok(bits[..NUM_CHALLENGE_BITS].into())
213 }
214
215 fn get_hash<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
216 where
217 CS: ConstraintSystem<Scalar>,
218 {
219 let bits = self.hash_inner(cs.namespace(|| "hash"))?;
220 Ok(bits[..NUM_HASH_BITS].into())
221 }
222}
223
224#[cfg(test)]
225mod tests {
226 use super::*;
227 type S = pasta_curves::pallas::Scalar;
228 type B = pasta_curves::vesta::Scalar;
229 type G = pasta_curves::pallas::Point;
230 use crate::{bellperson::solver::SatisfyingAssignment, gadgets::utils::le_bits_to_num};
231 use ff::Field;
232 use rand::rngs::OsRng;
233
234 #[test]
235 fn test_poseidon_ro() {
236 // Check that the number computed inside the circuit is equal to the number computed outside the circuit
237 let mut csprng: OsRng = OsRng;
238 let constants = PoseidonConstantsCircuit::new();
239 let mut ro: PoseidonHashFunc<S, B> = PoseidonHashFunc::new(constants.clone());
240 let mut ro_gadget: PoseidonHashFuncCircuit<S> = PoseidonHashFuncCircuit::new(constants);
241 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
242 for i in 0..27 {
243 let num = S::random(&mut csprng);
244 ro.absorb(num);
245 let num_gadget =
246 AllocatedNum::alloc(cs.namespace(|| format!("data {}", i)), || Ok(num)).unwrap();
247 num_gadget
248 .inputize(&mut cs.namespace(|| format!("input {}", i)))
249 .unwrap();
250 ro_gadget.absorb(num_gadget);
251 }
252 let num = ro.get_challenge();
253 let num2_bits = ro_gadget.get_challenge(&mut cs).unwrap();
254 let num2 = le_bits_to_num(&mut cs, num2_bits).unwrap();
255 assert_eq!(num.to_repr(), num2.get_value().unwrap().to_repr());
256 }
257}