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