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