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