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