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