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