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