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