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