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