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).
3///
4/// The structure of the Nova code is the following:
5/// - NIFS implementation for Nova (nifs.rs), Mova (mova.rs), Ova (ova.rs)
6/// - IVC and the Decider (offchain Decider & onchain Decider) implementations for Nova
7use ark_crypto_primitives::sponge::{
8 poseidon::{PoseidonConfig, PoseidonSponge},
9 Absorb, CryptographicSponge,
10};
11use ark_ec::{CurveGroup, Group};
12use ark_ff::{BigInteger, PrimeField};
13use ark_r1cs_std::{prelude::CurveVar, ToConstraintFieldGadget};
14use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
15use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Valid};
16use ark_std::fmt::Debug;
17use ark_std::rand::RngCore;
18use ark_std::{One, UniformRand, Zero};
19use core::marker::PhantomData;
20use decider_eth_circuit::WitnessVar;
21
22use crate::folding::circuits::cyclefold::{
23 fold_cyclefold_circuit, CycleFoldCircuit, CycleFoldCommittedInstance, CycleFoldConfig,
24 CycleFoldWitness,
25};
26use crate::folding::{
27 circuits::{CF1, CF2},
28 traits::Dummy,
29};
30use crate::frontend::FCircuit;
31use crate::transcript::{poseidon::poseidon_canonical_config, AbsorbNonNative, Transcript};
32use crate::utils::vec::is_zero_vec;
33use crate::Error;
34use crate::FoldingScheme;
35use crate::{
36 arith::r1cs::{extract_r1cs, extract_w_x, R1CS},
37 constants::NOVA_N_BITS_RO,
38 utils::{get_cm_coordinates, pp_hash},
39};
40use crate::{arith::Arith, commitment::CommitmentScheme};
41
42pub mod circuits;
43pub mod traits;
44pub mod zk;
45
46// NIFS related:
47pub mod nifs;
48
49use circuits::{AugmentedFCircuit, CommittedInstanceVar};
50use nifs::{nova::NIFS, NIFSTrait};
51
52// offchain decider
53pub mod decider;
54pub mod decider_circuits;
55// onchain decider
56pub mod decider_eth;
57pub mod decider_eth_circuit;
58
59use super::traits::{CommittedInstanceOps, Inputize, WitnessOps};
60
61/// Configuration for Nova's CycleFold circuit
62pub struct NovaCycleFoldConfig<C: CurveGroup> {
63 _c: PhantomData<C>,
64}
65
66impl<C: CurveGroup> CycleFoldConfig for NovaCycleFoldConfig<C> {
67 const RANDOMNESS_BIT_LENGTH: usize = NOVA_N_BITS_RO;
68 // Number of points to be folded in the CycleFold circuit, in Nova's case, this is a fixed
69 // amount:
70 // 2 points to be folded.
71 const N_INPUT_POINTS: usize = 2;
72 type C = C;
73 type F = C::BaseField;
74}
75
76/// CycleFold circuit for computing random linear combinations of group elements
77/// in Nova instances.
78pub type NovaCycleFoldCircuit<C, GC> = CycleFoldCircuit<NovaCycleFoldConfig<C>, GC>;
79
80#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
81pub struct CommittedInstance<C: CurveGroup> {
82 pub cmE: C,
83 pub u: C::ScalarField,
84 pub cmW: C,
85 pub x: Vec<C::ScalarField>,
86}
87
88impl<C: CurveGroup> Dummy<usize> for CommittedInstance<C> {
89 fn dummy(io_len: usize) -> Self {
90 Self {
91 cmE: C::zero(),
92 u: CF1::<C>::zero(),
93 cmW: C::zero(),
94 x: vec![CF1::<C>::zero(); io_len],
95 }
96 }
97}
98
99impl<C: CurveGroup> Dummy<&R1CS<CF1<C>>> for CommittedInstance<C> {
100 fn dummy(r1cs: &R1CS<CF1<C>>) -> Self {
101 Self::dummy(r1cs.l)
102 }
103}
104
105impl<C: CurveGroup> Absorb for CommittedInstance<C>
106where
107 C::ScalarField: Absorb,
108{
109 fn to_sponge_bytes(&self, dest: &mut Vec<u8>) {
110 C::ScalarField::batch_to_sponge_bytes(&self.to_sponge_field_elements_as_vec(), dest);
111 }
112
113 fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
114 self.u.to_sponge_field_elements(dest);
115 self.x.to_sponge_field_elements(dest);
116 // We cannot call `to_native_sponge_field_elements(dest)` directly, as
117 // `to_native_sponge_field_elements` needs `F` to be `C::ScalarField`,
118 // but here `F` is a generic `PrimeField`.
119 self.cmE
120 .to_native_sponge_field_elements_as_vec()
121 .to_sponge_field_elements(dest);
122 self.cmW
123 .to_native_sponge_field_elements_as_vec()
124 .to_sponge_field_elements(dest);
125 }
126}
127
128impl<C: CurveGroup> CommittedInstanceOps<C> for CommittedInstance<C> {
129 type Var = CommittedInstanceVar<C>;
130
131 fn get_commitments(&self) -> Vec<C> {
132 vec![self.cmW, self.cmE]
133 }
134
135 fn is_incoming(&self) -> bool {
136 self.cmE == C::zero() && self.u == One::one()
137 }
138}
139
140impl<C: CurveGroup> Inputize<C::ScalarField, CommittedInstanceVar<C>> for CommittedInstance<C> {
141 fn inputize(&self) -> Vec<C::ScalarField> {
142 [
143 &[self.u][..],
144 &self.x,
145 &self.cmE.inputize(),
146 &self.cmW.inputize(),
147 ]
148 .concat()
149 }
150}
151
152#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
153pub struct Witness<C: CurveGroup> {
154 pub E: Vec<C::ScalarField>,
155 pub rE: C::ScalarField,
156 pub W: Vec<C::ScalarField>,
157 pub rW: C::ScalarField,
158}
159
160impl<C: CurveGroup> Witness<C> {
161 pub fn new<const H: bool>(w: Vec<C::ScalarField>, e_len: usize, mut rng: impl RngCore) -> Self {
162 let (rW, rE) = if H {
163 (
164 C::ScalarField::rand(&mut rng),
165 C::ScalarField::rand(&mut rng),
166 )
167 } else {
168 (C::ScalarField::zero(), C::ScalarField::zero())
169 };
170
171 Self {
172 E: vec![C::ScalarField::zero(); e_len],
173 rE,
174 W: w,
175 rW,
176 }
177 }
178
179 pub fn commit<CS: CommitmentScheme<C, HC>, const HC: bool>(
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
198impl<C: CurveGroup> Dummy<&R1CS<CF1<C>>> for Witness<C> {
199 fn dummy(r1cs: &R1CS<CF1<C>>) -> Self {
200 Self {
201 E: vec![C::ScalarField::zero(); r1cs.A.n_rows],
202 rE: C::ScalarField::zero(),
203 W: vec![C::ScalarField::zero(); r1cs.A.n_cols - 1 - r1cs.l],
204 rW: C::ScalarField::zero(),
205 }
206 }
207}
208
209impl<C: CurveGroup> WitnessOps<C::ScalarField> for Witness<C> {
210 type Var = WitnessVar<C>;
211
212 fn get_openings(&self) -> Vec<(&[C::ScalarField], C::ScalarField)> {
213 vec![(&self.W, self.rW), (&self.E, self.rE)]
214 }
215}
216
217#[derive(Debug, Clone)]
218pub struct PreprocessorParam<C1, C2, FC, CS1, CS2, const H: bool = false>
219where
220 C1: CurveGroup,
221 C2: CurveGroup,
222 FC: FCircuit<C1::ScalarField>,
223 CS1: CommitmentScheme<C1, H>,
224 CS2: CommitmentScheme<C2, H>,
225{
226 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
227 pub F: FC,
228 // cs params if not provided, will be generated at the preprocess method
229 pub cs_pp: Option<CS1::ProverParams>,
230 pub cs_vp: Option<CS1::VerifierParams>,
231 pub cf_cs_pp: Option<CS2::ProverParams>,
232 pub cf_cs_vp: Option<CS2::VerifierParams>,
233}
234
235impl<C1, C2, FC, CS1, CS2, const H: bool> PreprocessorParam<C1, C2, FC, CS1, CS2, H>
236where
237 C1: CurveGroup,
238 C2: CurveGroup,
239 FC: FCircuit<C1::ScalarField>,
240 CS1: CommitmentScheme<C1, H>,
241 CS2: CommitmentScheme<C2, H>,
242{
243 pub fn new(poseidon_config: PoseidonConfig<C1::ScalarField>, F: FC) -> Self {
244 Self {
245 poseidon_config,
246 F,
247 cs_pp: None,
248 cs_vp: None,
249 cf_cs_pp: None,
250 cf_cs_vp: None,
251 }
252 }
253}
254
255/// Proving parameters for Nova-based IVC
256#[derive(Debug, Clone)]
257pub struct ProverParams<C1, C2, CS1, CS2, const H: bool = false>
258where
259 C1: CurveGroup,
260 C2: CurveGroup,
261 CS1: CommitmentScheme<C1, H>,
262 CS2: CommitmentScheme<C2, H>,
263{
264 /// Poseidon sponge configuration
265 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
266 /// Proving parameters of the underlying commitment scheme over C1
267 pub cs_pp: CS1::ProverParams,
268 /// Proving parameters of the underlying commitment scheme over C2
269 pub cf_cs_pp: CS2::ProverParams,
270}
271
272impl<C1, C2, CS1, CS2, const H: bool> Valid for ProverParams<C1, C2, CS1, CS2, H>
273where
274 C1: CurveGroup,
275 C2: CurveGroup,
276 CS1: CommitmentScheme<C1, H>,
277 CS2: CommitmentScheme<C2, H>,
278{
279 fn check(&self) -> Result<(), ark_serialize::SerializationError> {
280 self.poseidon_config.full_rounds.check()?;
281 self.poseidon_config.partial_rounds.check()?;
282 self.poseidon_config.alpha.check()?;
283 self.poseidon_config.ark.check()?;
284 self.poseidon_config.mds.check()?;
285 self.poseidon_config.rate.check()?;
286 self.poseidon_config.capacity.check()?;
287 self.cs_pp.check()?;
288 self.cf_cs_pp.check()?;
289 Ok(())
290 }
291}
292impl<C1, C2, CS1, CS2, const H: bool> CanonicalSerialize for ProverParams<C1, C2, CS1, CS2, H>
293where
294 C1: CurveGroup,
295 C2: CurveGroup,
296 CS1: CommitmentScheme<C1, H>,
297 CS2: CommitmentScheme<C2, H>,
298{
299 fn serialize_with_mode<W: std::io::prelude::Write>(
300 &self,
301 mut writer: W,
302 compress: ark_serialize::Compress,
303 ) -> Result<(), ark_serialize::SerializationError> {
304 self.cs_pp.serialize_with_mode(&mut writer, compress)?;
305 self.cf_cs_pp.serialize_with_mode(&mut writer, compress)
306 }
307
308 fn serialized_size(&self, compress: ark_serialize::Compress) -> usize {
309 self.cs_pp.serialized_size(compress) + self.cf_cs_pp.serialized_size(compress)
310 }
311}
312impl<C1, C2, CS1, CS2, const H: bool> CanonicalDeserialize for ProverParams<C1, C2, CS1, CS2, H>
313where
314 C1: CurveGroup,
315 C2: CurveGroup,
316 CS1: CommitmentScheme<C1, H>,
317 CS2: CommitmentScheme<C2, H>,
318{
319 fn deserialize_with_mode<R: std::io::prelude::Read>(
320 mut reader: R,
321 compress: ark_serialize::Compress,
322 validate: ark_serialize::Validate,
323 ) -> Result<Self, ark_serialize::SerializationError> {
324 let cs_pp = CS1::ProverParams::deserialize_with_mode(&mut reader, compress, validate)?;
325 let cf_cs_pp = CS2::ProverParams::deserialize_with_mode(&mut reader, compress, validate)?;
326 Ok(ProverParams {
327 poseidon_config: poseidon_canonical_config::<C1::ScalarField>(),
328 cs_pp,
329 cf_cs_pp,
330 })
331 }
332}
333
334/// Verification parameters for Nova-based IVC
335#[derive(Debug, Clone)]
336pub struct VerifierParams<C1, C2, CS1, CS2, const H: bool = false>
337where
338 C1: CurveGroup,
339 C2: CurveGroup,
340 CS1: CommitmentScheme<C1, H>,
341 CS2: CommitmentScheme<C2, H>,
342{
343 /// Poseidon sponge configuration
344 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
345 /// R1CS of the Augmented step circuit
346 pub r1cs: R1CS<C1::ScalarField>,
347 /// R1CS of the CycleFold circuit
348 pub cf_r1cs: R1CS<C2::ScalarField>,
349 /// Verification parameters of the underlying commitment scheme over C1
350 pub cs_vp: CS1::VerifierParams,
351 /// Verification parameters of the underlying commitment scheme over C2
352 pub cf_cs_vp: CS2::VerifierParams,
353}
354
355impl<C1, C2, CS1, CS2, const H: bool> Valid for VerifierParams<C1, C2, CS1, CS2, H>
356where
357 C1: CurveGroup,
358 C2: CurveGroup,
359 CS1: CommitmentScheme<C1, H>,
360 CS2: CommitmentScheme<C2, H>,
361{
362 fn check(&self) -> Result<(), ark_serialize::SerializationError> {
363 self.cs_vp.check()?;
364 self.cf_cs_vp.check()?;
365 Ok(())
366 }
367}
368impl<C1, C2, CS1, CS2, const H: bool> CanonicalSerialize for VerifierParams<C1, C2, CS1, CS2, H>
369where
370 C1: CurveGroup,
371 C2: CurveGroup,
372 CS1: CommitmentScheme<C1, H>,
373 CS2: CommitmentScheme<C2, H>,
374{
375 fn serialize_with_mode<W: std::io::prelude::Write>(
376 &self,
377 mut writer: W,
378 compress: ark_serialize::Compress,
379 ) -> Result<(), ark_serialize::SerializationError> {
380 self.cs_vp.serialize_with_mode(&mut writer, compress)?;
381 self.cf_cs_vp.serialize_with_mode(&mut writer, compress)
382 }
383
384 fn serialized_size(&self, compress: ark_serialize::Compress) -> usize {
385 self.cs_vp.serialized_size(compress) + self.cf_cs_vp.serialized_size(compress)
386 }
387}
388
389impl<C1, C2, CS1, CS2, const H: bool> VerifierParams<C1, C2, CS1, CS2, H>
390where
391 C1: CurveGroup,
392 C2: CurveGroup,
393 CS1: CommitmentScheme<C1, H>,
394 CS2: CommitmentScheme<C2, H>,
395{
396 /// returns the hash of the public parameters of Nova
397 pub fn pp_hash(&self) -> Result<C1::ScalarField, Error> {
398 pp_hash::<C1, C2, CS1, CS2, H>(
399 &self.r1cs,
400 &self.cf_r1cs,
401 &self.cs_vp,
402 &self.cf_cs_vp,
403 &self.poseidon_config,
404 )
405 }
406}
407
408#[derive(PartialEq, Eq, Debug, Clone, CanonicalSerialize, CanonicalDeserialize)]
409pub struct IVCProof<C1, C2>
410where
411 C1: CurveGroup,
412 C2: CurveGroup,
413{
414 // current step of the IVC
415 pub i: C1::ScalarField,
416 // initial state
417 pub z_0: Vec<C1::ScalarField>,
418 // current state
419 pub z_i: Vec<C1::ScalarField>,
420 // running instance
421 pub W_i: Witness<C1>,
422 pub U_i: CommittedInstance<C1>,
423 // incoming instance
424 pub w_i: Witness<C1>,
425 pub u_i: CommittedInstance<C1>,
426 // CycleFold instances
427 pub cf_W_i: CycleFoldWitness<C2>,
428 pub cf_U_i: CycleFoldCommittedInstance<C2>,
429}
430
431/// Implements Nova+CycleFold's IVC, described in [Nova](https://eprint.iacr.org/2021/370.pdf) and
432/// [CycleFold](https://eprint.iacr.org/2023/1192.pdf), following the FoldingScheme trait
433/// The `H` const generic specifies whether the homorphic commitment scheme is blinding
434#[derive(Clone, Debug)]
435pub struct Nova<C1, GC1, C2, GC2, FC, CS1, CS2, const H: bool = false>
436where
437 C1: CurveGroup,
438 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
439 C2: CurveGroup,
440 GC2: CurveVar<C2, CF2<C2>>,
441 FC: FCircuit<C1::ScalarField>,
442 CS1: CommitmentScheme<C1, H>,
443 CS2: CommitmentScheme<C2, H>,
444{
445 _gc1: PhantomData<GC1>,
446 _c2: PhantomData<C2>,
447 _gc2: PhantomData<GC2>,
448 /// R1CS of the Augmented Function circuit
449 pub r1cs: R1CS<C1::ScalarField>,
450 /// R1CS of the CycleFold circuit
451 pub cf_r1cs: R1CS<C2::ScalarField>,
452 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
453 /// CommitmentScheme::ProverParams over C1
454 pub cs_pp: CS1::ProverParams,
455 /// CycleFold CommitmentScheme::ProverParams, over C2
456 pub cf_cs_pp: CS2::ProverParams,
457 /// F circuit, the circuit that is being folded
458 pub F: FC,
459 /// public params hash
460 pub pp_hash: C1::ScalarField,
461 pub i: C1::ScalarField,
462 /// initial state
463 pub z_0: Vec<C1::ScalarField>,
464 /// current i-th state
465 pub z_i: Vec<C1::ScalarField>,
466 /// Nova instances
467 pub w_i: Witness<C1>,
468 pub u_i: CommittedInstance<C1>,
469 pub W_i: Witness<C1>,
470 pub U_i: CommittedInstance<C1>,
471
472 /// CycleFold running instance
473 pub cf_W_i: CycleFoldWitness<C2>,
474 pub cf_U_i: CycleFoldCommittedInstance<C2>,
475}
476
477impl<C1, GC1, C2, GC2, FC, CS1, CS2, const H: bool> FoldingScheme<C1, C2, FC>
478 for Nova<C1, GC1, C2, GC2, FC, CS1, CS2, H>
479where
480 C1: CurveGroup,
481 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
482 C2: CurveGroup,
483 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
484 FC: FCircuit<C1::ScalarField>,
485 CS1: CommitmentScheme<C1, H>,
486 CS2: CommitmentScheme<C2, H>,
487 <C1 as CurveGroup>::BaseField: PrimeField,
488 <C2 as CurveGroup>::BaseField: PrimeField,
489 <C1 as Group>::ScalarField: Absorb,
490 <C2 as Group>::ScalarField: Absorb,
491 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
492{
493 type PreprocessorParam = PreprocessorParam<C1, C2, FC, CS1, CS2, H>;
494 type ProverParam = ProverParams<C1, C2, CS1, CS2, H>;
495 type VerifierParam = VerifierParams<C1, C2, CS1, CS2, H>;
496 type RunningInstance = (CommittedInstance<C1>, Witness<C1>);
497 type IncomingInstance = (CommittedInstance<C1>, Witness<C1>);
498 type MultiCommittedInstanceWithWitness = ();
499 type CFInstance = (CycleFoldCommittedInstance<C2>, CycleFoldWitness<C2>);
500 type IVCProof = IVCProof<C1, C2>;
501
502 fn pp_deserialize_with_mode<R: std::io::prelude::Read>(
503 reader: R,
504 compress: ark_serialize::Compress,
505 validate: ark_serialize::Validate,
506 _fc_params: FC::Params, // FCircuit params
507 ) -> Result<Self::ProverParam, Error> {
508 Ok(Self::ProverParam::deserialize_with_mode(
509 reader, compress, validate,
510 )?)
511 }
512 fn vp_deserialize_with_mode<R: std::io::prelude::Read>(
513 mut reader: R,
514 compress: ark_serialize::Compress,
515 validate: ark_serialize::Validate,
516 fc_params: FC::Params,
517 ) -> Result<Self::VerifierParam, Error> {
518 let poseidon_config = poseidon_canonical_config::<C1::ScalarField>();
519
520 // generate the r1cs & cf_r1cs needed for the VerifierParams. In this way we avoid needing
521 // to serialize them, saving significant space in the VerifierParams serialized size.
522
523 // main circuit R1CS:
524 let f_circuit = FC::new(fc_params)?;
525 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
526 let augmented_F_circuit =
527 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(&poseidon_config, f_circuit.clone());
528 augmented_F_circuit.generate_constraints(cs.clone())?;
529 cs.finalize();
530 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
531 let r1cs = extract_r1cs::<C1::ScalarField>(&cs)?;
532
533 // CycleFold circuit R1CS
534 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
535 let cf_circuit = NovaCycleFoldCircuit::<C1, GC1>::empty();
536 cf_circuit.generate_constraints(cs2.clone())?;
537 cs2.finalize();
538 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
539 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2)?;
540
541 let cs_vp = CS1::VerifierParams::deserialize_with_mode(&mut reader, compress, validate)?;
542 let cf_cs_vp = CS2::VerifierParams::deserialize_with_mode(&mut reader, compress, validate)?;
543
544 Ok(Self::VerifierParam {
545 poseidon_config,
546 r1cs,
547 cf_r1cs,
548 cs_vp,
549 cf_cs_vp,
550 })
551 }
552
553 fn preprocess(
554 mut rng: impl RngCore,
555 prep_param: &Self::PreprocessorParam,
556 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
557 let (r1cs, cf_r1cs) =
558 get_r1cs::<C1, GC1, C2, GC2, FC>(&prep_param.poseidon_config, prep_param.F.clone())?;
559
560 // if cs params exist, use them, if not, generate new ones
561 let (cs_pp, cs_vp) = match (&prep_param.cs_pp, &prep_param.cs_vp) {
562 (Some(cs_pp), Some(cs_vp)) => (cs_pp.clone(), cs_vp.clone()),
563 _ => CS1::setup(&mut rng, r1cs.A.n_rows)?,
564 };
565 let (cf_cs_pp, cf_cs_vp) = match (&prep_param.cf_cs_pp, &prep_param.cf_cs_vp) {
566 (Some(cf_cs_pp), Some(cf_cs_vp)) => (cf_cs_pp.clone(), cf_cs_vp.clone()),
567 _ => CS2::setup(&mut rng, cf_r1cs.A.n_rows)?,
568 };
569
570 let prover_params = ProverParams::<C1, C2, CS1, CS2, H> {
571 poseidon_config: prep_param.poseidon_config.clone(),
572 cs_pp: cs_pp.clone(),
573 cf_cs_pp: cf_cs_pp.clone(),
574 };
575 let verifier_params = VerifierParams::<C1, C2, CS1, CS2, H> {
576 poseidon_config: prep_param.poseidon_config.clone(),
577 r1cs,
578 cf_r1cs,
579 cs_vp,
580 cf_cs_vp,
581 };
582
583 Ok((prover_params, verifier_params))
584 }
585
586 /// Initializes the Nova+CycleFold's IVC for the given parameters and initial state `z_0`.
587 fn init(
588 params: &(Self::ProverParam, Self::VerifierParam),
589 F: FC,
590 z_0: Vec<C1::ScalarField>,
591 ) -> Result<Self, Error> {
592 let (pp, vp) = params;
593
594 // prepare the circuit to obtain its R1CS
595 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
596 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
597
598 let augmented_F_circuit =
599 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(&pp.poseidon_config, F.clone());
600 let cf_circuit = NovaCycleFoldCircuit::<C1, GC1>::empty();
601
602 augmented_F_circuit.generate_constraints(cs.clone())?;
603 cs.finalize();
604 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
605 let r1cs = extract_r1cs::<C1::ScalarField>(&cs)?;
606
607 cf_circuit.generate_constraints(cs2.clone())?;
608 cs2.finalize();
609 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
610 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2)?;
611
612 // compute the public params hash
613 let pp_hash = vp.pp_hash()?;
614
615 // setup the dummy instances
616 let (W_dummy, U_dummy) = r1cs.dummy_witness_instance();
617 let (w_dummy, u_dummy) = r1cs.dummy_witness_instance();
618 let (cf_W_dummy, cf_U_dummy) = cf_r1cs.dummy_witness_instance();
619
620 // W_dummy=W_0 is a 'dummy witness', all zeroes, but with the size corresponding to the
621 // R1CS that we're working with.
622 Ok(Self {
623 _gc1: PhantomData,
624 _c2: PhantomData,
625 _gc2: PhantomData,
626 r1cs,
627 cf_r1cs,
628 poseidon_config: pp.poseidon_config.clone(),
629 cs_pp: pp.cs_pp.clone(),
630 cf_cs_pp: pp.cf_cs_pp.clone(),
631 F,
632 pp_hash,
633 i: C1::ScalarField::zero(),
634 z_0: z_0.clone(),
635 z_i: z_0,
636 w_i: w_dummy,
637 u_i: u_dummy,
638 W_i: W_dummy,
639 U_i: U_dummy,
640 // cyclefold running instance
641 cf_W_i: cf_W_dummy,
642 cf_U_i: cf_U_dummy,
643 })
644 }
645
646 /// Implements IVC.P of Nova+CycleFold
647 fn prove_step(
648 &mut self,
649 mut rng: impl RngCore,
650 external_inputs: Vec<C1::ScalarField>,
651 // Nova does not support multi-instances folding
652 _other_instances: Option<Self::MultiCommittedInstanceWithWitness>,
653 ) -> Result<(), Error> {
654 // ensure that commitments are blinding if user has specified so.
655 if H && self.i >= C1::ScalarField::one() {
656 let blinding_commitments = if self.i == C1::ScalarField::one() {
657 // blinding values of the running instances are zero at the first iteration
658 vec![self.w_i.rW, self.w_i.rE]
659 } else {
660 vec![self.w_i.rW, self.w_i.rE, self.W_i.rW, self.W_i.rE]
661 };
662 if blinding_commitments.contains(&C1::ScalarField::zero()) {
663 return Err(Error::IncorrectBlinding(
664 H,
665 format!("{:?}", blinding_commitments),
666 ));
667 }
668 }
669 // `sponge` is for digest computation.
670 let sponge = PoseidonSponge::<C1::ScalarField>::new(&self.poseidon_config);
671 // `transcript` is for challenge generation.
672 let mut transcript = sponge.clone();
673
674 let augmented_F_circuit: AugmentedFCircuit<C1, C2, GC2, FC>;
675
676 // Nova does not support (by design) multi-instances folding
677 if _other_instances.is_some() {
678 return Err(Error::NoMultiInstances);
679 }
680
681 if self.z_i.len() != self.F.state_len() {
682 return Err(Error::NotSameLength(
683 "z_i.len()".to_string(),
684 self.z_i.len(),
685 "F.state_len()".to_string(),
686 self.F.state_len(),
687 ));
688 }
689 if external_inputs.len() != self.F.external_inputs_len() {
690 return Err(Error::NotSameLength(
691 "F.external_inputs_len()".to_string(),
692 self.F.external_inputs_len(),
693 "external_inputs.len()".to_string(),
694 external_inputs.len(),
695 ));
696 }
697
698 if self.i > C1::ScalarField::from_le_bytes_mod_order(&usize::MAX.to_le_bytes()) {
699 return Err(Error::MaxStep);
700 }
701
702 let i_usize;
703
704 #[cfg(target_pointer_width = "64")]
705 {
706 let mut i_bytes: [u8; 8] = [0; 8];
707 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..8]);
708 i_usize = usize::from_le_bytes(i_bytes);
709 }
710
711 #[cfg(target_pointer_width = "32")]
712 {
713 let mut i_bytes: [u8; 4] = [0; 4];
714 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..4]);
715 i_usize = usize::from_le_bytes(i_bytes);
716 }
717
718 let z_i1 = self
719 .F
720 .step_native(i_usize, self.z_i.clone(), external_inputs.clone())?;
721
722 // fold Nova instances
723 let (W_i1, U_i1, cmT, r_bits): (Witness<C1>, CommittedInstance<C1>, C1, Vec<bool>) =
724 NIFS::<C1, CS1, PoseidonSponge<C1::ScalarField>, H>::prove(
725 &self.cs_pp,
726 &self.r1cs,
727 &mut transcript,
728 self.pp_hash,
729 &self.W_i,
730 &self.U_i,
731 &self.w_i,
732 &self.u_i,
733 )?;
734 let r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&r_bits))
735 .ok_or(Error::OutOfBounds)?;
736
737 // folded instance output (public input, x)
738 // u_{i+1}.x[0] = H(i+1, z_0, z_{i+1}, U_{i+1})
739 let u_i1_x = U_i1.hash(
740 &sponge,
741 self.pp_hash,
742 self.i + C1::ScalarField::one(),
743 &self.z_0,
744 &z_i1,
745 );
746 // u_{i+1}.x[1] = H(cf_U_{i+1})
747 let cf_u_i1_x: C1::ScalarField;
748
749 if self.i == C1::ScalarField::zero() {
750 cf_u_i1_x = self.cf_U_i.hash_cyclefold(&sponge, self.pp_hash);
751 // base case
752 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
753 _gc2: PhantomData,
754 poseidon_config: self.poseidon_config.clone(),
755 pp_hash: Some(self.pp_hash),
756 i: Some(C1::ScalarField::zero()), // = i=0
757 i_usize: Some(0),
758 z_0: Some(self.z_0.clone()), // = z_i
759 z_i: Some(self.z_i.clone()),
760 external_inputs: Some(external_inputs.clone()),
761 u_i_cmW: Some(self.u_i.cmW), // = dummy
762 U_i: Some(self.U_i.clone()), // = dummy
763 U_i1_cmE: Some(U_i1.cmE),
764 U_i1_cmW: Some(U_i1.cmW),
765 cmT: Some(cmT),
766 F: self.F.clone(),
767 x: Some(u_i1_x),
768 cf1_u_i_cmW: None,
769 cf2_u_i_cmW: None,
770 cf_U_i: None,
771 cf1_cmT: None,
772 cf2_cmT: None,
773 cf_x: Some(cf_u_i1_x),
774 };
775
776 #[cfg(test)]
777 {
778 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
779 .ok_or(Error::OutOfBounds)?;
780 let expected =
781 NIFS::<C1, CS1, PoseidonSponge<C1::ScalarField>, H>::fold_committed_instances(
782 r_Fr, &self.U_i, &self.u_i, &cmT,
783 );
784 assert_eq!(U_i1, expected);
785 }
786 } else {
787 // CycleFold part:
788 // get the vector used as public inputs 'x' in the CycleFold circuit
789 // cyclefold circuit for cmW
790 let cfW_u_i_x = [
791 vec![r_Fq],
792 get_cm_coordinates(&self.U_i.cmW),
793 get_cm_coordinates(&self.u_i.cmW),
794 get_cm_coordinates(&U_i1.cmW),
795 ]
796 .concat();
797 // cyclefold circuit for cmE
798 let cfE_u_i_x = [
799 vec![r_Fq],
800 get_cm_coordinates(&self.U_i.cmE),
801 get_cm_coordinates(&cmT),
802 get_cm_coordinates(&U_i1.cmE),
803 ]
804 .concat();
805
806 let cfW_circuit = NovaCycleFoldCircuit::<C1, GC1> {
807 _gc: PhantomData,
808 r_bits: Some(r_bits.clone()),
809 points: Some(vec![self.U_i.clone().cmW, self.u_i.clone().cmW]),
810 x: Some(cfW_u_i_x.clone()),
811 };
812 let cfE_circuit = NovaCycleFoldCircuit::<C1, GC1> {
813 _gc: PhantomData,
814 r_bits: Some(r_bits.clone()),
815 points: Some(vec![self.U_i.clone().cmE, cmT]),
816 x: Some(cfE_u_i_x.clone()),
817 };
818
819 // fold self.cf_U_i + cfW_U -> folded running with cfW
820 let (_cfW_w_i, cfW_u_i, cfW_W_i1, cfW_U_i1, cfW_cmT, _) = self.fold_cyclefold_circuit(
821 &mut transcript,
822 self.cf_W_i.clone(), // CycleFold running instance witness
823 self.cf_U_i.clone(), // CycleFold running instance
824 cfW_u_i_x,
825 cfW_circuit,
826 &mut rng,
827 )?;
828 // fold [the output from folding self.cf_U_i + cfW_U] + cfE_U = folded_running_with_cfW + cfE
829 let (_cfE_w_i, cfE_u_i, cf_W_i1, cf_U_i1, cf_cmT, _) = self.fold_cyclefold_circuit(
830 &mut transcript,
831 cfW_W_i1,
832 cfW_U_i1.clone(),
833 cfE_u_i_x,
834 cfE_circuit,
835 &mut rng,
836 )?;
837
838 cf_u_i1_x = cf_U_i1.hash_cyclefold(&sponge, self.pp_hash);
839
840 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
841 _gc2: PhantomData,
842 poseidon_config: self.poseidon_config.clone(),
843 pp_hash: Some(self.pp_hash),
844 i: Some(self.i),
845 i_usize: Some(i_usize),
846 z_0: Some(self.z_0.clone()),
847 z_i: Some(self.z_i.clone()),
848 external_inputs: Some(external_inputs.clone()),
849 u_i_cmW: Some(self.u_i.cmW),
850 U_i: Some(self.U_i.clone()),
851 U_i1_cmE: Some(U_i1.cmE),
852 U_i1_cmW: Some(U_i1.cmW),
853 cmT: Some(cmT),
854 F: self.F.clone(),
855 x: Some(u_i1_x),
856 // cyclefold values
857 cf1_u_i_cmW: Some(cfW_u_i.cmW),
858 cf2_u_i_cmW: Some(cfE_u_i.cmW),
859 cf_U_i: Some(self.cf_U_i.clone()),
860 cf1_cmT: Some(cfW_cmT),
861 cf2_cmT: Some(cf_cmT),
862 cf_x: Some(cf_u_i1_x),
863 };
864
865 self.cf_W_i = cf_W_i1;
866 self.cf_U_i = cf_U_i1;
867
868 #[cfg(test)]
869 {
870 cfW_u_i.check_incoming()?;
871 cfE_u_i.check_incoming()?;
872 self.cf_r1cs.check_relation(&_cfW_w_i, &cfW_u_i)?;
873 self.cf_r1cs.check_relation(&_cfE_w_i, &cfE_u_i)?;
874 self.cf_r1cs.check_relation(&self.cf_W_i, &self.cf_U_i)?;
875 }
876 }
877
878 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
879
880 augmented_F_circuit.generate_constraints(cs.clone())?;
881
882 #[cfg(test)]
883 assert!(cs.is_satisfied().unwrap());
884
885 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
886 let (w_i1, x_i1) = extract_w_x::<C1::ScalarField>(&cs);
887 if x_i1[0] != u_i1_x || x_i1[1] != cf_u_i1_x {
888 return Err(Error::NotEqual);
889 }
890
891 #[cfg(test)]
892 if x_i1.len() != 2 {
893 return Err(Error::NotExpectedLength(x_i1.len(), 2));
894 }
895
896 // set values for next iteration
897 self.i += C1::ScalarField::one();
898 self.z_i = z_i1;
899 self.w_i = Witness::<C1>::new::<H>(w_i1, self.r1cs.A.n_rows, &mut rng);
900 self.u_i = self.w_i.commit::<CS1, H>(&self.cs_pp, x_i1)?;
901 self.W_i = W_i1;
902 self.U_i = U_i1;
903
904 #[cfg(test)]
905 {
906 self.u_i.check_incoming()?;
907 self.r1cs.check_relation(&self.w_i, &self.u_i)?;
908 self.r1cs.check_relation(&self.W_i, &self.U_i)?;
909 }
910
911 Ok(())
912 }
913
914 fn state(&self) -> Vec<C1::ScalarField> {
915 self.z_i.clone()
916 }
917
918 fn ivc_proof(&self) -> Self::IVCProof {
919 Self::IVCProof {
920 i: self.i,
921 z_0: self.z_0.clone(),
922 z_i: self.z_i.clone(),
923 W_i: self.W_i.clone(),
924 U_i: self.U_i.clone(),
925 w_i: self.w_i.clone(),
926 u_i: self.u_i.clone(),
927 cf_W_i: self.cf_W_i.clone(),
928 cf_U_i: self.cf_U_i.clone(),
929 }
930 }
931
932 fn from_ivc_proof(
933 ivc_proof: IVCProof<C1, C2>,
934 fcircuit_params: FC::Params,
935 params: (Self::ProverParam, Self::VerifierParam),
936 ) -> Result<Self, Error> {
937 let IVCProof {
938 i,
939 z_0,
940 z_i,
941 W_i,
942 U_i,
943 w_i,
944 u_i,
945 cf_W_i,
946 cf_U_i,
947 } = ivc_proof;
948 let (pp, vp) = params;
949
950 let f_circuit = FC::new(fcircuit_params)?;
951 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
952 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
953 let augmented_F_circuit =
954 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(&pp.poseidon_config, f_circuit.clone());
955 let cf_circuit = NovaCycleFoldCircuit::<C1, GC1>::empty();
956
957 augmented_F_circuit.generate_constraints(cs.clone())?;
958 cs.finalize();
959 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
960 let r1cs = extract_r1cs::<C1::ScalarField>(&cs)?;
961
962 cf_circuit.generate_constraints(cs2.clone())?;
963 cs2.finalize();
964 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
965 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2)?;
966
967 Ok(Self {
968 _gc1: PhantomData,
969 _c2: PhantomData,
970 _gc2: PhantomData,
971 r1cs,
972 cf_r1cs,
973 poseidon_config: pp.poseidon_config,
974 cs_pp: pp.cs_pp,
975 cf_cs_pp: pp.cf_cs_pp,
976 F: f_circuit,
977 pp_hash: vp.pp_hash()?,
978 i,
979 z_0,
980 z_i,
981 w_i,
982 u_i,
983 W_i,
984 U_i,
985 cf_W_i,
986 cf_U_i,
987 })
988 }
989
990 /// Implements IVC.V of Nov.clone()a+CycleFold. Notice that this method does not include the
991 /// commitments verification, which is done in the Decider.
992 fn verify(vp: Self::VerifierParam, ivc_proof: Self::IVCProof) -> Result<(), Error> {
993 let Self::IVCProof {
994 i: num_steps,
995 z_0,
996 z_i,
997 W_i,
998 U_i,
999 w_i,
1000 u_i,
1001 cf_W_i,
1002 cf_U_i,
1003 } = ivc_proof;
1004
1005 let sponge = PoseidonSponge::<C1::ScalarField>::new(&vp.poseidon_config);
1006
1007 if num_steps == C1::ScalarField::zero() {
1008 if z_0 != z_i {
1009 return Err(Error::IVCVerificationFail);
1010 }
1011 return Ok(());
1012 }
1013
1014 if u_i.x.len() != 2 || U_i.x.len() != 2 {
1015 return Err(Error::IVCVerificationFail);
1016 }
1017
1018 let pp_hash = vp.pp_hash()?;
1019
1020 // check that u_i's output points to the running instance
1021 // u_i.X[0] == H(i, z_0, z_i, U_i)
1022 let expected_u_i_x = U_i.hash(&sponge, pp_hash, num_steps, &z_0, &z_i);
1023 if expected_u_i_x != u_i.x[0] {
1024 return Err(Error::IVCVerificationFail);
1025 }
1026 // u_i.X[1] == H(cf_U_i)
1027 let expected_cf_u_i_x = cf_U_i.hash_cyclefold(&sponge, pp_hash);
1028 if expected_cf_u_i_x != u_i.x[1] {
1029 return Err(Error::IVCVerificationFail);
1030 }
1031
1032 // check R1CS satisfiability, which is equivalent to checking if `u_i`
1033 // is an incoming instance and if `w_i` and `u_i` satisfy RelaxedR1CS
1034 u_i.check_incoming()?;
1035 vp.r1cs.check_relation(&w_i, &u_i)?;
1036 // check RelaxedR1CS satisfiability
1037 vp.r1cs.check_relation(&W_i, &U_i)?;
1038
1039 // check CycleFold RelaxedR1CS satisfiability
1040 vp.cf_r1cs.check_relation(&cf_W_i, &cf_U_i)?;
1041
1042 Ok(())
1043 }
1044}
1045
1046impl<C1, GC1, C2, GC2, FC, CS1, CS2, const H: bool> Nova<C1, GC1, C2, GC2, FC, CS1, CS2, H>
1047where
1048 C1: CurveGroup,
1049 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
1050 C2: CurveGroup,
1051 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
1052 FC: FCircuit<C1::ScalarField>,
1053 CS1: CommitmentScheme<C1, H>,
1054 CS2: CommitmentScheme<C2, H>,
1055 <C1 as CurveGroup>::BaseField: PrimeField,
1056 <C2 as CurveGroup>::BaseField: PrimeField,
1057 <C1 as Group>::ScalarField: Absorb,
1058 <C2 as Group>::ScalarField: Absorb,
1059 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
1060{
1061 // folds the given cyclefold circuit and its instances
1062 #[allow(clippy::type_complexity)]
1063 fn fold_cyclefold_circuit<T: Transcript<C1::ScalarField>>(
1064 &self,
1065 transcript: &mut T,
1066 cf_W_i: CycleFoldWitness<C2>, // witness of the running instance
1067 cf_U_i: CycleFoldCommittedInstance<C2>, // running instance
1068 cf_u_i_x: Vec<C2::ScalarField>,
1069 cf_circuit: NovaCycleFoldCircuit<C1, GC1>,
1070 rng: &mut impl RngCore,
1071 ) -> Result<
1072 (
1073 CycleFoldWitness<C2>,
1074 CycleFoldCommittedInstance<C2>, // u_i
1075 CycleFoldWitness<C2>, // W_i1
1076 CycleFoldCommittedInstance<C2>, // U_i1
1077 C2, // cmT
1078 C2::ScalarField, // r_Fq
1079 ),
1080 Error,
1081 > {
1082 fold_cyclefold_circuit::<NovaCycleFoldConfig<C1>, C1, GC1, C2, GC2, CS2, H>(
1083 transcript,
1084 self.cf_r1cs.clone(),
1085 self.cf_cs_pp.clone(),
1086 self.pp_hash,
1087 cf_W_i,
1088 cf_U_i,
1089 cf_u_i_x,
1090 cf_circuit,
1091 rng,
1092 )
1093 }
1094}
1095
1096/// helper method to get the r1cs from the ConstraintSynthesizer
1097pub fn get_r1cs_from_cs<F: PrimeField>(
1098 circuit: impl ConstraintSynthesizer<F>,
1099) -> Result<R1CS<F>, Error> {
1100 let cs = ConstraintSystem::<F>::new_ref();
1101 circuit.generate_constraints(cs.clone())?;
1102 cs.finalize();
1103 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
1104 let r1cs = extract_r1cs::<F>(&cs)?;
1105 Ok(r1cs)
1106}
1107
1108/// helper method to get the R1CS for both the AugmentedFCircuit and the CycleFold circuit
1109#[allow(clippy::type_complexity)]
1110pub fn get_r1cs<C1, GC1, C2, GC2, FC>(
1111 poseidon_config: &PoseidonConfig<C1::ScalarField>,
1112 F_circuit: FC,
1113) -> Result<(R1CS<C1::ScalarField>, R1CS<C2::ScalarField>), Error>
1114where
1115 C1: CurveGroup,
1116 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
1117 C2: CurveGroup,
1118 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
1119 FC: FCircuit<C1::ScalarField>,
1120 <C1 as CurveGroup>::BaseField: PrimeField,
1121 <C2 as CurveGroup>::BaseField: PrimeField,
1122 <C1 as Group>::ScalarField: Absorb,
1123 <C2 as Group>::ScalarField: Absorb,
1124 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
1125{
1126 let augmented_F_circuit =
1127 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(poseidon_config, F_circuit);
1128 let cf_circuit = NovaCycleFoldCircuit::<C1, GC1>::empty();
1129 let r1cs = get_r1cs_from_cs::<C1::ScalarField>(augmented_F_circuit)?;
1130 let cf_r1cs = get_r1cs_from_cs::<C2::ScalarField>(cf_circuit)?;
1131 Ok((r1cs, cf_r1cs))
1132}
1133
1134/// helper method to get the pedersen params length for both the AugmentedFCircuit and the
1135/// CycleFold circuit
1136pub fn get_cs_params_len<C1, GC1, C2, GC2, FC>(
1137 poseidon_config: &PoseidonConfig<C1::ScalarField>,
1138 F_circuit: FC,
1139) -> Result<(usize, usize), Error>
1140where
1141 C1: CurveGroup,
1142 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
1143 C2: CurveGroup,
1144 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
1145 FC: FCircuit<C1::ScalarField>,
1146 <C1 as CurveGroup>::BaseField: PrimeField,
1147 <C2 as CurveGroup>::BaseField: PrimeField,
1148 <C1 as Group>::ScalarField: Absorb,
1149 <C2 as Group>::ScalarField: Absorb,
1150 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
1151{
1152 let (r1cs, cf_r1cs) = get_r1cs::<C1, GC1, C2, GC2, FC>(poseidon_config, F_circuit)?;
1153 Ok((r1cs.A.n_rows, cf_r1cs.A.n_rows))
1154}
1155
1156#[cfg(test)]
1157pub mod tests {
1158 use crate::commitment::kzg::KZG;
1159 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
1160 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
1161
1162 use super::*;
1163 use crate::commitment::pedersen::Pedersen;
1164 use crate::frontend::utils::CubicFCircuit;
1165 use crate::transcript::poseidon::poseidon_canonical_config;
1166
1167 /// This test tests the Nova+CycleFold IVC, and by consequence it is also testing the
1168 /// AugmentedFCircuit
1169 #[test]
1170 fn test_ivc() {
1171 let poseidon_config = poseidon_canonical_config::<Fr>();
1172
1173 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
1174
1175 // run the test using Pedersen commitments on both sides of the curve cycle
1176 test_ivc_opt::<Pedersen<Projective>, Pedersen<Projective2>, false>(
1177 poseidon_config.clone(),
1178 F_circuit,
1179 3,
1180 );
1181
1182 test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
1183 poseidon_config.clone(),
1184 F_circuit,
1185 3,
1186 );
1187
1188 // run the test using KZG for the commitments on the main curve, and Pedersen for the
1189 // commitments on the secondary curve
1190 test_ivc_opt::<KZG<Bn254>, Pedersen<Projective2>, false>(poseidon_config, F_circuit, 3);
1191 }
1192
1193 // test_ivc allowing to choose the CommitmentSchemes
1194 #[allow(clippy::type_complexity)]
1195 pub(crate) fn test_ivc_opt<
1196 CS1: CommitmentScheme<Projective, H>,
1197 CS2: CommitmentScheme<Projective2, H>,
1198 const H: bool,
1199 >(
1200 poseidon_config: PoseidonConfig<Fr>,
1201 F_circuit: CubicFCircuit<Fr>,
1202 num_steps: usize,
1203 ) -> (
1204 Vec<Fr>,
1205 Nova<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2, H>,
1206 ) {
1207 let mut rng = ark_std::test_rng();
1208
1209 let prep_param =
1210 PreprocessorParam::<Projective, Projective2, CubicFCircuit<Fr>, CS1, CS2, H> {
1211 poseidon_config,
1212 F: F_circuit,
1213 cs_pp: None,
1214 cs_vp: None,
1215 cf_cs_pp: None,
1216 cf_cs_vp: None,
1217 };
1218 let nova_params = Nova::<
1219 Projective,
1220 GVar,
1221 Projective2,
1222 GVar2,
1223 CubicFCircuit<Fr>,
1224 CS1,
1225 CS2,
1226 H,
1227 >::preprocess(&mut rng, &prep_param)
1228 .unwrap();
1229
1230 let z_0 = vec![Fr::from(3_u32)];
1231 let mut nova =
1232 Nova::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2, H>::init(
1233 &nova_params,
1234 F_circuit,
1235 z_0.clone(),
1236 )
1237 .unwrap();
1238
1239 for _ in 0..num_steps {
1240 nova.prove_step(&mut rng, vec![], None).unwrap();
1241 }
1242 assert_eq!(Fr::from(num_steps as u32), nova.i);
1243
1244 // serialize the Nova Prover & Verifier params. These params are the trusted setup of the commitment schemes used
1245 let mut nova_pp_serialized = vec![];
1246 nova_params
1247 .0
1248 .serialize_compressed(&mut nova_pp_serialized)
1249 .unwrap();
1250 let mut nova_vp_serialized = vec![];
1251 nova_params
1252 .1
1253 .serialize_compressed(&mut nova_vp_serialized)
1254 .unwrap();
1255
1256 // deserialize the Nova params
1257 let _nova_pp_deserialized =
1258 ProverParams::<Projective, Projective2, CS1, CS2, H>::deserialize_compressed(
1259 &mut nova_pp_serialized.as_slice(),
1260 )
1261 .unwrap();
1262 let nova_vp_deserialized = Nova::<
1263 Projective,
1264 GVar,
1265 Projective2,
1266 GVar2,
1267 CubicFCircuit<Fr>,
1268 CS1,
1269 CS2,
1270 H,
1271 >::vp_deserialize_with_mode(
1272 &mut nova_vp_serialized.as_slice(),
1273 ark_serialize::Compress::Yes,
1274 ark_serialize::Validate::Yes,
1275 (), // fcircuit_params
1276 )
1277 .unwrap();
1278
1279 let ivc_proof = nova.ivc_proof();
1280
1281 // serialize IVCProof
1282 let mut ivc_proof_serialized = vec![];
1283 assert!(ivc_proof
1284 .serialize_compressed(&mut ivc_proof_serialized)
1285 .is_ok());
1286 // deserialize IVCProof
1287 let ivc_proof_deserialized = <Nova::<
1288 Projective,
1289 GVar,
1290 Projective2,
1291 GVar2,
1292 CubicFCircuit<Fr>,
1293 CS1,
1294 CS2,
1295 H,
1296 > as FoldingScheme<Projective,Projective2, CubicFCircuit<Fr>>>::IVCProof::deserialize_compressed(
1297 ivc_proof_serialized.as_slice()
1298 )
1299 .unwrap();
1300
1301 // verify the deserialized IVCProof with the deserialized VerifierParams
1302 Nova::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2, H>::verify(
1303 nova_vp_deserialized, // Nova's verifier params
1304 ivc_proof_deserialized,
1305 )
1306 .unwrap();
1307
1308 (z_0, nova)
1309 }
1310}