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