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