sonobe/folding-schemes/src/folding/nova/cyclefold.rs
folding-schemes/src/folding/nova/cyclefold.rsRaw
1/// contains [CycleFold](https://eprint.iacr.org/2023/1192.pdf) related circuits
2use ark_crypto_primitives::{
3 crh::{
4 poseidon::constraints::{CRHGadget, CRHParametersVar},
5 CRHSchemeGadget,
6 },
7 sponge::{
8 constraints::CryptographicSpongeVar,
9 poseidon::{constraints::PoseidonSpongeVar, PoseidonConfig, PoseidonSponge},
10 Absorb, CryptographicSponge,
11 },
12};
13use ark_ec::{AffineRepr, CurveGroup};
14use ark_ff::{Field, PrimeField, ToConstraintField};
15use ark_r1cs_std::{
16 alloc::{AllocVar, AllocationMode},
17 boolean::Boolean,
18 eq::EqGadget,
19 fields::{fp::FpVar, nonnative::NonNativeFieldVar, FieldVar},
20 groups::GroupOpsBounds,
21 prelude::CurveVar,
22 ToConstraintFieldGadget,
23};
24use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, Namespace, SynthesisError};
25use ark_std::fmt::Debug;
26use ark_std::{One, Zero};
27use core::{borrow::Borrow, marker::PhantomData};
28
29use super::circuits::CF2;
30use super::CommittedInstance;
31use crate::constants::N_BITS_RO;
32use crate::folding::circuits::nonnative::nonnative_field_var_to_constraint_field;
33use crate::Error;
34
35// public inputs length for the CycleFoldCircuit: |[r, p1.x,y, p2.x,y, p3.x,y]|
36pub const CF_IO_LEN: usize = 7;
37
38/// CycleFoldCommittedInstanceVar is the CycleFold CommittedInstance representation in the Nova
39/// circuit.
40#[derive(Debug, Clone)]
41pub struct CycleFoldCommittedInstanceVar<C: CurveGroup, GC: CurveVar<C, CF2<C>>>
42where
43 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
44{
45 _c: PhantomData<C>,
46 pub cmE: GC,
47 pub u: NonNativeFieldVar<C::ScalarField, CF2<C>>,
48 pub cmW: GC,
49 pub x: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>,
50}
51impl<C, GC> AllocVar<CommittedInstance<C>, CF2<C>> for CycleFoldCommittedInstanceVar<C, GC>
52where
53 C: CurveGroup,
54 GC: CurveVar<C, CF2<C>>,
55 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
56 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
57{
58 fn new_variable<T: Borrow<CommittedInstance<C>>>(
59 cs: impl Into<Namespace<CF2<C>>>,
60 f: impl FnOnce() -> Result<T, SynthesisError>,
61 mode: AllocationMode,
62 ) -> Result<Self, SynthesisError> {
63 f().and_then(|val| {
64 let cs = cs.into();
65
66 let cmE = GC::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
67 let cmW = GC::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
68 let u = NonNativeFieldVar::<C::ScalarField, CF2<C>>::new_variable(
69 cs.clone(),
70 || Ok(val.borrow().u),
71 mode,
72 )?;
73 let x = Vec::<NonNativeFieldVar<C::ScalarField, CF2<C>>>::new_variable(
74 cs.clone(),
75 || Ok(val.borrow().x.clone()),
76 mode,
77 )?;
78
79 Ok(Self {
80 _c: PhantomData,
81 cmE,
82 u,
83 cmW,
84 x,
85 })
86 })
87 }
88}
89
90impl<C, GC> ToConstraintFieldGadget<CF2<C>> for CycleFoldCommittedInstanceVar<C, GC>
91where
92 C: CurveGroup,
93 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
94 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
95 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
96{
97 // Extract the underlying field elements from `CycleFoldCommittedInstanceVar`, in the order of
98 // `u`, `x`, `cmE.x`, `cmE.y`, `cmW.x`, `cmW.y`, `cmE.is_inf || cmW.is_inf` (|| is for concat).
99 fn to_constraint_field(&self) -> Result<Vec<FpVar<CF2<C>>>, SynthesisError> {
100 let mut cmE_elems = self.cmE.to_constraint_field()?;
101 let mut cmW_elems = self.cmW.to_constraint_field()?;
102
103 let cmE_is_inf = cmE_elems.pop().unwrap();
104 let cmW_is_inf = cmW_elems.pop().unwrap();
105 // Concatenate `cmE_is_inf` and `cmW_is_inf` to save constraints for CRHGadget::evaluate
106 let is_inf = cmE_is_inf.double()? + cmW_is_inf;
107
108 Ok([
109 nonnative_field_var_to_constraint_field(&self.u)?,
110 self.x
111 .iter()
112 .map(nonnative_field_var_to_constraint_field)
113 .collect::<Result<Vec<_>, _>>()?
114 .concat(),
115 cmE_elems,
116 cmW_elems,
117 vec![is_inf],
118 ]
119 .concat())
120 }
121}
122
123impl<C, GC> CycleFoldCommittedInstanceVar<C, GC>
124where
125 C: CurveGroup,
126 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
127 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
128 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
129{
130 /// hash implements the committed instance hash compatible with the native implementation from
131 /// CommittedInstance.hash_cyclefold.
132 /// Returns `H(U_i)`, where `U` is the `CommittedInstance` for CycleFold.
133 /// Additionally it returns the vector of the field elements from the self parameters, so they
134 /// can be reused in other gadgets avoiding recalculating (reconstraining) them.
135 #[allow(clippy::type_complexity)]
136 pub fn hash(
137 self,
138 crh_params: &CRHParametersVar<CF2<C>>,
139 ) -> Result<(FpVar<CF2<C>>, Vec<FpVar<CF2<C>>>), SynthesisError> {
140 let U_vec = self.to_constraint_field()?;
141 Ok((CRHGadget::evaluate(crh_params, &U_vec)?, U_vec))
142 }
143}
144
145/// CommittedInstanceInCycleFoldVar represents the Nova CommittedInstance in the CycleFold circuit,
146/// where the commitments to E and W (cmW and cmW) from the CommittedInstance on the E2,
147/// represented as native points, which are folded on the auxiliary curve constraints field (E2::Fr
148/// = E1::Fq).
149#[derive(Debug, Clone)]
150pub struct CommittedInstanceInCycleFoldVar<C: CurveGroup, GC: CurveVar<C, CF2<C>>>
151where
152 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
153{
154 _c: PhantomData<C>,
155 pub cmE: GC,
156 pub cmW: GC,
157}
158
159impl<C, GC> AllocVar<CommittedInstance<C>, CF2<C>> for CommittedInstanceInCycleFoldVar<C, GC>
160where
161 C: CurveGroup,
162 GC: CurveVar<C, CF2<C>>,
163 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
164{
165 fn new_variable<T: Borrow<CommittedInstance<C>>>(
166 cs: impl Into<Namespace<CF2<C>>>,
167 f: impl FnOnce() -> Result<T, SynthesisError>,
168 mode: AllocationMode,
169 ) -> Result<Self, SynthesisError> {
170 f().and_then(|val| {
171 let cs = cs.into();
172
173 let cmE = GC::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
174 let cmW = GC::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
175
176 Ok(Self {
177 _c: PhantomData,
178 cmE,
179 cmW,
180 })
181 })
182 }
183}
184
185/// This is the gadget used in the AugmentedFCircuit to verify the CycleFold instances folding,
186/// which checks the correct RLC of u,x,cmE,cmW (hence the name containing 'Full', since it checks
187/// all the RLC values, not only the native ones). It assumes that ci2.cmE=0, ci2.u=1.
188pub struct NIFSFullGadget<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
189 _c: PhantomData<C>,
190 _gc: PhantomData<GC>,
191}
192impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> NIFSFullGadget<C, GC>
193where
194 C: CurveGroup,
195 GC: CurveVar<C, CF2<C>>,
196 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
197 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
198{
199 pub fn verify(
200 // assumes that r_bits is equal to r_nonnat just that in a different format
201 r_bits: Vec<Boolean<CF2<C>>>,
202 r_nonnat: NonNativeFieldVar<C::ScalarField, CF2<C>>,
203 cmT: GC,
204 // ci1 is assumed to be always with cmE=0, u=1 (checks done previous to this method)
205 ci1: CycleFoldCommittedInstanceVar<C, GC>,
206 ci2: CycleFoldCommittedInstanceVar<C, GC>,
207 ci3: CycleFoldCommittedInstanceVar<C, GC>,
208 ) -> Result<Boolean<CF2<C>>, SynthesisError> {
209 // cm(E) check: ci3.cmE == ci1.cmE + r * cmT (ci2.cmE=0)
210 let first_check = ci3
211 .cmE
212 .is_eq(&(cmT.scalar_mul_le(r_bits.iter())? + ci1.cmE))?;
213
214 // cm(W) check: ci3.cmW == ci1.cmW + r * ci2.cmW
215 let second_check = ci3
216 .cmW
217 .is_eq(&(ci1.cmW + ci2.cmW.scalar_mul_le(r_bits.iter())?))?;
218
219 let u_rlc: NonNativeFieldVar<C::ScalarField, CF2<C>> = ci1.u + r_nonnat.clone();
220 let third_check = u_rlc.is_eq(&ci3.u)?;
221
222 // ensure that: ci3.x == ci1.x + r * ci2.x
223 let x_rlc: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>> = ci1
224 .x
225 .iter()
226 .zip(ci2.x)
227 .map(|(a, b)| a + &r_nonnat * &b)
228 .collect::<Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>>();
229 let fourth_check = x_rlc.is_eq(&ci3.x)?;
230
231 first_check
232 .and(&second_check)?
233 .and(&third_check)?
234 .and(&fourth_check)
235 }
236}
237
238/// CycleFoldChallengeGadget computes the RO challenge used for the CycleFold instances NIFS, it contains a
239/// rust-native and a in-circuit compatible versions.
240pub struct CycleFoldChallengeGadget<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
241 _c: PhantomData<C>, // Nova's Curve2, the one used for the CycleFold circuit
242 _gc: PhantomData<GC>,
243}
244impl<C, GC> CycleFoldChallengeGadget<C, GC>
245where
246 C: CurveGroup,
247 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
248 <C as CurveGroup>::BaseField: PrimeField,
249 <C as CurveGroup>::BaseField: Absorb,
250 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
251{
252 pub fn get_challenge_native(
253 poseidon_config: &PoseidonConfig<C::BaseField>,
254 U_i: CommittedInstance<C>,
255 u_i: CommittedInstance<C>,
256 cmT: C,
257 ) -> Result<Vec<bool>, Error> {
258 let mut sponge = PoseidonSponge::<C::BaseField>::new(poseidon_config);
259
260 let mut U_vec = U_i.to_field_elements().unwrap();
261 let mut u_vec = u_i.to_field_elements().unwrap();
262 let (cmT_x, cmT_y, cmT_is_inf) = match cmT.into_affine().xy() {
263 Some((&x, &y)) => (x, y, C::BaseField::zero()),
264 None => (
265 C::BaseField::zero(),
266 C::BaseField::zero(),
267 C::BaseField::one(),
268 ),
269 };
270
271 let U_cm_is_inf = U_vec.pop().unwrap();
272 let u_cm_is_inf = u_vec.pop().unwrap();
273
274 // Concatenate `U_i.cmE_is_inf`, `U_i.cmW_is_inf`, `u_i.cmE_is_inf`, `u_i.cmW_is_inf`, `cmT_is_inf`
275 // to save constraints for sponge.squeeze_bits in the corresponding circuit
276 let is_inf = U_cm_is_inf * CF2::<C>::from(8u8) + u_cm_is_inf.double() + cmT_is_inf;
277
278 let input = [U_vec, u_vec, vec![cmT_x, cmT_y, is_inf]].concat();
279 sponge.absorb(&input);
280 let bits = sponge.squeeze_bits(N_BITS_RO);
281 Ok(bits)
282 }
283
284 // compatible with the native get_challenge_native
285 pub fn get_challenge_gadget(
286 cs: ConstraintSystemRef<C::BaseField>,
287 poseidon_config: &PoseidonConfig<C::BaseField>,
288 U_i: CycleFoldCommittedInstanceVar<C, GC>,
289 u_i: CycleFoldCommittedInstanceVar<C, GC>,
290 cmT: GC,
291 ) -> Result<Vec<Boolean<C::BaseField>>, SynthesisError> {
292 let mut sponge = PoseidonSpongeVar::<C::BaseField>::new(cs, poseidon_config);
293
294 let mut U_vec = U_i.to_constraint_field()?;
295 let mut u_vec = u_i.to_constraint_field()?;
296 let mut cmT_vec = cmT.to_constraint_field()?;
297
298 let U_cm_is_inf = U_vec.pop().unwrap();
299 let u_cm_is_inf = u_vec.pop().unwrap();
300 let cmT_is_inf = cmT_vec.pop().unwrap();
301
302 // Concatenate `U_i.cmE_is_inf`, `U_i.cmW_is_inf`, `u_i.cmE_is_inf`, `u_i.cmW_is_inf`, `cmT_is_inf`
303 // to save constraints for sponge.squeeze_bits
304 let is_inf = U_cm_is_inf * CF2::<C>::from(8u8) + u_cm_is_inf.double()? + cmT_is_inf;
305
306 let input = [U_vec, u_vec, cmT_vec, vec![is_inf]].concat();
307 sponge.absorb(&input)?;
308 let bits = sponge.squeeze_bits(N_BITS_RO)?;
309 Ok(bits)
310 }
311}
312
313/// CycleFoldCircuit contains the constraints that check the correct fold of the committed
314/// instances from Curve1. Namely, it checks the random linear combinations of the elliptic curve
315/// (Curve1) points of u_i, U_i leading to U_{i+1}
316#[derive(Debug, Clone)]
317pub struct CycleFoldCircuit<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
318 pub _gc: PhantomData<GC>,
319 pub r_bits: Option<Vec<bool>>,
320 pub p1: Option<C>,
321 pub p2: Option<C>,
322 pub p3: Option<C>,
323 pub x: Option<Vec<CF2<C>>>, // public inputs (cf_u_{i+1}.x)
324}
325impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> CycleFoldCircuit<C, GC> {
326 pub fn empty() -> Self {
327 Self {
328 _gc: PhantomData,
329 r_bits: None,
330 p1: None,
331 p2: None,
332 p3: None,
333 x: None,
334 }
335 }
336}
337impl<C, GC> ConstraintSynthesizer<CF2<C>> for CycleFoldCircuit<C, GC>
338where
339 C: CurveGroup,
340 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
341 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
342 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
343{
344 fn generate_constraints(self, cs: ConstraintSystemRef<CF2<C>>) -> Result<(), SynthesisError> {
345 let r_bits: Vec<Boolean<CF2<C>>> = Vec::new_witness(cs.clone(), || {
346 Ok(self.r_bits.unwrap_or(vec![false; N_BITS_RO]))
347 })?;
348 let p1 = GC::new_witness(cs.clone(), || Ok(self.p1.unwrap_or(C::zero())))?;
349 let p2 = GC::new_witness(cs.clone(), || Ok(self.p2.unwrap_or(C::zero())))?;
350 let p3 = GC::new_witness(cs.clone(), || Ok(self.p3.unwrap_or(C::zero())))?;
351
352 let x = Vec::<FpVar<CF2<C>>>::new_input(cs.clone(), || {
353 Ok(self.x.unwrap_or(vec![CF2::<C>::zero(); CF_IO_LEN]))
354 })?;
355 #[cfg(test)]
356 assert_eq!(x.len(), CF_IO_LEN); // non-constrained sanity check
357
358 // check that the points coordinates are placed as the public input x: x == [r, p1, p2, p3]
359 let r: FpVar<CF2<C>> = Boolean::le_bits_to_fp_var(&r_bits)?;
360 let points_coords: Vec<FpVar<CF2<C>>> = [
361 vec![r],
362 p1.clone().to_constraint_field()?[..2].to_vec(),
363 p2.clone().to_constraint_field()?[..2].to_vec(),
364 p3.clone().to_constraint_field()?[..2].to_vec(),
365 ]
366 .concat();
367 points_coords.enforce_equal(&x)?;
368
369 // Fold the original Nova instances natively in CycleFold
370 // For the cmW we're checking: U_i1.cmW == U_i.cmW + r * u_i.cmW
371 // For the cmE we're checking: U_i1.cmE == U_i.cmE + r * cmT + r^2 * u_i.cmE, where u_i.cmE
372 // is assumed to be 0, so, U_i1.cmE == U_i.cmE + r * cmT
373 p3.enforce_equal(&(p1 + p2.scalar_mul_le(r_bits.iter())?))?;
374
375 Ok(())
376 }
377}
378
379#[cfg(test)]
380pub mod tests {
381 use super::*;
382 use ark_bn254::{constraints::GVar, Fq, Fr, G1Projective as Projective};
383 use ark_ff::BigInteger;
384 use ark_r1cs_std::R1CSVar;
385 use ark_relations::r1cs::ConstraintSystem;
386 use ark_std::UniformRand;
387
388 use crate::folding::nova::get_cm_coordinates;
389 use crate::folding::nova::nifs::tests::prepare_simple_fold_inputs;
390 use crate::transcript::poseidon::poseidon_test_config;
391
392 #[test]
393 fn test_committed_instance_cyclefold_var() {
394 let mut rng = ark_std::test_rng();
395
396 let ci = CommittedInstance::<Projective> {
397 cmE: Projective::rand(&mut rng),
398 u: Fr::rand(&mut rng),
399 cmW: Projective::rand(&mut rng),
400 x: vec![Fr::rand(&mut rng); 1],
401 };
402
403 // check the instantiation of the CycleFold side:
404 let cs = ConstraintSystem::<Fq>::new_ref();
405 let ciVar =
406 CommittedInstanceInCycleFoldVar::<Projective, GVar>::new_witness(cs.clone(), || {
407 Ok(ci.clone())
408 })
409 .unwrap();
410 assert_eq!(ciVar.cmE.value().unwrap(), ci.cmE);
411 assert_eq!(ciVar.cmW.value().unwrap(), ci.cmW);
412 }
413
414 #[test]
415 fn test_CycleFoldCircuit_constraints() {
416 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, _) = prepare_simple_fold_inputs();
417 let r_Fq = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
418
419 // cs is the Constraint System on the Curve Cycle auxiliary curve constraints field
420 // (E1::Fq=E2::Fr)
421 let cs = ConstraintSystem::<Fq>::new_ref();
422
423 let cfW_u_i_x: Vec<Fq> = [
424 vec![r_Fq],
425 get_cm_coordinates(&ci1.cmW),
426 get_cm_coordinates(&ci2.cmW),
427 get_cm_coordinates(&ci3.cmW),
428 ]
429 .concat();
430 let cfW_circuit = CycleFoldCircuit::<Projective, GVar> {
431 _gc: PhantomData,
432 r_bits: Some(r_bits.clone()),
433 p1: Some(ci1.clone().cmW),
434 p2: Some(ci2.clone().cmW),
435 p3: Some(ci3.clone().cmW),
436 x: Some(cfW_u_i_x.clone()),
437 };
438 cfW_circuit.generate_constraints(cs.clone()).unwrap();
439 assert!(cs.is_satisfied().unwrap());
440
441 // same for E:
442 let cs = ConstraintSystem::<Fq>::new_ref();
443 let cfE_u_i_x = [
444 vec![r_Fq],
445 get_cm_coordinates(&ci1.cmE),
446 get_cm_coordinates(&cmT),
447 get_cm_coordinates(&ci3.cmE),
448 ]
449 .concat();
450 let cfE_circuit = CycleFoldCircuit::<Projective, GVar> {
451 _gc: PhantomData,
452 r_bits: Some(r_bits.clone()),
453 p1: Some(ci1.clone().cmE),
454 p2: Some(cmT),
455 p3: Some(ci3.clone().cmE),
456 x: Some(cfE_u_i_x.clone()),
457 };
458 cfE_circuit.generate_constraints(cs.clone()).unwrap();
459 assert!(cs.is_satisfied().unwrap());
460 }
461
462 #[test]
463 fn test_nifs_full_gadget() {
464 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, r_Fr) = prepare_simple_fold_inputs();
465
466 let cs = ConstraintSystem::<Fq>::new_ref();
467
468 let r_nonnatVar =
469 NonNativeFieldVar::<Fr, Fq>::new_witness(cs.clone(), || Ok(r_Fr)).unwrap();
470 let r_bitsVar = Vec::<Boolean<Fq>>::new_witness(cs.clone(), || Ok(r_bits)).unwrap();
471
472 let ci1Var =
473 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
474 Ok(ci1.clone())
475 })
476 .unwrap();
477 let ci2Var =
478 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
479 Ok(ci2.clone())
480 })
481 .unwrap();
482 let ci3Var =
483 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
484 Ok(ci3.clone())
485 })
486 .unwrap();
487 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
488
489 let nifs_check = NIFSFullGadget::<Projective, GVar>::verify(
490 r_bitsVar,
491 r_nonnatVar,
492 cmTVar,
493 ci1Var,
494 ci2Var,
495 ci3Var,
496 )
497 .unwrap();
498 nifs_check.enforce_equal(&Boolean::<Fq>::TRUE).unwrap();
499 assert!(cs.is_satisfied().unwrap());
500 }
501
502 #[test]
503 fn test_cyclefold_challenge_gadget() {
504 let mut rng = ark_std::test_rng();
505 let poseidon_config = poseidon_test_config::<Fq>();
506
507 let u_i = CommittedInstance::<Projective> {
508 cmE: Projective::zero(), // zero on purpose, so we test also the zero point case
509 u: Fr::zero(),
510 cmW: Projective::rand(&mut rng),
511 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
512 .take(CF_IO_LEN)
513 .collect(),
514 };
515 let U_i = CommittedInstance::<Projective> {
516 cmE: Projective::rand(&mut rng),
517 u: Fr::rand(&mut rng),
518 cmW: Projective::rand(&mut rng),
519 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
520 .take(CF_IO_LEN)
521 .collect(),
522 };
523 let cmT = Projective::rand(&mut rng);
524
525 // compute the challenge natively
526 let r_bits = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_native(
527 &poseidon_config,
528 U_i.clone(),
529 u_i.clone(),
530 cmT,
531 )
532 .unwrap();
533
534 let cs = ConstraintSystem::<Fq>::new_ref();
535 let u_iVar =
536 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
537 Ok(u_i.clone())
538 })
539 .unwrap();
540 let U_iVar =
541 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
542 Ok(U_i.clone())
543 })
544 .unwrap();
545 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
546
547 let r_bitsVar = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_gadget(
548 cs.clone(),
549 &poseidon_config,
550 U_iVar,
551 u_iVar,
552 cmTVar,
553 )
554 .unwrap();
555 assert!(cs.is_satisfied().unwrap());
556
557 // check that the natively computed and in-circuit computed hashes match
558 let rVar = Boolean::le_bits_to_fp_var(&r_bitsVar).unwrap();
559 let r = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
560 assert_eq!(rVar.value().unwrap(), r);
561 assert_eq!(r_bitsVar.value().unwrap(), r_bits);
562 }
563
564 #[test]
565 fn test_cyclefold_hash_gadget() {
566 let mut rng = ark_std::test_rng();
567 let poseidon_config = poseidon_test_config::<Fq>();
568
569 let U_i = CommittedInstance::<Projective> {
570 cmE: Projective::rand(&mut rng),
571 u: Fr::rand(&mut rng),
572 cmW: Projective::rand(&mut rng),
573 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
574 .take(CF_IO_LEN)
575 .collect(),
576 };
577 let h = U_i.hash_cyclefold(&poseidon_config).unwrap();
578
579 let cs = ConstraintSystem::<Fq>::new_ref();
580 let U_iVar =
581 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
582 Ok(U_i.clone())
583 })
584 .unwrap();
585 let (hVar, _) = U_iVar
586 .hash(&CRHParametersVar::new_constant(cs.clone(), poseidon_config).unwrap())
587 .unwrap();
588 hVar.enforce_equal(&FpVar::new_witness(cs.clone(), || Ok(h)).unwrap())
589 .unwrap();
590 assert!(cs.is_satisfied().unwrap());
591 }
592}