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::sponge::{Absorb, CryptographicSponge};
4use ark_ec::{CurveGroup, Group};
5use ark_ff::{BigInteger, PrimeField};
6use ark_r1cs_std::{
7 alloc::{AllocVar, AllocationMode},
8 boolean::Boolean,
9 eq::EqGadget,
10 fields::fp::FpVar,
11 groups::GroupOpsBounds,
12 prelude::CurveVar,
13 ToConstraintFieldGadget,
14};
15use ark_relations::r1cs::{
16 ConstraintSynthesizer, ConstraintSystem, ConstraintSystemRef, Namespace, SynthesisError,
17};
18use ark_std::fmt::Debug;
19use ark_std::rand::RngCore;
20use ark_std::Zero;
21use core::{borrow::Borrow, marker::PhantomData};
22
23use super::{nonnative::uint::NonNativeUintVar, CF2};
24use crate::arith::r1cs::{extract_w_x, R1CS};
25use crate::commitment::CommitmentScheme;
26use crate::constants::N_BITS_RO;
27use crate::folding::nova::{nifs::NIFS, CommittedInstance, Witness};
28use crate::frontend::FCircuit;
29use crate::transcript::{AbsorbNonNativeGadget, Transcript, TranscriptVar};
30use crate::Error;
31
32/// Public inputs length for the CycleFoldCircuit:
33/// For Nova this is: |[r, p1.x,y, p2.x,y, p3.x,y]|
34/// In general, |[r * (n_points-1), (p_i.x,y)*n_points, p_folded.x,y]|, thus, io len is:
35/// (n_points-1) + 2*n_points + 2
36pub fn cf_io_len(n_points: usize) -> usize {
37 (n_points - 1) + 2 * n_points + 2
38}
39
40/// CycleFoldCommittedInstanceVar is the CycleFold CommittedInstance representation in the Nova
41/// circuit.
42#[derive(Debug, Clone)]
43pub struct CycleFoldCommittedInstanceVar<C: CurveGroup, GC: CurveVar<C, CF2<C>>>
44where
45 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
46{
47 pub cmE: GC,
48 pub u: NonNativeUintVar<CF2<C>>,
49 pub cmW: GC,
50 pub x: Vec<NonNativeUintVar<CF2<C>>>,
51}
52impl<C, GC> AllocVar<CommittedInstance<C>, CF2<C>> for CycleFoldCommittedInstanceVar<C, GC>
53where
54 C: CurveGroup,
55 GC: CurveVar<C, CF2<C>>,
56 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
57 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
58{
59 fn new_variable<T: Borrow<CommittedInstance<C>>>(
60 cs: impl Into<Namespace<CF2<C>>>,
61 f: impl FnOnce() -> Result<T, SynthesisError>,
62 mode: AllocationMode,
63 ) -> Result<Self, SynthesisError> {
64 f().and_then(|val| {
65 let cs = cs.into();
66
67 let cmE = GC::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
68 let cmW = GC::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
69 let u = NonNativeUintVar::new_variable(cs.clone(), || Ok(val.borrow().u), mode)?;
70 let x = Vec::new_variable(cs.clone(), || Ok(val.borrow().x.clone()), mode)?;
71
72 Ok(Self { cmE, u, cmW, x })
73 })
74 }
75}
76
77impl<C, GC> AbsorbNonNativeGadget<C::BaseField> for CycleFoldCommittedInstanceVar<C, GC>
78where
79 C: CurveGroup,
80 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
81 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
82 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
83{
84 /// Extracts the underlying field elements from `CycleFoldCommittedInstanceVar`, in the order
85 /// of `u`, `x`, `cmE.x`, `cmE.y`, `cmW.x`, `cmW.y`, `cmE.is_inf || cmW.is_inf` (|| is for
86 /// concat).
87 fn to_native_sponge_field_elements(&self) -> Result<Vec<FpVar<CF2<C>>>, SynthesisError> {
88 let mut cmE_elems = self.cmE.to_constraint_field()?;
89 let mut cmW_elems = self.cmW.to_constraint_field()?;
90
91 // See `transcript/poseidon.rs: TranscriptVar::absorb_point` for details
92 // why the last element is unnecessary.
93 cmE_elems.pop();
94 cmW_elems.pop();
95
96 Ok([
97 self.u.to_native_sponge_field_elements()?,
98 self.x
99 .iter()
100 .map(|i| i.to_native_sponge_field_elements())
101 .collect::<Result<Vec<_>, _>>()?
102 .concat(),
103 cmE_elems,
104 cmW_elems,
105 ]
106 .concat())
107 }
108}
109
110impl<C, GC> CycleFoldCommittedInstanceVar<C, GC>
111where
112 C: CurveGroup,
113 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
114 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
115 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
116{
117 /// hash implements the committed instance hash compatible with the native implementation from
118 /// CommittedInstance.hash_cyclefold. Returns `H(U_i)`, where `U` is the `CommittedInstance`
119 /// for CycleFold. Additionally it returns the vector of the field elements from the self
120 /// parameters, so they can be reused in other gadgets avoiding recalculating (reconstraining)
121 /// them.
122 #[allow(clippy::type_complexity)]
123 pub fn hash<S: CryptographicSponge, T: TranscriptVar<CF2<C>, S>>(
124 self,
125 sponge: &T,
126 pp_hash: FpVar<CF2<C>>, // public params hash
127 ) -> Result<(FpVar<CF2<C>>, Vec<FpVar<CF2<C>>>), SynthesisError> {
128 let mut sponge = sponge.clone();
129 let U_vec = self.to_native_sponge_field_elements()?;
130 sponge.absorb(&pp_hash)?;
131 sponge.absorb(&U_vec)?;
132 Ok((sponge.squeeze_field_elements(1)?.pop().unwrap(), 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<T: Transcript<C::BaseField>>(
254 transcript: &mut T,
255 pp_hash: C::BaseField, // public params hash
256 U_i: CommittedInstance<C>,
257 u_i: CommittedInstance<C>,
258 cmT: C,
259 ) -> Vec<bool> {
260 transcript.absorb(&pp_hash);
261 transcript.absorb_nonnative(&U_i);
262 transcript.absorb_nonnative(&u_i);
263 transcript.absorb_point(&cmT);
264 transcript.squeeze_bits(N_BITS_RO)
265 }
266
267 // compatible with the native get_challenge_native
268 pub fn get_challenge_gadget<S: CryptographicSponge, T: TranscriptVar<C::BaseField, S>>(
269 transcript: &mut T,
270 pp_hash: FpVar<C::BaseField>, // public params hash
271 U_i_vec: Vec<FpVar<C::BaseField>>,
272 u_i: CycleFoldCommittedInstanceVar<C, GC>,
273 cmT: GC,
274 ) -> Result<Vec<Boolean<C::BaseField>>, SynthesisError> {
275 transcript.absorb(&pp_hash)?;
276 transcript.absorb(&U_i_vec)?;
277 transcript.absorb_nonnative(&u_i)?;
278 transcript.absorb_point(&cmT)?;
279 transcript.squeeze_bits(N_BITS_RO)
280 }
281}
282
283/// CycleFoldCircuit contains the constraints that check the correct fold of the committed
284/// instances from Curve1. Namely, it checks the random linear combinations of the elliptic curve
285/// (Curve1) points of u_i, U_i leading to U_{i+1}
286#[derive(Debug, Clone)]
287pub struct CycleFoldCircuit<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
288 pub _gc: PhantomData<GC>,
289 /// number of points being folded
290 pub n_points: usize,
291 /// r_bits is a vector containing the r_bits, one for each point except for the first one. They
292 /// are used for the scalar multiplication of the points. The r_bits are the bit
293 /// representation of each power of r (in Fr, while the CycleFoldCircuit is in Fq).
294 pub r_bits: Option<Vec<Vec<bool>>>,
295 /// points to be folded in the CycleFoldCircuit
296 pub points: Option<Vec<C>>,
297 pub x: Option<Vec<CF2<C>>>, // public inputs (cf_u_{i+1}.x)
298}
299impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> CycleFoldCircuit<C, GC> {
300 /// n_points indicates the number of points being folded in the CycleFoldCircuit
301 pub fn empty(n_points: usize) -> Self {
302 Self {
303 _gc: PhantomData,
304 n_points,
305 r_bits: None,
306 points: None,
307 x: None,
308 }
309 }
310}
311impl<C, GC> ConstraintSynthesizer<CF2<C>> for CycleFoldCircuit<C, GC>
312where
313 C: CurveGroup,
314 GC: CurveVar<C, CF2<C>> + ToConstraintFieldGadget<CF2<C>>,
315 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
316 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
317{
318 fn generate_constraints(self, cs: ConstraintSystemRef<CF2<C>>) -> Result<(), SynthesisError> {
319 let r_bits: Vec<Vec<Boolean<CF2<C>>>> = self
320 .r_bits
321 // n_points-1, bcs is one for each point except for the first one
322 .unwrap_or(vec![vec![false; N_BITS_RO]; self.n_points - 1])
323 .iter()
324 .map(|r_bits_i| {
325 Vec::<Boolean<CF2<C>>>::new_witness(cs.clone(), || Ok(r_bits_i.clone()))
326 })
327 .collect::<Result<Vec<Vec<Boolean<CF2<C>>>>, SynthesisError>>()?;
328 let points = Vec::<GC>::new_witness(cs.clone(), || {
329 Ok(self.points.unwrap_or(vec![C::zero(); self.n_points]))
330 })?;
331
332 #[cfg(test)]
333 {
334 assert_eq!(self.n_points, points.len());
335 assert_eq!(self.n_points - 1, r_bits.len());
336 }
337
338 // Fold the original points of the instances natively in CycleFold.
339 // In Nova,
340 // - for the cmW we're computing: U_i1.cmW = U_i.cmW + r * u_i.cmW
341 // - for the cmE we're computing: U_i1.cmE = U_i.cmE + r * cmT + r^2 * u_i.cmE, where u_i.cmE
342 // is assumed to be 0, so, U_i1.cmE = U_i.cmE + r * cmT
343 let mut p_folded: GC = points[0].clone();
344 // iter over n_points-1 because the first point is not multiplied by r^i (it is multiplied
345 // by r^0=1)
346 for i in 0..self.n_points - 1 {
347 p_folded += points[i + 1].scalar_mul_le(r_bits[i].iter())?;
348 }
349
350 let x = Vec::<FpVar<CF2<C>>>::new_input(cs.clone(), || {
351 Ok(self
352 .x
353 .unwrap_or(vec![CF2::<C>::zero(); cf_io_len(self.n_points)]))
354 })?;
355 #[cfg(test)]
356 assert_eq!(x.len(), cf_io_len(self.n_points)); // non-constrained sanity check
357
358 // Check that the points coordinates are placed as the public input x:
359 // In Nova, this is: x == [r, p1, p2, p3] (wheere p3 is the p_folded).
360 // In multifolding schemes such as HyperNova, this is:
361 // computed_x = [r_0, r_1, r_2, ..., r_n, p_0, p_1, p_2, ..., p_n, p_folded],
362 // where each p_i is in fact p_i.to_constraint_field()
363 let computed_x: Vec<FpVar<CF2<C>>> = [
364 r_bits
365 .iter()
366 .map(|r_bits_i| Boolean::le_bits_to_fp_var(r_bits_i))
367 .collect::<Result<Vec<FpVar<CF2<C>>>, SynthesisError>>()?,
368 points
369 .iter()
370 .map(|p_i| Ok(p_i.to_constraint_field()?[..2].to_vec()))
371 .collect::<Result<Vec<Vec<FpVar<CF2<C>>>>, SynthesisError>>()?
372 .concat(),
373 p_folded.to_constraint_field()?[..2].to_vec(),
374 ]
375 .concat();
376 computed_x.enforce_equal(&x)?;
377
378 Ok(())
379 }
380}
381
382/// Folds the given cyclefold circuit and its instances. This method is abstracted from any folding
383/// scheme struct because it is used both by Nova & HyperNova's CycleFold.
384#[allow(clippy::type_complexity)]
385#[allow(clippy::too_many_arguments)]
386pub fn fold_cyclefold_circuit<C1, GC1, C2, GC2, FC, CS1, CS2, const H: bool>(
387 _n_points: usize,
388 transcript: &mut impl Transcript<C1::ScalarField>,
389 cf_r1cs: R1CS<C2::ScalarField>,
390 cf_cs_params: CS2::ProverParams,
391 pp_hash: C1::ScalarField, // public params hash
392 cf_W_i: Witness<C2>, // witness of the running instance
393 cf_U_i: CommittedInstance<C2>, // running instance
394 cf_u_i_x: Vec<C2::ScalarField>,
395 cf_circuit: CycleFoldCircuit<C1, GC1>,
396 mut rng: impl RngCore,
397) -> Result<
398 (
399 Witness<C2>,
400 CommittedInstance<C2>, // u_i
401 Witness<C2>, // W_i1
402 CommittedInstance<C2>, // U_i1
403 C2, // cmT
404 C2::ScalarField, // r_Fq
405 ),
406 Error,
407>
408where
409 C1: CurveGroup,
410 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
411 C2: CurveGroup,
412 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
413 FC: FCircuit<C1::ScalarField>,
414 CS1: CommitmentScheme<C1, H>,
415 CS2: CommitmentScheme<C2, H>,
416 <C1 as CurveGroup>::BaseField: PrimeField,
417 <C2 as CurveGroup>::BaseField: PrimeField,
418 <C1 as Group>::ScalarField: Absorb,
419 <C2 as Group>::ScalarField: Absorb,
420 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
421 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
422 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
423{
424 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
425 cf_circuit.generate_constraints(cs2.clone())?;
426
427 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
428 let (cf_w_i, cf_x_i) = extract_w_x::<C1::BaseField>(&cs2);
429 if cf_x_i != cf_u_i_x {
430 return Err(Error::NotEqual);
431 }
432
433 #[cfg(test)]
434 assert_eq!(cf_x_i.len(), cf_io_len(_n_points));
435
436 // fold cyclefold instances
437 let cf_w_i = Witness::<C2>::new::<H>(cf_w_i.clone(), cf_r1cs.A.n_rows, &mut rng);
438 let cf_u_i: CommittedInstance<C2> = cf_w_i.commit::<CS2, H>(&cf_cs_params, cf_x_i.clone())?;
439
440 // compute T* and cmT* for CycleFoldCircuit
441 let (cf_T, cf_cmT) = NIFS::<C2, CS2, H>::compute_cyclefold_cmT(
442 &cf_cs_params,
443 &cf_r1cs,
444 &cf_w_i,
445 &cf_u_i,
446 &cf_W_i,
447 &cf_U_i,
448 )?;
449
450 let cf_r_bits = CycleFoldChallengeGadget::<C2, GC2>::get_challenge_native(
451 transcript,
452 pp_hash,
453 cf_U_i.clone(),
454 cf_u_i.clone(),
455 cf_cmT,
456 );
457 let cf_r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&cf_r_bits))
458 .expect("cf_r_bits out of bounds");
459
460 let (cf_W_i1, cf_U_i1) = NIFS::<C2, CS2, H>::fold_instances(
461 cf_r_Fq, &cf_W_i, &cf_U_i, &cf_w_i, &cf_u_i, &cf_T, cf_cmT,
462 )?;
463 Ok((cf_w_i, cf_u_i, cf_W_i1, cf_U_i1, cf_cmT, cf_r_Fq))
464}
465
466#[cfg(test)]
467pub mod tests {
468 use ark_bn254::{constraints::GVar, Fq, Fr, G1Projective as Projective};
469 use ark_crypto_primitives::sponge::{
470 constraints::CryptographicSpongeVar,
471 poseidon::{constraints::PoseidonSpongeVar, PoseidonSponge},
472 };
473 use ark_r1cs_std::R1CSVar;
474 use ark_std::UniformRand;
475
476 use super::*;
477 use crate::folding::nova::nifs::tests::prepare_simple_fold_inputs;
478 use crate::transcript::poseidon::poseidon_canonical_config;
479 use crate::utils::get_cm_coordinates;
480
481 #[test]
482 fn test_committed_instance_cyclefold_var() {
483 let mut rng = ark_std::test_rng();
484
485 let ci = CommittedInstance::<Projective> {
486 cmE: Projective::rand(&mut rng),
487 u: Fr::rand(&mut rng),
488 cmW: Projective::rand(&mut rng),
489 x: vec![Fr::rand(&mut rng); 1],
490 };
491
492 // check the instantiation of the CycleFold side:
493 let cs = ConstraintSystem::<Fq>::new_ref();
494 let ciVar =
495 CommittedInstanceInCycleFoldVar::<Projective, GVar>::new_witness(cs.clone(), || {
496 Ok(ci.clone())
497 })
498 .unwrap();
499 assert_eq!(ciVar.cmE.value().unwrap(), ci.cmE);
500 assert_eq!(ciVar.cmW.value().unwrap(), ci.cmW);
501 }
502
503 #[test]
504 fn test_CycleFoldCircuit_constraints() {
505 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, _) = prepare_simple_fold_inputs();
506 let r_Fq = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
507
508 // cs is the Constraint System on the Curve Cycle auxiliary curve constraints field
509 // (E1::Fq=E2::Fr)
510 let cs = ConstraintSystem::<Fq>::new_ref();
511
512 let cfW_u_i_x: Vec<Fq> = [
513 vec![r_Fq],
514 get_cm_coordinates(&ci1.cmW),
515 get_cm_coordinates(&ci2.cmW),
516 get_cm_coordinates(&ci3.cmW),
517 ]
518 .concat();
519 let cfW_circuit = CycleFoldCircuit::<Projective, GVar> {
520 _gc: PhantomData,
521 n_points: 2,
522 r_bits: Some(vec![r_bits.clone()]),
523 points: Some(vec![ci1.clone().cmW, ci2.clone().cmW]),
524 x: Some(cfW_u_i_x.clone()),
525 };
526 cfW_circuit.generate_constraints(cs.clone()).unwrap();
527 assert!(cs.is_satisfied().unwrap());
528
529 // same for E:
530 let cs = ConstraintSystem::<Fq>::new_ref();
531 let cfE_u_i_x = [
532 vec![r_Fq],
533 get_cm_coordinates(&ci1.cmE),
534 get_cm_coordinates(&cmT),
535 get_cm_coordinates(&ci3.cmE),
536 ]
537 .concat();
538 let cfE_circuit = CycleFoldCircuit::<Projective, GVar> {
539 _gc: PhantomData,
540 n_points: 2,
541 r_bits: Some(vec![r_bits.clone()]),
542 points: Some(vec![ci1.clone().cmE, cmT]),
543 x: Some(cfE_u_i_x.clone()),
544 };
545 cfE_circuit.generate_constraints(cs.clone()).unwrap();
546 assert!(cs.is_satisfied().unwrap());
547 }
548
549 #[test]
550 fn test_nifs_full_gadget() {
551 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, r_Fr) = prepare_simple_fold_inputs();
552
553 let cs = ConstraintSystem::<Fq>::new_ref();
554
555 let r_nonnatVar = NonNativeUintVar::<Fq>::new_witness(cs.clone(), || Ok(r_Fr)).unwrap();
556 let r_bitsVar = Vec::<Boolean<Fq>>::new_witness(cs.clone(), || Ok(r_bits)).unwrap();
557
558 let ci1Var =
559 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
560 Ok(ci1.clone())
561 })
562 .unwrap();
563 let ci2Var =
564 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
565 Ok(ci2.clone())
566 })
567 .unwrap();
568 let ci3Var =
569 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
570 Ok(ci3.clone())
571 })
572 .unwrap();
573 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
574
575 NIFSFullGadget::<Projective, GVar>::verify(
576 r_bitsVar,
577 r_nonnatVar,
578 cmTVar,
579 ci1Var,
580 ci2Var,
581 ci3Var,
582 )
583 .unwrap();
584 assert!(cs.is_satisfied().unwrap());
585 }
586
587 #[test]
588 fn test_cyclefold_challenge_gadget() {
589 let mut rng = ark_std::test_rng();
590 let poseidon_config = poseidon_canonical_config::<Fq>();
591 let mut transcript = PoseidonSponge::<Fq>::new(&poseidon_config);
592
593 let u_i = CommittedInstance::<Projective> {
594 cmE: Projective::zero(), // zero on purpose, so we test also the zero point case
595 u: Fr::zero(),
596 cmW: Projective::rand(&mut rng),
597 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
598 .take(7) // 7 = cf_io_len
599 .collect(),
600 };
601 let U_i = CommittedInstance::<Projective> {
602 cmE: Projective::rand(&mut rng),
603 u: Fr::rand(&mut rng),
604 cmW: Projective::rand(&mut rng),
605 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
606 .take(7) // 7 = cf_io_len
607 .collect(),
608 };
609 let cmT = Projective::rand(&mut rng);
610
611 // compute the challenge natively
612 let pp_hash = Fq::from(42u32); // only for test
613 let r_bits = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_native(
614 &mut transcript,
615 pp_hash,
616 U_i.clone(),
617 u_i.clone(),
618 cmT,
619 );
620
621 let cs = ConstraintSystem::<Fq>::new_ref();
622 let u_iVar =
623 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
624 Ok(u_i.clone())
625 })
626 .unwrap();
627 let U_iVar =
628 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
629 Ok(U_i.clone())
630 })
631 .unwrap();
632 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
633 let mut transcript_var =
634 PoseidonSpongeVar::<Fq>::new(ConstraintSystem::<Fq>::new_ref(), &poseidon_config);
635
636 let pp_hashVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
637 let r_bitsVar = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_gadget(
638 &mut transcript_var,
639 pp_hashVar,
640 U_iVar.to_native_sponge_field_elements().unwrap(),
641 u_iVar,
642 cmTVar,
643 )
644 .unwrap();
645 assert!(cs.is_satisfied().unwrap());
646
647 // check that the natively computed and in-circuit computed hashes match
648 let rVar = Boolean::le_bits_to_fp_var(&r_bitsVar).unwrap();
649 let r = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
650 assert_eq!(rVar.value().unwrap(), r);
651 assert_eq!(r_bitsVar.value().unwrap(), r_bits);
652 }
653
654 #[test]
655 fn test_cyclefold_hash_gadget() {
656 let mut rng = ark_std::test_rng();
657 let poseidon_config = poseidon_canonical_config::<Fq>();
658 let sponge = PoseidonSponge::<Fq>::new(&poseidon_config);
659
660 let U_i = CommittedInstance::<Projective> {
661 cmE: Projective::rand(&mut rng),
662 u: Fr::rand(&mut rng),
663 cmW: Projective::rand(&mut rng),
664 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
665 .take(7) // 7 = cf_io_len in Nova
666 .collect(),
667 };
668 let pp_hash = Fq::from(42u32); // only for test
669 let h = U_i.hash_cyclefold(&sponge, pp_hash);
670
671 let cs = ConstraintSystem::<Fq>::new_ref();
672 let U_iVar =
673 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
674 Ok(U_i.clone())
675 })
676 .unwrap();
677 let pp_hashVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
678 let (hVar, _) = U_iVar
679 .hash(
680 &PoseidonSpongeVar::new(cs.clone(), &poseidon_config),
681 pp_hashVar,
682 )
683 .unwrap();
684 hVar.enforce_equal(&FpVar::new_witness(cs.clone(), || Ok(h)).unwrap())
685 .unwrap();
686 assert!(cs.is_satisfied().unwrap());
687 }
688}