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