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::{
4 crh::{poseidon::CRH, CRHScheme},
5 sponge::{poseidon::PoseidonConfig, Absorb},
6};
7use ark_ec::{AffineRepr, CurveGroup, Group};
8use ark_ff::{BigInteger, Field, PrimeField, ToConstraintField};
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, Zero};
15use core::marker::PhantomData;
16
17use crate::arith::r1cs::{extract_r1cs, extract_w_x, R1CS};
18use crate::commitment::CommitmentScheme;
19use crate::folding::circuits::{
20 cyclefold::{fold_cyclefold_circuit, CycleFoldCircuit},
21 nonnative::{
22 affine::nonnative_affine_to_field_elements, uint::nonnative_field_to_field_elements,
23 },
24 CF2,
25};
26use crate::frontend::FCircuit;
27use crate::utils::{get_cm_coordinates, pp_hash, vec::is_zero_vec};
28use crate::Error;
29use crate::FoldingScheme;
30
31pub mod circuits;
32pub mod decider_eth;
33pub mod decider_eth_circuit;
34pub mod nifs;
35pub mod serialize;
36pub mod traits;
37use circuits::{AugmentedFCircuit, ChallengeGadget};
38use nifs::NIFS;
39use traits::NovaR1CS;
40
41#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
42pub struct CommittedInstance<C: CurveGroup> {
43 pub cmE: C,
44 pub u: C::ScalarField,
45 pub cmW: C,
46 pub x: Vec<C::ScalarField>,
47}
48
49impl<C: CurveGroup> CommittedInstance<C> {
50 pub fn dummy(io_len: usize) -> Self {
51 Self {
52 cmE: C::zero(),
53 u: C::ScalarField::zero(),
54 cmW: C::zero(),
55 x: vec![C::ScalarField::zero(); io_len],
56 }
57 }
58}
59
60impl<C: CurveGroup> CommittedInstance<C>
61where
62 <C as Group>::ScalarField: Absorb,
63 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
64{
65 /// hash implements the committed instance hash compatible with the gadget implemented in
66 /// nova/circuits.rs::CommittedInstanceVar.hash.
67 /// Returns `H(i, z_0, z_i, U_i)`, where `i` can be `i` but also `i+1`, and `U_i` is the
68 /// `CommittedInstance`.
69 pub fn hash(
70 &self,
71 poseidon_config: &PoseidonConfig<C::ScalarField>,
72 pp_hash: C::ScalarField, // public params hash
73 i: C::ScalarField,
74 z_0: Vec<C::ScalarField>,
75 z_i: Vec<C::ScalarField>,
76 ) -> Result<C::ScalarField, Error> {
77 let (cmE_x, cmE_y) = nonnative_affine_to_field_elements::<C>(self.cmE)?;
78 let (cmW_x, cmW_y) = nonnative_affine_to_field_elements::<C>(self.cmW)?;
79
80 CRH::<C::ScalarField>::evaluate(
81 poseidon_config,
82 vec![
83 vec![pp_hash, i],
84 z_0,
85 z_i,
86 vec![self.u],
87 self.x.clone(),
88 cmE_x,
89 cmE_y,
90 cmW_x,
91 cmW_y,
92 ]
93 .concat(),
94 )
95 .map_err(|e| Error::Other(e.to_string()))
96 }
97}
98
99impl<C: CurveGroup> ToConstraintField<C::BaseField> for CommittedInstance<C>
100where
101 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
102{
103 fn to_field_elements(&self) -> Option<Vec<C::BaseField>> {
104 let u = nonnative_field_to_field_elements(&self.u);
105 let x = self
106 .x
107 .iter()
108 .flat_map(nonnative_field_to_field_elements)
109 .collect::<Vec<_>>();
110 let (cmE_x, cmE_y, cmE_is_inf) = match self.cmE.into_affine().xy() {
111 Some((&x, &y)) => (x, y, C::BaseField::zero()),
112 None => (
113 C::BaseField::zero(),
114 C::BaseField::zero(),
115 C::BaseField::one(),
116 ),
117 };
118 let (cmW_x, cmW_y, cmW_is_inf) = match self.cmW.into_affine().xy() {
119 Some((&x, &y)) => (x, y, C::BaseField::zero()),
120 None => (
121 C::BaseField::zero(),
122 C::BaseField::zero(),
123 C::BaseField::one(),
124 ),
125 };
126 // Concatenate `cmE_is_inf` and `cmW_is_inf` to save constraints for CRHGadget::evaluate in the corresponding circuit
127 let is_inf = cmE_is_inf.double() + cmW_is_inf;
128
129 Some([u, x, vec![cmE_x, cmE_y, cmW_x, cmW_y, is_inf]].concat())
130 }
131}
132
133impl<C: CurveGroup> CommittedInstance<C>
134where
135 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField + Absorb,
136{
137 /// hash_cyclefold implements the committed instance hash compatible with the gadget implemented in
138 /// nova/cyclefold.rs::CycleFoldCommittedInstanceVar.hash.
139 /// Returns `H(U_i)`, where `U_i` is the `CommittedInstance` for CycleFold.
140 pub fn hash_cyclefold(
141 &self,
142 poseidon_config: &PoseidonConfig<C::BaseField>,
143 pp_hash: C::BaseField, // public params hash
144 ) -> Result<C::BaseField, Error> {
145 CRH::<C::BaseField>::evaluate(
146 poseidon_config,
147 [vec![pp_hash], self.to_field_elements().unwrap()].concat(),
148 )
149 .map_err(|e| Error::Other(e.to_string()))
150 }
151}
152
153#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
154pub struct Witness<C: CurveGroup> {
155 pub E: Vec<C::ScalarField>,
156 pub rE: C::ScalarField,
157 pub W: Vec<C::ScalarField>,
158 pub rW: C::ScalarField,
159}
160
161impl<C: CurveGroup> Witness<C>
162where
163 <C as Group>::ScalarField: Absorb,
164{
165 pub fn new(w: Vec<C::ScalarField>, e_len: usize) -> Self {
166 // note: at the current version, we don't use the blinding factors and we set them to 0
167 // always.
168 Self {
169 E: vec![C::ScalarField::zero(); e_len],
170 rE: C::ScalarField::zero(),
171 W: w,
172 rW: C::ScalarField::zero(),
173 }
174 }
175 pub fn commit<CS: CommitmentScheme<C>>(
176 &self,
177 params: &CS::ProverParams,
178 x: Vec<C::ScalarField>,
179 ) -> Result<CommittedInstance<C>, Error> {
180 let mut cmE = C::zero();
181 if !is_zero_vec::<C::ScalarField>(&self.E) {
182 cmE = CS::commit(params, &self.E, &self.rE)?;
183 }
184 let cmW = CS::commit(params, &self.W, &self.rW)?;
185 Ok(CommittedInstance {
186 cmE,
187 u: C::ScalarField::one(),
188 cmW,
189 x,
190 })
191 }
192}
193
194#[derive(Debug, Clone)]
195pub struct PreprocessorParam<C1, C2, FC, CS1, CS2>
196where
197 C1: CurveGroup,
198 C2: CurveGroup,
199 FC: FCircuit<C1::ScalarField>,
200 CS1: CommitmentScheme<C1>,
201 CS2: CommitmentScheme<C2>,
202{
203 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
204 pub F: FC,
205 // cs params if not provided, will be generated at the preprocess method
206 pub cs_pp: Option<CS1::ProverParams>,
207 pub cs_vp: Option<CS1::VerifierParams>,
208 pub cf_cs_pp: Option<CS2::ProverParams>,
209 pub cf_cs_vp: Option<CS2::VerifierParams>,
210}
211
212impl<C1, C2, FC, CS1, CS2> PreprocessorParam<C1, C2, FC, CS1, CS2>
213where
214 C1: CurveGroup,
215 C2: CurveGroup,
216 FC: FCircuit<C1::ScalarField>,
217 CS1: CommitmentScheme<C1>,
218 CS2: CommitmentScheme<C2>,
219{
220 pub fn new(poseidon_config: PoseidonConfig<C1::ScalarField>, F: FC) -> Self {
221 Self {
222 poseidon_config,
223 F,
224 cs_pp: None,
225 cs_vp: None,
226 cf_cs_pp: None,
227 cf_cs_vp: None,
228 }
229 }
230}
231
232#[derive(Debug, Clone)]
233pub struct ProverParams<C1, C2, CS1, CS2>
234where
235 C1: CurveGroup,
236 C2: CurveGroup,
237 CS1: CommitmentScheme<C1>,
238 CS2: CommitmentScheme<C2>,
239{
240 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
241 pub cs_pp: CS1::ProverParams,
242 pub cf_cs_pp: CS2::ProverParams,
243}
244
245#[derive(Debug, Clone)]
246pub struct VerifierParams<C1, C2, CS1, CS2>
247where
248 C1: CurveGroup,
249 C2: CurveGroup,
250 CS1: CommitmentScheme<C1>,
251 CS2: CommitmentScheme<C2>,
252{
253 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
254 pub r1cs: R1CS<C1::ScalarField>,
255 pub cf_r1cs: R1CS<C2::ScalarField>,
256 pub cs_vp: CS1::VerifierParams,
257 pub cf_cs_vp: CS2::VerifierParams,
258}
259
260impl<C1, C2, CS1, CS2> VerifierParams<C1, C2, CS1, CS2>
261where
262 C1: CurveGroup,
263 C2: CurveGroup,
264 CS1: CommitmentScheme<C1>,
265 CS2: CommitmentScheme<C2>,
266{
267 /// returns the hash of the public parameters of Nova
268 pub fn pp_hash(&self) -> Result<C1::ScalarField, Error> {
269 pp_hash::<C1, C2, CS1, CS2>(
270 &self.r1cs,
271 &self.cf_r1cs,
272 &self.cs_vp,
273 &self.cf_cs_vp,
274 &self.poseidon_config,
275 )
276 }
277}
278
279/// Implements Nova+CycleFold's IVC, described in [Nova](https://eprint.iacr.org/2021/370.pdf) and
280/// [CycleFold](https://eprint.iacr.org/2023/1192.pdf), following the FoldingScheme trait
281#[derive(Clone, Debug)]
282pub struct Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
283where
284 C1: CurveGroup,
285 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
286 C2: CurveGroup,
287 GC2: CurveVar<C2, CF2<C2>>,
288 FC: FCircuit<C1::ScalarField>,
289 CS1: CommitmentScheme<C1>,
290 CS2: CommitmentScheme<C2>,
291{
292 _gc1: PhantomData<GC1>,
293 _c2: PhantomData<C2>,
294 _gc2: PhantomData<GC2>,
295 /// R1CS of the Augmented Function circuit
296 pub r1cs: R1CS<C1::ScalarField>,
297 /// R1CS of the CycleFold circuit
298 pub cf_r1cs: R1CS<C2::ScalarField>,
299 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
300 /// CommitmentScheme::ProverParams over C1
301 pub cs_pp: CS1::ProverParams,
302 /// CycleFold CommitmentScheme::ProverParams, over C2
303 pub cf_cs_pp: CS2::ProverParams,
304 /// F circuit, the circuit that is being folded
305 pub F: FC,
306 /// public params hash
307 pub pp_hash: C1::ScalarField,
308 pub i: C1::ScalarField,
309 /// initial state
310 pub z_0: Vec<C1::ScalarField>,
311 /// current i-th state
312 pub z_i: Vec<C1::ScalarField>,
313 /// Nova instances
314 pub w_i: Witness<C1>,
315 pub u_i: CommittedInstance<C1>,
316 pub W_i: Witness<C1>,
317 pub U_i: CommittedInstance<C1>,
318
319 /// CycleFold running instance
320 pub cf_W_i: Witness<C2>,
321 pub cf_U_i: CommittedInstance<C2>,
322}
323
324impl<C1, GC1, C2, GC2, FC, CS1, CS2> FoldingScheme<C1, C2, FC>
325 for Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
326where
327 C1: CurveGroup,
328 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
329 C2: CurveGroup,
330 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
331 FC: FCircuit<C1::ScalarField>,
332 CS1: CommitmentScheme<C1>,
333 CS2: CommitmentScheme<C2>,
334 <C1 as CurveGroup>::BaseField: PrimeField,
335 <C2 as CurveGroup>::BaseField: PrimeField,
336 <C1 as Group>::ScalarField: Absorb,
337 <C2 as Group>::ScalarField: Absorb,
338 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
339 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
340 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
341{
342 type PreprocessorParam = PreprocessorParam<C1, C2, FC, CS1, CS2>;
343 type ProverParam = ProverParams<C1, C2, CS1, CS2>;
344 type VerifierParam = VerifierParams<C1, C2, CS1, CS2>;
345 type RunningInstance = (CommittedInstance<C1>, Witness<C1>);
346 type IncomingInstance = (CommittedInstance<C1>, Witness<C1>);
347 type CFInstance = (CommittedInstance<C2>, Witness<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> {
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> {
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 = CycleFoldCircuit::<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 _rng: impl RngCore,
454 external_inputs: Vec<C1::ScalarField>,
455 ) -> Result<(), Error> {
456 let augmented_F_circuit: AugmentedFCircuit<C1, C2, GC2, FC>;
457
458 if self.z_i.len() != self.F.state_len() {
459 return Err(Error::NotSameLength(
460 "z_i.len()".to_string(),
461 self.z_i.len(),
462 "F.state_len()".to_string(),
463 self.F.state_len(),
464 ));
465 }
466 if external_inputs.len() != self.F.external_inputs_len() {
467 return Err(Error::NotSameLength(
468 "F.external_inputs_len()".to_string(),
469 self.F.external_inputs_len(),
470 "external_inputs.len()".to_string(),
471 external_inputs.len(),
472 ));
473 }
474
475 if self.i > C1::ScalarField::from_le_bytes_mod_order(&usize::MAX.to_le_bytes()) {
476 return Err(Error::MaxStep);
477 }
478 let mut i_bytes: [u8; 8] = [0; 8];
479 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..8]);
480 let i_usize: usize = usize::from_le_bytes(i_bytes);
481
482 let z_i1 = self
483 .F
484 .step_native(i_usize, self.z_i.clone(), external_inputs.clone())?;
485
486 // compute T and cmT for AugmentedFCircuit
487 let (T, cmT) = self.compute_cmT()?;
488
489 // r_bits is the r used to the RLC of the F' instances
490 let r_bits = ChallengeGadget::<C1>::get_challenge_native(
491 &self.poseidon_config,
492 self.pp_hash,
493 self.U_i.clone(),
494 self.u_i.clone(),
495 cmT,
496 )?;
497 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
498 .ok_or(Error::OutOfBounds)?;
499 let r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&r_bits))
500 .ok_or(Error::OutOfBounds)?;
501
502 // fold Nova instances
503 let (W_i1, U_i1): (Witness<C1>, CommittedInstance<C1>) = NIFS::<C1, CS1>::fold_instances(
504 r_Fr, &self.W_i, &self.U_i, &self.w_i, &self.u_i, &T, cmT,
505 )?;
506
507 // folded instance output (public input, x)
508 // u_{i+1}.x[0] = H(i+1, z_0, z_{i+1}, U_{i+1})
509 let u_i1_x = U_i1.hash(
510 &self.poseidon_config,
511 self.pp_hash,
512 self.i + C1::ScalarField::one(),
513 self.z_0.clone(),
514 z_i1.clone(),
515 )?;
516 // u_{i+1}.x[1] = H(cf_U_{i+1})
517 let cf_u_i1_x: C1::ScalarField;
518
519 if self.i == C1::ScalarField::zero() {
520 cf_u_i1_x = self
521 .cf_U_i
522 .hash_cyclefold(&self.poseidon_config, self.pp_hash)?;
523 // base case
524 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
525 _gc2: PhantomData,
526 poseidon_config: self.poseidon_config.clone(),
527 pp_hash: Some(self.pp_hash),
528 i: Some(C1::ScalarField::zero()), // = i=0
529 i_usize: Some(0),
530 z_0: Some(self.z_0.clone()), // = z_i
531 z_i: Some(self.z_i.clone()),
532 external_inputs: Some(external_inputs.clone()),
533 u_i_cmW: Some(self.u_i.cmW), // = dummy
534 U_i: Some(self.U_i.clone()), // = dummy
535 U_i1_cmE: Some(U_i1.cmE),
536 U_i1_cmW: Some(U_i1.cmW),
537 cmT: Some(cmT),
538 F: self.F.clone(),
539 x: Some(u_i1_x),
540 cf1_u_i_cmW: None,
541 cf2_u_i_cmW: None,
542 cf_U_i: None,
543 cf1_cmT: None,
544 cf2_cmT: None,
545 cf_x: Some(cf_u_i1_x),
546 };
547
548 #[cfg(test)]
549 NIFS::<C1, CS1>::verify_folded_instance(r_Fr, &self.U_i, &self.u_i, &U_i1, &cmT)?;
550 } else {
551 // CycleFold part:
552 // get the vector used as public inputs 'x' in the CycleFold circuit
553 // cyclefold circuit for cmW
554 let cfW_u_i_x = [
555 vec![r_Fq],
556 get_cm_coordinates(&self.U_i.cmW),
557 get_cm_coordinates(&self.u_i.cmW),
558 get_cm_coordinates(&U_i1.cmW),
559 ]
560 .concat();
561 // cyclefold circuit for cmE
562 let cfE_u_i_x = [
563 vec![r_Fq],
564 get_cm_coordinates(&self.U_i.cmE),
565 get_cm_coordinates(&cmT),
566 get_cm_coordinates(&U_i1.cmE),
567 ]
568 .concat();
569
570 let cfW_circuit = CycleFoldCircuit::<C1, GC1> {
571 _gc: PhantomData,
572 r_bits: Some(r_bits.clone()),
573 p1: Some(self.U_i.clone().cmW),
574 p2: Some(self.u_i.clone().cmW),
575 x: Some(cfW_u_i_x.clone()),
576 };
577 let cfE_circuit = CycleFoldCircuit::<C1, GC1> {
578 _gc: PhantomData,
579 r_bits: Some(r_bits.clone()),
580 p1: Some(self.U_i.clone().cmE),
581 p2: Some(cmT),
582 x: Some(cfE_u_i_x.clone()),
583 };
584
585 // fold self.cf_U_i + cfW_U -> folded running with cfW
586 let (_cfW_w_i, cfW_u_i, cfW_W_i1, cfW_U_i1, cfW_cmT, _) = self.fold_cyclefold_circuit(
587 self.cf_W_i.clone(), // CycleFold running instance witness
588 self.cf_U_i.clone(), // CycleFold running instance
589 cfW_u_i_x,
590 cfW_circuit,
591 )?;
592 // fold [the output from folding self.cf_U_i + cfW_U] + cfE_U = folded_running_with_cfW + cfE
593 let (_cfE_w_i, cfE_u_i, cf_W_i1, cf_U_i1, cf_cmT, _) =
594 self.fold_cyclefold_circuit(cfW_W_i1, cfW_U_i1.clone(), cfE_u_i_x, cfE_circuit)?;
595
596 cf_u_i1_x = cf_U_i1.hash_cyclefold(&self.poseidon_config, self.pp_hash)?;
597
598 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
599 _gc2: PhantomData,
600 poseidon_config: self.poseidon_config.clone(),
601 pp_hash: Some(self.pp_hash),
602 i: Some(self.i),
603 i_usize: Some(i_usize),
604 z_0: Some(self.z_0.clone()),
605 z_i: Some(self.z_i.clone()),
606 external_inputs: Some(external_inputs.clone()),
607 u_i_cmW: Some(self.u_i.cmW),
608 U_i: Some(self.U_i.clone()),
609 U_i1_cmE: Some(U_i1.cmE),
610 U_i1_cmW: Some(U_i1.cmW),
611 cmT: Some(cmT),
612 F: self.F.clone(),
613 x: Some(u_i1_x),
614 // cyclefold values
615 cf1_u_i_cmW: Some(cfW_u_i.cmW),
616 cf2_u_i_cmW: Some(cfE_u_i.cmW),
617 cf_U_i: Some(self.cf_U_i.clone()),
618 cf1_cmT: Some(cfW_cmT),
619 cf2_cmT: Some(cf_cmT),
620 cf_x: Some(cf_u_i1_x),
621 };
622
623 self.cf_W_i = cf_W_i1;
624 self.cf_U_i = cf_U_i1;
625
626 #[cfg(test)]
627 {
628 self.cf_r1cs.check_instance_relation(&_cfW_w_i, &cfW_u_i)?;
629 self.cf_r1cs.check_instance_relation(&_cfE_w_i, &cfE_u_i)?;
630 self.cf_r1cs
631 .check_relaxed_instance_relation(&self.cf_W_i, &self.cf_U_i)?;
632 }
633 }
634
635 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
636
637 augmented_F_circuit.generate_constraints(cs.clone())?;
638
639 #[cfg(test)]
640 assert!(cs.is_satisfied().unwrap());
641
642 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
643 let (w_i1, x_i1) = extract_w_x::<C1::ScalarField>(&cs);
644 if x_i1[0] != u_i1_x || x_i1[1] != cf_u_i1_x {
645 return Err(Error::NotEqual);
646 }
647
648 #[cfg(test)]
649 if x_i1.len() != 2 {
650 return Err(Error::NotExpectedLength(x_i1.len(), 2));
651 }
652
653 // set values for next iteration
654 self.i += C1::ScalarField::one();
655 self.z_i = z_i1;
656 self.w_i = Witness::<C1>::new(w_i1, self.r1cs.A.n_rows);
657 self.u_i = self.w_i.commit::<CS1>(&self.cs_pp, x_i1)?;
658 self.W_i = W_i1;
659 self.U_i = U_i1;
660
661 #[cfg(test)]
662 {
663 self.r1cs.check_instance_relation(&self.w_i, &self.u_i)?;
664 self.r1cs
665 .check_relaxed_instance_relation(&self.W_i, &self.U_i)?;
666 }
667
668 Ok(())
669 }
670
671 fn state(&self) -> Vec<C1::ScalarField> {
672 self.z_i.clone()
673 }
674
675 fn instances(
676 &self,
677 ) -> (
678 Self::RunningInstance,
679 Self::IncomingInstance,
680 Self::CFInstance,
681 ) {
682 (
683 (self.U_i.clone(), self.W_i.clone()),
684 (self.u_i.clone(), self.w_i.clone()),
685 (self.cf_U_i.clone(), self.cf_W_i.clone()),
686 )
687 }
688
689 /// Implements IVC.V of Nova+CycleFold. Notice that this method does not include the
690 /// commitments verification, which is done in the Decider.
691 fn verify(
692 vp: Self::VerifierParam,
693 z_0: Vec<C1::ScalarField>, // initial state
694 z_i: Vec<C1::ScalarField>, // last state
695 num_steps: C1::ScalarField,
696 running_instance: Self::RunningInstance,
697 incoming_instance: Self::IncomingInstance,
698 cyclefold_instance: Self::CFInstance,
699 ) -> Result<(), Error> {
700 if num_steps == C1::ScalarField::zero() {
701 if z_0 != z_i {
702 return Err(Error::IVCVerificationFail);
703 }
704 return Ok(());
705 }
706
707 let (U_i, W_i) = running_instance;
708 let (u_i, w_i) = incoming_instance;
709 let (cf_U_i, cf_W_i) = cyclefold_instance;
710
711 if u_i.x.len() != 2 || U_i.x.len() != 2 {
712 return Err(Error::IVCVerificationFail);
713 }
714
715 let pp_hash = vp.pp_hash()?;
716
717 // check that u_i's output points to the running instance
718 // u_i.X[0] == H(i, z_0, z_i, U_i)
719 let expected_u_i_x = U_i.hash(&vp.poseidon_config, pp_hash, num_steps, z_0, z_i.clone())?;
720 if expected_u_i_x != u_i.x[0] {
721 return Err(Error::IVCVerificationFail);
722 }
723 // u_i.X[1] == H(cf_U_i)
724 let expected_cf_u_i_x = cf_U_i.hash_cyclefold(&vp.poseidon_config, pp_hash)?;
725 if expected_cf_u_i_x != u_i.x[1] {
726 return Err(Error::IVCVerificationFail);
727 }
728
729 // check u_i.cmE==0, u_i.u==1 (=u_i is a un-relaxed instance)
730 if !u_i.cmE.is_zero() || !u_i.u.is_one() {
731 return Err(Error::IVCVerificationFail);
732 }
733
734 // check R1CS satisfiability
735 vp.r1cs.check_instance_relation(&w_i, &u_i)?;
736 // check RelaxedR1CS satisfiability
737 vp.r1cs.check_relaxed_instance_relation(&W_i, &U_i)?;
738
739 // check CycleFold RelaxedR1CS satisfiability
740 vp.cf_r1cs
741 .check_relaxed_instance_relation(&cf_W_i, &cf_U_i)?;
742
743 Ok(())
744 }
745}
746
747impl<C1, GC1, C2, GC2, FC, CS1, CS2> Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
748where
749 C1: CurveGroup,
750 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
751 C2: CurveGroup,
752 GC2: CurveVar<C2, CF2<C2>>,
753 FC: FCircuit<C1::ScalarField>,
754 CS1: CommitmentScheme<C1>,
755 CS2: CommitmentScheme<C2>,
756 <C2 as CurveGroup>::BaseField: PrimeField,
757 <C1 as Group>::ScalarField: Absorb,
758 <C2 as Group>::ScalarField: Absorb,
759 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
760{
761 // computes T and cmT for the AugmentedFCircuit
762 fn compute_cmT(&self) -> Result<(Vec<C1::ScalarField>, C1), Error> {
763 NIFS::<C1, CS1>::compute_cmT(
764 &self.cs_pp,
765 &self.r1cs,
766 &self.w_i,
767 &self.u_i,
768 &self.W_i,
769 &self.U_i,
770 )
771 }
772}
773
774impl<C1, GC1, C2, GC2, FC, CS1, CS2> Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
775where
776 C1: CurveGroup,
777 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
778 C2: CurveGroup,
779 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
780 FC: FCircuit<C1::ScalarField>,
781 CS1: CommitmentScheme<C1>,
782 CS2: CommitmentScheme<C2>,
783 <C1 as CurveGroup>::BaseField: PrimeField,
784 <C2 as CurveGroup>::BaseField: PrimeField,
785 <C1 as Group>::ScalarField: Absorb,
786 <C2 as Group>::ScalarField: Absorb,
787 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
788 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
789 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
790{
791 // folds the given cyclefold circuit and its instances
792 #[allow(clippy::type_complexity)]
793 fn fold_cyclefold_circuit(
794 &self,
795 cf_W_i: Witness<C2>, // witness of the running instance
796 cf_U_i: CommittedInstance<C2>, // running instance
797 cf_u_i_x: Vec<C2::ScalarField>,
798 cf_circuit: CycleFoldCircuit<C1, GC1>,
799 ) -> Result<
800 (
801 Witness<C2>,
802 CommittedInstance<C2>, // u_i
803 Witness<C2>, // W_i1
804 CommittedInstance<C2>, // U_i1
805 C2, // cmT
806 C2::ScalarField, // r_Fq
807 ),
808 Error,
809 > {
810 fold_cyclefold_circuit::<C1, GC1, C2, GC2, FC, CS1, CS2>(
811 &self.poseidon_config,
812 self.cf_r1cs.clone(),
813 self.cf_cs_pp.clone(),
814 self.pp_hash,
815 cf_W_i,
816 cf_U_i,
817 cf_u_i_x,
818 cf_circuit,
819 )
820 }
821}
822
823/// helper method to get the r1cs from the ConstraintSynthesizer
824pub fn get_r1cs_from_cs<F: PrimeField>(
825 circuit: impl ConstraintSynthesizer<F>,
826) -> Result<R1CS<F>, Error> {
827 let cs = ConstraintSystem::<F>::new_ref();
828 circuit.generate_constraints(cs.clone())?;
829 cs.finalize();
830 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
831 let r1cs = extract_r1cs::<F>(&cs);
832 Ok(r1cs)
833}
834
835/// helper method to get the R1CS for both the AugmentedFCircuit and the CycleFold circuit
836#[allow(clippy::type_complexity)]
837pub fn get_r1cs<C1, GC1, C2, GC2, FC>(
838 poseidon_config: &PoseidonConfig<C1::ScalarField>,
839 F_circuit: FC,
840) -> Result<(R1CS<C1::ScalarField>, R1CS<C2::ScalarField>), Error>
841where
842 C1: CurveGroup,
843 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
844 C2: CurveGroup,
845 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
846 FC: FCircuit<C1::ScalarField>,
847 <C1 as CurveGroup>::BaseField: PrimeField,
848 <C2 as CurveGroup>::BaseField: PrimeField,
849 <C1 as Group>::ScalarField: Absorb,
850 <C2 as Group>::ScalarField: Absorb,
851 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
852 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
853 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
854{
855 let augmented_F_circuit =
856 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(poseidon_config, F_circuit);
857 let cf_circuit = CycleFoldCircuit::<C1, GC1>::empty();
858 let r1cs = get_r1cs_from_cs::<C1::ScalarField>(augmented_F_circuit)?;
859 let cf_r1cs = get_r1cs_from_cs::<C2::ScalarField>(cf_circuit)?;
860 Ok((r1cs, cf_r1cs))
861}
862
863/// helper method to get the pedersen params length for both the AugmentedFCircuit and the
864/// CycleFold circuit
865pub fn get_cs_params_len<C1, GC1, C2, GC2, FC>(
866 poseidon_config: &PoseidonConfig<C1::ScalarField>,
867 F_circuit: FC,
868) -> Result<(usize, usize), Error>
869where
870 C1: CurveGroup,
871 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
872 C2: CurveGroup,
873 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
874 FC: FCircuit<C1::ScalarField>,
875 <C1 as CurveGroup>::BaseField: PrimeField,
876 <C2 as CurveGroup>::BaseField: PrimeField,
877 <C1 as Group>::ScalarField: Absorb,
878 <C2 as Group>::ScalarField: Absorb,
879 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
880 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
881 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
882{
883 let (r1cs, cf_r1cs) = get_r1cs::<C1, GC1, C2, GC2, FC>(poseidon_config, F_circuit)?;
884 Ok((r1cs.A.n_rows, cf_r1cs.A.n_rows))
885}
886
887#[cfg(test)]
888pub mod tests {
889 use crate::commitment::kzg::KZG;
890 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
891 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
892
893 use super::*;
894 use crate::commitment::pedersen::Pedersen;
895 use crate::frontend::tests::CubicFCircuit;
896 use crate::transcript::poseidon::poseidon_canonical_config;
897
898 /// This test tests the Nova+CycleFold IVC, and by consequence it is also testing the
899 /// AugmentedFCircuit
900 #[test]
901 fn test_ivc() {
902 let poseidon_config = poseidon_canonical_config::<Fr>();
903
904 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
905
906 // run the test using Pedersen commitments on both sides of the curve cycle
907 test_ivc_opt::<Pedersen<Projective>, Pedersen<Projective2>>(
908 poseidon_config.clone(),
909 F_circuit,
910 );
911 // run the test using KZG for the commitments on the main curve, and Pedersen for the
912 // commitments on the secondary curve
913 test_ivc_opt::<KZG<Bn254>, Pedersen<Projective2>>(poseidon_config, F_circuit);
914 }
915
916 // test_ivc allowing to choose the CommitmentSchemes
917 fn test_ivc_opt<CS1: CommitmentScheme<Projective>, CS2: CommitmentScheme<Projective2>>(
918 poseidon_config: PoseidonConfig<Fr>,
919 F_circuit: CubicFCircuit<Fr>,
920 ) {
921 let mut rng = ark_std::test_rng();
922 type N<CS1, CS2> = Nova<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2>;
923
924 let prep_param = PreprocessorParam::<Projective, Projective2, CubicFCircuit<Fr>, CS1, CS2> {
925 poseidon_config,
926 F: F_circuit,
927 cs_pp: None,
928 cs_vp: None,
929 cf_cs_pp: None,
930 cf_cs_vp: None,
931 };
932 let nova_params = N::preprocess(&mut rng, &prep_param).unwrap();
933
934 let z_0 = vec![Fr::from(3_u32)];
935 let mut nova = N::init(nova_params.clone(), F_circuit, z_0.clone()).unwrap();
936
937 let num_steps: usize = 3;
938 for _ in 0..num_steps {
939 nova.prove_step(&mut rng, vec![]).unwrap();
940 }
941 assert_eq!(Fr::from(num_steps as u32), nova.i);
942
943 let (running_instance, incoming_instance, cyclefold_instance) = nova.instances();
944 N::<CS1, CS2>::verify(
945 nova_params.1, // Nova's verifier params
946 z_0,
947 nova.z_i,
948 nova.i,
949 running_instance,
950 incoming_instance,
951 cyclefold_instance,
952 )
953 .unwrap();
954 }
955}