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