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