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 NovaPoseidonConstants<Scalar>
25where
26 Scalar: PrimeField,
27{
28 constants27: PoseidonConstants<Scalar, U27>,
29 constants32: PoseidonConstants<Scalar, U32>,
30}
31
32impl<Scalar> HashFuncConstantsTrait<Scalar> for NovaPoseidonConstants<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: NovaPoseidonConstants<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 = NovaPoseidonConstants<Base>;
90
91 #[allow(dead_code)]
92 fn new(constants: NovaPoseidonConstants<Base>) -> Self {
93 Self {
94 state: Vec::new(),
95 constants,
96 _p: PhantomData::default(),
97 }
98 }
99
100 /// Absorb a new number into the state of the oracle
101 #[allow(dead_code)]
102 fn absorb(&mut self, e: Base) {
103 self.state.push(e);
104 }
105
106 /// Compute a challenge by hashing the current state
107 #[allow(dead_code)]
108 fn get_challenge(&self) -> Scalar {
109 let hash = self.hash_inner();
110 // Only keep NUM_CHALLENGE_BITS bits
111 let bits = hash.to_le_bits();
112 let mut res = Scalar::zero();
113 let mut coeff = Scalar::one();
114 for bit in bits[0..NUM_CHALLENGE_BITS].into_iter() {
115 if *bit {
116 res += coeff;
117 }
118 coeff += coeff;
119 }
120 res
121 }
122
123 #[allow(dead_code)]
124 fn get_hash(&self) -> Scalar {
125 let hash = self.hash_inner();
126 // Only keep NUM_HASH_BITS bits
127 let bits = hash.to_le_bits();
128 let mut res = Scalar::zero();
129 let mut coeff = Scalar::one();
130 for bit in bits[0..NUM_HASH_BITS].into_iter() {
131 if *bit {
132 res += coeff;
133 }
134 coeff += coeff;
135 }
136 res
137 }
138}
139
140/// A Poseidon-based RO gadget to use inside the verifier circuit.
141pub struct PoseidonROGadget<Scalar>
142where
143 Scalar: PrimeField + PrimeFieldBits,
144{
145 // Internal state
146 state: Vec<AllocatedNum<Scalar>>,
147 constants: NovaPoseidonConstants<Scalar>,
148}
149
150impl<Scalar> PoseidonROGadget<Scalar>
151where
152 Scalar: PrimeField + PrimeFieldBits,
153{
154 /// Initialize the internal state and set the poseidon constants
155 #[allow(dead_code)]
156 pub fn new(constants: NovaPoseidonConstants<Scalar>) -> Self {
157 Self {
158 state: Vec::new(),
159 constants,
160 }
161 }
162
163 /// Absorb a new number into the state of the oracle
164 #[allow(dead_code)]
165 pub fn absorb(&mut self, e: AllocatedNum<Scalar>) {
166 self.state.push(e);
167 }
168
169 fn hash_inner<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
170 where
171 CS: ConstraintSystem<Scalar>,
172 {
173 let out = match self.state.len() {
174 27 => poseidon_hash(
175 cs.namespace(|| "Poseidon hash"),
176 self.state.clone(),
177 &self.constants.constants27,
178 )?,
179 32 => poseidon_hash(
180 cs.namespace(|| "Posideon hash"),
181 self.state.clone(),
182 &self.constants.constants32,
183 )?,
184 _ => {
185 panic!(
186 "Number of elements in the RO state does not match any of the arities used in Nova: {}",
187 self.state.len()
188 )
189 }
190 };
191
192 // return the hash as a vector of bits
193 Ok(
194 out
195 .to_bits_le_strict(cs.namespace(|| "poseidon hash to boolean"))?
196 .iter()
197 .map(|boolean| match boolean {
198 Boolean::Is(ref x) => x.clone(),
199 _ => panic!("Wrong type of input. We should have never reached there"),
200 })
201 .collect(),
202 )
203 }
204
205 /// Compute a challenge by hashing the current state
206 #[allow(dead_code)]
207 pub 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 #[allow(dead_code)]
216 pub fn get_hash<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
217 where
218 CS: ConstraintSystem<Scalar>,
219 {
220 let bits = self.hash_inner(cs.namespace(|| "hash"))?;
221 Ok(bits[..NUM_HASH_BITS].into())
222 }
223}
224
225#[cfg(test)]
226mod tests {
227 use super::*;
228 type S = pasta_curves::pallas::Scalar;
229 type B = pasta_curves::vesta::Scalar;
230 type G = pasta_curves::pallas::Point;
231 use crate::{bellperson::solver::SatisfyingAssignment, gadgets::utils::le_bits_to_num};
232 use ff::Field;
233 use rand::rngs::OsRng;
234
235 #[test]
236 fn test_poseidon_ro() {
237 // Check that the number computed inside the circuit is equal to the number computed outside the circuit
238 let mut csprng: OsRng = OsRng;
239 let constants = NovaPoseidonConstants::new();
240 let mut ro: PoseidonRO<S, B> = PoseidonRO::new(constants.clone());
241 let mut ro_gadget: PoseidonROGadget<S> = PoseidonROGadget::new(constants);
242 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
243 for i in 0..27 {
244 let num = S::random(&mut csprng);
245 ro.absorb(num);
246 let num_gadget =
247 AllocatedNum::alloc(cs.namespace(|| format!("data {}", i)), || Ok(num)).unwrap();
248 let _ = num_gadget
249 .inputize(&mut cs.namespace(|| format!("input {}", i)))
250 .unwrap();
251 ro_gadget.absorb(num_gadget);
252 }
253 let num = ro.get_challenge();
254 let num2_bits = ro_gadget.get_challenge(&mut cs).unwrap();
255 let num2 = le_bits_to_num(&mut cs, num2_bits).unwrap();
256 assert_eq!(num.to_repr(), num2.get_value().unwrap().to_repr());
257 }
258}