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