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;
40
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 let mut i_bytes: [u8; 8] = [0; 8];
506 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..8]);
507 let i_usize: usize = usize::from_le_bytes(i_bytes);
508
509 let z_i1 = self
510 .F
511 .step_native(i_usize, self.z_i.clone(), external_inputs.clone())?;
512
513 // compute T and cmT for AugmentedFCircuit
514 let (T, cmT) = self.compute_cmT()?;
515
516 // r_bits is the r used to the RLC of the F' instances
517 let r_bits = ChallengeGadget::<C1>::get_challenge_native(
518 &mut transcript,
519 self.pp_hash,
520 self.U_i.clone(),
521 self.u_i.clone(),
522 cmT,
523 );
524 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
525 .ok_or(Error::OutOfBounds)?;
526 let r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&r_bits))
527 .ok_or(Error::OutOfBounds)?;
528
529 // fold Nova instances
530 let (W_i1, U_i1): (Witness<C1>, CommittedInstance<C1>) =
531 NIFS::<C1, CS1, H>::fold_instances(
532 r_Fr, &self.W_i, &self.U_i, &self.w_i, &self.u_i, &T, cmT,
533 )?;
534
535 // folded instance output (public input, x)
536 // u_{i+1}.x[0] = H(i+1, z_0, z_{i+1}, U_{i+1})
537 let u_i1_x = U_i1.hash(
538 &sponge,
539 self.pp_hash,
540 self.i + C1::ScalarField::one(),
541 self.z_0.clone(),
542 z_i1.clone(),
543 );
544 // u_{i+1}.x[1] = H(cf_U_{i+1})
545 let cf_u_i1_x: C1::ScalarField;
546
547 if self.i == C1::ScalarField::zero() {
548 cf_u_i1_x = self.cf_U_i.hash_cyclefold(&sponge, self.pp_hash);
549 // base case
550 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
551 _gc2: PhantomData,
552 poseidon_config: self.poseidon_config.clone(),
553 pp_hash: Some(self.pp_hash),
554 i: Some(C1::ScalarField::zero()), // = i=0
555 i_usize: Some(0),
556 z_0: Some(self.z_0.clone()), // = z_i
557 z_i: Some(self.z_i.clone()),
558 external_inputs: Some(external_inputs.clone()),
559 u_i_cmW: Some(self.u_i.cmW), // = dummy
560 U_i: Some(self.U_i.clone()), // = dummy
561 U_i1_cmE: Some(U_i1.cmE),
562 U_i1_cmW: Some(U_i1.cmW),
563 cmT: Some(cmT),
564 F: self.F.clone(),
565 x: Some(u_i1_x),
566 cf1_u_i_cmW: None,
567 cf2_u_i_cmW: None,
568 cf_U_i: None,
569 cf1_cmT: None,
570 cf2_cmT: None,
571 cf_x: Some(cf_u_i1_x),
572 };
573
574 #[cfg(test)]
575 NIFS::<C1, CS1, H>::verify_folded_instance(r_Fr, &self.U_i, &self.u_i, &U_i1, &cmT)?;
576 } else {
577 // CycleFold part:
578 // get the vector used as public inputs 'x' in the CycleFold circuit
579 // cyclefold circuit for cmW
580 let cfW_u_i_x = [
581 vec![r_Fq],
582 get_cm_coordinates(&self.U_i.cmW),
583 get_cm_coordinates(&self.u_i.cmW),
584 get_cm_coordinates(&U_i1.cmW),
585 ]
586 .concat();
587 // cyclefold circuit for cmE
588 let cfE_u_i_x = [
589 vec![r_Fq],
590 get_cm_coordinates(&self.U_i.cmE),
591 get_cm_coordinates(&cmT),
592 get_cm_coordinates(&U_i1.cmE),
593 ]
594 .concat();
595
596 let cfW_circuit = NovaCycleFoldCircuit::<C1, GC1> {
597 _gc: PhantomData,
598 r_bits: Some(vec![r_bits.clone()]),
599 points: Some(vec![self.U_i.clone().cmW, self.u_i.clone().cmW]),
600 x: Some(cfW_u_i_x.clone()),
601 };
602 let cfE_circuit = NovaCycleFoldCircuit::<C1, GC1> {
603 _gc: PhantomData,
604 r_bits: Some(vec![r_bits.clone()]),
605 points: Some(vec![self.U_i.clone().cmE, cmT]),
606 x: Some(cfE_u_i_x.clone()),
607 };
608
609 // fold self.cf_U_i + cfW_U -> folded running with cfW
610 let (_cfW_w_i, cfW_u_i, cfW_W_i1, cfW_U_i1, cfW_cmT, _) = self.fold_cyclefold_circuit(
611 &mut transcript,
612 self.cf_W_i.clone(), // CycleFold running instance witness
613 self.cf_U_i.clone(), // CycleFold running instance
614 cfW_u_i_x,
615 cfW_circuit,
616 &mut rng,
617 )?;
618 // fold [the output from folding self.cf_U_i + cfW_U] + cfE_U = folded_running_with_cfW + cfE
619 let (_cfE_w_i, cfE_u_i, cf_W_i1, cf_U_i1, cf_cmT, _) = self.fold_cyclefold_circuit(
620 &mut transcript,
621 cfW_W_i1,
622 cfW_U_i1.clone(),
623 cfE_u_i_x,
624 cfE_circuit,
625 &mut rng,
626 )?;
627
628 cf_u_i1_x = cf_U_i1.hash_cyclefold(&sponge, self.pp_hash);
629
630 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
631 _gc2: PhantomData,
632 poseidon_config: self.poseidon_config.clone(),
633 pp_hash: Some(self.pp_hash),
634 i: Some(self.i),
635 i_usize: Some(i_usize),
636 z_0: Some(self.z_0.clone()),
637 z_i: Some(self.z_i.clone()),
638 external_inputs: Some(external_inputs.clone()),
639 u_i_cmW: Some(self.u_i.cmW),
640 U_i: Some(self.U_i.clone()),
641 U_i1_cmE: Some(U_i1.cmE),
642 U_i1_cmW: Some(U_i1.cmW),
643 cmT: Some(cmT),
644 F: self.F.clone(),
645 x: Some(u_i1_x),
646 // cyclefold values
647 cf1_u_i_cmW: Some(cfW_u_i.cmW),
648 cf2_u_i_cmW: Some(cfE_u_i.cmW),
649 cf_U_i: Some(self.cf_U_i.clone()),
650 cf1_cmT: Some(cfW_cmT),
651 cf2_cmT: Some(cf_cmT),
652 cf_x: Some(cf_u_i1_x),
653 };
654
655 self.cf_W_i = cf_W_i1;
656 self.cf_U_i = cf_U_i1;
657
658 #[cfg(test)]
659 {
660 self.cf_r1cs.check_instance_relation(&_cfW_w_i, &cfW_u_i)?;
661 self.cf_r1cs.check_instance_relation(&_cfE_w_i, &cfE_u_i)?;
662 self.cf_r1cs
663 .check_relaxed_instance_relation(&self.cf_W_i, &self.cf_U_i)?;
664 }
665 }
666
667 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
668
669 augmented_F_circuit.generate_constraints(cs.clone())?;
670
671 #[cfg(test)]
672 assert!(cs.is_satisfied().unwrap());
673
674 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
675 let (w_i1, x_i1) = extract_w_x::<C1::ScalarField>(&cs);
676 if x_i1[0] != u_i1_x || x_i1[1] != cf_u_i1_x {
677 return Err(Error::NotEqual);
678 }
679
680 #[cfg(test)]
681 if x_i1.len() != 2 {
682 return Err(Error::NotExpectedLength(x_i1.len(), 2));
683 }
684
685 // set values for next iteration
686 self.i += C1::ScalarField::one();
687 self.z_i = z_i1;
688 self.w_i = Witness::<C1>::new::<H>(w_i1, self.r1cs.A.n_rows, &mut rng);
689 self.u_i = self.w_i.commit::<CS1, H>(&self.cs_pp, x_i1)?;
690 self.W_i = W_i1;
691 self.U_i = U_i1;
692
693 #[cfg(test)]
694 {
695 self.r1cs.check_instance_relation(&self.w_i, &self.u_i)?;
696 self.r1cs
697 .check_relaxed_instance_relation(&self.W_i, &self.U_i)?;
698 }
699
700 Ok(())
701 }
702
703 fn state(&self) -> Vec<C1::ScalarField> {
704 self.z_i.clone()
705 }
706
707 fn instances(
708 &self,
709 ) -> (
710 Self::RunningInstance,
711 Self::IncomingInstance,
712 Self::CFInstance,
713 ) {
714 (
715 (self.U_i.clone(), self.W_i.clone()),
716 (self.u_i.clone(), self.w_i.clone()),
717 (self.cf_U_i.clone(), self.cf_W_i.clone()),
718 )
719 }
720
721 /// Implements IVC.V of Nova+CycleFold. Notice that this method does not include the
722 /// commitments verification, which is done in the Decider.
723 fn verify(
724 vp: Self::VerifierParam,
725 z_0: Vec<C1::ScalarField>, // initial state
726 z_i: Vec<C1::ScalarField>, // last state
727 num_steps: C1::ScalarField,
728 running_instance: Self::RunningInstance,
729 incoming_instance: Self::IncomingInstance,
730 cyclefold_instance: Self::CFInstance,
731 ) -> Result<(), Error> {
732 let sponge = PoseidonSponge::<C1::ScalarField>::new(&vp.poseidon_config);
733
734 if num_steps == C1::ScalarField::zero() {
735 if z_0 != z_i {
736 return Err(Error::IVCVerificationFail);
737 }
738 return Ok(());
739 }
740
741 let (U_i, W_i) = running_instance;
742 let (u_i, w_i) = incoming_instance;
743 let (cf_U_i, cf_W_i) = cyclefold_instance;
744
745 if u_i.x.len() != 2 || U_i.x.len() != 2 {
746 return Err(Error::IVCVerificationFail);
747 }
748
749 let pp_hash = vp.pp_hash()?;
750
751 // check that u_i's output points to the running instance
752 // u_i.X[0] == H(i, z_0, z_i, U_i)
753 let expected_u_i_x = U_i.hash(&sponge, pp_hash, num_steps, z_0, z_i.clone());
754 if expected_u_i_x != u_i.x[0] {
755 return Err(Error::IVCVerificationFail);
756 }
757 // u_i.X[1] == H(cf_U_i)
758 let expected_cf_u_i_x = cf_U_i.hash_cyclefold(&sponge, pp_hash);
759 if expected_cf_u_i_x != u_i.x[1] {
760 return Err(Error::IVCVerificationFail);
761 }
762
763 // check u_i.cmE==0, u_i.u==1 (=u_i is a un-relaxed instance)
764 if !u_i.cmE.is_zero() || !u_i.u.is_one() {
765 return Err(Error::IVCVerificationFail);
766 }
767
768 // check R1CS satisfiability
769 vp.r1cs.check_instance_relation(&w_i, &u_i)?;
770 // check RelaxedR1CS satisfiability
771 vp.r1cs.check_relaxed_instance_relation(&W_i, &U_i)?;
772
773 // check CycleFold RelaxedR1CS satisfiability
774 vp.cf_r1cs
775 .check_relaxed_instance_relation(&cf_W_i, &cf_U_i)?;
776
777 Ok(())
778 }
779}
780
781impl<C1, GC1, C2, GC2, FC, CS1, CS2, const H: bool> Nova<C1, GC1, C2, GC2, FC, CS1, CS2, H>
782where
783 C1: CurveGroup,
784 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
785 C2: CurveGroup,
786 GC2: CurveVar<C2, CF2<C2>>,
787 FC: FCircuit<C1::ScalarField>,
788 CS1: CommitmentScheme<C1, H>,
789 CS2: CommitmentScheme<C2, H>,
790 <C2 as CurveGroup>::BaseField: PrimeField,
791 <C1 as Group>::ScalarField: Absorb,
792 <C2 as Group>::ScalarField: Absorb,
793 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
794{
795 // computes T and cmT for the AugmentedFCircuit
796 fn compute_cmT(&self) -> Result<(Vec<C1::ScalarField>, C1), Error> {
797 NIFS::<C1, CS1, H>::compute_cmT(
798 &self.cs_pp,
799 &self.r1cs,
800 &self.w_i,
801 &self.u_i,
802 &self.W_i,
803 &self.U_i,
804 )
805 }
806}
807
808impl<C1, GC1, C2, GC2, FC, CS1, CS2, const H: bool> Nova<C1, GC1, C2, GC2, FC, CS1, CS2, H>
809where
810 C1: CurveGroup,
811 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
812 C2: CurveGroup,
813 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
814 FC: FCircuit<C1::ScalarField>,
815 CS1: CommitmentScheme<C1, H>,
816 CS2: CommitmentScheme<C2, H>,
817 <C1 as CurveGroup>::BaseField: PrimeField,
818 <C2 as CurveGroup>::BaseField: PrimeField,
819 <C1 as Group>::ScalarField: Absorb,
820 <C2 as Group>::ScalarField: Absorb,
821 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
822 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
823 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
824{
825 // folds the given cyclefold circuit and its instances
826 #[allow(clippy::type_complexity)]
827 fn fold_cyclefold_circuit<T: Transcript<C1::ScalarField>>(
828 &self,
829 transcript: &mut T,
830 cf_W_i: CycleFoldWitness<C2>, // witness of the running instance
831 cf_U_i: CycleFoldCommittedInstance<C2>, // running instance
832 cf_u_i_x: Vec<C2::ScalarField>,
833 cf_circuit: NovaCycleFoldCircuit<C1, GC1>,
834 rng: &mut impl RngCore,
835 ) -> Result<
836 (
837 CycleFoldWitness<C2>,
838 CycleFoldCommittedInstance<C2>, // u_i
839 CycleFoldWitness<C2>, // W_i1
840 CycleFoldCommittedInstance<C2>, // U_i1
841 C2, // cmT
842 C2::ScalarField, // r_Fq
843 ),
844 Error,
845 > {
846 fold_cyclefold_circuit::<NovaCycleFoldConfig<C1>, C1, GC1, C2, GC2, CS2, H>(
847 transcript,
848 self.cf_r1cs.clone(),
849 self.cf_cs_pp.clone(),
850 self.pp_hash,
851 cf_W_i,
852 cf_U_i,
853 cf_u_i_x,
854 cf_circuit,
855 rng,
856 )
857 }
858}
859
860/// helper method to get the r1cs from the ConstraintSynthesizer
861pub fn get_r1cs_from_cs<F: PrimeField>(
862 circuit: impl ConstraintSynthesizer<F>,
863) -> Result<R1CS<F>, Error> {
864 let cs = ConstraintSystem::<F>::new_ref();
865 circuit.generate_constraints(cs.clone())?;
866 cs.finalize();
867 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
868 let r1cs = extract_r1cs::<F>(&cs);
869 Ok(r1cs)
870}
871
872/// helper method to get the R1CS for both the AugmentedFCircuit and the CycleFold circuit
873#[allow(clippy::type_complexity)]
874pub fn get_r1cs<C1, GC1, C2, GC2, FC>(
875 poseidon_config: &PoseidonConfig<C1::ScalarField>,
876 F_circuit: FC,
877) -> Result<(R1CS<C1::ScalarField>, R1CS<C2::ScalarField>), Error>
878where
879 C1: CurveGroup,
880 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
881 C2: CurveGroup,
882 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
883 FC: FCircuit<C1::ScalarField>,
884 <C1 as CurveGroup>::BaseField: PrimeField,
885 <C2 as CurveGroup>::BaseField: PrimeField,
886 <C1 as Group>::ScalarField: Absorb,
887 <C2 as Group>::ScalarField: Absorb,
888 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
889 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
890 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
891{
892 let augmented_F_circuit =
893 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(poseidon_config, F_circuit);
894 let cf_circuit = NovaCycleFoldCircuit::<C1, GC1>::empty();
895 let r1cs = get_r1cs_from_cs::<C1::ScalarField>(augmented_F_circuit)?;
896 let cf_r1cs = get_r1cs_from_cs::<C2::ScalarField>(cf_circuit)?;
897 Ok((r1cs, cf_r1cs))
898}
899
900/// helper method to get the pedersen params length for both the AugmentedFCircuit and the
901/// CycleFold circuit
902pub fn get_cs_params_len<C1, GC1, C2, GC2, FC>(
903 poseidon_config: &PoseidonConfig<C1::ScalarField>,
904 F_circuit: FC,
905) -> Result<(usize, usize), Error>
906where
907 C1: CurveGroup,
908 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
909 C2: CurveGroup,
910 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
911 FC: FCircuit<C1::ScalarField>,
912 <C1 as CurveGroup>::BaseField: PrimeField,
913 <C2 as CurveGroup>::BaseField: PrimeField,
914 <C1 as Group>::ScalarField: Absorb,
915 <C2 as Group>::ScalarField: Absorb,
916 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
917 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
918 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
919{
920 let (r1cs, cf_r1cs) = get_r1cs::<C1, GC1, C2, GC2, FC>(poseidon_config, F_circuit)?;
921 Ok((r1cs.A.n_rows, cf_r1cs.A.n_rows))
922}
923
924#[cfg(test)]
925pub mod tests {
926 use crate::commitment::kzg::KZG;
927 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
928 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
929
930 use super::*;
931 use crate::commitment::pedersen::Pedersen;
932 use crate::frontend::tests::CubicFCircuit;
933 use crate::transcript::poseidon::poseidon_canonical_config;
934
935 /// This test tests the Nova+CycleFold IVC, and by consequence it is also testing the
936 /// AugmentedFCircuit
937 #[test]
938 fn test_ivc() {
939 let poseidon_config = poseidon_canonical_config::<Fr>();
940
941 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
942
943 // run the test using Pedersen commitments on both sides of the curve cycle
944 test_ivc_opt::<Pedersen<Projective>, Pedersen<Projective2>, false>(
945 poseidon_config.clone(),
946 F_circuit,
947 );
948 test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
949 poseidon_config.clone(),
950 F_circuit,
951 );
952
953 // run the test using KZG for the commitments on the main curve, and Pedersen for the
954 // commitments on the secondary curve
955 test_ivc_opt::<KZG<Bn254>, Pedersen<Projective2>, false>(poseidon_config, F_circuit);
956 }
957
958 // test_ivc allowing to choose the CommitmentSchemes
959 fn test_ivc_opt<
960 CS1: CommitmentScheme<Projective, H>,
961 CS2: CommitmentScheme<Projective2, H>,
962 const H: bool,
963 >(
964 poseidon_config: PoseidonConfig<Fr>,
965 F_circuit: CubicFCircuit<Fr>,
966 ) {
967 let mut rng = ark_std::test_rng();
968
969 let prep_param =
970 PreprocessorParam::<Projective, Projective2, CubicFCircuit<Fr>, CS1, CS2, H> {
971 poseidon_config,
972 F: F_circuit,
973 cs_pp: None,
974 cs_vp: None,
975 cf_cs_pp: None,
976 cf_cs_vp: None,
977 };
978 let nova_params = Nova::<
979 Projective,
980 GVar,
981 Projective2,
982 GVar2,
983 CubicFCircuit<Fr>,
984 CS1,
985 CS2,
986 H,
987 >::preprocess(&mut rng, &prep_param)
988 .unwrap();
989
990 let z_0 = vec![Fr::from(3_u32)];
991 let mut nova =
992 Nova::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2, H>::init(
993 &nova_params,
994 F_circuit,
995 z_0.clone(),
996 )
997 .unwrap();
998
999 let num_steps: usize = 3;
1000 for _ in 0..num_steps {
1001 nova.prove_step(&mut rng, vec![], None).unwrap();
1002 }
1003 assert_eq!(Fr::from(num_steps as u32), nova.i);
1004
1005 let (running_instance, incoming_instance, cyclefold_instance) = nova.instances();
1006 Nova::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2, H>::verify(
1007 nova_params.1, // Nova's verifier params
1008 z_0,
1009 nova.z_i,
1010 nova.i,
1011 running_instance,
1012 incoming_instance,
1013 cyclefold_instance,
1014 )
1015 .unwrap();
1016 }
1017}