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::{U25, U27, U31, U8};
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 constants8: PoseidonConstants<F, U8>,
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 #[allow(clippy::new_without_default)]
38 pub fn new() -> Self {
39 let constants8 = PoseidonConstants::<F, U8>::new_with_strength(Strength::Strengthened);
40 let constants25 = PoseidonConstants::<F, U25>::new_with_strength(Strength::Strengthened);
41 let constants27 = PoseidonConstants::<F, U27>::new_with_strength(Strength::Strengthened);
42 let constants31 = PoseidonConstants::<F, U31>::new_with_strength(Strength::Strengthened);
43 Self {
44 constants8,
45 constants25,
46 constants27,
47 constants31,
48 }
49 }
50}
51
52/// A Poseidon-based RO to use outside circuits
53pub struct PoseidonRO<Scalar>
54where
55 Scalar: PrimeField + PrimeFieldBits,
56{
57 // Internal State
58 state: Vec<Scalar>,
59 // Constants for Poseidon
60 constants: NovaPoseidonConstants<Scalar>,
61}
62
63impl<Scalar> PoseidonRO<Scalar>
64where
65 Scalar: PrimeField + PrimeFieldBits,
66{
67 #[allow(dead_code)]
68 pub fn new(constants: NovaPoseidonConstants<Scalar>) -> Self {
69 Self {
70 state: Vec::new(),
71 constants,
72 }
73 }
74
75 /// Absorb a new number into the state of the oracle
76 #[allow(dead_code)]
77 pub fn absorb(&mut self, e: Scalar) {
78 self.state.push(e);
79 }
80
81 fn hash_inner(&mut self) -> Scalar {
82 match self.state.len() {
83 8 => {
84 Poseidon::<Scalar, U8>::new_with_preimage(&self.state, &self.constants.constants8).hash()
85 }
86 25 => {
87 Poseidon::<Scalar, U25>::new_with_preimage(&self.state, &self.constants.constants25).hash()
88 }
89 27 => {
90 Poseidon::<Scalar, U27>::new_with_preimage(&self.state, &self.constants.constants27).hash()
91 }
92 31 => {
93 Poseidon::<Scalar, U31>::new_with_preimage(&self.state, &self.constants.constants31).hash()
94 }
95 _ => {
96 panic!("Number of elements in the RO state does not match any of the arities used in Nova")
97 }
98 }
99 }
100
101 /// Compute a challenge by hashing the current state
102 #[allow(dead_code)]
103 pub fn get_challenge(&mut 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 pub fn get_hash(&mut 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 25 => poseidon_hash(
175 cs.namespace(|| "Poseidon hash"),
176 self.state.clone(),
177 &self.constants.constants25,
178 )?,
179 27 => poseidon_hash(
180 cs.namespace(|| "Poseidon hash"),
181 self.state.clone(),
182 &self.constants.constants27,
183 )?,
184 31 => poseidon_hash(
185 cs.namespace(|| "Poseidon hash"),
186 self.state.clone(),
187 &self.constants.constants31,
188 )?,
189 _ => {
190 panic!(
191 "Number of elements in the RO state does not match any of the arities used in Nova {}",
192 self.state.len()
193 )
194 }
195 };
196
197 // return the hash as a vector of bits
198 Ok(
199 out
200 .to_bits_le_strict(cs.namespace(|| "poseidon hash to boolean"))?
201 .iter()
202 .map(|boolean| match boolean {
203 Boolean::Is(ref x) => x.clone(),
204 _ => panic!("Wrong type of input. We should have never reached there"),
205 })
206 .collect(),
207 )
208 }
209
210 /// Compute a challenge by hashing the current state
211 #[allow(dead_code)]
212 pub fn get_challenge<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 128 bits
218 Ok(bits[..128].into())
219 }
220
221 #[allow(dead_code)]
222 pub fn get_hash<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 250 bits
228 Ok(bits[..250].into())
229 }
230}
231
232#[cfg(test)]
233mod tests {
234 use super::*;
235 type S = pasta_curves::pallas::Scalar;
236 type G = pasta_curves::pallas::Point;
237 use crate::{bellperson::solver::SatisfyingAssignment, gadgets::utils::le_bits_to_num};
238 use ff::Field;
239 use rand::rngs::OsRng;
240
241 #[test]
242 fn test_poseidon_ro() {
243 // Check that the number computed inside the circuit is equal to the number computed outside the circuit
244 let mut csprng: OsRng = OsRng;
245 let constants = NovaPoseidonConstants::new();
246 let mut ro: PoseidonRO<S> = PoseidonRO::new(constants.clone());
247 let mut ro_gadget: PoseidonROGadget<S> = PoseidonROGadget::new(constants);
248 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
249 for i in 0..31 {
250 let num = S::random(&mut csprng);
251 ro.absorb(num);
252 let num_gadget =
253 AllocatedNum::alloc(cs.namespace(|| format!("data {}", i)), || Ok(num)).unwrap();
254 let _ = num_gadget
255 .inputize(&mut cs.namespace(|| format!("input {}", i)))
256 .unwrap();
257 ro_gadget.absorb(num_gadget);
258 }
259 let num = ro.get_challenge();
260 let num2_bits = ro_gadget.get_challenge(&mut cs).unwrap();
261 let num2 = le_bits_to_num(&mut cs, num2_bits).unwrap();
262 assert_eq!(num, num2.get_value().unwrap());
263 }
264}