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