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