sonobe/folding-schemes/src/folding/nova/mod.rs
folding-schemes/src/folding/nova/mod.rsRaw
1/// Implements the scheme described in [Nova](https://eprint.iacr.org/2021/370.pdf) and
2/// [CycleFold](https://eprint.iacr.org/2023/1192.pdf).
3use ark_crypto_primitives::sponge::{
4 poseidon::{PoseidonConfig, PoseidonSponge},
5 Absorb, CryptographicSponge,
6};
7use ark_ec::{AffineRepr, CurveGroup, Group};
8use ark_ff::{BigInteger, PrimeField};
9use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
10use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
11use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
12use ark_std::fmt::Debug;
13use ark_std::rand::RngCore;
14use ark_std::{One, Zero};
15use core::marker::PhantomData;
16
17use crate::commitment::CommitmentScheme;
18use crate::folding::circuits::cyclefold::{fold_cyclefold_circuit, CycleFoldCircuit};
19use crate::folding::circuits::CF2;
20use crate::frontend::FCircuit;
21use crate::transcript::{AbsorbNonNative, Transcript};
22use crate::utils::vec::is_zero_vec;
23use crate::Error;
24use crate::FoldingScheme;
25use crate::{
26 arith::r1cs::{extract_r1cs, extract_w_x, R1CS},
27 utils::{get_cm_coordinates, pp_hash},
28};
29
30pub mod circuits;
31pub mod decider_eth;
32pub mod decider_eth_circuit;
33pub mod nifs;
34pub mod serialize;
35pub mod traits;
36use circuits::{AugmentedFCircuit, ChallengeGadget};
37use nifs::NIFS;
38use traits::NovaR1CS;
39
40#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
41pub struct CommittedInstance<C: CurveGroup> {
42 pub cmE: C,
43 pub u: C::ScalarField,
44 pub cmW: C,
45 pub x: Vec<C::ScalarField>,
46}
47
48impl<C: CurveGroup> CommittedInstance<C> {
49 pub fn dummy(io_len: usize) -> Self {
50 Self {
51 cmE: C::zero(),
52 u: C::ScalarField::zero(),
53 cmW: C::zero(),
54 x: vec![C::ScalarField::zero(); io_len],
55 }
56 }
57}
58
59impl<C: CurveGroup> Absorb for CommittedInstance<C>
60where
61 C::ScalarField: Absorb,
62{
63 fn to_sponge_bytes(&self, _dest: &mut Vec<u8>) {
64 // This is never called
65 unimplemented!()
66 }
67
68 fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
69 self.u.to_sponge_field_elements(dest);
70 self.x.to_sponge_field_elements(dest);
71 // We cannot call `to_native_sponge_field_elements(dest)` directly, as
72 // `to_native_sponge_field_elements` needs `F` to be `C::ScalarField`,
73 // but here `F` is a generic `PrimeField`.
74 self.cmE
75 .to_native_sponge_field_elements_as_vec()
76 .to_sponge_field_elements(dest);
77 self.cmW
78 .to_native_sponge_field_elements_as_vec()
79 .to_sponge_field_elements(dest);
80 }
81}
82
83impl<C: CurveGroup> AbsorbNonNative<C::BaseField> for CommittedInstance<C>
84where
85 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
86{
87 // Compatible with the in-circuit `CycleFoldCommittedInstanceVar::to_native_sponge_field_elements`
88 // in `cyclefold.rs`.
89 fn to_native_sponge_field_elements(&self, dest: &mut Vec<C::BaseField>) {
90 [self.u].to_native_sponge_field_elements(dest);
91 self.x.to_native_sponge_field_elements(dest);
92 let (cmE_x, cmE_y) = match self.cmE.into_affine().xy() {
93 Some((&x, &y)) => (x, y),
94 None => (C::BaseField::zero(), C::BaseField::zero()),
95 };
96 let (cmW_x, cmW_y) = match self.cmW.into_affine().xy() {
97 Some((&x, &y)) => (x, y),
98 None => (C::BaseField::zero(), C::BaseField::zero()),
99 };
100 cmE_x.to_sponge_field_elements(dest);
101 cmE_y.to_sponge_field_elements(dest);
102 cmW_x.to_sponge_field_elements(dest);
103 cmW_y.to_sponge_field_elements(dest);
104 }
105}
106
107impl<C: CurveGroup> CommittedInstance<C>
108where
109 <C as Group>::ScalarField: Absorb,
110 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
111{
112 /// hash implements the committed instance hash compatible with the gadget implemented in
113 /// nova/circuits.rs::CommittedInstanceVar.hash.
114 /// Returns `H(i, z_0, z_i, U_i)`, where `i` can be `i` but also `i+1`, and `U_i` is the
115 /// `CommittedInstance`.
116 pub fn hash<T: Transcript<C::ScalarField>>(
117 &self,
118 sponge: &T,
119 pp_hash: C::ScalarField, // public params hash
120 i: C::ScalarField,
121 z_0: Vec<C::ScalarField>,
122 z_i: Vec<C::ScalarField>,
123 ) -> C::ScalarField {
124 let mut sponge = sponge.clone();
125 sponge.absorb(&pp_hash);
126 sponge.absorb(&i);
127 sponge.absorb(&z_0);
128 sponge.absorb(&z_i);
129 sponge.absorb(&self);
130 sponge.squeeze_field_elements(1)[0]
131 }
132}
133
134impl<C: CurveGroup> CommittedInstance<C>
135where
136 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
137{
138 /// hash_cyclefold implements the committed instance hash compatible with the gadget implemented in
139 /// nova/cyclefold.rs::CycleFoldCommittedInstanceVar.hash.
140 /// Returns `H(U_i)`, where `U_i` is the `CommittedInstance` for CycleFold.
141 pub fn hash_cyclefold<T: Transcript<C::BaseField>>(
142 &self,
143 sponge: &T,
144 pp_hash: C::BaseField, // public params hash
145 ) -> C::BaseField {
146 let mut sponge = sponge.clone();
147 sponge.absorb(&pp_hash);
148 sponge.absorb_nonnative(self);
149 sponge.squeeze_field_elements(1)[0]
150 }
151}
152
153#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
154pub struct Witness<C: CurveGroup> {
155 pub E: Vec<C::ScalarField>,
156 pub rE: C::ScalarField,
157 pub W: Vec<C::ScalarField>,
158 pub rW: C::ScalarField,
159}
160
161impl<C: CurveGroup> Witness<C>
162where
163 <C as Group>::ScalarField: Absorb,
164{
165 pub fn new(w: Vec<C::ScalarField>, e_len: usize) -> Self {
166 // note: at the current version, we don't use the blinding factors and we set them to 0
167 // always.
168 Self {
169 E: vec![C::ScalarField::zero(); e_len],
170 rE: C::ScalarField::zero(),
171 W: w,
172 rW: C::ScalarField::zero(),
173 }
174 }
175 pub fn commit<CS: CommitmentScheme<C>>(
176 &self,
177 params: &CS::ProverParams,
178 x: Vec<C::ScalarField>,
179 ) -> Result<CommittedInstance<C>, Error> {
180 let mut cmE = C::zero();
181 if !is_zero_vec::<C::ScalarField>(&self.E) {
182 cmE = CS::commit(params, &self.E, &self.rE)?;
183 }
184 let cmW = CS::commit(params, &self.W, &self.rW)?;
185 Ok(CommittedInstance {
186 cmE,
187 u: C::ScalarField::one(),
188 cmW,
189 x,
190 })
191 }
192}
193
194#[derive(Debug, Clone)]
195pub struct PreprocessorParam<C1, C2, FC, CS1, CS2>
196where
197 C1: CurveGroup,
198 C2: CurveGroup,
199 FC: FCircuit<C1::ScalarField>,
200 CS1: CommitmentScheme<C1>,
201 CS2: CommitmentScheme<C2>,
202{
203 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
204 pub F: FC,
205 // cs params if not provided, will be generated at the preprocess method
206 pub cs_pp: Option<CS1::ProverParams>,
207 pub cs_vp: Option<CS1::VerifierParams>,
208 pub cf_cs_pp: Option<CS2::ProverParams>,
209 pub cf_cs_vp: Option<CS2::VerifierParams>,
210}
211
212impl<C1, C2, FC, CS1, CS2> PreprocessorParam<C1, C2, FC, CS1, CS2>
213where
214 C1: CurveGroup,
215 C2: CurveGroup,
216 FC: FCircuit<C1::ScalarField>,
217 CS1: CommitmentScheme<C1>,
218 CS2: CommitmentScheme<C2>,
219{
220 pub fn new(poseidon_config: PoseidonConfig<C1::ScalarField>, F: FC) -> Self {
221 Self {
222 poseidon_config,
223 F,
224 cs_pp: None,
225 cs_vp: None,
226 cf_cs_pp: None,
227 cf_cs_vp: None,
228 }
229 }
230}
231
232#[derive(Debug, Clone)]
233pub struct ProverParams<C1, C2, CS1, CS2>
234where
235 C1: CurveGroup,
236 C2: CurveGroup,
237 CS1: CommitmentScheme<C1>,
238 CS2: CommitmentScheme<C2>,
239{
240 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
241 pub cs_pp: CS1::ProverParams,
242 pub cf_cs_pp: CS2::ProverParams,
243}
244
245#[derive(Debug, Clone)]
246pub struct VerifierParams<C1, C2, CS1, CS2>
247where
248 C1: CurveGroup,
249 C2: CurveGroup,
250 CS1: CommitmentScheme<C1>,
251 CS2: CommitmentScheme<C2>,
252{
253 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
254 pub r1cs: R1CS<C1::ScalarField>,
255 pub cf_r1cs: R1CS<C2::ScalarField>,
256 pub cs_vp: CS1::VerifierParams,
257 pub cf_cs_vp: CS2::VerifierParams,
258}
259
260impl<C1, C2, CS1, CS2> VerifierParams<C1, C2, CS1, CS2>
261where
262 C1: CurveGroup,
263 C2: CurveGroup,
264 CS1: CommitmentScheme<C1>,
265 CS2: CommitmentScheme<C2>,
266{
267 /// returns the hash of the public parameters of Nova
268 pub fn pp_hash(&self) -> Result<C1::ScalarField, Error> {
269 pp_hash::<C1, C2, CS1, CS2>(
270 &self.r1cs,
271 &self.cf_r1cs,
272 &self.cs_vp,
273 &self.cf_cs_vp,
274 &self.poseidon_config,
275 )
276 }
277}
278
279/// Implements Nova+CycleFold's IVC, described in [Nova](https://eprint.iacr.org/2021/370.pdf) and
280/// [CycleFold](https://eprint.iacr.org/2023/1192.pdf), following the FoldingScheme trait
281#[derive(Clone, Debug)]
282pub struct Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
283where
284 C1: CurveGroup,
285 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
286 C2: CurveGroup,
287 GC2: CurveVar<C2, CF2<C2>>,
288 FC: FCircuit<C1::ScalarField>,
289 CS1: CommitmentScheme<C1>,
290 CS2: CommitmentScheme<C2>,
291{
292 _gc1: PhantomData<GC1>,
293 _c2: PhantomData<C2>,
294 _gc2: PhantomData<GC2>,
295 /// R1CS of the Augmented Function circuit
296 pub r1cs: R1CS<C1::ScalarField>,
297 /// R1CS of the CycleFold circuit
298 pub cf_r1cs: R1CS<C2::ScalarField>,
299 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
300 /// CommitmentScheme::ProverParams over C1
301 pub cs_pp: CS1::ProverParams,
302 /// CycleFold CommitmentScheme::ProverParams, over C2
303 pub cf_cs_pp: CS2::ProverParams,
304 /// F circuit, the circuit that is being folded
305 pub F: FC,
306 /// public params hash
307 pub pp_hash: C1::ScalarField,
308 pub i: C1::ScalarField,
309 /// initial state
310 pub z_0: Vec<C1::ScalarField>,
311 /// current i-th state
312 pub z_i: Vec<C1::ScalarField>,
313 /// Nova instances
314 pub w_i: Witness<C1>,
315 pub u_i: CommittedInstance<C1>,
316 pub W_i: Witness<C1>,
317 pub U_i: CommittedInstance<C1>,
318
319 /// CycleFold running instance
320 pub cf_W_i: Witness<C2>,
321 pub cf_U_i: CommittedInstance<C2>,
322}
323
324impl<C1, GC1, C2, GC2, FC, CS1, CS2> FoldingScheme<C1, C2, FC>
325 for Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
326where
327 C1: CurveGroup,
328 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
329 C2: CurveGroup,
330 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
331 FC: FCircuit<C1::ScalarField>,
332 CS1: CommitmentScheme<C1>,
333 CS2: CommitmentScheme<C2>,
334 <C1 as CurveGroup>::BaseField: PrimeField,
335 <C2 as CurveGroup>::BaseField: PrimeField,
336 <C1 as Group>::ScalarField: Absorb,
337 <C2 as Group>::ScalarField: Absorb,
338 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
339 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
340 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
341{
342 type PreprocessorParam = PreprocessorParam<C1, C2, FC, CS1, CS2>;
343 type ProverParam = ProverParams<C1, C2, CS1, CS2>;
344 type VerifierParam = VerifierParams<C1, C2, CS1, CS2>;
345 type RunningInstance = (CommittedInstance<C1>, Witness<C1>);
346 type IncomingInstance = (CommittedInstance<C1>, Witness<C1>);
347 type CFInstance = (CommittedInstance<C2>, Witness<C2>);
348
349 fn preprocess(
350 mut rng: impl RngCore,
351 prep_param: &Self::PreprocessorParam,
352 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
353 let (r1cs, cf_r1cs) =
354 get_r1cs::<C1, GC1, C2, GC2, FC>(&prep_param.poseidon_config, prep_param.F.clone())?;
355
356 // if cs params exist, use them, if not, generate new ones
357 let cs_pp: CS1::ProverParams;
358 let cs_vp: CS1::VerifierParams;
359 let cf_cs_pp: CS2::ProverParams;
360 let cf_cs_vp: CS2::VerifierParams;
361 if prep_param.cs_pp.is_some()
362 && prep_param.cf_cs_pp.is_some()
363 && prep_param.cs_vp.is_some()
364 && prep_param.cf_cs_vp.is_some()
365 {
366 cs_pp = prep_param.clone().cs_pp.unwrap();
367 cs_vp = prep_param.clone().cs_vp.unwrap();
368 cf_cs_pp = prep_param.clone().cf_cs_pp.unwrap();
369 cf_cs_vp = prep_param.clone().cf_cs_vp.unwrap();
370 } else {
371 (cs_pp, cs_vp) = CS1::setup(&mut rng, r1cs.A.n_rows)?;
372 (cf_cs_pp, cf_cs_vp) = CS2::setup(&mut rng, cf_r1cs.A.n_rows)?;
373 }
374
375 let prover_params = ProverParams::<C1, C2, CS1, CS2> {
376 poseidon_config: prep_param.poseidon_config.clone(),
377 cs_pp: cs_pp.clone(),
378 cf_cs_pp: cf_cs_pp.clone(),
379 };
380 let verifier_params = VerifierParams::<C1, C2, CS1, CS2> {
381 poseidon_config: prep_param.poseidon_config.clone(),
382 r1cs,
383 cf_r1cs,
384 cs_vp,
385 cf_cs_vp,
386 };
387
388 Ok((prover_params, verifier_params))
389 }
390
391 /// Initializes the Nova+CycleFold's IVC for the given parameters and initial state `z_0`.
392 fn init(
393 params: (Self::ProverParam, Self::VerifierParam),
394 F: FC,
395 z_0: Vec<C1::ScalarField>,
396 ) -> Result<Self, Error> {
397 let (pp, vp) = params;
398
399 // prepare the circuit to obtain its R1CS
400 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
401 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
402
403 let augmented_F_circuit =
404 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(&pp.poseidon_config, F.clone());
405 let cf_circuit = CycleFoldCircuit::<C1, GC1>::empty();
406
407 augmented_F_circuit.generate_constraints(cs.clone())?;
408 cs.finalize();
409 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
410 let r1cs = extract_r1cs::<C1::ScalarField>(&cs);
411
412 cf_circuit.generate_constraints(cs2.clone())?;
413 cs2.finalize();
414 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
415 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2);
416
417 // compute the public params hash
418 let pp_hash = vp.pp_hash()?;
419
420 // setup the dummy instances
421 let (w_dummy, u_dummy) = r1cs.dummy_instance();
422 let (cf_w_dummy, cf_u_dummy) = cf_r1cs.dummy_instance();
423
424 // W_dummy=W_0 is a 'dummy witness', all zeroes, but with the size corresponding to the
425 // R1CS that we're working with.
426 Ok(Self {
427 _gc1: PhantomData,
428 _c2: PhantomData,
429 _gc2: PhantomData,
430 r1cs,
431 cf_r1cs,
432 poseidon_config: pp.poseidon_config.clone(),
433 cs_pp: pp.cs_pp.clone(),
434 cf_cs_pp: pp.cf_cs_pp.clone(),
435 F,
436 pp_hash,
437 i: C1::ScalarField::zero(),
438 z_0: z_0.clone(),
439 z_i: z_0,
440 w_i: w_dummy.clone(),
441 u_i: u_dummy.clone(),
442 W_i: w_dummy,
443 U_i: u_dummy,
444 // cyclefold running instance
445 cf_W_i: cf_w_dummy.clone(),
446 cf_U_i: cf_u_dummy.clone(),
447 })
448 }
449
450 /// Implements IVC.P of Nova+CycleFold
451 fn prove_step(
452 &mut self,
453 _rng: impl RngCore,
454 external_inputs: Vec<C1::ScalarField>,
455 ) -> Result<(), Error> {
456 // `sponge` is for digest computation.
457 let sponge = PoseidonSponge::<C1::ScalarField>::new(&self.poseidon_config);
458 // `transcript` is for challenge generation.
459 let mut transcript = sponge.clone();
460
461 let augmented_F_circuit: AugmentedFCircuit<C1, C2, GC2, FC>;
462
463 if self.z_i.len() != self.F.state_len() {
464 return Err(Error::NotSameLength(
465 "z_i.len()".to_string(),
466 self.z_i.len(),
467 "F.state_len()".to_string(),
468 self.F.state_len(),
469 ));
470 }
471 if external_inputs.len() != self.F.external_inputs_len() {
472 return Err(Error::NotSameLength(
473 "F.external_inputs_len()".to_string(),
474 self.F.external_inputs_len(),
475 "external_inputs.len()".to_string(),
476 external_inputs.len(),
477 ));
478 }
479
480 if self.i > C1::ScalarField::from_le_bytes_mod_order(&usize::MAX.to_le_bytes()) {
481 return Err(Error::MaxStep);
482 }
483 let mut i_bytes: [u8; 8] = [0; 8];
484 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..8]);
485 let i_usize: usize = usize::from_le_bytes(i_bytes);
486
487 let z_i1 = self
488 .F
489 .step_native(i_usize, self.z_i.clone(), external_inputs.clone())?;
490
491 // compute T and cmT for AugmentedFCircuit
492 let (T, cmT) = self.compute_cmT()?;
493
494 // r_bits is the r used to the RLC of the F' instances
495 let r_bits = ChallengeGadget::<C1>::get_challenge_native(
496 &mut transcript,
497 self.pp_hash,
498 self.U_i.clone(),
499 self.u_i.clone(),
500 cmT,
501 );
502 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
503 .ok_or(Error::OutOfBounds)?;
504 let r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&r_bits))
505 .ok_or(Error::OutOfBounds)?;
506
507 // fold Nova instances
508 let (W_i1, U_i1): (Witness<C1>, CommittedInstance<C1>) = NIFS::<C1, CS1>::fold_instances(
509 r_Fr, &self.W_i, &self.U_i, &self.w_i, &self.u_i, &T, cmT,
510 )?;
511
512 // folded instance output (public input, x)
513 // u_{i+1}.x[0] = H(i+1, z_0, z_{i+1}, U_{i+1})
514 let u_i1_x = U_i1.hash(
515 &sponge,
516 self.pp_hash,
517 self.i + C1::ScalarField::one(),
518 self.z_0.clone(),
519 z_i1.clone(),
520 );
521 // u_{i+1}.x[1] = H(cf_U_{i+1})
522 let cf_u_i1_x: C1::ScalarField;
523
524 if self.i == C1::ScalarField::zero() {
525 cf_u_i1_x = self.cf_U_i.hash_cyclefold(&sponge, self.pp_hash);
526 // base case
527 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
528 _gc2: PhantomData,
529 poseidon_config: self.poseidon_config.clone(),
530 pp_hash: Some(self.pp_hash),
531 i: Some(C1::ScalarField::zero()), // = i=0
532 i_usize: Some(0),
533 z_0: Some(self.z_0.clone()), // = z_i
534 z_i: Some(self.z_i.clone()),
535 external_inputs: Some(external_inputs.clone()),
536 u_i_cmW: Some(self.u_i.cmW), // = dummy
537 U_i: Some(self.U_i.clone()), // = dummy
538 U_i1_cmE: Some(U_i1.cmE),
539 U_i1_cmW: Some(U_i1.cmW),
540 cmT: Some(cmT),
541 F: self.F.clone(),
542 x: Some(u_i1_x),
543 cf1_u_i_cmW: None,
544 cf2_u_i_cmW: None,
545 cf_U_i: None,
546 cf1_cmT: None,
547 cf2_cmT: None,
548 cf_x: Some(cf_u_i1_x),
549 };
550
551 #[cfg(test)]
552 NIFS::<C1, CS1>::verify_folded_instance(r_Fr, &self.U_i, &self.u_i, &U_i1, &cmT)?;
553 } else {
554 // CycleFold part:
555 // get the vector used as public inputs 'x' in the CycleFold circuit
556 // cyclefold circuit for cmW
557 let cfW_u_i_x = [
558 vec![r_Fq],
559 get_cm_coordinates(&self.U_i.cmW),
560 get_cm_coordinates(&self.u_i.cmW),
561 get_cm_coordinates(&U_i1.cmW),
562 ]
563 .concat();
564 // cyclefold circuit for cmE
565 let cfE_u_i_x = [
566 vec![r_Fq],
567 get_cm_coordinates(&self.U_i.cmE),
568 get_cm_coordinates(&cmT),
569 get_cm_coordinates(&U_i1.cmE),
570 ]
571 .concat();
572
573 let cfW_circuit = CycleFoldCircuit::<C1, GC1> {
574 _gc: PhantomData,
575 r_bits: Some(r_bits.clone()),
576 p1: Some(self.U_i.clone().cmW),
577 p2: Some(self.u_i.clone().cmW),
578 x: Some(cfW_u_i_x.clone()),
579 };
580 let cfE_circuit = CycleFoldCircuit::<C1, GC1> {
581 _gc: PhantomData,
582 r_bits: Some(r_bits.clone()),
583 p1: Some(self.U_i.clone().cmE),
584 p2: Some(cmT),
585 x: Some(cfE_u_i_x.clone()),
586 };
587
588 // fold self.cf_U_i + cfW_U -> folded running with cfW
589 let (_cfW_w_i, cfW_u_i, cfW_W_i1, cfW_U_i1, cfW_cmT, _) = self.fold_cyclefold_circuit(
590 &mut transcript,
591 self.cf_W_i.clone(), // CycleFold running instance witness
592 self.cf_U_i.clone(), // CycleFold running instance
593 cfW_u_i_x,
594 cfW_circuit,
595 )?;
596 // fold [the output from folding self.cf_U_i + cfW_U] + cfE_U = folded_running_with_cfW + cfE
597 let (_cfE_w_i, cfE_u_i, cf_W_i1, cf_U_i1, cf_cmT, _) = self.fold_cyclefold_circuit(
598 &mut transcript,
599 cfW_W_i1,
600 cfW_U_i1.clone(),
601 cfE_u_i_x,
602 cfE_circuit,
603 )?;
604
605 cf_u_i1_x = cf_U_i1.hash_cyclefold(&sponge, self.pp_hash);
606
607 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
608 _gc2: PhantomData,
609 poseidon_config: self.poseidon_config.clone(),
610 pp_hash: Some(self.pp_hash),
611 i: Some(self.i),
612 i_usize: Some(i_usize),
613 z_0: Some(self.z_0.clone()),
614 z_i: Some(self.z_i.clone()),
615 external_inputs: Some(external_inputs.clone()),
616 u_i_cmW: Some(self.u_i.cmW),
617 U_i: Some(self.U_i.clone()),
618 U_i1_cmE: Some(U_i1.cmE),
619 U_i1_cmW: Some(U_i1.cmW),
620 cmT: Some(cmT),
621 F: self.F.clone(),
622 x: Some(u_i1_x),
623 // cyclefold values
624 cf1_u_i_cmW: Some(cfW_u_i.cmW),
625 cf2_u_i_cmW: Some(cfE_u_i.cmW),
626 cf_U_i: Some(self.cf_U_i.clone()),
627 cf1_cmT: Some(cfW_cmT),
628 cf2_cmT: Some(cf_cmT),
629 cf_x: Some(cf_u_i1_x),
630 };
631
632 self.cf_W_i = cf_W_i1;
633 self.cf_U_i = cf_U_i1;
634
635 #[cfg(test)]
636 {
637 self.cf_r1cs.check_instance_relation(&_cfW_w_i, &cfW_u_i)?;
638 self.cf_r1cs.check_instance_relation(&_cfE_w_i, &cfE_u_i)?;
639 self.cf_r1cs
640 .check_relaxed_instance_relation(&self.cf_W_i, &self.cf_U_i)?;
641 }
642 }
643
644 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
645
646 augmented_F_circuit.generate_constraints(cs.clone())?;
647
648 #[cfg(test)]
649 assert!(cs.is_satisfied().unwrap());
650
651 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
652 let (w_i1, x_i1) = extract_w_x::<C1::ScalarField>(&cs);
653 if x_i1[0] != u_i1_x || x_i1[1] != cf_u_i1_x {
654 return Err(Error::NotEqual);
655 }
656
657 #[cfg(test)]
658 if x_i1.len() != 2 {
659 return Err(Error::NotExpectedLength(x_i1.len(), 2));
660 }
661
662 // set values for next iteration
663 self.i += C1::ScalarField::one();
664 self.z_i = z_i1;
665 self.w_i = Witness::<C1>::new(w_i1, self.r1cs.A.n_rows);
666 self.u_i = self.w_i.commit::<CS1>(&self.cs_pp, x_i1)?;
667 self.W_i = W_i1;
668 self.U_i = U_i1;
669
670 #[cfg(test)]
671 {
672 self.r1cs.check_instance_relation(&self.w_i, &self.u_i)?;
673 self.r1cs
674 .check_relaxed_instance_relation(&self.W_i, &self.U_i)?;
675 }
676
677 Ok(())
678 }
679
680 fn state(&self) -> Vec<C1::ScalarField> {
681 self.z_i.clone()
682 }
683
684 fn instances(
685 &self,
686 ) -> (
687 Self::RunningInstance,
688 Self::IncomingInstance,
689 Self::CFInstance,
690 ) {
691 (
692 (self.U_i.clone(), self.W_i.clone()),
693 (self.u_i.clone(), self.w_i.clone()),
694 (self.cf_U_i.clone(), self.cf_W_i.clone()),
695 )
696 }
697
698 /// Implements IVC.V of Nova+CycleFold. Notice that this method does not include the
699 /// commitments verification, which is done in the Decider.
700 fn verify(
701 vp: Self::VerifierParam,
702 z_0: Vec<C1::ScalarField>, // initial state
703 z_i: Vec<C1::ScalarField>, // last state
704 num_steps: C1::ScalarField,
705 running_instance: Self::RunningInstance,
706 incoming_instance: Self::IncomingInstance,
707 cyclefold_instance: Self::CFInstance,
708 ) -> Result<(), Error> {
709 let sponge = PoseidonSponge::<C1::ScalarField>::new(&vp.poseidon_config);
710
711 if num_steps == C1::ScalarField::zero() {
712 if z_0 != z_i {
713 return Err(Error::IVCVerificationFail);
714 }
715 return Ok(());
716 }
717
718 let (U_i, W_i) = running_instance;
719 let (u_i, w_i) = incoming_instance;
720 let (cf_U_i, cf_W_i) = cyclefold_instance;
721
722 if u_i.x.len() != 2 || U_i.x.len() != 2 {
723 return Err(Error::IVCVerificationFail);
724 }
725
726 let pp_hash = vp.pp_hash()?;
727
728 // check that u_i's output points to the running instance
729 // u_i.X[0] == H(i, z_0, z_i, U_i)
730 let expected_u_i_x = U_i.hash(&sponge, pp_hash, num_steps, z_0, z_i.clone());
731 if expected_u_i_x != u_i.x[0] {
732 return Err(Error::IVCVerificationFail);
733 }
734 // u_i.X[1] == H(cf_U_i)
735 let expected_cf_u_i_x = cf_U_i.hash_cyclefold(&sponge, pp_hash);
736 if expected_cf_u_i_x != u_i.x[1] {
737 return Err(Error::IVCVerificationFail);
738 }
739
740 // check u_i.cmE==0, u_i.u==1 (=u_i is a un-relaxed instance)
741 if !u_i.cmE.is_zero() || !u_i.u.is_one() {
742 return Err(Error::IVCVerificationFail);
743 }
744
745 // check R1CS satisfiability
746 vp.r1cs.check_instance_relation(&w_i, &u_i)?;
747 // check RelaxedR1CS satisfiability
748 vp.r1cs.check_relaxed_instance_relation(&W_i, &U_i)?;
749
750 // check CycleFold RelaxedR1CS satisfiability
751 vp.cf_r1cs
752 .check_relaxed_instance_relation(&cf_W_i, &cf_U_i)?;
753
754 Ok(())
755 }
756}
757
758impl<C1, GC1, C2, GC2, FC, CS1, CS2> Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
759where
760 C1: CurveGroup,
761 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
762 C2: CurveGroup,
763 GC2: CurveVar<C2, CF2<C2>>,
764 FC: FCircuit<C1::ScalarField>,
765 CS1: CommitmentScheme<C1>,
766 CS2: CommitmentScheme<C2>,
767 <C2 as CurveGroup>::BaseField: PrimeField,
768 <C1 as Group>::ScalarField: Absorb,
769 <C2 as Group>::ScalarField: Absorb,
770 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
771{
772 // computes T and cmT for the AugmentedFCircuit
773 fn compute_cmT(&self) -> Result<(Vec<C1::ScalarField>, C1), Error> {
774 NIFS::<C1, CS1>::compute_cmT(
775 &self.cs_pp,
776 &self.r1cs,
777 &self.w_i,
778 &self.u_i,
779 &self.W_i,
780 &self.U_i,
781 )
782 }
783}
784
785impl<C1, GC1, C2, GC2, FC, CS1, CS2> Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
786where
787 C1: CurveGroup,
788 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
789 C2: CurveGroup,
790 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
791 FC: FCircuit<C1::ScalarField>,
792 CS1: CommitmentScheme<C1>,
793 CS2: CommitmentScheme<C2>,
794 <C1 as CurveGroup>::BaseField: PrimeField,
795 <C2 as CurveGroup>::BaseField: PrimeField,
796 <C1 as Group>::ScalarField: Absorb,
797 <C2 as Group>::ScalarField: Absorb,
798 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
799 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
800 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
801{
802 // folds the given cyclefold circuit and its instances
803 #[allow(clippy::type_complexity)]
804 fn fold_cyclefold_circuit<T: Transcript<C1::ScalarField>>(
805 &self,
806 transcript: &mut T,
807 cf_W_i: Witness<C2>, // witness of the running instance
808 cf_U_i: CommittedInstance<C2>, // running instance
809 cf_u_i_x: Vec<C2::ScalarField>,
810 cf_circuit: CycleFoldCircuit<C1, GC1>,
811 ) -> Result<
812 (
813 Witness<C2>,
814 CommittedInstance<C2>, // u_i
815 Witness<C2>, // W_i1
816 CommittedInstance<C2>, // U_i1
817 C2, // cmT
818 C2::ScalarField, // r_Fq
819 ),
820 Error,
821 > {
822 fold_cyclefold_circuit::<C1, GC1, C2, GC2, FC, CS1, CS2>(
823 transcript,
824 self.cf_r1cs.clone(),
825 self.cf_cs_pp.clone(),
826 self.pp_hash,
827 cf_W_i,
828 cf_U_i,
829 cf_u_i_x,
830 cf_circuit,
831 )
832 }
833}
834
835/// helper method to get the r1cs from the ConstraintSynthesizer
836pub fn get_r1cs_from_cs<F: PrimeField>(
837 circuit: impl ConstraintSynthesizer<F>,
838) -> Result<R1CS<F>, Error> {
839 let cs = ConstraintSystem::<F>::new_ref();
840 circuit.generate_constraints(cs.clone())?;
841 cs.finalize();
842 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
843 let r1cs = extract_r1cs::<F>(&cs);
844 Ok(r1cs)
845}
846
847/// helper method to get the R1CS for both the AugmentedFCircuit and the CycleFold circuit
848#[allow(clippy::type_complexity)]
849pub fn get_r1cs<C1, GC1, C2, GC2, FC>(
850 poseidon_config: &PoseidonConfig<C1::ScalarField>,
851 F_circuit: FC,
852) -> Result<(R1CS<C1::ScalarField>, R1CS<C2::ScalarField>), Error>
853where
854 C1: CurveGroup,
855 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
856 C2: CurveGroup,
857 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
858 FC: FCircuit<C1::ScalarField>,
859 <C1 as CurveGroup>::BaseField: PrimeField,
860 <C2 as CurveGroup>::BaseField: PrimeField,
861 <C1 as Group>::ScalarField: Absorb,
862 <C2 as Group>::ScalarField: Absorb,
863 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
864 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
865 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
866{
867 let augmented_F_circuit =
868 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(poseidon_config, F_circuit);
869 let cf_circuit = CycleFoldCircuit::<C1, GC1>::empty();
870 let r1cs = get_r1cs_from_cs::<C1::ScalarField>(augmented_F_circuit)?;
871 let cf_r1cs = get_r1cs_from_cs::<C2::ScalarField>(cf_circuit)?;
872 Ok((r1cs, cf_r1cs))
873}
874
875/// helper method to get the pedersen params length for both the AugmentedFCircuit and the
876/// CycleFold circuit
877pub fn get_cs_params_len<C1, GC1, C2, GC2, FC>(
878 poseidon_config: &PoseidonConfig<C1::ScalarField>,
879 F_circuit: FC,
880) -> Result<(usize, usize), Error>
881where
882 C1: CurveGroup,
883 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
884 C2: CurveGroup,
885 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
886 FC: FCircuit<C1::ScalarField>,
887 <C1 as CurveGroup>::BaseField: PrimeField,
888 <C2 as CurveGroup>::BaseField: PrimeField,
889 <C1 as Group>::ScalarField: Absorb,
890 <C2 as Group>::ScalarField: Absorb,
891 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
892 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
893 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
894{
895 let (r1cs, cf_r1cs) = get_r1cs::<C1, GC1, C2, GC2, FC>(poseidon_config, F_circuit)?;
896 Ok((r1cs.A.n_rows, cf_r1cs.A.n_rows))
897}
898
899#[cfg(test)]
900pub mod tests {
901 use crate::commitment::kzg::KZG;
902 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
903 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
904
905 use super::*;
906 use crate::commitment::pedersen::Pedersen;
907 use crate::frontend::tests::CubicFCircuit;
908 use crate::transcript::poseidon::poseidon_canonical_config;
909
910 /// This test tests the Nova+CycleFold IVC, and by consequence it is also testing the
911 /// AugmentedFCircuit
912 #[test]
913 fn test_ivc() {
914 let poseidon_config = poseidon_canonical_config::<Fr>();
915
916 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
917
918 // run the test using Pedersen commitments on both sides of the curve cycle
919 test_ivc_opt::<Pedersen<Projective>, Pedersen<Projective2>>(
920 poseidon_config.clone(),
921 F_circuit,
922 );
923 // run the test using KZG for the commitments on the main curve, and Pedersen for the
924 // commitments on the secondary curve
925 test_ivc_opt::<KZG<Bn254>, Pedersen<Projective2>>(poseidon_config, F_circuit);
926 }
927
928 // test_ivc allowing to choose the CommitmentSchemes
929 fn test_ivc_opt<CS1: CommitmentScheme<Projective>, CS2: CommitmentScheme<Projective2>>(
930 poseidon_config: PoseidonConfig<Fr>,
931 F_circuit: CubicFCircuit<Fr>,
932 ) {
933 let mut rng = ark_std::test_rng();
934 type N<CS1, CS2> = Nova<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2>;
935
936 let prep_param = PreprocessorParam::<Projective, Projective2, CubicFCircuit<Fr>, CS1, CS2> {
937 poseidon_config,
938 F: F_circuit,
939 cs_pp: None,
940 cs_vp: None,
941 cf_cs_pp: None,
942 cf_cs_vp: None,
943 };
944 let nova_params = N::preprocess(&mut rng, &prep_param).unwrap();
945
946 let z_0 = vec![Fr::from(3_u32)];
947 let mut nova = N::init(nova_params.clone(), F_circuit, z_0.clone()).unwrap();
948
949 let num_steps: usize = 3;
950 for _ in 0..num_steps {
951 nova.prove_step(&mut rng, vec![]).unwrap();
952 }
953 assert_eq!(Fr::from(num_steps as u32), nova.i);
954
955 let (running_instance, incoming_instance, cyclefold_instance) = nova.instances();
956 N::<CS1, CS2>::verify(
957 nova_params.1, // Nova's verifier params
958 z_0,
959 nova.z_i,
960 nova.i,
961 running_instance,
962 incoming_instance,
963 cyclefold_instance,
964 )
965 .unwrap();
966 }
967}