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