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::arith::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 pp_hash: FpVar<CF2<C>>, // public params hash
131 ) -> Result<(FpVar<CF2<C>>, Vec<FpVar<CF2<C>>>), SynthesisError> {
132 let U_vec = self.to_constraint_field()?;
133 Ok((
134 CRHGadget::evaluate(crh_params, &[vec![pp_hash], U_vec.clone()].concat())?,
135 U_vec,
136 ))
137 }
138}
139
140/// CommittedInstanceInCycleFoldVar represents the Nova CommittedInstance in the CycleFold circuit,
141/// where the commitments to E and W (cmW and cmW) from the CommittedInstance on the E2,
142/// represented as native points, which are folded on the auxiliary curve constraints field (E2::Fr
143/// = E1::Fq).
144#[derive(Debug, Clone)]
145pub struct CommittedInstanceInCycleFoldVar<C: CurveGroup, GC: CurveVar<C, CF2<C>>>
146where
147 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
148{
149 _c: PhantomData<C>,
150 pub cmE: GC,
151 pub cmW: GC,
152}
153
154impl<C, GC> AllocVar<CommittedInstance<C>, CF2<C>> for CommittedInstanceInCycleFoldVar<C, GC>
155where
156 C: CurveGroup,
157 GC: CurveVar<C, CF2<C>>,
158 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
159{
160 fn new_variable<T: Borrow<CommittedInstance<C>>>(
161 cs: impl Into<Namespace<CF2<C>>>,
162 f: impl FnOnce() -> Result<T, SynthesisError>,
163 mode: AllocationMode,
164 ) -> Result<Self, SynthesisError> {
165 f().and_then(|val| {
166 let cs = cs.into();
167
168 let cmE = GC::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
169 let cmW = GC::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
170
171 Ok(Self {
172 _c: PhantomData,
173 cmE,
174 cmW,
175 })
176 })
177 }
178}
179
180/// This is the gadget used in the AugmentedFCircuit to verify the CycleFold instances folding,
181/// which checks the correct RLC of u,x,cmE,cmW (hence the name containing 'Full', since it checks
182/// all the RLC values, not only the native ones). It assumes that ci2.cmE=0, ci2.u=1.
183pub struct NIFSFullGadget<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
184 _c: PhantomData<C>,
185 _gc: PhantomData<GC>,
186}
187
188impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> NIFSFullGadget<C, GC>
189where
190 C: CurveGroup,
191 GC: CurveVar<C, CF2<C>>,
192 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
193 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
194{
195 pub fn fold_committed_instance(
196 // assumes that r_bits is equal to r_nonnat just that in a different format
197 r_bits: Vec<Boolean<CF2<C>>>,
198 r_nonnat: NonNativeUintVar<CF2<C>>,
199 cmT: GC,
200 ci1: CycleFoldCommittedInstanceVar<C, GC>,
201 // ci2 is assumed to be always with cmE=0, u=1 (checks done previous to this method)
202 ci2: CycleFoldCommittedInstanceVar<C, GC>,
203 ) -> Result<CycleFoldCommittedInstanceVar<C, GC>, SynthesisError> {
204 Ok(CycleFoldCommittedInstanceVar {
205 cmE: cmT.scalar_mul_le(r_bits.iter())? + ci1.cmE,
206 cmW: ci1.cmW + ci2.cmW.scalar_mul_le(r_bits.iter())?,
207 u: ci1.u.add_no_align(&r_nonnat).modulo::<C::ScalarField>()?,
208 x: ci1
209 .x
210 .iter()
211 .zip(ci2.x)
212 .map(|(a, b)| {
213 a.add_no_align(&r_nonnat.mul_no_align(&b)?)
214 .modulo::<C::ScalarField>()
215 })
216 .collect::<Result<Vec<_>, _>>()?,
217 })
218 }
219
220 pub fn verify(
221 // assumes that r_bits is equal to r_nonnat just that in a different format
222 r_bits: Vec<Boolean<CF2<C>>>,
223 r_nonnat: NonNativeUintVar<CF2<C>>,
224 cmT: GC,
225 ci1: CycleFoldCommittedInstanceVar<C, GC>,
226 // ci2 is assumed to be always with cmE=0, u=1 (checks done previous to this method)
227 ci2: CycleFoldCommittedInstanceVar<C, GC>,
228 ci3: CycleFoldCommittedInstanceVar<C, GC>,
229 ) -> Result<(), SynthesisError> {
230 let ci = Self::fold_committed_instance(r_bits, r_nonnat, cmT, ci1, ci2)?;
231
232 ci.cmE.enforce_equal(&ci3.cmE)?;
233 ci.u.enforce_equal_unaligned(&ci3.u)?;
234 ci.cmW.enforce_equal(&ci3.cmW)?;
235 for (x, y) in ci.x.iter().zip(ci3.x.iter()) {
236 x.enforce_equal_unaligned(y)?;
237 }
238
239 Ok(())
240 }
241}
242
243/// CycleFoldChallengeGadget computes the RO challenge used for the CycleFold instances NIFS, it contains a
244/// rust-native and a in-circuit compatible versions.
245pub struct CycleFoldChallengeGadget<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
246 _c: PhantomData<C>, // Nova's Curve2, the one used for the CycleFold circuit
247 _gc: PhantomData<GC>,
248}
249impl<C, GC> CycleFoldChallengeGadget<C, GC>
250where
251 C: CurveGroup,
252 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
253 <C as CurveGroup>::BaseField: PrimeField,
254 <C as CurveGroup>::BaseField: Absorb,
255 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
256{
257 pub fn get_challenge_native(
258 poseidon_config: &PoseidonConfig<C::BaseField>,
259 pp_hash: C::BaseField, // public params hash
260 U_i: CommittedInstance<C>,
261 u_i: CommittedInstance<C>,
262 cmT: C,
263 ) -> Result<Vec<bool>, Error> {
264 let mut sponge = PoseidonSponge::<C::BaseField>::new(poseidon_config);
265
266 let mut U_vec = U_i.to_field_elements().unwrap();
267 let mut u_vec = u_i.to_field_elements().unwrap();
268 let (cmT_x, cmT_y, cmT_is_inf) = match cmT.into_affine().xy() {
269 Some((&x, &y)) => (x, y, C::BaseField::zero()),
270 None => (
271 C::BaseField::zero(),
272 C::BaseField::zero(),
273 C::BaseField::one(),
274 ),
275 };
276
277 let U_cm_is_inf = U_vec.pop().unwrap();
278 let u_cm_is_inf = u_vec.pop().unwrap();
279
280 // Concatenate `U_i.cmE_is_inf`, `U_i.cmW_is_inf`, `u_i.cmE_is_inf`, `u_i.cmW_is_inf`, `cmT_is_inf`
281 // to save constraints for sponge.squeeze_bits in the corresponding circuit
282 let is_inf = U_cm_is_inf * CF2::<C>::from(8u8) + u_cm_is_inf.double() + cmT_is_inf;
283
284 let input = [vec![pp_hash], U_vec, u_vec, vec![cmT_x, cmT_y, is_inf]].concat();
285 sponge.absorb(&input);
286 let bits = sponge.squeeze_bits(N_BITS_RO);
287 Ok(bits)
288 }
289
290 // compatible with the native get_challenge_native
291 pub fn get_challenge_gadget(
292 cs: ConstraintSystemRef<C::BaseField>,
293 poseidon_config: &PoseidonConfig<C::BaseField>,
294 pp_hash: FpVar<C::BaseField>, // public params hash
295 mut U_i_vec: Vec<FpVar<C::BaseField>>,
296 u_i: CycleFoldCommittedInstanceVar<C, GC>,
297 cmT: GC,
298 ) -> Result<Vec<Boolean<C::BaseField>>, SynthesisError> {
299 let mut sponge = PoseidonSpongeVar::<C::BaseField>::new(cs, poseidon_config);
300
301 let mut u_i_vec = u_i.to_constraint_field()?;
302 let mut cmT_vec = cmT.to_constraint_field()?;
303
304 let U_cm_is_inf = U_i_vec.pop().unwrap();
305 let u_cm_is_inf = u_i_vec.pop().unwrap();
306 let cmT_is_inf = cmT_vec.pop().unwrap();
307
308 // Concatenate `U_i.cmE_is_inf`, `U_i.cmW_is_inf`, `u_i.cmE_is_inf`, `u_i.cmW_is_inf`, `cmT_is_inf`
309 // to save constraints for sponge.squeeze_bits
310 let is_inf = U_cm_is_inf * CF2::<C>::from(8u8) + u_cm_is_inf.double()? + cmT_is_inf;
311
312 let input = [vec![pp_hash], U_i_vec, u_i_vec, cmT_vec, vec![is_inf]].concat();
313 sponge.absorb(&input)?;
314 let bits = sponge.squeeze_bits(N_BITS_RO)?;
315 Ok(bits)
316 }
317}
318
319/// CycleFoldCircuit contains the constraints that check the correct fold of the committed
320/// instances from Curve1. Namely, it checks the random linear combinations of the elliptic curve
321/// (Curve1) points of u_i, U_i leading to U_{i+1}
322#[derive(Debug, Clone)]
323pub struct CycleFoldCircuit<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
324 pub _gc: PhantomData<GC>,
325 pub r_bits: Option<Vec<bool>>,
326 pub p1: Option<C>,
327 pub p2: Option<C>,
328 pub x: Option<Vec<CF2<C>>>, // public inputs (cf_u_{i+1}.x)
329}
330impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> CycleFoldCircuit<C, GC> {
331 pub fn empty() -> Self {
332 Self {
333 _gc: PhantomData,
334 r_bits: None,
335 p1: None,
336 p2: None,
337 x: None,
338 }
339 }
340}
341impl<C, GC> ConstraintSynthesizer<CF2<C>> for CycleFoldCircuit<C, GC>
342where
343 C: CurveGroup,
344 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
345 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
346 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
347{
348 fn generate_constraints(self, cs: ConstraintSystemRef<CF2<C>>) -> Result<(), SynthesisError> {
349 let r_bits: Vec<Boolean<CF2<C>>> = Vec::new_witness(cs.clone(), || {
350 Ok(self.r_bits.unwrap_or(vec![false; N_BITS_RO]))
351 })?;
352 let p1 = GC::new_witness(cs.clone(), || Ok(self.p1.unwrap_or(C::zero())))?;
353 let p2 = GC::new_witness(cs.clone(), || Ok(self.p2.unwrap_or(C::zero())))?;
354 // Fold the original Nova instances natively in CycleFold
355 // For the cmW we're computing: U_i1.cmW = U_i.cmW + r * u_i.cmW
356 // For the cmE we're computing: U_i1.cmE = U_i.cmE + r * cmT + r^2 * u_i.cmE, where u_i.cmE
357 // is assumed to be 0, so, U_i1.cmE = U_i.cmE + r * cmT
358 let p3 = &p1 + p2.scalar_mul_le(r_bits.iter())?;
359
360 let x = Vec::<FpVar<CF2<C>>>::new_input(cs.clone(), || {
361 Ok(self.x.unwrap_or(vec![CF2::<C>::zero(); CF_IO_LEN]))
362 })?;
363 #[cfg(test)]
364 assert_eq!(x.len(), CF_IO_LEN); // non-constrained sanity check
365
366 // check that the points coordinates are placed as the public input x: x == [r, p1, p2, p3]
367 let r: FpVar<CF2<C>> = Boolean::le_bits_to_fp_var(&r_bits)?;
368 let points_coords: Vec<FpVar<CF2<C>>> = [
369 vec![r],
370 p1.to_constraint_field()?[..2].to_vec(),
371 p2.to_constraint_field()?[..2].to_vec(),
372 p3.to_constraint_field()?[..2].to_vec(),
373 ]
374 .concat();
375 points_coords.enforce_equal(&x)?;
376
377 Ok(())
378 }
379}
380
381/// Folds the given cyclefold circuit and its instances. This method is abstracted from any folding
382/// scheme struct because it is used both by Nova & HyperNova's CycleFold.
383#[allow(clippy::type_complexity)]
384#[allow(clippy::too_many_arguments)]
385pub fn fold_cyclefold_circuit<C1, GC1, C2, GC2, FC, CS1, CS2>(
386 poseidon_config: &PoseidonConfig<C1::ScalarField>,
387 cf_r1cs: R1CS<C2::ScalarField>,
388 cf_cs_params: CS2::ProverParams,
389 pp_hash: C1::ScalarField, // public params hash
390 cf_W_i: Witness<C2>, // witness of the running instance
391 cf_U_i: CommittedInstance<C2>, // running instance
392 cf_u_i_x: Vec<C2::ScalarField>,
393 cf_circuit: CycleFoldCircuit<C1, GC1>,
394) -> Result<
395 (
396 Witness<C2>,
397 CommittedInstance<C2>, // u_i
398 Witness<C2>, // W_i1
399 CommittedInstance<C2>, // U_i1
400 C2, // cmT
401 C2::ScalarField, // r_Fq
402 ),
403 Error,
404>
405where
406 C1: CurveGroup,
407 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
408 C2: CurveGroup,
409 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
410 FC: FCircuit<C1::ScalarField>,
411 CS1: CommitmentScheme<C1>,
412 CS2: CommitmentScheme<C2>,
413 <C1 as CurveGroup>::BaseField: PrimeField,
414 <C2 as CurveGroup>::BaseField: PrimeField,
415 <C1 as Group>::ScalarField: Absorb,
416 <C2 as Group>::ScalarField: Absorb,
417 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
418 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
419 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
420{
421 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
422 cf_circuit.generate_constraints(cs2.clone())?;
423
424 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
425 let (cf_w_i, cf_x_i) = extract_w_x::<C1::BaseField>(&cs2);
426 if cf_x_i != cf_u_i_x {
427 return Err(Error::NotEqual);
428 }
429
430 #[cfg(test)]
431 assert_eq!(cf_x_i.len(), CF_IO_LEN);
432
433 // fold cyclefold instances
434 let cf_w_i = Witness::<C2>::new(cf_w_i.clone(), cf_r1cs.A.n_rows);
435 let cf_u_i: CommittedInstance<C2> = cf_w_i.commit::<CS2>(&cf_cs_params, cf_x_i.clone())?;
436
437 // compute T* and cmT* for CycleFoldCircuit
438 let (cf_T, cf_cmT) = NIFS::<C2, CS2>::compute_cyclefold_cmT(
439 &cf_cs_params,
440 &cf_r1cs,
441 &cf_w_i,
442 &cf_u_i,
443 &cf_W_i,
444 &cf_U_i,
445 )?;
446
447 let cf_r_bits = CycleFoldChallengeGadget::<C2, GC2>::get_challenge_native(
448 poseidon_config,
449 pp_hash,
450 cf_U_i.clone(),
451 cf_u_i.clone(),
452 cf_cmT,
453 )?;
454 let cf_r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&cf_r_bits))
455 .expect("cf_r_bits out of bounds");
456
457 let (cf_W_i1, cf_U_i1) = NIFS::<C2, CS2>::fold_instances(
458 cf_r_Fq, &cf_W_i, &cf_U_i, &cf_w_i, &cf_u_i, &cf_T, cf_cmT,
459 )?;
460 Ok((cf_w_i, cf_u_i, cf_W_i1, cf_U_i1, cf_cmT, cf_r_Fq))
461}
462
463#[cfg(test)]
464pub mod tests {
465 use ark_bn254::{constraints::GVar, Fq, Fr, G1Projective as Projective};
466 use ark_ff::BigInteger;
467 use ark_r1cs_std::R1CSVar;
468 use ark_relations::r1cs::ConstraintSystem;
469 use ark_std::UniformRand;
470
471 use super::*;
472 use crate::folding::nova::nifs::tests::prepare_simple_fold_inputs;
473 use crate::transcript::poseidon::poseidon_canonical_config;
474 use crate::utils::get_cm_coordinates;
475
476 #[test]
477 fn test_committed_instance_cyclefold_var() {
478 let mut rng = ark_std::test_rng();
479
480 let ci = CommittedInstance::<Projective> {
481 cmE: Projective::rand(&mut rng),
482 u: Fr::rand(&mut rng),
483 cmW: Projective::rand(&mut rng),
484 x: vec![Fr::rand(&mut rng); 1],
485 };
486
487 // check the instantiation of the CycleFold side:
488 let cs = ConstraintSystem::<Fq>::new_ref();
489 let ciVar =
490 CommittedInstanceInCycleFoldVar::<Projective, GVar>::new_witness(cs.clone(), || {
491 Ok(ci.clone())
492 })
493 .unwrap();
494 assert_eq!(ciVar.cmE.value().unwrap(), ci.cmE);
495 assert_eq!(ciVar.cmW.value().unwrap(), ci.cmW);
496 }
497
498 #[test]
499 fn test_CycleFoldCircuit_constraints() {
500 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, _) = prepare_simple_fold_inputs();
501 let r_Fq = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
502
503 // cs is the Constraint System on the Curve Cycle auxiliary curve constraints field
504 // (E1::Fq=E2::Fr)
505 let cs = ConstraintSystem::<Fq>::new_ref();
506
507 let cfW_u_i_x: Vec<Fq> = [
508 vec![r_Fq],
509 get_cm_coordinates(&ci1.cmW),
510 get_cm_coordinates(&ci2.cmW),
511 get_cm_coordinates(&ci3.cmW),
512 ]
513 .concat();
514 let cfW_circuit = CycleFoldCircuit::<Projective, GVar> {
515 _gc: PhantomData,
516 r_bits: Some(r_bits.clone()),
517 p1: Some(ci1.clone().cmW),
518 p2: Some(ci2.clone().cmW),
519 x: Some(cfW_u_i_x.clone()),
520 };
521 cfW_circuit.generate_constraints(cs.clone()).unwrap();
522 assert!(cs.is_satisfied().unwrap());
523
524 // same for E:
525 let cs = ConstraintSystem::<Fq>::new_ref();
526 let cfE_u_i_x = [
527 vec![r_Fq],
528 get_cm_coordinates(&ci1.cmE),
529 get_cm_coordinates(&cmT),
530 get_cm_coordinates(&ci3.cmE),
531 ]
532 .concat();
533 let cfE_circuit = CycleFoldCircuit::<Projective, GVar> {
534 _gc: PhantomData,
535 r_bits: Some(r_bits.clone()),
536 p1: Some(ci1.clone().cmE),
537 p2: Some(cmT),
538 x: Some(cfE_u_i_x.clone()),
539 };
540 cfE_circuit.generate_constraints(cs.clone()).unwrap();
541 assert!(cs.is_satisfied().unwrap());
542 }
543
544 #[test]
545 fn test_nifs_full_gadget() {
546 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, r_Fr) = prepare_simple_fold_inputs();
547
548 let cs = ConstraintSystem::<Fq>::new_ref();
549
550 let r_nonnatVar = NonNativeUintVar::<Fq>::new_witness(cs.clone(), || Ok(r_Fr)).unwrap();
551 let r_bitsVar = Vec::<Boolean<Fq>>::new_witness(cs.clone(), || Ok(r_bits)).unwrap();
552
553 let ci1Var =
554 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
555 Ok(ci1.clone())
556 })
557 .unwrap();
558 let ci2Var =
559 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
560 Ok(ci2.clone())
561 })
562 .unwrap();
563 let ci3Var =
564 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
565 Ok(ci3.clone())
566 })
567 .unwrap();
568 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
569
570 NIFSFullGadget::<Projective, GVar>::verify(
571 r_bitsVar,
572 r_nonnatVar,
573 cmTVar,
574 ci1Var,
575 ci2Var,
576 ci3Var,
577 )
578 .unwrap();
579 assert!(cs.is_satisfied().unwrap());
580 }
581
582 #[test]
583 fn test_cyclefold_challenge_gadget() {
584 let mut rng = ark_std::test_rng();
585 let poseidon_config = poseidon_canonical_config::<Fq>();
586
587 let u_i = CommittedInstance::<Projective> {
588 cmE: Projective::zero(), // zero on purpose, so we test also the zero point case
589 u: Fr::zero(),
590 cmW: Projective::rand(&mut rng),
591 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
592 .take(CF_IO_LEN)
593 .collect(),
594 };
595 let U_i = CommittedInstance::<Projective> {
596 cmE: Projective::rand(&mut rng),
597 u: Fr::rand(&mut rng),
598 cmW: Projective::rand(&mut rng),
599 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
600 .take(CF_IO_LEN)
601 .collect(),
602 };
603 let cmT = Projective::rand(&mut rng);
604
605 // compute the challenge natively
606 let pp_hash = Fq::from(42u32); // only for test
607 let r_bits = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_native(
608 &poseidon_config,
609 pp_hash,
610 U_i.clone(),
611 u_i.clone(),
612 cmT,
613 )
614 .unwrap();
615
616 let cs = ConstraintSystem::<Fq>::new_ref();
617 let u_iVar =
618 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
619 Ok(u_i.clone())
620 })
621 .unwrap();
622 let U_iVar =
623 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
624 Ok(U_i.clone())
625 })
626 .unwrap();
627 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
628
629 let pp_hashVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
630 let r_bitsVar = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_gadget(
631 cs.clone(),
632 &poseidon_config,
633 pp_hashVar,
634 U_iVar.to_constraint_field().unwrap(),
635 u_iVar,
636 cmTVar,
637 )
638 .unwrap();
639 assert!(cs.is_satisfied().unwrap());
640
641 // check that the natively computed and in-circuit computed hashes match
642 let rVar = Boolean::le_bits_to_fp_var(&r_bitsVar).unwrap();
643 let r = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
644 assert_eq!(rVar.value().unwrap(), r);
645 assert_eq!(r_bitsVar.value().unwrap(), r_bits);
646 }
647
648 #[test]
649 fn test_cyclefold_hash_gadget() {
650 let mut rng = ark_std::test_rng();
651 let poseidon_config = poseidon_canonical_config::<Fq>();
652
653 let U_i = CommittedInstance::<Projective> {
654 cmE: Projective::rand(&mut rng),
655 u: Fr::rand(&mut rng),
656 cmW: Projective::rand(&mut rng),
657 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
658 .take(CF_IO_LEN)
659 .collect(),
660 };
661 let pp_hash = Fq::from(42u32); // only for test
662 let h = U_i.hash_cyclefold(&poseidon_config, pp_hash).unwrap();
663
664 let cs = ConstraintSystem::<Fq>::new_ref();
665 let U_iVar =
666 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
667 Ok(U_i.clone())
668 })
669 .unwrap();
670 let pp_hashVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
671 let (hVar, _) = U_iVar
672 .hash(
673 &CRHParametersVar::new_constant(cs.clone(), poseidon_config).unwrap(),
674 pp_hashVar,
675 )
676 .unwrap();
677 hVar.enforce_equal(&FpVar::new_witness(cs.clone(), || Ok(h)).unwrap())
678 .unwrap();
679 assert!(cs.is_satisfied().unwrap());
680 }
681}