sonobe/folding-schemes/src/transcript/poseidon.rs
folding-schemes/src/transcript/poseidon.rsRaw
1use ark_crypto_primitives::sponge::{
2 constraints::CryptographicSpongeVar,
3 poseidon::{constraints::PoseidonSpongeVar, PoseidonConfig, PoseidonSponge},
4 Absorb, CryptographicSponge,
5};
6use ark_ec::{AffineRepr, CurveGroup};
7use ark_ff::{BigInteger, PrimeField};
8use ark_r1cs_std::{
9 boolean::Boolean, fields::fp::FpVar, groups::CurveVar, ToConstraintFieldGadget,
10};
11use ark_relations::r1cs::SynthesisError;
12
13use super::{AbsorbNonNative, AbsorbNonNativeGadget, Transcript, TranscriptVar};
14
15impl<F: PrimeField + Absorb> Transcript<F> for PoseidonSponge<F> {
16 // Compatible with the in-circuit `TranscriptVar::absorb_point`
17 fn absorb_point<C: CurveGroup<BaseField = F>>(&mut self, p: &C) {
18 let (x, y) = match p.into_affine().xy() {
19 Some((&x, &y)) => (x, y),
20 None => (C::BaseField::zero(), C::BaseField::zero()),
21 };
22 self.absorb(&x);
23 self.absorb(&y);
24 }
25 fn absorb_nonnative<V: AbsorbNonNative<F>>(&mut self, v: &V) {
26 self.absorb(&v.to_native_sponge_field_elements_as_vec());
27 }
28 fn get_challenge(&mut self) -> F {
29 let c = self.squeeze_field_elements(1);
30 self.absorb(&c[0]);
31 c[0]
32 }
33 fn get_challenge_nbits(&mut self, nbits: usize) -> Vec<bool> {
34 let bits = self.squeeze_bits(nbits);
35 self.absorb(&F::from(F::BigInt::from_bits_le(&bits)));
36 bits
37 }
38 fn get_challenges(&mut self, n: usize) -> Vec<F> {
39 let c = self.squeeze_field_elements(n);
40 self.absorb(&c);
41 c
42 }
43}
44
45impl<F: PrimeField> TranscriptVar<F, PoseidonSponge<F>> for PoseidonSpongeVar<F> {
46 fn absorb_point<
47 C: CurveGroup<BaseField = F>,
48 GC: CurveVar<C, F> + ToConstraintFieldGadget<F>,
49 >(
50 &mut self,
51 v: &GC,
52 ) -> Result<(), SynthesisError> {
53 let mut vec = v.to_constraint_field()?;
54 // The last element in the vector tells whether the point is infinity,
55 // but we can in fact avoid absorbing it without loss of soundness.
56 // This is because the `to_constraint_field` method internally invokes
57 // [`ProjectiveVar::to_afine`](https://github.com/arkworks-rs/r1cs-std/blob/4020fbc22625621baa8125ede87abaeac3c1ca26/src/groups/curves/short_weierstrass/mod.rs#L160-L195),
58 // which guarantees that an infinity point is represented as `(0, 0)`,
59 // but the y-coordinate of a non-infinity point is never 0 (for why, see
60 // https://crypto.stackexchange.com/a/108242 ).
61 vec.pop();
62 self.absorb(&vec)
63 }
64 fn absorb_nonnative<V: AbsorbNonNativeGadget<F>>(
65 &mut self,
66 v: &V,
67 ) -> Result<(), SynthesisError> {
68 self.absorb(&v.to_native_sponge_field_elements()?)
69 }
70 fn get_challenge(&mut self) -> Result<FpVar<F>, SynthesisError> {
71 let c = self.squeeze_field_elements(1)?;
72 self.absorb(&c[0])?;
73 Ok(c[0].clone())
74 }
75
76 /// returns the bit representation of the challenge, we use its output in-circuit for the
77 /// `GC.scalar_mul_le` method.
78 fn get_challenge_nbits(&mut self, nbits: usize) -> Result<Vec<Boolean<F>>, SynthesisError> {
79 let bits = self.squeeze_bits(nbits)?;
80 self.absorb(&Boolean::le_bits_to_fp_var(&bits)?)?;
81 Ok(bits)
82 }
83 fn get_challenges(&mut self, n: usize) -> Result<Vec<FpVar<F>>, SynthesisError> {
84 let c = self.squeeze_field_elements(n)?;
85 self.absorb(&c)?;
86 Ok(c)
87 }
88}
89
90/// This Poseidon configuration generator agrees with Circom's Poseidon(4) in the case of BN254's scalar field
91pub fn poseidon_canonical_config<F: PrimeField>() -> PoseidonConfig<F> {
92 // 120 bit security target as in
93 // https://eprint.iacr.org/2019/458.pdf
94 // t = rate + 1
95
96 let full_rounds = 8;
97 let partial_rounds = 60;
98 let alpha = 5;
99 let rate = 4;
100
101 let (ark, mds) = ark_crypto_primitives::sponge::poseidon::find_poseidon_ark_and_mds::<F>(
102 F::MODULUS_BIT_SIZE as u64,
103 rate,
104 full_rounds,
105 partial_rounds,
106 0,
107 );
108
109 PoseidonConfig::new(
110 full_rounds as usize,
111 partial_rounds as usize,
112 alpha,
113 mds,
114 ark,
115 rate,
116 1,
117 )
118}
119
120#[cfg(test)]
121pub mod tests {
122 use crate::folding::circuits::nonnative::affine::NonNativeAffineVar;
123
124 use super::*;
125 use ark_bn254::{constraints::GVar, g1::Config, Fq, Fr, G1Projective as G1};
126 use ark_ec::Group;
127 use ark_ff::UniformRand;
128 use ark_r1cs_std::{
129 alloc::AllocVar, groups::curves::short_weierstrass::ProjectiveVar, R1CSVar,
130 };
131 use ark_relations::r1cs::ConstraintSystem;
132 use ark_std::test_rng;
133
134 // Test with value taken from https://github.com/iden3/circomlibjs/blob/43cc582b100fc3459cf78d903a6f538e5d7f38ee/test/poseidon.js#L32
135 #[test]
136 fn check_against_circom_poseidon() {
137 use ark_bn254::Fr;
138 use ark_crypto_primitives::sponge::{poseidon::PoseidonSponge, CryptographicSponge};
139 use std::str::FromStr;
140
141 let config = poseidon_canonical_config::<Fr>();
142 let mut poseidon_sponge: PoseidonSponge<_> = CryptographicSponge::new(&config);
143 let v: Vec<Fr> = vec!["1", "2", "3", "4"]
144 .into_iter()
145 .map(|x| Fr::from_str(x).unwrap())
146 .collect();
147 poseidon_sponge.absorb(&v);
148 poseidon_sponge.squeeze_field_elements::<Fr>(1);
149 assert!(
150 poseidon_sponge.state[0]
151 == Fr::from_str(
152 "18821383157269793795438455681495246036402687001665670618754263018637548127333"
153 )
154 .unwrap()
155 );
156 }
157
158 #[test]
159 fn test_transcript_and_transcriptvar_absorb_native_point() {
160 // use 'native' transcript
161 let config = poseidon_canonical_config::<Fq>();
162 let mut tr = PoseidonSponge::<Fq>::new(&config);
163 let rng = &mut test_rng();
164
165 let p = G1::rand(rng);
166 tr.absorb_point(&p);
167 let c = tr.get_challenge();
168
169 // use 'gadget' transcript
170 let cs = ConstraintSystem::<Fq>::new_ref();
171 let mut tr_var = PoseidonSpongeVar::<Fq>::new(cs.clone(), &config);
172 let p_var = ProjectiveVar::<Config, FpVar<Fq>>::new_witness(
173 ConstraintSystem::<Fq>::new_ref(),
174 || Ok(p),
175 )
176 .unwrap();
177 tr_var.absorb_point(&p_var).unwrap();
178 let c_var = tr_var.get_challenge().unwrap();
179
180 // assert that native & gadget transcripts return the same challenge
181 assert_eq!(c, c_var.value().unwrap());
182 }
183
184 #[test]
185 fn test_transcript_and_transcriptvar_absorb_nonnative_point() {
186 // use 'native' transcript
187 let config = poseidon_canonical_config::<Fr>();
188 let mut tr = PoseidonSponge::<Fr>::new(&config);
189 let rng = &mut test_rng();
190
191 let p = G1::rand(rng);
192 tr.absorb_nonnative(&p);
193 let c = tr.get_challenge();
194
195 // use 'gadget' transcript
196 let cs = ConstraintSystem::<Fr>::new_ref();
197 let mut tr_var = PoseidonSpongeVar::<Fr>::new(cs.clone(), &config);
198 let p_var =
199 NonNativeAffineVar::<G1>::new_witness(ConstraintSystem::<Fr>::new_ref(), || Ok(p))
200 .unwrap();
201 tr_var.absorb_nonnative(&p_var).unwrap();
202 let c_var = tr_var.get_challenge().unwrap();
203
204 // assert that native & gadget transcripts return the same challenge
205 assert_eq!(c, c_var.value().unwrap());
206 }
207
208 #[test]
209 fn test_transcript_and_transcriptvar_get_challenge() {
210 // use 'native' transcript
211 let config = poseidon_canonical_config::<Fr>();
212 let mut tr = PoseidonSponge::<Fr>::new(&config);
213 tr.absorb(&Fr::from(42_u32));
214 let c = tr.get_challenge();
215
216 // use 'gadget' transcript
217 let cs = ConstraintSystem::<Fr>::new_ref();
218 let mut tr_var = PoseidonSpongeVar::<Fr>::new(cs.clone(), &config);
219 let v = FpVar::<Fr>::new_witness(cs.clone(), || Ok(Fr::from(42_u32))).unwrap();
220 tr_var.absorb(&v).unwrap();
221 let c_var = tr_var.get_challenge().unwrap();
222
223 // assert that native & gadget transcripts return the same challenge
224 assert_eq!(c, c_var.value().unwrap());
225 }
226
227 #[test]
228 fn test_transcript_and_transcriptvar_nbits() {
229 let nbits = crate::constants::N_BITS_RO;
230
231 // use 'native' transcript
232 let config = poseidon_canonical_config::<Fq>();
233 let mut tr = PoseidonSponge::<Fq>::new(&config);
234 tr.absorb(&Fq::from(42_u32));
235
236 // get challenge from native transcript
237 let c_bits = tr.get_challenge_nbits(nbits);
238
239 // use 'gadget' transcript
240 let cs = ConstraintSystem::<Fq>::new_ref();
241 let mut tr_var = PoseidonSpongeVar::<Fq>::new(cs.clone(), &config);
242 let v = FpVar::<Fq>::new_witness(cs.clone(), || Ok(Fq::from(42_u32))).unwrap();
243 tr_var.absorb(&v).unwrap();
244
245 // get challenge from circuit transcript
246 let c_var = tr_var.get_challenge_nbits(nbits).unwrap();
247
248 let P = G1::generator();
249 let PVar = GVar::new_witness(cs.clone(), || Ok(P)).unwrap();
250
251 // multiply point P by the challenge in different formats, to ensure that we get the same
252 // result natively and in-circuit
253
254 // native c*P
255 let c_Fr = Fr::from_bigint(BigInteger::from_bits_le(&c_bits)).unwrap();
256 let cP_native = P * c_Fr;
257
258 // native c*P using mul_bits_be (notice the .rev to convert the LE to BE)
259 let cP_native_bits = P.mul_bits_be(c_bits.into_iter().rev());
260
261 // in-circuit c*P using scalar_mul_le
262 let cPVar = PVar.scalar_mul_le(c_var.iter()).unwrap();
263
264 // check that they are equal
265 assert_eq!(
266 cP_native.into_affine(),
267 cPVar.value().unwrap().into_affine()
268 );
269 assert_eq!(
270 cP_native_bits.into_affine(),
271 cPVar.value().unwrap().into_affine()
272 );
273 }
274}