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