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