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