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