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