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