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