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