sonobe/folding-schemes/src/folding/hypernova/mod.rs
folding-schemes/src/folding/hypernova/mod.rsRaw
1/// Implements the scheme described in [HyperNova](https://eprint.iacr.org/2023/573.pdf)
2use ark_crypto_primitives::sponge::{
3 poseidon::{PoseidonConfig, PoseidonSponge},
4 Absorb, CryptographicSponge,
5};
6use ark_ec::{CurveGroup, Group};
7use ark_ff::{BigInteger, PrimeField};
8use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
9use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
10use ark_std::{fmt::Debug, marker::PhantomData, rand::RngCore, One, Zero};
11
12pub mod cccs;
13pub mod circuits;
14pub mod decider_eth;
15pub mod decider_eth_circuit;
16pub mod lcccs;
17pub mod nimfs;
18pub mod serialize;
19pub mod utils;
20
21use cccs::CCCS;
22use circuits::AugmentedFCircuit;
23use decider_eth_circuit::WitnessVar;
24use lcccs::LCCCS;
25use nimfs::NIMFS;
26
27use crate::commitment::CommitmentScheme;
28use crate::constants::NOVA_N_BITS_RO;
29use crate::folding::{
30 circuits::{
31 cyclefold::{
32 fold_cyclefold_circuit, CycleFoldCircuit, CycleFoldCommittedInstance, CycleFoldConfig,
33 CycleFoldWitness,
34 },
35 CF2,
36 },
37 nova::{get_r1cs_from_cs, PreprocessorParam},
38 traits::{CommittedInstanceOps, Dummy, WitnessOps},
39};
40use crate::frontend::FCircuit;
41use crate::utils::{get_cm_coordinates, pp_hash};
42use crate::Error;
43use crate::{
44 arith::{
45 ccs::CCS,
46 r1cs::{extract_w_x, R1CS},
47 Arith,
48 },
49 FoldingScheme, MultiFolding,
50};
51
52/// Configuration for HyperNova's CycleFold circuit
53pub struct HyperNovaCycleFoldConfig<C: CurveGroup, const MU: usize, const NU: usize> {
54 _c: PhantomData<C>,
55}
56
57impl<C: CurveGroup, const MU: usize, const NU: usize> CycleFoldConfig
58 for HyperNovaCycleFoldConfig<C, MU, NU>
59{
60 const RANDOMNESS_BIT_LENGTH: usize = NOVA_N_BITS_RO;
61 const N_INPUT_POINTS: usize = MU + NU;
62 type C = C;
63 type F = C::BaseField;
64}
65
66/// CycleFold circuit for computing random linear combinations of group elements
67/// in HyperNova instances.
68pub type HyperNovaCycleFoldCircuit<C, GC, const MU: usize, const NU: usize> =
69 CycleFoldCircuit<HyperNovaCycleFoldConfig<C, MU, NU>, GC>;
70
71/// Witness for the LCCCS & CCCS, containing the w vector, and the r_w used as randomness in the Pedersen commitment.
72#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
73pub struct Witness<F: PrimeField> {
74 pub w: Vec<F>,
75 pub r_w: F,
76}
77
78impl<F: PrimeField> Witness<F> {
79 pub fn new(w: Vec<F>) -> Self {
80 // note: at the current version, we don't use the blinding factors and we set them to 0
81 // always.
82 Self { w, r_w: F::zero() }
83 }
84}
85
86impl<F: PrimeField> Dummy<&CCS<F>> for Witness<F> {
87 fn dummy(ccs: &CCS<F>) -> Self {
88 Self::new(vec![F::zero(); ccs.n - ccs.l - 1])
89 }
90}
91
92impl<F: PrimeField> WitnessOps<F> for Witness<F> {
93 type Var = WitnessVar<F>;
94
95 fn get_openings(&self) -> Vec<(&[F], F)> {
96 vec![(&self.w, self.r_w)]
97 }
98}
99
100/// Proving parameters for HyperNova-based IVC
101#[derive(Debug, Clone)]
102pub struct ProverParams<C1, C2, CS1, CS2, const H: bool>
103where
104 C1: CurveGroup,
105 C2: CurveGroup,
106 CS1: CommitmentScheme<C1, H>,
107 CS2: CommitmentScheme<C2, H>,
108{
109 /// Poseidon sponge configuration
110 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
111 /// Proving parameters of the underlying commitment scheme over C1
112 pub cs_pp: CS1::ProverParams,
113 /// Proving parameters of the underlying commitment scheme over C2
114 pub cf_cs_pp: CS2::ProverParams,
115 /// CCS of the Augmented Function circuit
116 /// If ccs is set, it will be used, if not, it will be computed at runtime
117 pub ccs: Option<CCS<C1::ScalarField>>,
118}
119
120/// Verification parameters for HyperNova-based IVC
121#[derive(Debug, Clone)]
122pub struct VerifierParams<
123 C1: CurveGroup,
124 C2: CurveGroup,
125 CS1: CommitmentScheme<C1, H>,
126 CS2: CommitmentScheme<C2, H>,
127 const H: bool,
128> {
129 /// Poseidon sponge configuration
130 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
131 /// CCS of the Augmented step circuit
132 pub ccs: CCS<C1::ScalarField>,
133 /// R1CS of the CycleFold circuit
134 pub cf_r1cs: R1CS<C2::ScalarField>,
135 /// Verification parameters of the underlying commitment scheme over C1
136 pub cs_vp: CS1::VerifierParams,
137 /// Verification parameters of the underlying commitment scheme over C2
138 pub cf_cs_vp: CS2::VerifierParams,
139}
140
141impl<C1, C2, CS1, CS2, const H: bool> VerifierParams<C1, C2, CS1, CS2, H>
142where
143 C1: CurveGroup,
144 C2: CurveGroup,
145 CS1: CommitmentScheme<C1, H>,
146 CS2: CommitmentScheme<C2, H>,
147{
148 /// returns the hash of the public parameters of HyperNova
149 pub fn pp_hash(&self) -> Result<C1::ScalarField, Error> {
150 pp_hash::<C1, C2, CS1, CS2, H>(
151 &self.ccs,
152 &self.cf_r1cs,
153 &self.cs_vp,
154 &self.cf_cs_vp,
155 &self.poseidon_config,
156 )
157 }
158}
159
160/// Implements HyperNova+CycleFold's IVC, described in
161/// [HyperNova](https://eprint.iacr.org/2023/573.pdf) and
162/// [CycleFold](https://eprint.iacr.org/2023/1192.pdf), following the FoldingScheme trait
163///
164/// For multi-instance folding, one needs to specify the const generics below:
165/// * `MU` - the number of LCCCS instances to be folded
166/// * `NU` - the number of CCCS instances to be folded
167#[derive(Clone, Debug)]
168pub struct HyperNova<
169 C1,
170 GC1,
171 C2,
172 GC2,
173 FC,
174 CS1,
175 CS2,
176 const MU: usize,
177 const NU: usize,
178 const H: bool,
179> where
180 C1: CurveGroup,
181 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
182 C2: CurveGroup,
183 GC2: CurveVar<C2, CF2<C2>>,
184 FC: FCircuit<C1::ScalarField>,
185 CS1: CommitmentScheme<C1, H>,
186 CS2: CommitmentScheme<C2, H>,
187{
188 _gc1: PhantomData<GC1>,
189 _c2: PhantomData<C2>,
190 _gc2: PhantomData<GC2>,
191
192 /// CCS of the Augmented Function circuit
193 pub ccs: CCS<C1::ScalarField>,
194 /// R1CS of the CycleFold circuit
195 pub cf_r1cs: R1CS<C2::ScalarField>,
196 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
197 /// CommitmentScheme::ProverParams over C1
198 pub cs_pp: CS1::ProverParams,
199 /// CycleFold CommitmentScheme::ProverParams, over C2
200 pub cf_cs_pp: CS2::ProverParams,
201 /// F circuit, the circuit that is being folded
202 pub F: FC,
203 /// public params hash
204 pub pp_hash: C1::ScalarField,
205 pub i: C1::ScalarField,
206 /// initial state
207 pub z_0: Vec<C1::ScalarField>,
208 /// current i-th state
209 pub z_i: Vec<C1::ScalarField>,
210 /// HyperNova instances
211 pub W_i: Witness<C1::ScalarField>,
212 pub U_i: LCCCS<C1>,
213 pub w_i: Witness<C1::ScalarField>,
214 pub u_i: CCCS<C1>,
215
216 /// CycleFold running instance
217 pub cf_W_i: CycleFoldWitness<C2>,
218 pub cf_U_i: CycleFoldCommittedInstance<C2>,
219}
220
221impl<C1, GC1, C2, GC2, FC, CS1, CS2, const MU: usize, const NU: usize, const H: bool>
222 MultiFolding<C1, C2, FC> for HyperNova<C1, GC1, C2, GC2, FC, CS1, CS2, MU, NU, H>
223where
224 C1: CurveGroup,
225 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
226 C2: CurveGroup,
227 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
228 FC: FCircuit<C1::ScalarField>,
229 CS1: CommitmentScheme<C1, H>,
230 CS2: CommitmentScheme<C2, H>,
231 <C1 as CurveGroup>::BaseField: PrimeField,
232 <C2 as CurveGroup>::BaseField: PrimeField,
233 <C1 as Group>::ScalarField: Absorb,
234 <C2 as Group>::ScalarField: Absorb,
235 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
236 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
237 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
238{
239 type RunningInstance = (LCCCS<C1>, Witness<C1::ScalarField>);
240 type IncomingInstance = (CCCS<C1>, Witness<C1::ScalarField>);
241 type MultiInstance = (Vec<Self::RunningInstance>, Vec<Self::IncomingInstance>);
242
243 /// Creates a new LCCS instance for the given state, which satisfies the HyperNova.CCS. This
244 /// method can be used to generate the 'other' LCCS instances to be folded in the multi-folding
245 /// step.
246 fn new_running_instance(
247 &self,
248 mut rng: impl RngCore,
249 state: Vec<C1::ScalarField>,
250 external_inputs: Vec<C1::ScalarField>,
251 ) -> Result<Self::RunningInstance, Error> {
252 let r1cs_z = self.new_instance_generic(state, external_inputs)?;
253 // compute committed instances, w_{i+1}, u_{i+1}, which will be used as w_i, u_i, so we
254 // assign them directly to w_i, u_i.
255 let (U_i, W_i) = self
256 .ccs
257 .to_lcccs::<_, _, CS1, H>(&mut rng, &self.cs_pp, &r1cs_z)?;
258
259 #[cfg(test)]
260 self.ccs.check_relation(&W_i, &U_i)?;
261
262 Ok((U_i, W_i))
263 }
264
265 /// Creates a new CCCS instance for the given state, which satisfies the HyperNova.CCS. This
266 /// method can be used to generate the 'other' CCCS instances to be folded in the multi-folding
267 /// step.
268 fn new_incoming_instance(
269 &self,
270 mut rng: impl RngCore,
271 state: Vec<C1::ScalarField>,
272 external_inputs: Vec<C1::ScalarField>,
273 ) -> Result<Self::IncomingInstance, Error> {
274 let r1cs_z = self.new_instance_generic(state, external_inputs)?;
275 // compute committed instances, w_{i+1}, u_{i+1}, which will be used as w_i, u_i, so we
276 // assign them directly to w_i, u_i.
277 let (u_i, w_i) = self
278 .ccs
279 .to_cccs::<_, _, CS1, H>(&mut rng, &self.cs_pp, &r1cs_z)?;
280
281 #[cfg(test)]
282 self.ccs.check_relation(&w_i, &u_i)?;
283
284 Ok((u_i, w_i))
285 }
286}
287
288impl<C1, GC1, C2, GC2, FC, CS1, CS2, const MU: usize, const NU: usize, const H: bool>
289 HyperNova<C1, GC1, C2, GC2, FC, CS1, CS2, MU, NU, H>
290where
291 C1: CurveGroup,
292 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
293 C2: CurveGroup,
294 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
295 FC: FCircuit<C1::ScalarField>,
296 CS1: CommitmentScheme<C1, H>,
297 CS2: CommitmentScheme<C2, H>,
298 <C1 as CurveGroup>::BaseField: PrimeField,
299 <C2 as CurveGroup>::BaseField: PrimeField,
300 <C1 as Group>::ScalarField: Absorb,
301 <C2 as Group>::ScalarField: Absorb,
302 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
303 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
304 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
305{
306 /// internal helper for new_running_instance & new_incoming_instance methods, returns the R1CS
307 /// z=[u,x,w] vector to be used to create the LCCCS & CCCS fresh instances.
308 fn new_instance_generic(
309 &self,
310 state: Vec<C1::ScalarField>,
311 external_inputs: Vec<C1::ScalarField>,
312 ) -> Result<Vec<C1::ScalarField>, Error> {
313 // prepare the initial dummy instances
314 let U_i = LCCCS::<C1>::dummy(&self.ccs);
315 let mut u_i = CCCS::<C1>::dummy(&self.ccs);
316 let (_, cf_U_i): (CycleFoldWitness<C2>, CycleFoldCommittedInstance<C2>) =
317 self.cf_r1cs.dummy_witness_instance();
318
319 let sponge = PoseidonSponge::<C1::ScalarField>::new(&self.poseidon_config);
320
321 u_i.x = vec![
322 U_i.hash(
323 &sponge,
324 self.pp_hash,
325 C1::ScalarField::zero(), // i
326 &self.z_0,
327 &state,
328 ),
329 cf_U_i.hash_cyclefold(&sponge, self.pp_hash),
330 ];
331 let us = vec![u_i.clone(); NU - 1];
332
333 let z_i1 = self
334 .F
335 .step_native(0, state.clone(), external_inputs.clone())?;
336
337 // compute u_{i+1}.x
338 let U_i1 = LCCCS::dummy(&self.ccs);
339 let u_i1_x = U_i1.hash(
340 &sponge,
341 self.pp_hash,
342 C1::ScalarField::one(), // i+1, where i=0
343 &self.z_0,
344 &z_i1,
345 );
346
347 let cf_u_i1_x = cf_U_i.hash_cyclefold(&sponge, self.pp_hash);
348 let augmented_f_circuit = AugmentedFCircuit::<C1, C2, GC2, FC, MU, NU> {
349 _c2: PhantomData,
350 _gc2: PhantomData,
351 poseidon_config: self.poseidon_config.clone(),
352 ccs: self.ccs.clone(),
353 pp_hash: Some(self.pp_hash),
354 i: Some(C1::ScalarField::zero()),
355 i_usize: Some(0),
356 z_0: Some(self.z_0.clone()),
357 z_i: Some(state.clone()),
358 external_inputs: Some(external_inputs),
359 U_i: Some(U_i.clone()),
360 Us: None,
361 u_i_C: Some(u_i.C),
362 us: Some(us),
363 U_i1_C: Some(U_i1.C),
364 F: self.F.clone(),
365 x: Some(u_i1_x),
366 nimfs_proof: None,
367
368 // cyclefold values
369 cf_u_i_cmW: None,
370 cf_U_i: None,
371 cf_x: Some(cf_u_i1_x),
372 cf_cmT: None,
373 };
374
375 let (cs, _) = augmented_f_circuit.compute_cs_ccs()?;
376
377 #[cfg(test)]
378 assert!(cs.is_satisfied()?);
379
380 let (r1cs_w_i1, r1cs_x_i1) = extract_w_x::<C1::ScalarField>(&cs); // includes 1 and public inputs
381
382 #[cfg(test)]
383 assert_eq!(r1cs_x_i1[0], augmented_f_circuit.x.unwrap());
384
385 let r1cs_z = [
386 vec![C1::ScalarField::one()],
387 r1cs_x_i1.clone(),
388 r1cs_w_i1.clone(),
389 ]
390 .concat();
391 Ok(r1cs_z)
392 }
393}
394
395impl<C1, GC1, C2, GC2, FC, CS1, CS2, const MU: usize, const NU: usize, const H: bool>
396 FoldingScheme<C1, C2, FC> for HyperNova<C1, GC1, C2, GC2, FC, CS1, CS2, MU, NU, H>
397where
398 C1: CurveGroup,
399 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
400 C2: CurveGroup,
401 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
402 FC: FCircuit<C1::ScalarField>,
403 CS1: CommitmentScheme<C1, H>,
404 CS2: CommitmentScheme<C2, H>,
405 <C1 as CurveGroup>::BaseField: PrimeField,
406 <C2 as CurveGroup>::BaseField: PrimeField,
407 <C1 as Group>::ScalarField: Absorb,
408 <C2 as Group>::ScalarField: Absorb,
409 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
410 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
411 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
412{
413 /// Reuse Nova's PreprocessorParam.
414 type PreprocessorParam = PreprocessorParam<C1, C2, FC, CS1, CS2, H>;
415 type ProverParam = ProverParams<C1, C2, CS1, CS2, H>;
416 type VerifierParam = VerifierParams<C1, C2, CS1, CS2, H>;
417 type RunningInstance = (LCCCS<C1>, Witness<C1::ScalarField>);
418 type IncomingInstance = (CCCS<C1>, Witness<C1::ScalarField>);
419 type MultiCommittedInstanceWithWitness =
420 (Vec<Self::RunningInstance>, Vec<Self::IncomingInstance>);
421 type CFInstance = (CycleFoldCommittedInstance<C2>, CycleFoldWitness<C2>);
422
423 fn preprocess(
424 mut rng: impl RngCore,
425 prep_param: &Self::PreprocessorParam,
426 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
427 if MU < 1 || NU < 1 {
428 return Err(Error::CantBeZero("mu,nu".to_string()));
429 }
430
431 let augmented_f_circuit = AugmentedFCircuit::<C1, C2, GC2, FC, MU, NU>::empty(
432 &prep_param.poseidon_config,
433 prep_param.F.clone(),
434 None,
435 )?;
436 let ccs = augmented_f_circuit.ccs.clone();
437
438 let cf_circuit = HyperNovaCycleFoldCircuit::<C1, GC1, MU, NU>::empty();
439 let cf_r1cs = get_r1cs_from_cs::<C2::ScalarField>(cf_circuit)?;
440
441 // if cs params exist, use them, if not, generate new ones
442 let cs_pp: CS1::ProverParams;
443 let cs_vp: CS1::VerifierParams;
444 let cf_cs_pp: CS2::ProverParams;
445 let cf_cs_vp: CS2::VerifierParams;
446 if prep_param.cs_pp.is_some()
447 && prep_param.cf_cs_pp.is_some()
448 && prep_param.cs_vp.is_some()
449 && prep_param.cf_cs_vp.is_some()
450 {
451 cs_pp = prep_param.clone().cs_pp.unwrap();
452 cs_vp = prep_param.clone().cs_vp.unwrap();
453 cf_cs_pp = prep_param.clone().cf_cs_pp.unwrap();
454 cf_cs_vp = prep_param.clone().cf_cs_vp.unwrap();
455 } else {
456 (cs_pp, cs_vp) = CS1::setup(&mut rng, ccs.n - ccs.l - 1)?;
457 (cf_cs_pp, cf_cs_vp) = CS2::setup(&mut rng, cf_r1cs.A.n_cols - cf_r1cs.l - 1)?;
458 }
459
460 let pp = ProverParams::<C1, C2, CS1, CS2, H> {
461 poseidon_config: prep_param.poseidon_config.clone(),
462 cs_pp,
463 cf_cs_pp,
464 ccs: Some(ccs.clone()),
465 };
466 let vp = VerifierParams::<C1, C2, CS1, CS2, H> {
467 poseidon_config: prep_param.poseidon_config.clone(),
468 ccs,
469 cf_r1cs,
470 cs_vp: cs_vp.clone(),
471 cf_cs_vp: cf_cs_vp.clone(),
472 };
473 Ok((pp, vp))
474 }
475
476 /// Initializes the HyperNova+CycleFold's IVC for the given parameters and initial state `z_0`.
477 fn init(
478 params: &(Self::ProverParam, Self::VerifierParam),
479 F: FC,
480 z_0: Vec<C1::ScalarField>,
481 ) -> Result<Self, Error> {
482 let (pp, vp) = params;
483 if MU < 1 || NU < 1 {
484 return Err(Error::CantBeZero("mu,nu".to_string()));
485 }
486
487 // `sponge` is for digest computation.
488 let sponge = PoseidonSponge::<C1::ScalarField>::new(&pp.poseidon_config);
489
490 // prepare the HyperNova's AugmentedFCircuit and CycleFold's circuits and obtain its CCS
491 // and R1CS respectively
492 let augmented_f_circuit = AugmentedFCircuit::<C1, C2, GC2, FC, MU, NU>::empty(
493 &pp.poseidon_config,
494 F.clone(),
495 pp.ccs.clone(),
496 )?;
497 let ccs = augmented_f_circuit.ccs.clone();
498
499 let cf_circuit = HyperNovaCycleFoldCircuit::<C1, GC1, MU, NU>::empty();
500 let cf_r1cs = get_r1cs_from_cs::<C2::ScalarField>(cf_circuit)?;
501
502 // compute the public params hash
503 let pp_hash = vp.pp_hash()?;
504
505 // setup the dummy instances
506 let W_dummy = Witness::<C1::ScalarField>::dummy(&ccs);
507 let U_dummy = LCCCS::<C1>::dummy(&ccs);
508 let w_dummy = W_dummy.clone();
509 let mut u_dummy = CCCS::<C1>::dummy(&ccs);
510 let (cf_W_dummy, cf_U_dummy): (CycleFoldWitness<C2>, CycleFoldCommittedInstance<C2>) =
511 cf_r1cs.dummy_witness_instance();
512 u_dummy.x = vec![
513 U_dummy.hash(&sponge, pp_hash, C1::ScalarField::zero(), &z_0, &z_0),
514 cf_U_dummy.hash_cyclefold(&sponge, pp_hash),
515 ];
516
517 // W_dummy=W_0 is a 'dummy witness', all zeroes, but with the size corresponding to the
518 // R1CS that we're working with.
519 Ok(Self {
520 _gc1: PhantomData,
521 _c2: PhantomData,
522 _gc2: PhantomData,
523 ccs,
524 cf_r1cs,
525 poseidon_config: pp.poseidon_config.clone(),
526 cs_pp: pp.cs_pp.clone(),
527 cf_cs_pp: pp.cf_cs_pp.clone(),
528 F,
529 pp_hash,
530 i: C1::ScalarField::zero(),
531 z_0: z_0.clone(),
532 z_i: z_0,
533 W_i: W_dummy,
534 U_i: U_dummy,
535 w_i: w_dummy,
536 u_i: u_dummy,
537 // cyclefold running instance
538 cf_W_i: cf_W_dummy,
539 cf_U_i: cf_U_dummy,
540 })
541 }
542
543 /// Implements IVC.P of HyperNova+CycleFold
544 fn prove_step(
545 &mut self,
546 mut rng: impl RngCore,
547 external_inputs: Vec<C1::ScalarField>,
548 other_instances: Option<Self::MultiCommittedInstanceWithWitness>,
549 ) -> Result<(), Error> {
550 // ensure that commitments are blinding if user has specified so.
551
552 if H {
553 let blinding_commitments = if self.i == C1::ScalarField::zero() {
554 vec![self.w_i.r_w]
555 } else {
556 vec![self.w_i.r_w, self.W_i.r_w]
557 };
558 if blinding_commitments.contains(&C1::ScalarField::zero()) {
559 return Err(Error::IncorrectBlinding(
560 H,
561 format!("{:?}", blinding_commitments),
562 ));
563 }
564 }
565
566 // `sponge` is for digest computation.
567 let sponge = PoseidonSponge::<C1::ScalarField>::new(&self.poseidon_config);
568
569 let other_instances = other_instances.ok_or(Error::MissingOtherInstances)?;
570
571 #[allow(clippy::type_complexity)]
572 let (lcccs, cccs): (
573 Vec<(LCCCS<C1>, Witness<C1::ScalarField>)>,
574 Vec<(CCCS<C1>, Witness<C1::ScalarField>)>,
575 ) = other_instances;
576
577 // recall, mu & nu is the number of all the LCCCS & CCCS respectively, including the
578 // running and incoming instances that are not part of the 'other_instances', hence the +1
579 // in the couple of following checks.
580 if lcccs.len() + 1 != MU {
581 return Err(Error::NotSameLength(
582 "other_instances.lcccs.len()".to_string(),
583 lcccs.len(),
584 "hypernova.mu".to_string(),
585 MU,
586 ));
587 }
588 if cccs.len() + 1 != NU {
589 return Err(Error::NotSameLength(
590 "other_instances.cccs.len()".to_string(),
591 cccs.len(),
592 "hypernova.nu".to_string(),
593 NU,
594 ));
595 }
596
597 let (Us, Ws): (Vec<LCCCS<C1>>, Vec<Witness<C1::ScalarField>>) = lcccs.into_iter().unzip();
598 let (us, ws): (Vec<CCCS<C1>>, Vec<Witness<C1::ScalarField>>) = cccs.into_iter().unzip();
599
600 let augmented_f_circuit: AugmentedFCircuit<C1, C2, GC2, FC, MU, NU>;
601
602 if self.z_i.len() != self.F.state_len() {
603 return Err(Error::NotSameLength(
604 "z_i.len()".to_string(),
605 self.z_i.len(),
606 "F.state_len()".to_string(),
607 self.F.state_len(),
608 ));
609 }
610 if external_inputs.len() != self.F.external_inputs_len() {
611 return Err(Error::NotSameLength(
612 "F.external_inputs_len()".to_string(),
613 self.F.external_inputs_len(),
614 "external_inputs.len()".to_string(),
615 external_inputs.len(),
616 ));
617 }
618
619 if self.i > C1::ScalarField::from_le_bytes_mod_order(&usize::MAX.to_le_bytes()) {
620 return Err(Error::MaxStep);
621 }
622
623 let i_usize;
624
625 #[cfg(target_pointer_width = "64")]
626 {
627 let mut i_bytes: [u8; 8] = [0; 8];
628 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..8]);
629 i_usize = usize::from_le_bytes(i_bytes);
630 }
631
632 #[cfg(target_pointer_width = "32")]
633 {
634 let mut i_bytes: [u8; 4] = [0; 4];
635 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..4]);
636 i_usize = usize::from_le_bytes(i_bytes);
637 }
638
639 let z_i1 = self
640 .F
641 .step_native(i_usize, self.z_i.clone(), external_inputs.clone())?;
642
643 // u_{i+1}.x[1] = H(cf_U_{i+1})
644 let cf_u_i1_x: C1::ScalarField;
645 let (U_i1, mut W_i1);
646
647 if self.i == C1::ScalarField::zero() {
648 W_i1 = Witness::<C1::ScalarField>::dummy(&self.ccs);
649 W_i1.r_w = self.W_i.r_w;
650 U_i1 = LCCCS::dummy(&self.ccs);
651
652 let u_i1_x = U_i1.hash(
653 &sponge,
654 self.pp_hash,
655 C1::ScalarField::one(),
656 &self.z_0,
657 &z_i1,
658 );
659
660 // hash the initial (dummy) CycleFold instance, which is used as the 2nd public
661 // input in the AugmentedFCircuit
662 cf_u_i1_x = self.cf_U_i.hash_cyclefold(&sponge, self.pp_hash);
663
664 augmented_f_circuit = AugmentedFCircuit::<C1, C2, GC2, FC, MU, NU> {
665 _c2: PhantomData,
666 _gc2: PhantomData,
667 poseidon_config: self.poseidon_config.clone(),
668 ccs: self.ccs.clone(),
669 pp_hash: Some(self.pp_hash),
670 i: Some(C1::ScalarField::zero()),
671 i_usize: Some(0),
672 z_0: Some(self.z_0.clone()),
673 z_i: Some(self.z_i.clone()),
674 external_inputs: Some(external_inputs.clone()),
675 U_i: Some(self.U_i.clone()),
676 Us: Some(Us.clone()),
677 u_i_C: Some(self.u_i.C),
678 us: Some(us.clone()),
679 U_i1_C: Some(U_i1.C),
680 F: self.F.clone(),
681 x: Some(u_i1_x),
682 nimfs_proof: None,
683
684 // cyclefold values
685 cf_u_i_cmW: None,
686 cf_U_i: None,
687 cf_x: Some(cf_u_i1_x),
688 cf_cmT: None,
689 };
690 } else {
691 let mut transcript_p: PoseidonSponge<C1::ScalarField> =
692 PoseidonSponge::<C1::ScalarField>::new(&self.poseidon_config);
693 transcript_p.absorb(&self.pp_hash);
694 let (rho, nimfs_proof);
695 (nimfs_proof, U_i1, W_i1, rho) = NIMFS::<C1, PoseidonSponge<C1::ScalarField>>::prove(
696 &mut transcript_p,
697 &self.ccs,
698 &[vec![self.U_i.clone()], Us.clone()].concat(),
699 &[vec![self.u_i.clone()], us.clone()].concat(),
700 &[vec![self.W_i.clone()], Ws].concat(),
701 &[vec![self.w_i.clone()], ws].concat(),
702 )?;
703
704 // sanity check: check the folded instance relation
705 #[cfg(test)]
706 self.ccs.check_relation(&W_i1, &U_i1)?;
707
708 let u_i1_x = U_i1.hash(
709 &sponge,
710 self.pp_hash,
711 self.i + C1::ScalarField::one(),
712 &self.z_0,
713 &z_i1,
714 );
715
716 let rho_bits = rho.into_bigint().to_bits_le()[..NOVA_N_BITS_RO].to_vec();
717 let rho_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&rho_bits)).unwrap();
718
719 // CycleFold part:
720 // get the vector used as public inputs 'x' in the CycleFold circuit.
721 // Place the random values and the points coordinates as the public input x:
722 // In Nova, this is: x == [r, p1, p2, p3].
723 // In multifolding schemes such as HyperNova, this is:
724 // computed_x = [r, p_0, p_1, p_2, ..., p_n],
725 // where each p_i is in fact p_i.to_constraint_field()
726 let cf_u_i_x = [
727 vec![rho_Fq],
728 get_cm_coordinates(&self.U_i.C),
729 Us.iter()
730 .flat_map(|Us_i| get_cm_coordinates(&Us_i.C))
731 .collect(),
732 get_cm_coordinates(&self.u_i.C),
733 us.iter()
734 .flat_map(|us_i| get_cm_coordinates(&us_i.C))
735 .collect(),
736 get_cm_coordinates(&U_i1.C),
737 ]
738 .concat();
739
740 let cf_circuit = HyperNovaCycleFoldCircuit::<C1, GC1, MU, NU> {
741 _gc: PhantomData,
742 r_bits: Some(rho_bits.clone()),
743 points: Some(
744 [
745 vec![self.U_i.clone().C],
746 Us.iter().map(|Us_i| Us_i.C).collect(),
747 vec![self.u_i.clone().C],
748 us.iter().map(|us_i| us_i.C).collect(),
749 ]
750 .concat(),
751 ),
752 x: Some(cf_u_i_x.clone()),
753 };
754
755 let (_cf_w_i, cf_u_i, cf_W_i1, cf_U_i1, cf_cmT, _) = fold_cyclefold_circuit::<
756 HyperNovaCycleFoldConfig<C1, MU, NU>,
757 C1,
758 GC1,
759 C2,
760 GC2,
761 CS2,
762 H,
763 >(
764 &mut transcript_p,
765 self.cf_r1cs.clone(),
766 self.cf_cs_pp.clone(),
767 self.pp_hash,
768 self.cf_W_i.clone(), // CycleFold running instance witness
769 self.cf_U_i.clone(), // CycleFold running instance
770 cf_u_i_x,
771 cf_circuit,
772 &mut rng,
773 )?;
774
775 cf_u_i1_x = cf_U_i1.hash_cyclefold(&sponge, self.pp_hash);
776
777 augmented_f_circuit = AugmentedFCircuit::<C1, C2, GC2, FC, MU, NU> {
778 _c2: PhantomData,
779 _gc2: PhantomData,
780 poseidon_config: self.poseidon_config.clone(),
781 ccs: self.ccs.clone(),
782 pp_hash: Some(self.pp_hash),
783 i: Some(self.i),
784 i_usize: Some(i_usize),
785 z_0: Some(self.z_0.clone()),
786 z_i: Some(self.z_i.clone()),
787 external_inputs: Some(external_inputs),
788 U_i: Some(self.U_i.clone()),
789 Us: Some(Us.clone()),
790 u_i_C: Some(self.u_i.C),
791 us: Some(us.clone()),
792 U_i1_C: Some(U_i1.C),
793 F: self.F.clone(),
794 x: Some(u_i1_x),
795 nimfs_proof: Some(nimfs_proof),
796
797 // cyclefold values
798 cf_u_i_cmW: Some(cf_u_i.cmW),
799 cf_U_i: Some(self.cf_U_i.clone()),
800 cf_x: Some(cf_u_i1_x),
801 cf_cmT: Some(cf_cmT),
802 };
803
804 // assign the next round instances
805 self.cf_W_i = cf_W_i1;
806 self.cf_U_i = cf_U_i1;
807 }
808
809 let (cs, _) = augmented_f_circuit.compute_cs_ccs()?;
810
811 #[cfg(test)]
812 assert!(cs.is_satisfied()?);
813
814 let (r1cs_w_i1, r1cs_x_i1) = extract_w_x::<C1::ScalarField>(&cs); // includes 1 and public inputs
815
816 let r1cs_z = [
817 vec![C1::ScalarField::one()],
818 r1cs_x_i1.clone(),
819 r1cs_w_i1.clone(),
820 ]
821 .concat();
822 // compute committed instances, w_{i+1}, u_{i+1}, which will be used as w_i, u_i, so we
823 // assign them directly to w_i, u_i.
824 let (u_i, w_i) = self
825 .ccs
826 .to_cccs::<_, C1, CS1, H>(&mut rng, &self.cs_pp, &r1cs_z)?;
827 self.u_i = u_i.clone();
828 self.w_i = w_i.clone();
829
830 // set values for next iteration
831 self.i += C1::ScalarField::one();
832 // assign z_{i+1} into z_i
833 self.z_i = z_i1.clone();
834 self.U_i = U_i1.clone();
835 self.W_i = W_i1.clone();
836
837 #[cfg(test)]
838 {
839 // check the new LCCCS instance relation
840 self.ccs.check_relation(&self.W_i, &self.U_i)?;
841 // check the new CCCS instance relation
842 self.ccs.check_relation(&self.w_i, &self.u_i)?;
843 }
844
845 Ok(())
846 }
847
848 fn state(&self) -> Vec<C1::ScalarField> {
849 self.z_i.clone()
850 }
851
852 fn instances(
853 &self,
854 ) -> (
855 Self::RunningInstance,
856 Self::IncomingInstance,
857 Self::CFInstance,
858 ) {
859 (
860 (self.U_i.clone(), self.W_i.clone()),
861 (self.u_i.clone(), self.w_i.clone()),
862 (self.cf_U_i.clone(), self.cf_W_i.clone()),
863 )
864 }
865
866 /// Implements IVC.V of HyperNova+CycleFold. Notice that this method does not include the
867 /// commitments verification, which is done in the Decider.
868 fn verify(
869 vp: Self::VerifierParam,
870 z_0: Vec<C1::ScalarField>, // initial state
871 z_i: Vec<C1::ScalarField>, // last state
872 num_steps: C1::ScalarField,
873 running_instance: Self::RunningInstance,
874 incoming_instance: Self::IncomingInstance,
875 cyclefold_instance: Self::CFInstance,
876 ) -> Result<(), Error> {
877 if num_steps == C1::ScalarField::zero() {
878 if z_0 != z_i {
879 return Err(Error::IVCVerificationFail);
880 }
881 return Ok(());
882 }
883 // `sponge` is for digest computation.
884 let sponge = PoseidonSponge::<C1::ScalarField>::new(&vp.poseidon_config);
885
886 let (U_i, W_i) = running_instance;
887 let (u_i, w_i) = incoming_instance;
888 let (cf_U_i, cf_W_i) = cyclefold_instance;
889 if u_i.x.len() != 2 || U_i.x.len() != 2 {
890 return Err(Error::IVCVerificationFail);
891 }
892
893 let pp_hash = vp.pp_hash()?;
894
895 // check that u_i's output points to the running instance
896 // u_i.X[0] == H(i, z_0, z_i, U_i)
897 let expected_u_i_x = U_i.hash(&sponge, pp_hash, num_steps, &z_0, &z_i);
898 if expected_u_i_x != u_i.x[0] {
899 return Err(Error::IVCVerificationFail);
900 }
901 // u_i.X[1] == H(cf_U_i)
902 let expected_cf_u_i_x = cf_U_i.hash_cyclefold(&sponge, pp_hash);
903 if expected_cf_u_i_x != u_i.x[1] {
904 return Err(Error::IVCVerificationFail);
905 }
906
907 // check LCCCS satisfiability
908 vp.ccs.check_relation(&W_i, &U_i)?;
909 // check CCCS satisfiability
910 vp.ccs.check_relation(&w_i, &u_i)?;
911
912 // check CycleFold's RelaxedR1CS satisfiability
913 vp.cf_r1cs.check_relation(&cf_W_i, &cf_U_i)?;
914
915 Ok(())
916 }
917}
918
919#[cfg(test)]
920mod tests {
921 use crate::commitment::kzg::KZG;
922 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
923 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
924 use ark_std::UniformRand;
925
926 use super::*;
927 use crate::commitment::pedersen::Pedersen;
928 use crate::frontend::utils::CubicFCircuit;
929 use crate::transcript::poseidon::poseidon_canonical_config;
930
931 #[test]
932 pub fn test_ivc() {
933 let poseidon_config = poseidon_canonical_config::<Fr>();
934
935 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
936
937 // run the test using Pedersen commitments on both sides of the curve cycle
938 test_ivc_opt::<Pedersen<Projective>, Pedersen<Projective2>, false>(
939 poseidon_config.clone(),
940 F_circuit,
941 );
942
943 test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
944 poseidon_config.clone(),
945 F_circuit,
946 );
947
948 // run the test using KZG for the commitments on the main curve, and Pedersen for the
949 // commitments on the secondary curve
950 test_ivc_opt::<KZG<Bn254>, Pedersen<Projective2>, false>(poseidon_config, F_circuit);
951 }
952
953 #[allow(clippy::type_complexity)]
954 // test_ivc allowing to choose the CommitmentSchemes
955 pub fn test_ivc_opt<
956 CS1: CommitmentScheme<Projective, H>,
957 CS2: CommitmentScheme<Projective2, H>,
958 const H: bool,
959 >(
960 poseidon_config: PoseidonConfig<Fr>,
961 F_circuit: CubicFCircuit<Fr>,
962 ) -> (
963 HyperNova<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2, 2, 3, H>,
964 (
965 ProverParams<Projective, Projective2, CS1, CS2, H>,
966 VerifierParams<Projective, Projective2, CS1, CS2, H>,
967 ),
968 (LCCCS<Projective>, Witness<Fr>),
969 (CCCS<Projective>, Witness<Fr>),
970 (
971 CycleFoldCommittedInstance<Projective2>,
972 CycleFoldWitness<Projective2>,
973 ),
974 ) {
975 let mut rng = ark_std::test_rng();
976
977 const MU: usize = 2;
978 const NU: usize = 3;
979
980 type HN<CS1, CS2, const H: bool> =
981 HyperNova<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2, MU, NU, H>;
982
983 let prep_param =
984 PreprocessorParam::<Projective, Projective2, CubicFCircuit<Fr>, CS1, CS2, H>::new(
985 poseidon_config.clone(),
986 F_circuit,
987 );
988 let hypernova_params = HN::preprocess(&mut rng, &prep_param).unwrap();
989
990 let z_0 = vec![Fr::from(3_u32)];
991 let mut hypernova = HN::init(&hypernova_params, F_circuit, z_0.clone()).unwrap();
992
993 let (w_i_blinding, W_i_blinding) = if H {
994 (Fr::rand(&mut rng), Fr::rand(&mut rng))
995 } else {
996 (Fr::zero(), Fr::zero())
997 };
998 hypernova.w_i.r_w = w_i_blinding;
999 hypernova.W_i.r_w = W_i_blinding;
1000
1001 let num_steps: usize = 3;
1002 for _ in 0..num_steps {
1003 // prepare some new instances to fold in the multifolding step
1004 let mut lcccs = vec![];
1005 for j in 0..MU - 1 {
1006 let instance_state = vec![Fr::from(j as u32 + 85_u32)];
1007 let (U, W) = hypernova
1008 .new_running_instance(&mut rng, instance_state, vec![])
1009 .unwrap();
1010 lcccs.push((U, W));
1011 }
1012 let mut cccs = vec![];
1013 for j in 0..NU - 1 {
1014 let instance_state = vec![Fr::from(j as u32 + 15_u32)];
1015 let (u, w) = hypernova
1016 .new_incoming_instance(&mut rng, instance_state, vec![])
1017 .unwrap();
1018 cccs.push((u, w));
1019 }
1020
1021 hypernova
1022 .prove_step(&mut rng, vec![], Some((lcccs, cccs)))
1023 .unwrap();
1024 }
1025 assert_eq!(Fr::from(num_steps as u32), hypernova.i);
1026
1027 let (running_instance, incoming_instance, cyclefold_instance) = hypernova.instances();
1028 HN::verify(
1029 hypernova_params.1.clone(), // verifier_params
1030 z_0,
1031 hypernova.z_i.clone(),
1032 hypernova.i,
1033 running_instance.clone(),
1034 incoming_instance.clone(),
1035 cyclefold_instance.clone(),
1036 )
1037 .unwrap();
1038
1039 (
1040 hypernova,
1041 hypernova_params,
1042 running_instance,
1043 incoming_instance,
1044 cyclefold_instance,
1045 )
1046 }
1047}