sonobe/folding-schemes/src/folding/hypernova/nimfs.rs
folding-schemes/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, 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(Clone, Debug)]
24pub struct Proof<C: CurveGroup> {
25 pub sc_proof: SumCheckProof<C::ScalarField>,
26 pub sigmas_thetas: SigmasThetas<C::ScalarField>,
27}
28
29#[derive(Clone, 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::ScalarField>,
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::ScalarField>,
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(
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
340 // check that the g(r_x') from the sumcheck proof is equal to the computed c from sigmas&thetas
341 if c != sumcheck_subclaim.expected_evaluation {
342 return Err(Error::NotEqual);
343 }
344
345 // Sanity check: we can also compute g(r_x') from the proof last evaluation value, and
346 // should be equal to the previously obtained values.
347 let g_on_rxprime_from_sumcheck_last_eval =
348 DensePolynomial::from_coefficients_slice(&proof.sc_proof.proofs.last().unwrap().coeffs)
349 .evaluate(r_x_prime.last().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::poseidon_test_config;
378 use crate::transcript::poseidon::PoseidonTranscript;
379 use ark_std::test_rng;
380 use ark_std::UniformRand;
381
382 use crate::commitment::{pedersen::Pedersen, CommitmentScheme};
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, _) =
400 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
401
402 let (lcccs, w1) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
403 let (cccs, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z2).unwrap();
404
405 lcccs.check_relation(&pedersen_params, &ccs, &w1).unwrap();
406 cccs.check_relation(&pedersen_params, &ccs, &w2).unwrap();
407
408 let mut rng = test_rng();
409 let rho = Fr::rand(&mut rng);
410
411 let folded = NIMFS::<Projective, PoseidonTranscript<Projective>>::fold(
412 &[lcccs],
413 &[cccs],
414 &sigmas_thetas,
415 r_x_prime,
416 rho,
417 );
418
419 let w_folded =
420 NIMFS::<Projective, PoseidonTranscript<Projective>>::fold_witness(&[w1], &[w2], rho);
421
422 // check lcccs relation
423 folded
424 .check_relation(&pedersen_params, &ccs, &w_folded)
425 .unwrap();
426 }
427
428 /// Perform multifolding of an LCCCS instance with a CCCS instance (as described in the paper)
429 #[test]
430 pub fn test_basic_multifolding() {
431 let mut rng = test_rng();
432
433 // Create a basic CCS circuit
434 let ccs = get_test_ccs::<Fr>();
435 let (pedersen_params, _) =
436 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
437
438 // Generate a satisfying witness
439 let z_1 = get_test_z(3);
440 // Generate another satisfying witness
441 let z_2 = get_test_z(4);
442
443 // Create the LCCCS instance out of z_1
444 let (running_instance, w1) = ccs.to_lcccs(&mut rng, &pedersen_params, &z_1).unwrap();
445 // Create the CCCS instance out of z_2
446 let (new_instance, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z_2).unwrap();
447
448 // Prover's transcript
449 let poseidon_config = poseidon_test_config::<Fr>();
450 let mut transcript_p: PoseidonTranscript<Projective> =
451 PoseidonTranscript::<Projective>::new(&poseidon_config);
452 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
453
454 // Run the prover side of the multifolding
455 let (proof, folded_lcccs, folded_witness) =
456 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
457 &mut transcript_p,
458 &ccs,
459 &[running_instance.clone()],
460 &[new_instance.clone()],
461 &[w1],
462 &[w2],
463 )
464 .unwrap();
465
466 // Verifier's transcript
467 let mut transcript_v: PoseidonTranscript<Projective> =
468 PoseidonTranscript::<Projective>::new(&poseidon_config);
469 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
470
471 // Run the verifier side of the multifolding
472 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
473 &mut transcript_v,
474 &ccs,
475 &[running_instance.clone()],
476 &[new_instance.clone()],
477 proof,
478 )
479 .unwrap();
480 assert_eq!(folded_lcccs, folded_lcccs_v);
481
482 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
483 folded_lcccs
484 .check_relation(&pedersen_params, &ccs, &folded_witness)
485 .unwrap();
486 }
487
488 /// Perform multiple steps of multifolding of an LCCCS instance with a CCCS instance
489 #[test]
490 pub fn test_multifolding_two_instances_multiple_steps() {
491 let mut rng = test_rng();
492
493 let ccs = get_test_ccs::<Fr>();
494
495 let (pedersen_params, _) =
496 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
497
498 // LCCCS witness
499 let z_1 = get_test_z(2);
500 let (mut running_instance, mut w1) =
501 ccs.to_lcccs(&mut rng, &pedersen_params, &z_1).unwrap();
502
503 let poseidon_config = poseidon_test_config::<Fr>();
504
505 let mut transcript_p: PoseidonTranscript<Projective> =
506 PoseidonTranscript::<Projective>::new(&poseidon_config);
507 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
508
509 let mut transcript_v: PoseidonTranscript<Projective> =
510 PoseidonTranscript::<Projective>::new(&poseidon_config);
511 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
512
513 let n: usize = 10;
514 for i in 3..n {
515 println!("\niteration: i {}", i); // DBG
516
517 // CCS witness
518 let z_2 = get_test_z(i);
519 println!("z_2 {:?}", z_2); // DBG
520
521 let (new_instance, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z_2).unwrap();
522
523 // run the prover side of the multifolding
524 let (proof, folded_lcccs, folded_witness) =
525 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
526 &mut transcript_p,
527 &ccs,
528 &[running_instance.clone()],
529 &[new_instance.clone()],
530 &[w1],
531 &[w2],
532 )
533 .unwrap();
534
535 // run the verifier side of the multifolding
536 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
537 &mut transcript_v,
538 &ccs,
539 &[running_instance.clone()],
540 &[new_instance.clone()],
541 proof,
542 )
543 .unwrap();
544 assert_eq!(folded_lcccs, folded_lcccs_v);
545
546 // check that the folded instance with the folded witness holds the LCCCS relation
547 println!("check_relation {}", i);
548 folded_lcccs
549 .check_relation(&pedersen_params, &ccs, &folded_witness)
550 .unwrap();
551
552 running_instance = folded_lcccs;
553 w1 = folded_witness;
554 }
555 }
556
557 /// Test that generates mu>1 and nu>1 instances, and folds them in a single multifolding step.
558 #[test]
559 pub fn test_multifolding_mu_nu_instances() {
560 let mut rng = test_rng();
561
562 // Create a basic CCS circuit
563 let ccs = get_test_ccs::<Fr>();
564 let (pedersen_params, _) =
565 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
566
567 let mu = 10;
568 let nu = 15;
569
570 // Generate a mu LCCCS & nu CCCS satisfying witness
571 let mut z_lcccs = Vec::new();
572 for i in 0..mu {
573 let z = get_test_z(i + 3);
574 z_lcccs.push(z);
575 }
576 let mut z_cccs = Vec::new();
577 for i in 0..nu {
578 let z = get_test_z(nu + i + 3);
579 z_cccs.push(z);
580 }
581
582 // Create the LCCCS instances out of z_lcccs
583 let mut lcccs_instances = Vec::new();
584 let mut w_lcccs = Vec::new();
585 for z_i in z_lcccs.iter() {
586 let (running_instance, w) = ccs.to_lcccs(&mut rng, &pedersen_params, z_i).unwrap();
587 lcccs_instances.push(running_instance);
588 w_lcccs.push(w);
589 }
590 // Create the CCCS instance out of z_cccs
591 let mut cccs_instances = Vec::new();
592 let mut w_cccs = Vec::new();
593 for z_i in z_cccs.iter() {
594 let (new_instance, w) = ccs.to_cccs(&mut rng, &pedersen_params, z_i).unwrap();
595 cccs_instances.push(new_instance);
596 w_cccs.push(w);
597 }
598
599 // Prover's transcript
600 let poseidon_config = poseidon_test_config::<Fr>();
601 let mut transcript_p: PoseidonTranscript<Projective> =
602 PoseidonTranscript::<Projective>::new(&poseidon_config);
603 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
604
605 // Run the prover side of the multifolding
606 let (proof, folded_lcccs, folded_witness) =
607 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
608 &mut transcript_p,
609 &ccs,
610 &lcccs_instances,
611 &cccs_instances,
612 &w_lcccs,
613 &w_cccs,
614 )
615 .unwrap();
616
617 // Verifier's transcript
618 let mut transcript_v: PoseidonTranscript<Projective> =
619 PoseidonTranscript::<Projective>::new(&poseidon_config);
620 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
621
622 // Run the verifier side of the multifolding
623 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
624 &mut transcript_v,
625 &ccs,
626 &lcccs_instances,
627 &cccs_instances,
628 proof,
629 )
630 .unwrap();
631 assert_eq!(folded_lcccs, folded_lcccs_v);
632
633 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
634 folded_lcccs
635 .check_relation(&pedersen_params, &ccs, &folded_witness)
636 .unwrap();
637 }
638
639 /// Test that generates mu>1 and nu>1 instances, and folds them in a single multifolding step
640 /// and repeats the process doing multiple steps.
641 #[test]
642 pub fn test_multifolding_mu_nu_instances_multiple_steps() {
643 let mut rng = test_rng();
644
645 // Create a basic CCS circuit
646 let ccs = get_test_ccs::<Fr>();
647 let (pedersen_params, _) =
648 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
649
650 let poseidon_config = poseidon_test_config::<Fr>();
651 // Prover's transcript
652 let mut transcript_p: PoseidonTranscript<Projective> =
653 PoseidonTranscript::<Projective>::new(&poseidon_config);
654 transcript_p.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
655
656 // Verifier's transcript
657 let mut transcript_v: PoseidonTranscript<Projective> =
658 PoseidonTranscript::<Projective>::new(&poseidon_config);
659 transcript_v.absorb(&Fr::from_le_bytes_mod_order(b"init init"));
660
661 let n_steps = 3;
662
663 // number of LCCCS & CCCS instances in each multifolding step
664 let mu = 10;
665 let nu = 15;
666
667 // Generate a mu LCCCS & nu CCCS satisfying witness, for each step
668 for step in 0..n_steps {
669 let mut z_lcccs = Vec::new();
670 for i in 0..mu {
671 let z = get_test_z(step + i + 3);
672 z_lcccs.push(z);
673 }
674 let mut z_cccs = Vec::new();
675 for i in 0..nu {
676 let z = get_test_z(nu + i + 3);
677 z_cccs.push(z);
678 }
679
680 // Create the LCCCS instances out of z_lcccs
681 let mut lcccs_instances = Vec::new();
682 let mut w_lcccs = Vec::new();
683 for z_i in z_lcccs.iter() {
684 let (running_instance, w) = ccs.to_lcccs(&mut rng, &pedersen_params, z_i).unwrap();
685 lcccs_instances.push(running_instance);
686 w_lcccs.push(w);
687 }
688 // Create the CCCS instance out of z_cccs
689 let mut cccs_instances = Vec::new();
690 let mut w_cccs = Vec::new();
691 for z_i in z_cccs.iter() {
692 let (new_instance, w) = ccs.to_cccs(&mut rng, &pedersen_params, z_i).unwrap();
693 cccs_instances.push(new_instance);
694 w_cccs.push(w);
695 }
696
697 // Run the prover side of the multifolding
698 let (proof, folded_lcccs, folded_witness) =
699 NIMFS::<Projective, PoseidonTranscript<Projective>>::prove(
700 &mut transcript_p,
701 &ccs,
702 &lcccs_instances,
703 &cccs_instances,
704 &w_lcccs,
705 &w_cccs,
706 )
707 .unwrap();
708
709 // Run the verifier side of the multifolding
710 let folded_lcccs_v = NIMFS::<Projective, PoseidonTranscript<Projective>>::verify(
711 &mut transcript_v,
712 &ccs,
713 &lcccs_instances,
714 &cccs_instances,
715 proof,
716 )
717 .unwrap();
718
719 assert_eq!(folded_lcccs, folded_lcccs_v);
720
721 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
722 folded_lcccs
723 .check_relation(&pedersen_params, &ccs, &folded_witness)
724 .unwrap();
725 }
726 }
727}