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