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