Nova/src/poseidon.rs
src/poseidon.rsRaw
1//! Poseidon Constants and Poseidon-based RO used in Nova
2use bellperson::{
3 gadgets::{
4 boolean::{AllocatedBit, Boolean},
5 num::AllocatedNum,
6 },
7 ConstraintSystem, SynthesisError,
8};
9use ff::{PrimeField, PrimeFieldBits};
10use generic_array::typenum::{U24, U25, U27, U31};
11use neptune::{
12 circuit::poseidon_hash,
13 poseidon::{Poseidon, PoseidonConstants},
14};
15
16#[cfg(test)]
17use neptune::Strength;
18
19/// All Poseidon Constants that are used in Nova
20#[derive(Clone)]
21pub struct NovaPoseidonConstants<F>
22where
23 F: PrimeField,
24{
25 constants24: PoseidonConstants<F, U24>,
26 constants25: PoseidonConstants<F, U25>,
27 constants27: PoseidonConstants<F, U27>,
28 constants31: PoseidonConstants<F, U31>,
29}
30
31#[cfg(test)]
32impl<F> NovaPoseidonConstants<F>
33where
34 F: PrimeField,
35{
36 /// Generate Poseidon constants for the arities that Nova uses
37 pub fn new() -> Self {
38 let constants24 = PoseidonConstants::<F, U24>::new_with_strength(Strength::Strengthened);
39 let constants25 = PoseidonConstants::<F, U25>::new_with_strength(Strength::Strengthened);
40 let constants27 = PoseidonConstants::<F, U27>::new_with_strength(Strength::Strengthened);
41 let constants31 = PoseidonConstants::<F, U31>::new_with_strength(Strength::Strengthened);
42 Self {
43 constants24,
44 constants25,
45 constants27,
46 constants31,
47 }
48 }
49}
50
51/// A Poseidon-based RO to use outside circuits
52pub struct PoseidonRO<Scalar>
53where
54 Scalar: PrimeField + PrimeFieldBits,
55{
56 // Internal State
57 state: Vec<Scalar>,
58 // Constants for Poseidon
59 constants: NovaPoseidonConstants<Scalar>,
60}
61
62impl<Scalar> PoseidonRO<Scalar>
63where
64 Scalar: PrimeField + PrimeFieldBits,
65{
66 #[allow(dead_code)]
67 pub fn new(constants: NovaPoseidonConstants<Scalar>) -> Self {
68 Self {
69 state: Vec::new(),
70 constants,
71 }
72 }
73
74 #[allow(dead_code)]
75 /// Flush the state of the RO
76 pub fn flush_state(&mut self) {
77 self.state = Vec::new();
78 }
79
80 /// Absorb a new number into the state of the oracle
81 #[allow(dead_code)]
82 pub fn absorb(&mut self, e: Scalar) {
83 self.state.push(e);
84 }
85
86 fn hash_inner(&mut self) -> Scalar {
87 match self.state.len() {
88 24 => {
89 Poseidon::<Scalar, U24>::new_with_preimage(&self.state, &self.constants.constants24).hash()
90 }
91 25 => {
92 Poseidon::<Scalar, U25>::new_with_preimage(&self.state, &self.constants.constants25).hash()
93 }
94 27 => {
95 Poseidon::<Scalar, U27>::new_with_preimage(&self.state, &self.constants.constants27).hash()
96 }
97 31 => {
98 Poseidon::<Scalar, U31>::new_with_preimage(&self.state, &self.constants.constants31).hash()
99 }
100 _ => {
101 panic!("Number of elements in the RO state does not match any of the arities used in Nova")
102 }
103 }
104 }
105
106 /// Compute a challenge by hashing the current state
107 #[allow(dead_code)]
108 pub fn get_challenge(&mut self) -> Scalar {
109 let hash = self.hash_inner();
110 // Only keep 128 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..128].into_iter() {
115 if *bit {
116 res += coeff;
117 }
118 coeff += coeff;
119 }
120 res
121 }
122
123 #[allow(dead_code)]
124 pub fn get_hash(&mut self) -> Scalar {
125 let hash = self.hash_inner();
126 // Only keep 250 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..250].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 /// Flush the state of the RO
164 pub fn flush_state(&mut self) {
165 self.state = Vec::new();
166 }
167
168 /// Absorb a new number into the state of the oracle
169 #[allow(dead_code)]
170 pub fn absorb(&mut self, e: AllocatedNum<Scalar>) {
171 self.state.push(e);
172 }
173
174 fn hash_inner<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
175 where
176 CS: ConstraintSystem<Scalar>,
177 {
178 let out = match self.state.len() {
179 24 => poseidon_hash(
180 cs.namespace(|| "Posideon hash"),
181 self.state.clone(),
182 &self.constants.constants24,
183 )?,
184 25 => poseidon_hash(
185 cs.namespace(|| "Poseidon hash"),
186 self.state.clone(),
187 &self.constants.constants25,
188 )?,
189 27 => poseidon_hash(
190 cs.namespace(|| "Poseidon hash"),
191 self.state.clone(),
192 &self.constants.constants27,
193 )?,
194 31 => poseidon_hash(
195 cs.namespace(|| "Poseidon hash"),
196 self.state.clone(),
197 &self.constants.constants31,
198 )?,
199 _ => {
200 panic!(
201 "Number of elements in the RO state does not match any of the arities used in Nova {}",
202 self.state.len()
203 )
204 }
205 };
206
207 // return the hash as a vector of bits
208 Ok(
209 out
210 .to_bits_le_strict(cs.namespace(|| "poseidon hash to boolean"))?
211 .iter()
212 .map(|boolean| match boolean {
213 Boolean::Is(ref x) => x.clone(),
214 _ => panic!("Wrong type of input. We should have never reached there"),
215 })
216 .collect(),
217 )
218 }
219
220 /// Compute a challenge by hashing the current state
221 #[allow(dead_code)]
222 pub fn get_challenge<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
223 where
224 CS: ConstraintSystem<Scalar>,
225 {
226 let bits = self.hash_inner(cs.namespace(|| "hash"))?;
227 // Only keep 128 bits
228 Ok(bits[..128].into())
229 }
230
231 #[allow(dead_code)]
232 pub fn get_hash<CS>(&mut self, mut cs: CS) -> Result<Vec<AllocatedBit>, SynthesisError>
233 where
234 CS: ConstraintSystem<Scalar>,
235 {
236 let bits = self.hash_inner(cs.namespace(|| "hash"))?;
237 // Only keep 250 bits
238 Ok(bits[..250].into())
239 }
240}
241
242#[cfg(test)]
243mod tests {
244 use super::*;
245 type S = pasta_curves::pallas::Scalar;
246 type G = pasta_curves::pallas::Point;
247 use crate::{bellperson::solver::SatisfyingAssignment, gadgets::utils::le_bits_to_num};
248 use ff::Field;
249 use rand::rngs::OsRng;
250
251 #[test]
252 fn test_poseidon_ro() {
253 // Check that the number computed inside the circuit is equal to the number computed outside the circuit
254 let mut csprng: OsRng = OsRng;
255 let constants = NovaPoseidonConstants::new();
256 let mut ro: PoseidonRO<S> = PoseidonRO::new(constants.clone());
257 let mut ro_gadget: PoseidonROGadget<S> = PoseidonROGadget::new(constants);
258 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
259 for i in 0..31 {
260 let num = S::random(&mut csprng);
261 ro.absorb(num);
262 let num_gadget =
263 AllocatedNum::alloc(cs.namespace(|| format!("data {}", i)), || Ok(num)).unwrap();
264 let _ = num_gadget
265 .inputize(&mut cs.namespace(|| format!("input {}", i)))
266 .unwrap();
267 ro_gadget.absorb(num_gadget);
268 }
269 let num = ro.get_challenge();
270 let num2_bits = ro_gadget.get_challenge(&mut cs).unwrap();
271 let num2 = le_bits_to_num(&mut cs, num2_bits).unwrap();
272 assert_eq!(num, num2.get_value().unwrap());
273 }
274}