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