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