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