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