sonobe/src/folding/hypernova/nimfs.rs
src/folding/hypernova/nimfs.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::{CurveGroup, Group};
3use ark_ff::{Field, PrimeField};
4use ark_std::{One, Zero};
5
6use super::cccs::{Witness, CCCS};
7use super::lcccs::LCCCS;
8use super::utils::{compute_c_from_sigmas_and_thetas, compute_g, compute_sigmas_and_thetas};
9use crate::ccs::CCS;
10use crate::transcript::Transcript;
11use crate::utils::hypercube::BooleanHypercube;
12use crate::utils::sum_check::structs::IOPProof as SumCheckProof;
13use crate::utils::sum_check::verifier::interpolate_uni_poly;
14use crate::utils::sum_check::{IOPSumCheck, SumCheck};
15use crate::utils::virtual_polynomial::VPAuxInfo;
16use crate::Error;
17
18use std::fmt::Debug;
19use std::marker::PhantomData;
20
21/// Proof defines a multifolding proof
22#[derive(Debug)]
23pub struct Proof<C: CurveGroup> {
24 pub sc_proof: SumCheckProof<C::ScalarField>,
25 pub sigmas_thetas: SigmasThetas<C::ScalarField>,
26}
27
28#[derive(Debug)]
29pub struct SigmasThetas<F: PrimeField>(pub Vec<Vec<F>>, pub Vec<Vec<F>>);
30
31#[derive(Debug)]
32/// Implements the Non-Interactive Multi Folding Scheme described in section 5 of
33/// [HyperNova](https://eprint.iacr.org/2023/573.pdf)
34pub struct NIMFS<C: CurveGroup, T: Transcript<C>> {
35 pub _c: PhantomData<C>,
36 pub _t: PhantomData<T>,
37}
38
39impl<C: CurveGroup, T: Transcript<C>> NIMFS<C, T>
40where
41 <C as Group>::ScalarField: Absorb,
42{
43 pub fn fold(
44 lcccs: &[LCCCS<C>],
45 cccs: &[CCCS<C>],
46 sigmas_thetas: &SigmasThetas<C::ScalarField>,
47 r_x_prime: Vec<C::ScalarField>,
48 rho: C::ScalarField,
49 ) -> LCCCS<C> {
50 let (sigmas, thetas) = (sigmas_thetas.0.clone(), sigmas_thetas.1.clone());
51 let mut C_folded = C::zero();
52 let mut u_folded = C::ScalarField::zero();
53 let mut x_folded: Vec<C::ScalarField> = vec![C::ScalarField::zero(); lcccs[0].x.len()];
54 let mut v_folded: Vec<C::ScalarField> = vec![C::ScalarField::zero(); sigmas[0].len()];
55
56 for i in 0..(lcccs.len() + cccs.len()) {
57 let rho_i = rho.pow([i as u64]);
58
59 let c: C;
60 let u: C::ScalarField;
61 let x: Vec<C::ScalarField>;
62 let v: Vec<C::ScalarField>;
63 if i < lcccs.len() {
64 c = lcccs[i].C;
65 u = lcccs[i].u;
66 x = lcccs[i].x.clone();
67 v = sigmas[i].clone();
68 } else {
69 c = cccs[i - lcccs.len()].C;
70 u = C::ScalarField::one();
71 x = cccs[i - lcccs.len()].x.clone();
72 v = thetas[i - lcccs.len()].clone();
73 }
74
75 C_folded += c.mul(rho_i);
76 u_folded += rho_i * u;
77 x_folded = x_folded
78 .iter()
79 .zip(
80 x.iter()
81 .map(|x_i| *x_i * rho_i)
82 .collect::<Vec<C::ScalarField>>(),
83 )
84 .map(|(a_i, b_i)| *a_i + b_i)
85 .collect();
86
87 v_folded = v_folded
88 .iter()
89 .zip(
90 v.iter()
91 .map(|x_i| *x_i * rho_i)
92 .collect::<Vec<C::ScalarField>>(),
93 )
94 .map(|(a_i, b_i)| *a_i + b_i)
95 .collect();
96 }
97
98 LCCCS::<C> {
99 C: C_folded,
100 u: u_folded,
101 x: x_folded,
102 r_x: r_x_prime,
103 v: v_folded,
104 }
105 }
106
107 pub fn fold_witness(
108 w_lcccs: &[Witness<C::ScalarField>],
109 w_cccs: &[Witness<C::ScalarField>],
110 rho: C::ScalarField,
111 ) -> Witness<C::ScalarField> {
112 let mut w_folded: Vec<C::ScalarField> = vec![C::ScalarField::zero(); w_lcccs[0].w.len()];
113 let mut r_w_folded = C::ScalarField::zero();
114
115 for i in 0..(w_lcccs.len() + w_cccs.len()) {
116 let rho_i = rho.pow([i as u64]);
117 let w: Vec<C::ScalarField>;
118 let r_w: C::ScalarField;
119
120 if i < w_lcccs.len() {
121 w = w_lcccs[i].w.clone();
122 r_w = w_lcccs[i].r_w;
123 } else {
124 w = w_cccs[i - w_lcccs.len()].w.clone();
125 r_w = w_cccs[i - w_lcccs.len()].r_w;
126 }
127
128 w_folded = w_folded
129 .iter()
130 .zip(
131 w.iter()
132 .map(|x_i| *x_i * rho_i)
133 .collect::<Vec<C::ScalarField>>(),
134 )
135 .map(|(a_i, b_i)| *a_i + b_i)
136 .collect();
137
138 r_w_folded += rho_i * r_w;
139 }
140 Witness {
141 w: w_folded,
142 r_w: r_w_folded,
143 }
144 }
145
146 /// Performs the multifolding prover. Given μ LCCCS instances and ν CCS instances, fold them
147 /// into a single LCCCS instance. Since this is the prover, also fold their witness.
148 /// Returns the final folded LCCCS, the folded witness, and the multifolding proof, which
149 /// contains the sumcheck proof and the helper sumcheck claim sigmas and thetas.
150 #[allow(clippy::type_complexity)]
151 pub fn prove(
152 transcript: &mut impl Transcript<C>,
153 ccs: &CCS<C>,
154 running_instances: &[LCCCS<C>],
155 new_instances: &[CCCS<C>],
156 w_lcccs: &[Witness<C::ScalarField>],
157 w_cccs: &[Witness<C::ScalarField>],
158 ) -> Result<(Proof<C>, LCCCS<C>, Witness<C::ScalarField>), Error> {
159 // TODO appends to transcript
160
161 if running_instances.is_empty() {
162 return Err(Error::Empty);
163 }
164 if new_instances.is_empty() {
165 return Err(Error::Empty);
166 }
167
168 // construct the LCCCS z vector from the relaxation factor, public IO and witness
169 // XXX this deserves its own function in LCCCS
170 let mut z_lcccs = Vec::new();
171 for (i, running_instance) in running_instances.iter().enumerate() {
172 let z_1: Vec<C::ScalarField> = [
173 vec![running_instance.u],
174 running_instance.x.clone(),
175 w_lcccs[i].w.to_vec(),
176 ]
177 .concat();
178 z_lcccs.push(z_1);
179 }
180 // construct the CCCS z vector from the public IO and witness
181 let mut z_cccs = Vec::new();
182 for (i, new_instance) in new_instances.iter().enumerate() {
183 let z_2: Vec<C::ScalarField> = [
184 vec![C::ScalarField::one()],
185 new_instance.x.clone(),
186 w_cccs[i].w.to_vec(),
187 ]
188 .concat();
189 z_cccs.push(z_2);
190 }
191
192 // Step 1: Get some challenges
193 let gamma_scalar = C::ScalarField::from_le_bytes_mod_order(b"gamma");
194 let beta_scalar = C::ScalarField::from_le_bytes_mod_order(b"beta");
195 transcript.absorb(&gamma_scalar);
196 let gamma: C::ScalarField = transcript.get_challenge();
197 transcript.absorb(&beta_scalar);
198 let beta: Vec<C::ScalarField> = transcript.get_challenges(ccs.s);
199
200 // Compute g(x)
201 let g = compute_g(ccs, running_instances, &z_lcccs, &z_cccs, gamma, &beta);
202
203 // Step 3: Run the sumcheck prover
204 let sumcheck_proof = IOPSumCheck::<C, T>::prove(&g, transcript)
205 .map_err(|err| Error::SumCheckProveError(err.to_string()))?;
206
207 // Note: The following two "sanity checks" are done for this prototype, in a final version
208 // they should be removed.
209 //
210 // Sanity check 1: evaluate g(x) over x \in {0,1} (the boolean hypercube), and check that
211 // its sum is equal to the extracted_sum from the SumCheck.
212 //////////////////////////////////////////////////////////////////////
213 let mut g_over_bhc = C::ScalarField::zero();
214 for x in BooleanHypercube::new(ccs.s) {
215 g_over_bhc += g.evaluate(&x).unwrap();
216 }
217
218 // note: this is the sum of g(x) over the whole boolean hypercube
219 let extracted_sum = IOPSumCheck::<C, T>::extract_sum(&sumcheck_proof);
220
221 if extracted_sum != g_over_bhc {
222 return Err(Error::NotEqual);
223 }
224 // Sanity check 2: expect \sum v_j * gamma^j to be equal to the sum of g(x) over the
225 // boolean hypercube (and also equal to the extracted_sum from the SumCheck).
226 let mut sum_v_j_gamma = C::ScalarField::zero();
227 for (i, running_instance) in running_instances.iter().enumerate() {
228 for j in 0..running_instance.v.len() {
229 let gamma_j = gamma.pow([(i * ccs.t + j) as u64]);
230 sum_v_j_gamma += running_instance.v[j] * gamma_j;
231 }
232 }
233 if g_over_bhc != sum_v_j_gamma {
234 return Err(Error::NotEqual);
235 }
236 if extracted_sum != sum_v_j_gamma {
237 return Err(Error::NotEqual);
238 }
239 //////////////////////////////////////////////////////////////////////
240
241 // Step 2: dig into the sumcheck and extract r_x_prime
242 let r_x_prime = sumcheck_proof.point.clone();
243
244 // Step 4: compute sigmas and thetas
245 let sigmas_thetas = compute_sigmas_and_thetas(ccs, &z_lcccs, &z_cccs, &r_x_prime);
246
247 // Step 6: Get the folding challenge
248 let rho_scalar = C::ScalarField::from_le_bytes_mod_order(b"rho");
249 transcript.absorb(&rho_scalar);
250 let rho: C::ScalarField = transcript.get_challenge();
251
252 // Step 7: Create the folded instance
253 let folded_lcccs = Self::fold(
254 running_instances,
255 new_instances,
256 &sigmas_thetas,
257 r_x_prime,
258 rho,
259 );
260
261 // Step 8: Fold the witnesses
262 let folded_witness = Self::fold_witness(w_lcccs, w_cccs, rho);
263
264 Ok((
265 Proof::<C> {
266 sc_proof: sumcheck_proof,
267 sigmas_thetas,
268 },
269 folded_lcccs,
270 folded_witness,
271 ))
272 }
273
274 /// Performs the multifolding verifier. Given μ LCCCS instances and ν CCS instances, fold them
275 /// into a single LCCCS instance.
276 /// Returns the folded LCCCS instance.
277 pub fn verify(
278 transcript: &mut impl Transcript<C>,
279 ccs: &CCS<C>,
280 running_instances: &[LCCCS<C>],
281 new_instances: &[CCCS<C>],
282 proof: Proof<C>,
283 ) -> Result<LCCCS<C>, Error> {
284 // TODO appends to transcript
285
286 if running_instances.is_empty() {
287 return Err(Error::Empty);
288 }
289 if new_instances.is_empty() {
290 return Err(Error::Empty);
291 }
292
293 // Step 1: Get some challenges
294 let gamma_scalar = C::ScalarField::from_le_bytes_mod_order(b"gamma");
295 transcript.absorb(&gamma_scalar);
296 let gamma: C::ScalarField = transcript.get_challenge();
297
298 let beta_scalar = C::ScalarField::from_le_bytes_mod_order(b"beta");
299 transcript.absorb(&beta_scalar);
300 let beta: Vec<C::ScalarField> = transcript.get_challenges(ccs.s);
301
302 let vp_aux_info = VPAuxInfo::<C::ScalarField> {
303 max_degree: ccs.d + 1,
304 num_variables: ccs.s,
305 phantom: PhantomData::<C::ScalarField>,
306 };
307
308 // Step 3: Start verifying the sumcheck
309 // First, compute the expected sumcheck sum: \sum gamma^j v_j
310 let mut sum_v_j_gamma = C::ScalarField::zero();
311 for (i, running_instance) in running_instances.iter().enumerate() {
312 for j in 0..running_instance.v.len() {
313 let gamma_j = gamma.pow([(i * ccs.t + j) as u64]);
314 sum_v_j_gamma += running_instance.v[j] * gamma_j;
315 }
316 }
317
318 // Verify the interactive part of the sumcheck
319 let sumcheck_subclaim =
320 IOPSumCheck::<C, T>::verify(sum_v_j_gamma, &proof.sc_proof, &vp_aux_info, transcript)
321 .map_err(|err| Error::SumCheckVerifyError(err.to_string()))?;
322
323 // Step 2: Dig into the sumcheck claim and extract the randomness used
324 let r_x_prime = sumcheck_subclaim.point.clone();
325
326 // Step 5: Finish verifying sumcheck (verify the claim c)
327 let c = compute_c_from_sigmas_and_thetas(
328 ccs,
329 &proof.sigmas_thetas,
330 gamma,
331 &beta,
332 &running_instances
333 .iter()
334 .map(|lcccs| lcccs.r_x.clone())
335 .collect(),
336 &r_x_prime,
337 );
338 // check that the g(r_x') from the sumcheck proof is equal to the computed c from sigmas&thetas
339 if c != sumcheck_subclaim.expected_evaluation {
340 return Err(Error::NotEqual);
341 }
342
343 // Sanity check: we can also compute g(r_x') from the proof last evaluation value, and
344 // should be equal to the previously obtained values.
345 let g_on_rxprime_from_sumcheck_last_eval = interpolate_uni_poly::<C::ScalarField>(
346 &proof.sc_proof.proofs.last().unwrap().evaluations,
347 *r_x_prime.last().unwrap(),
348 )
349 .unwrap();
350 if g_on_rxprime_from_sumcheck_last_eval != c {
351 return Err(Error::NotEqual);
352 }
353 if g_on_rxprime_from_sumcheck_last_eval != sumcheck_subclaim.expected_evaluation {
354 return Err(Error::NotEqual);
355 }
356
357 // Step 6: Get the folding challenge
358 let rho_scalar = C::ScalarField::from_le_bytes_mod_order(b"rho");
359 transcript.absorb(&rho_scalar);
360 let rho: C::ScalarField = transcript.get_challenge();
361
362 // Step 7: Compute the folded instance
363 Ok(Self::fold(
364 running_instances,
365 new_instances,
366 &proof.sigmas_thetas,
367 r_x_prime,
368 rho,
369 ))
370 }
371}
372
373#[cfg(test)]
374pub mod tests {
375 use super::*;
376 use crate::ccs::tests::{get_test_ccs, get_test_z};
377 use crate::transcript::poseidon::tests::poseidon_test_config;
378 use crate::transcript::poseidon::PoseidonTranscript;
379 use ark_std::test_rng;
380 use ark_std::UniformRand;
381
382 use crate::pedersen::Pedersen;
383 use ark_pallas::{Fr, Projective};
384
385 #[test]
386 fn test_fold() {
387 let ccs = get_test_ccs();
388 let z1 = get_test_z::<Fr>(3);
389 let z2 = get_test_z::<Fr>(4);
390 ccs.check_relation(&z1).unwrap();
391 ccs.check_relation(&z2).unwrap();
392
393 let mut rng = test_rng();
394 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
395
396 let sigmas_thetas =
397 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
398
399 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, ccs.n - ccs.l - 1);
400
401 let (lcccs, w1) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
402 let (cccs, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z2).unwrap();
403
404 lcccs.check_relation(&pedersen_params, &ccs, &w1).unwrap();
405 cccs.check_relation(&pedersen_params, &ccs, &w2).unwrap();
406
407 let mut rng = test_rng();
408 let rho = Fr::rand(&mut rng);
409
410 let folded = NIMFS::<Projective, PoseidonTranscript<Projective>>::fold(
411 &[lcccs],
412 &[cccs],
413 &sigmas_thetas,
414 r_x_prime,
415 rho,
416 );
417
418 let w_folded =
419 NIMFS::<Projective, PoseidonTranscript<Projective>>::fold_witness(&[w1], &[w2], rho);
420
421 // check lcccs relation
422 folded
423 .check_relation(&pedersen_params, &ccs, &w_folded)
424 .unwrap();
425 }
426
427 /// Perform multifolding of an LCCCS instance with a CCCS instance (as described in the paper)
428 #[test]
429 pub fn test_basic_multifolding() {
430 let mut rng = test_rng();
431
432 // Create a basic CCS circuit
433 let ccs = get_test_ccs::<Projective>();
434 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
435
436 // Generate a satisfying witness
437 let z_1 = get_test_z(3);
438 // Generate another satisfying witness
439 let z_2 = get_test_z(4);
440
441 // Create the LCCCS instance out of z_1
442 let (running_instance, w1) = ccs.to_lcccs(&mut rng, &pedersen_params, &z_1).unwrap();
443 // Create the CCCS instance out of z_2
444 let (new_instance, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z_2).unwrap();
445
446 // Prover's transcript
447 let poseidon_config = poseidon_test_config::<Fr>();
448 let mut transcript_p: PoseidonTranscript<Projective> =
449 PoseidonTranscript::<Projective>::new(&poseidon_config);
450 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
451
452 // Run the prover side of the multifolding
453 let (proof, folded_lcccs, folded_witness) =
454 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
455 &mut transcript_p,
456 &ccs,
457 &[running_instance.clone()],
458 &[new_instance.clone()],
459 &[w1],
460 &[w2],
461 )
462 .unwrap();
463
464 // Verifier's transcript
465 let mut transcript_v: PoseidonTranscript<Projective> =
466 PoseidonTranscript::<Projective>::new(&poseidon_config);
467 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
468
469 // Run the verifier side of the multifolding
470 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
471 &mut transcript_v,
472 &ccs,
473 &[running_instance.clone()],
474 &[new_instance.clone()],
475 proof,
476 )
477 .unwrap();
478 assert_eq!(folded_lcccs, folded_lcccs_v);
479
480 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
481 folded_lcccs
482 .check_relation(&pedersen_params, &ccs, &folded_witness)
483 .unwrap();
484 }
485
486 /// Perform multiple steps of multifolding of an LCCCS instance with a CCCS instance
487 #[test]
488 pub fn test_multifolding_two_instances_multiple_steps() {
489 let mut rng = test_rng();
490
491 let ccs = get_test_ccs::<Projective>();
492
493 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
494
495 // LCCCS witness
496 let z_1 = get_test_z(2);
497 let (mut running_instance, mut w1) =
498 ccs.to_lcccs(&mut rng, &pedersen_params, &z_1).unwrap();
499
500 let poseidon_config = poseidon_test_config::<Fr>();
501
502 let mut transcript_p: PoseidonTranscript<Projective> =
503 PoseidonTranscript::<Projective>::new(&poseidon_config);
504 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
505
506 let mut transcript_v: PoseidonTranscript<Projective> =
507 PoseidonTranscript::<Projective>::new(&poseidon_config);
508 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
509
510 let n: usize = 10;
511 for i in 3..n {
512 println!("\niteration: i {}", i); // DBG
513
514 // CCS witness
515 let z_2 = get_test_z(i);
516 println!("z_2 {:?}", z_2); // DBG
517
518 let (new_instance, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z_2).unwrap();
519
520 // run the prover side of the multifolding
521 let (proof, folded_lcccs, folded_witness) =
522 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
523 &mut transcript_p,
524 &ccs,
525 &[running_instance.clone()],
526 &[new_instance.clone()],
527 &[w1],
528 &[w2],
529 )
530 .unwrap();
531
532 // run the verifier side of the multifolding
533 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
534 &mut transcript_v,
535 &ccs,
536 &[running_instance.clone()],
537 &[new_instance.clone()],
538 proof,
539 )
540 .unwrap();
541 assert_eq!(folded_lcccs, folded_lcccs_v);
542
543 // check that the folded instance with the folded witness holds the LCCCS relation
544 println!("check_relation {}", i);
545 folded_lcccs
546 .check_relation(&pedersen_params, &ccs, &folded_witness)
547 .unwrap();
548
549 running_instance = folded_lcccs;
550 w1 = folded_witness;
551 }
552 }
553
554 /// Test that generates mu>1 and nu>1 instances, and folds them in a single multifolding step.
555 #[test]
556 pub fn test_multifolding_mu_nu_instances() {
557 let mut rng = test_rng();
558
559 // Create a basic CCS circuit
560 let ccs = get_test_ccs::<Projective>();
561 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
562
563 let mu = 10;
564 let nu = 15;
565
566 // Generate a mu LCCCS & nu CCCS satisfying witness
567 let mut z_lcccs = Vec::new();
568 for i in 0..mu {
569 let z = get_test_z(i + 3);
570 z_lcccs.push(z);
571 }
572 let mut z_cccs = Vec::new();
573 for i in 0..nu {
574 let z = get_test_z(nu + i + 3);
575 z_cccs.push(z);
576 }
577
578 // Create the LCCCS instances out of z_lcccs
579 let mut lcccs_instances = Vec::new();
580 let mut w_lcccs = Vec::new();
581 for z_i in z_lcccs.iter() {
582 let (running_instance, w) = ccs.to_lcccs(&mut rng, &pedersen_params, z_i).unwrap();
583 lcccs_instances.push(running_instance);
584 w_lcccs.push(w);
585 }
586 // Create the CCCS instance out of z_cccs
587 let mut cccs_instances = Vec::new();
588 let mut w_cccs = Vec::new();
589 for z_i in z_cccs.iter() {
590 let (new_instance, w) = ccs.to_cccs(&mut rng, &pedersen_params, z_i).unwrap();
591 cccs_instances.push(new_instance);
592 w_cccs.push(w);
593 }
594
595 // Prover's transcript
596 let poseidon_config = poseidon_test_config::<Fr>();
597 let mut transcript_p: PoseidonTranscript<Projective> =
598 PoseidonTranscript::<Projective>::new(&poseidon_config);
599 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
600
601 // Run the prover side of the multifolding
602 let (proof, folded_lcccs, folded_witness) =
603 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
604 &mut transcript_p,
605 &ccs,
606 &lcccs_instances,
607 &cccs_instances,
608 &w_lcccs,
609 &w_cccs,
610 )
611 .unwrap();
612
613 // Verifier's transcript
614 let mut transcript_v: PoseidonTranscript<Projective> =
615 PoseidonTranscript::<Projective>::new(&poseidon_config);
616 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
617
618 // Run the verifier side of the multifolding
619 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
620 &mut transcript_v,
621 &ccs,
622 &lcccs_instances,
623 &cccs_instances,
624 proof,
625 )
626 .unwrap();
627 assert_eq!(folded_lcccs, folded_lcccs_v);
628
629 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
630 folded_lcccs
631 .check_relation(&pedersen_params, &ccs, &folded_witness)
632 .unwrap();
633 }
634
635 /// Test that generates mu>1 and nu>1 instances, and folds them in a single multifolding step
636 /// and repeats the process doing multiple steps.
637 #[test]
638 pub fn test_multifolding_mu_nu_instances_multiple_steps() {
639 let mut rng = test_rng();
640
641 // Create a basic CCS circuit
642 let ccs = get_test_ccs::<Projective>();
643 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
644
645 let poseidon_config = poseidon_test_config::<Fr>();
646 // Prover's transcript
647 let mut transcript_p: PoseidonTranscript<Projective> =
648 PoseidonTranscript::<Projective>::new(&poseidon_config);
649 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
650
651 // Verifier's transcript
652 let mut transcript_v: PoseidonTranscript<Projective> =
653 PoseidonTranscript::<Projective>::new(&poseidon_config);
654 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
655
656 let n_steps = 3;
657
658 // number of LCCCS & CCCS instances in each multifolding step
659 let mu = 10;
660 let nu = 15;
661
662 // Generate a mu LCCCS & nu CCCS satisfying witness, for each step
663 for step in 0..n_steps {
664 let mut z_lcccs = Vec::new();
665 for i in 0..mu {
666 let z = get_test_z(step + i + 3);
667 z_lcccs.push(z);
668 }
669 let mut z_cccs = Vec::new();
670 for i in 0..nu {
671 let z = get_test_z(nu + i + 3);
672 z_cccs.push(z);
673 }
674
675 // Create the LCCCS instances out of z_lcccs
676 let mut lcccs_instances = Vec::new();
677 let mut w_lcccs = Vec::new();
678 for z_i in z_lcccs.iter() {
679 let (running_instance, w) = ccs.to_lcccs(&mut rng, &pedersen_params, z_i).unwrap();
680 lcccs_instances.push(running_instance);
681 w_lcccs.push(w);
682 }
683 // Create the CCCS instance out of z_cccs
684 let mut cccs_instances = Vec::new();
685 let mut w_cccs = Vec::new();
686 for z_i in z_cccs.iter() {
687 let (new_instance, w) = ccs.to_cccs(&mut rng, &pedersen_params, z_i).unwrap();
688 cccs_instances.push(new_instance);
689 w_cccs.push(w);
690 }
691
692 // Run the prover side of the multifolding
693 let (proof, folded_lcccs, folded_witness) =
694 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
695 &mut transcript_p,
696 &ccs,
697 &lcccs_instances,
698 &cccs_instances,
699 &w_lcccs,
700 &w_cccs,
701 )
702 .unwrap();
703
704 // Run the verifier side of the multifolding
705 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
706 &mut transcript_v,
707 &ccs,
708 &lcccs_instances,
709 &cccs_instances,
710 proof,
711 )
712 .unwrap();
713
714 assert_eq!(folded_lcccs, folded_lcccs_v);
715
716 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
717 folded_lcccs
718 .check_relation(&pedersen_params, &ccs, &folded_witness)
719 .unwrap();
720 }
721 }
722}