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
363/// `CycleFoldConfig` allows us to customize the behavior of CycleFold circuit
364/// according to the folding scheme we are working with.
365pub trait CycleFoldConfig {
366 /// `N_INPUT_POINTS` specifies the number of input points that are folded in
367 /// [`CycleFoldCircuit`] via random linear combinations.
368 const N_INPUT_POINTS: usize;
369 /// `RANDOMNESS_BIT_LENGTH` is the (maximum) bit length of randomness `r`.
370 const RANDOMNESS_BIT_LENGTH: usize;
371 /// `FIELD_CAPACITY` is the maximum number of bits that can be stored in a
372 /// field element.
373 ///
374 /// E.g., given a randomness `r` with `RANDOMNESS_BIT_LENGTH` bits, we need
375 /// `RANDOMNESS_BIT_LENGTH / FIELD_CAPACITY` field elements to represent `r`
376 /// compactly in-circuit.
377 const FIELD_CAPACITY: usize = CF2::<Self::C>::MODULUS_BIT_SIZE as usize - 1;
378
379 /// Public inputs length for the CycleFoldCircuit.
380 /// * For Nova this is: `|[r, p1.x,y, p2.x,y, p3.x,y]|`
381 /// * In general, `|[r, (p_i.x,y)*n_points, p_folded.x,y]|`.
382 ///
383 /// Thus, `IO_LEN` is:
384 /// `RANDOMNESS_BIT_LENGTH / FIELD_CAPACITY + 2 * N_INPUT_POINTS + 2`
385 const IO_LEN: usize = {
386 Self::RANDOMNESS_BIT_LENGTH.div_ceil(Self::FIELD_CAPACITY) + 2 * Self::N_INPUT_POINTS + 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 the bit representation of the r whose powers are used in the
400 /// random-linear-combination inside the CycleFoldCircuit
401 pub r_bits: Option<Vec<bool>>,
402 /// points to be folded in the CycleFoldCircuit
403 pub points: Option<Vec<CFG::C>>,
404 /// public inputs (cf_u_{i+1}.x)
405 pub x: Option<Vec<CFG::F>>,
406}
407
408impl<CFG: CycleFoldConfig, GC: CurveVar<CFG::C, CFG::F>> CycleFoldCircuit<CFG, GC> {
409 /// n_points indicates the number of points being folded in the CycleFoldCircuit
410 pub fn empty() -> Self {
411 Self {
412 _gc: PhantomData,
413 r_bits: None,
414 points: None,
415 x: None,
416 }
417 }
418}
419
420impl<CFG: CycleFoldConfig, GC: CurveVar<CFG::C, CFG::F>> ConstraintSynthesizer<CFG::F>
421 for CycleFoldCircuit<CFG, GC>
422where
423 GC: ToConstraintFieldGadget<CFG::F>,
424 CFG::F: PrimeField,
425 for<'a> &'a GC: GroupOpsBounds<'a, CFG::C, GC>,
426{
427 fn generate_constraints(self, cs: ConstraintSystemRef<CFG::F>) -> Result<(), SynthesisError> {
428 let r_bits = Vec::<Boolean<CFG::F>>::new_witness(cs.clone(), || {
429 Ok(self
430 .r_bits
431 .unwrap_or(vec![false; CFG::RANDOMNESS_BIT_LENGTH]))
432 })?;
433 let points = Vec::<GC>::new_witness(cs.clone(), || {
434 Ok(self
435 .points
436 .unwrap_or(vec![CFG::C::zero(); CFG::N_INPUT_POINTS]))
437 })?;
438
439 #[cfg(test)]
440 {
441 assert_eq!(CFG::N_INPUT_POINTS, points.len());
442 assert_eq!(CFG::RANDOMNESS_BIT_LENGTH, r_bits.len());
443 }
444
445 // Fold the original points of the instances natively in CycleFold.
446 // In Nova,
447 // - for the cmW we're computing: U_i1.cmW = U_i.cmW + r * u_i.cmW
448 // - for the cmE we're computing: U_i1.cmE = U_i.cmE + r * cmT + r^2 * u_i.cmE, where u_i.cmE
449 // is assumed to be 0, so, U_i1.cmE = U_i.cmE + r * cmT
450 // We want to compute
451 // P_folded = p_0 + r * P_1 + r^2 * P_2 + r^3 * P_3 + ... + r^{n-2} * P_{n-2} + r^{n-1} * P_{n-1}
452 // so in order to do it more efficiently (less constraints) we do
453 // P_folded = (((P_{n-1} * r + P_{n-2}) * r + P_{n-3})... ) * r + P_0
454 let mut p_folded: GC = points[CFG::N_INPUT_POINTS - 1].clone();
455 for i in (0..CFG::N_INPUT_POINTS - 1).rev() {
456 p_folded = p_folded.scalar_mul_le(r_bits.iter())? + points[i].clone();
457 }
458
459 let x = Vec::<FpVar<CFG::F>>::new_input(cs.clone(), || {
460 Ok(self.x.unwrap_or(vec![CFG::F::zero(); CFG::IO_LEN]))
461 })?;
462 #[cfg(test)]
463 assert_eq!(x.len(), CFG::IO_LEN); // non-constrained sanity check
464
465 // Check that the points coordinates are placed as the public input x:
466 // In Nova, this is: x == [r, p1, p2, p3] (wheere p3 is the p_folded).
467 // In multifolding schemes such as HyperNova, this is:
468 // computed_x = [r, p_0, p_1, p_2, ..., p_n, p_folded],
469 // where each p_i is in fact p_i.to_constraint_field()
470 let r_fp = r_bits
471 .chunks(CFG::F::MODULUS_BIT_SIZE as usize - 1)
472 .map(Boolean::le_bits_to_fp_var)
473 .collect::<Result<Vec<_>, _>>()?;
474 let points_aux: Vec<FpVar<CFG::F>> = points
475 .iter()
476 .map(|p_i| Ok(p_i.to_constraint_field()?[..2].to_vec()))
477 .collect::<Result<Vec<_>, SynthesisError>>()?
478 .into_iter()
479 .flatten()
480 .collect();
481
482 let computed_x: Vec<FpVar<CFG::F>> = [
483 r_fp,
484 points_aux,
485 p_folded.to_constraint_field()?[..2].to_vec(),
486 ]
487 .concat();
488 computed_x.enforce_equal(&x)?;
489
490 Ok(())
491 }
492}
493
494/// Folds the given cyclefold circuit and its instances. This method is abstracted from any folding
495/// scheme struct because it is used both by Nova & HyperNova's CycleFold.
496#[allow(clippy::type_complexity)]
497#[allow(clippy::too_many_arguments)]
498pub fn fold_cyclefold_circuit<CFG, C1, GC1, C2, GC2, CS2, const H: bool>(
499 transcript: &mut impl Transcript<C1::ScalarField>,
500 cf_r1cs: R1CS<C2::ScalarField>,
501 cf_cs_params: CS2::ProverParams,
502 pp_hash: C1::ScalarField, // public params hash
503 cf_W_i: CycleFoldWitness<C2>, // witness of the running instance
504 cf_U_i: CycleFoldCommittedInstance<C2>, // running instance
505 cf_u_i_x: Vec<C2::ScalarField>,
506 cf_circuit: CycleFoldCircuit<CFG, GC1>,
507 mut rng: impl RngCore,
508) -> Result<
509 (
510 CycleFoldWitness<C2>,
511 CycleFoldCommittedInstance<C2>, // u_i
512 CycleFoldWitness<C2>, // W_i1
513 CycleFoldCommittedInstance<C2>, // U_i1
514 C2, // cmT
515 C2::ScalarField, // r_Fq
516 ),
517 Error,
518>
519where
520 CFG: CycleFoldConfig<C = C1, F = CF2<C1>>,
521 C1: CurveGroup,
522 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
523 C2: CurveGroup,
524 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
525 CS2: CommitmentScheme<C2, H>,
526 <C1 as CurveGroup>::BaseField: PrimeField,
527 <C2 as CurveGroup>::BaseField: PrimeField,
528 <C1 as Group>::ScalarField: Absorb,
529 <C2 as Group>::ScalarField: Absorb,
530 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
531 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
532 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
533{
534 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
535 cf_circuit.generate_constraints(cs2.clone())?;
536
537 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
538 let (cf_w_i, cf_x_i) = extract_w_x::<C1::BaseField>(&cs2);
539 if cf_x_i != cf_u_i_x {
540 return Err(Error::NotEqual);
541 }
542
543 #[cfg(test)]
544 assert_eq!(cf_x_i.len(), CFG::IO_LEN);
545
546 // fold cyclefold instances
547 let cf_w_i = CycleFoldWitness::<C2>::new::<H>(cf_w_i.clone(), cf_r1cs.A.n_rows, &mut rng);
548 let cf_u_i: CycleFoldCommittedInstance<C2> =
549 cf_w_i.commit::<CS2, H>(&cf_cs_params, cf_x_i.clone())?;
550
551 // compute T* and cmT* for CycleFoldCircuit
552 let (cf_T, cf_cmT) = NIFS::<C2, CS2, H>::compute_cyclefold_cmT(
553 &cf_cs_params,
554 &cf_r1cs,
555 &cf_w_i,
556 &cf_u_i,
557 &cf_W_i,
558 &cf_U_i,
559 )?;
560
561 let cf_r_bits = CycleFoldChallengeGadget::<C2, GC2>::get_challenge_native(
562 transcript,
563 pp_hash,
564 cf_U_i.clone(),
565 cf_u_i.clone(),
566 cf_cmT,
567 );
568 let cf_r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&cf_r_bits))
569 .expect("cf_r_bits out of bounds");
570
571 let (cf_W_i1, cf_U_i1) = NIFS::<C2, CS2, H>::fold_instances(
572 cf_r_Fq, &cf_W_i, &cf_U_i, &cf_w_i, &cf_u_i, &cf_T, cf_cmT,
573 )?;
574 Ok((cf_w_i, cf_u_i, cf_W_i1, cf_U_i1, cf_cmT, cf_r_Fq))
575}
576
577#[cfg(test)]
578pub mod tests {
579 use ark_bn254::{constraints::GVar, Fq, Fr, G1Projective as Projective};
580 use ark_crypto_primitives::sponge::{
581 constraints::CryptographicSpongeVar,
582 poseidon::{constraints::PoseidonSpongeVar, PoseidonSponge},
583 };
584 use ark_r1cs_std::R1CSVar;
585 use ark_std::UniformRand;
586
587 use super::*;
588 use crate::folding::nova::nifs::tests::prepare_simple_fold_inputs;
589 use crate::transcript::poseidon::poseidon_canonical_config;
590 use crate::utils::get_cm_coordinates;
591
592 struct TestCycleFoldConfig<C: CurveGroup, const N: usize> {
593 _c: PhantomData<C>,
594 }
595
596 impl<C: CurveGroup, const N: usize> CycleFoldConfig for TestCycleFoldConfig<C, N> {
597 const RANDOMNESS_BIT_LENGTH: usize = NOVA_N_BITS_RO;
598 const N_INPUT_POINTS: usize = N;
599 type C = C;
600 type F = C::BaseField;
601 }
602
603 #[test]
604 fn test_committed_instance_cyclefold_var() {
605 let mut rng = ark_std::test_rng();
606
607 let ci = CycleFoldCommittedInstance::<Projective> {
608 cmE: Projective::rand(&mut rng),
609 u: Fr::rand(&mut rng),
610 cmW: Projective::rand(&mut rng),
611 x: vec![Fr::rand(&mut rng); 1],
612 };
613
614 // check the instantiation of the CycleFold side:
615 let cs = ConstraintSystem::<Fq>::new_ref();
616 let ciVar =
617 CommittedInstanceInCycleFoldVar::<Projective, GVar>::new_witness(cs.clone(), || {
618 Ok(ci.clone())
619 })
620 .unwrap();
621 assert_eq!(ciVar.cmE.value().unwrap(), ci.cmE);
622 assert_eq!(ciVar.cmW.value().unwrap(), ci.cmW);
623 }
624
625 #[test]
626 fn test_CycleFoldCircuit_n_points_constraints() {
627 const n: usize = 16;
628 let mut rng = ark_std::test_rng();
629
630 // points to random-linear-combine
631 let points: Vec<Projective> = std::iter::repeat_with(|| Projective::rand(&mut rng))
632 .take(n)
633 .collect();
634
635 use std::ops::Mul;
636 let rho_raw = Fq::rand(&mut rng);
637 let rho_bits = rho_raw.into_bigint().to_bits_le()[..NOVA_N_BITS_RO].to_vec();
638 let rho_Fq = Fq::from_bigint(BigInteger::from_bits_le(&rho_bits)).unwrap();
639 let rho_Fr = Fr::from_bigint(BigInteger::from_bits_le(&rho_bits)).unwrap();
640 let mut res = Projective::zero();
641 use ark_std::One;
642 let mut rho_i = Fr::one();
643 for point_i in points.iter() {
644 res += point_i.mul(rho_i);
645 rho_i *= rho_Fr;
646 }
647
648 // cs is the Constraint System on the Curve Cycle auxiliary curve constraints field
649 // (E1::Fq=E2::Fr)
650 let cs = ConstraintSystem::<Fq>::new_ref();
651
652 let x: Vec<Fq> = [
653 vec![rho_Fq],
654 points.iter().flat_map(get_cm_coordinates).collect(),
655 get_cm_coordinates(&res),
656 ]
657 .concat();
658 let cf_circuit = CycleFoldCircuit::<TestCycleFoldConfig<Projective, n>, GVar> {
659 _gc: PhantomData,
660 r_bits: Some(rho_bits),
661 points: Some(points),
662 x: Some(x.clone()),
663 };
664 cf_circuit.generate_constraints(cs.clone()).unwrap();
665 assert!(cs.is_satisfied().unwrap());
666 }
667
668 #[test]
669 fn test_nifs_full_gadget() {
670 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, _) = prepare_simple_fold_inputs();
671
672 let cs = ConstraintSystem::<Fq>::new_ref();
673
674 let r_bitsVar = Vec::<Boolean<Fq>>::new_witness(cs.clone(), || Ok(r_bits)).unwrap();
675
676 let ci1Var =
677 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
678 Ok(ci1.clone())
679 })
680 .unwrap();
681 let ci2Var =
682 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
683 Ok(ci2.clone())
684 })
685 .unwrap();
686 let ci3Var =
687 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
688 Ok(ci3.clone())
689 })
690 .unwrap();
691 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
692
693 NIFSFullGadget::<Projective, GVar>::verify(r_bitsVar, cmTVar, ci1Var, ci2Var, ci3Var)
694 .unwrap();
695 assert!(cs.is_satisfied().unwrap());
696 }
697
698 #[test]
699 fn test_cyclefold_challenge_gadget() {
700 let mut rng = ark_std::test_rng();
701 let poseidon_config = poseidon_canonical_config::<Fq>();
702 let mut transcript = PoseidonSponge::<Fq>::new(&poseidon_config);
703
704 let u_i = CycleFoldCommittedInstance::<Projective> {
705 cmE: Projective::zero(), // zero on purpose, so we test also the zero point case
706 u: Fr::zero(),
707 cmW: Projective::rand(&mut rng),
708 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
709 .take(TestCycleFoldConfig::<Projective, 2>::IO_LEN)
710 .collect(),
711 };
712 let U_i = CycleFoldCommittedInstance::<Projective> {
713 cmE: Projective::rand(&mut rng),
714 u: Fr::rand(&mut rng),
715 cmW: Projective::rand(&mut rng),
716 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
717 .take(TestCycleFoldConfig::<Projective, 2>::IO_LEN)
718 .collect(),
719 };
720 let cmT = Projective::rand(&mut rng);
721
722 // compute the challenge natively
723 let pp_hash = Fq::from(42u32); // only for test
724 let r_bits = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_native(
725 &mut transcript,
726 pp_hash,
727 U_i.clone(),
728 u_i.clone(),
729 cmT,
730 );
731
732 let cs = ConstraintSystem::<Fq>::new_ref();
733 let u_iVar =
734 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
735 Ok(u_i.clone())
736 })
737 .unwrap();
738 let U_iVar =
739 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
740 Ok(U_i.clone())
741 })
742 .unwrap();
743 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
744 let mut transcript_var =
745 PoseidonSpongeVar::<Fq>::new(ConstraintSystem::<Fq>::new_ref(), &poseidon_config);
746
747 let pp_hashVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
748 let r_bitsVar = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_gadget(
749 &mut transcript_var,
750 pp_hashVar,
751 U_iVar.to_native_sponge_field_elements().unwrap(),
752 u_iVar,
753 cmTVar,
754 )
755 .unwrap();
756 assert!(cs.is_satisfied().unwrap());
757
758 // check that the natively computed and in-circuit computed hashes match
759 let rVar = Boolean::le_bits_to_fp_var(&r_bitsVar).unwrap();
760 let r = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
761 assert_eq!(rVar.value().unwrap(), r);
762 assert_eq!(r_bitsVar.value().unwrap(), r_bits);
763 }
764
765 #[test]
766 fn test_cyclefold_hash_gadget() {
767 let mut rng = ark_std::test_rng();
768 let poseidon_config = poseidon_canonical_config::<Fq>();
769 let sponge = PoseidonSponge::<Fq>::new(&poseidon_config);
770
771 let U_i = CycleFoldCommittedInstance::<Projective> {
772 cmE: Projective::rand(&mut rng),
773 u: Fr::rand(&mut rng),
774 cmW: Projective::rand(&mut rng),
775 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
776 .take(TestCycleFoldConfig::<Projective, 2>::IO_LEN)
777 .collect(),
778 };
779 let pp_hash = Fq::from(42u32); // only for test
780 let h = U_i.hash_cyclefold(&sponge, pp_hash);
781
782 let cs = ConstraintSystem::<Fq>::new_ref();
783 let U_iVar =
784 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
785 Ok(U_i.clone())
786 })
787 .unwrap();
788 let pp_hashVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
789 let (hVar, _) = U_iVar
790 .hash(
791 &PoseidonSpongeVar::new(cs.clone(), &poseidon_config),
792 pp_hashVar,
793 )
794 .unwrap();
795 hVar.enforce_equal(&FpVar::new_witness(cs.clone(), || Ok(h)).unwrap())
796 .unwrap();
797 assert!(cs.is_satisfied().unwrap());
798 }
799}