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