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