1use crate::{Curve, CurveScalarSponge, CurveSponge, ScalarField, Sponge, SRS_SIZE};
34use ark_ec::AffineRepr;
35use ark_ff::{Field, One, Zero};
36use ark_poly::{
37 univariate::DensePolynomial, EvaluationDomain, Evaluations, Polynomial,
38 Radix2EvaluationDomain as R2D,
39};
40use kimchi::{circuits::domains::EvaluationDomains, curve::KimchiCurve, plonk_sponge::FrSponge};
41use poly_commitment::{
42 commitment::{combined_inner_product, BatchEvaluationProof, CommitmentCurve, Evaluation},
43 ipa::{OpeningProof, SRS},
44 utils::DensePolynomialOrEvaluations,
45 PolyComm, SRS as _,
46};
47use rand::{CryptoRng, RngCore};
48
49#[derive(PartialEq, Eq)]
50pub struct CoreInstance {
52 pub comm_d: Curve,
54 pub comm_q: Curve,
56 pub comm_a: Curve,
58}
59
60#[derive(PartialEq, Eq)]
61pub struct RelaxedInstance {
63 pub core: CoreInstance,
65 pub u: ScalarField,
67 pub comm_e: Curve,
69}
70
71impl CoreInstance {
72 pub fn relax(self) -> RelaxedInstance {
73 RelaxedInstance {
74 core: self,
75 u: ScalarField::one(),
76 comm_e: Curve::zero(),
77 }
78 }
79}
80
81#[derive(PartialEq, Eq)]
82pub struct CoreWitness {
85 pub d: Evaluations<ScalarField, R2D<ScalarField>>,
86 pub q: Evaluations<ScalarField, R2D<ScalarField>>,
87 pub a: Evaluations<ScalarField, R2D<ScalarField>>,
88}
89
90#[derive(PartialEq, Eq)]
91pub struct RelaxedWitness {
94 pub core: CoreWitness,
95 pub e: Evaluations<ScalarField, R2D<ScalarField>>,
96}
97
98impl CoreWitness {
99 pub fn relax(self, domain: R2D<ScalarField>) -> RelaxedWitness {
100 RelaxedWitness {
101 core: self,
102 e: Evaluations::from_vec_and_domain(vec![ScalarField::zero(); domain.size()], domain),
103 }
104 }
105}
106
107impl RelaxedInstance {
108 pub fn check_in_language(
112 &self,
113 srs: &SRS<Curve>,
114 domain: R2D<ScalarField>,
115 wit: &RelaxedWitness,
116 ) -> bool {
117 for i in 0..SRS_SIZE {
118 if self.u * wit.core.a[i] - wit.core.q[i] * wit.core.d[i] + wit.e[i]
120 != ScalarField::zero()
121 {
122 return false;
123 }
124 }
125 if self.core.comm_a
126 != srs
127 .commit_evaluations_non_hiding(domain, &wit.core.a)
128 .chunks[0]
129 {
130 return false;
131 }
132 if self.core.comm_d
133 != srs
134 .commit_evaluations_non_hiding(domain, &wit.core.d)
135 .chunks[0]
136 {
137 return false;
138 }
139 if self.core.comm_q
140 != srs
141 .commit_evaluations_non_hiding(domain, &wit.core.q)
142 .chunks[0]
143 {
144 return false;
145 }
146 if self.comm_e != srs.commit_evaluations_non_hiding(domain, &wit.e).chunks[0] {
147 return false;
148 }
149 true
150 }
151}
152
153pub fn folding_prover(
154 srs: &SRS<Curve>,
155 domain: R2D<ScalarField>,
156 inst1: &CoreInstance,
157 wit1: &CoreWitness,
158 inst2: &RelaxedInstance,
159 wit2: &RelaxedWitness,
160) -> (RelaxedInstance, RelaxedWitness, Curve) {
161 let mut curve_sponge = CurveSponge::new(Curve::other_curve_sponge_params());
162
163 let cross_term: Evaluations<ScalarField, R2D<ScalarField>> =
164 &(&(&wit2.core.a + &(&wit1.a * inst2.u)) - &(&wit2.core.q * &wit1.d))
165 - &(&wit1.q * &wit2.core.d);
166
167 let cross_term_comm: Curve = srs
168 .commit_evaluations_non_hiding(domain, &cross_term.clone())
169 .chunks[0];
170
171 curve_sponge.absorb_g(&[
172 inst1.comm_d,
173 inst1.comm_q,
174 inst1.comm_a,
175 inst2.core.comm_d,
176 inst2.core.comm_q,
177 inst2.core.comm_a,
178 inst2.comm_e,
179 cross_term_comm,
180 ]);
181
182 let recombination_chal = curve_sponge.challenge();
183
184 let a3 = &wit1.a + &(&wit2.core.a * recombination_chal);
185 let q3 = &wit1.q + &(&wit2.core.q * recombination_chal);
186 let d3 = &wit1.d + &(&wit2.core.d * recombination_chal);
187
188 let comm_a3 = inst1.comm_a + inst2.core.comm_a * recombination_chal;
189 let comm_q3 = inst1.comm_q + inst2.core.comm_q * recombination_chal;
190 let comm_d3 = inst1.comm_d + inst2.core.comm_d * recombination_chal;
191
192 let new_u = ScalarField::one() + recombination_chal * inst2.u;
193
194 let e3 = &(&wit2.e * (recombination_chal * recombination_chal))
195 - &(&cross_term * recombination_chal);
196 let comm_e3 = inst2.comm_e * (recombination_chal * recombination_chal)
197 - cross_term_comm * recombination_chal;
198
199 let new_inst = RelaxedInstance {
200 u: new_u,
201 comm_e: comm_e3.into(),
202 core: CoreInstance {
203 comm_d: comm_d3.into(),
204 comm_q: comm_q3.into(),
205 comm_a: comm_a3.into(),
206 },
207 };
208
209 let new_wit = RelaxedWitness {
210 e: e3,
211 core: CoreWitness {
212 d: d3,
213 q: q3,
214 a: a3,
215 },
216 };
217
218 (new_inst, new_wit, cross_term_comm)
219}
220
221pub fn folding_verifier(
222 inst1: &CoreInstance,
223 inst2: &RelaxedInstance,
224 cross_term_comm: Curve,
225) -> RelaxedInstance {
226 let mut curve_sponge = CurveSponge::new(Curve::other_curve_sponge_params());
227 curve_sponge.absorb_g(&[
228 inst1.comm_d,
229 inst1.comm_q,
230 inst1.comm_a,
231 inst2.core.comm_d,
232 inst2.core.comm_q,
233 inst2.core.comm_a,
234 inst2.comm_e,
235 cross_term_comm,
236 ]);
237
238 let recombination_chal = curve_sponge.challenge();
239
240 let comm_a3 = inst1.comm_a + inst2.core.comm_a * recombination_chal;
241 let comm_q3 = inst1.comm_q + inst2.core.comm_q * recombination_chal;
242 let comm_d3 = inst1.comm_d + inst2.core.comm_d * recombination_chal;
243
244 let new_u = ScalarField::one() + recombination_chal * inst2.u;
245
246 let comm_e3 = inst2.comm_e * (recombination_chal * recombination_chal)
247 - cross_term_comm * recombination_chal;
248
249 RelaxedInstance {
250 u: new_u,
251 comm_e: comm_e3.into(),
252 core: CoreInstance {
253 comm_d: comm_d3.into(),
254 comm_q: comm_q3.into(),
255 comm_a: comm_a3.into(),
256 },
257 }
258}
259
260#[derive(Debug, Clone)]
261pub struct ReadProof {
263 pub quotient_comm: Curve,
265
266 pub data_eval: ScalarField,
268 pub query_eval: ScalarField,
270 pub answer_eval: ScalarField,
272 pub error_eval: ScalarField,
274
275 pub opening_proof: OpeningProof<Curve>,
277}
278
279pub fn prove_relaxed<RNG>(
280 srs: &SRS<Curve>,
281 domain: EvaluationDomains<ScalarField>,
282 group_map: &<Curve as CommitmentCurve>::Map,
283 rng: &mut RNG,
284 inst: &RelaxedInstance,
285 wit: &RelaxedWitness,
286) -> ReadProof
287where
288 RNG: RngCore + CryptoRng,
289{
290 let mut curve_sponge = CurveSponge::new(Curve::other_curve_sponge_params());
291
292 let data_poly: DensePolynomial<ScalarField> = wit.core.d.interpolate_by_ref();
293 let query_poly: DensePolynomial<ScalarField> = wit.core.q.interpolate_by_ref();
294 let answer_poly: DensePolynomial<ScalarField> = wit.core.a.interpolate_by_ref();
295 let error_poly: DensePolynomial<ScalarField> = wit.e.interpolate_by_ref();
296
297 curve_sponge.absorb_g(&[
298 inst.core.comm_d,
299 inst.core.comm_q,
300 inst.core.comm_a,
301 inst.comm_e,
302 ]);
303
304 let quotient_poly: DensePolynomial<ScalarField> = {
306 let data_d2 = data_poly.evaluate_over_domain_by_ref(domain.d2);
307 let query_d2 = query_poly.evaluate_over_domain_by_ref(domain.d2);
308 let answer_d2 = answer_poly.evaluate_over_domain_by_ref(domain.d2);
309 let error_d2 = error_poly.evaluate_over_domain_by_ref(domain.d2);
310
311 let numerator_eval: Evaluations<ScalarField, R2D<ScalarField>> =
313 &(&(&answer_d2 * inst.u) - &(&data_d2 * &query_d2)) + &error_d2;
314
315 let numerator_eval_interpolated = numerator_eval.interpolate();
316
317 let fail_final_q_division = || panic!("Division by vanishing poly must not fail");
318 let (quotient, res) = numerator_eval_interpolated.divide_by_vanishing_poly(domain.d1);
321 if !res.is_zero() {
325 fail_final_q_division();
326 }
327
328 quotient
329 };
330
331 let quotient_comm = srs.commit_non_hiding("ient_poly, 1).chunks[0];
334 curve_sponge.absorb_g(&[quotient_comm]);
335
336 let evaluation_point = curve_sponge.challenge();
338
339 let mut scalar_sponge = CurveScalarSponge::new(Curve::sponge_params());
341 scalar_sponge.absorb(&curve_sponge.clone().digest());
342
343 let data_eval = data_poly.evaluate(&evaluation_point);
344 let query_eval = query_poly.evaluate(&evaluation_point);
345 let answer_eval = answer_poly.evaluate(&evaluation_point);
346 let error_eval = error_poly.evaluate(&evaluation_point);
347 let quotient_eval = quotient_poly.evaluate(&evaluation_point);
348
349 for eval in [
350 data_eval,
351 query_eval,
352 answer_eval,
353 error_eval,
354 quotient_eval,
355 ]
356 .into_iter()
357 {
358 scalar_sponge.absorb(&eval);
359 }
360
361 let (_, endo_r) = Curve::endos();
362 let polyscale = scalar_sponge.challenge().to_field(endo_r);
364 let evalscale = scalar_sponge.challenge().to_field(endo_r);
365
366 let opening_proof_inputs: Vec<_> = {
369 let coefficients_form =
370 DensePolynomialOrEvaluations::<_, R2D<ScalarField>>::DensePolynomial;
371 let non_hiding = |n_chunks| PolyComm {
372 chunks: vec![ScalarField::zero(); n_chunks],
373 };
374
375 vec![
376 (coefficients_form(&data_poly), non_hiding(1)),
377 (coefficients_form(&query_poly), non_hiding(1)),
378 (coefficients_form(&answer_poly), non_hiding(1)),
379 (coefficients_form(&error_poly), non_hiding(1)),
380 (coefficients_form("ient_poly), non_hiding(1)),
381 ]
382 };
383
384 let opening_proof = srs.open(
385 group_map,
386 opening_proof_inputs.as_slice(),
387 &[evaluation_point],
388 polyscale,
389 evalscale,
390 curve_sponge,
391 rng,
392 );
393
394 ReadProof {
395 quotient_comm,
396 data_eval,
397 query_eval,
398 answer_eval,
399 error_eval,
400 opening_proof,
401 }
402}
403
404pub fn verify_relaxed<RNG>(
405 srs: &SRS<Curve>,
406 domain: EvaluationDomains<ScalarField>,
407 group_map: &<Curve as CommitmentCurve>::Map,
408 rng: &mut RNG,
409 inst: &RelaxedInstance,
410 proof: &ReadProof,
411) -> bool
412where
413 RNG: RngCore + CryptoRng,
414{
415 let mut curve_sponge = CurveSponge::new(Curve::other_curve_sponge_params());
416 curve_sponge.absorb_g(&[
417 inst.core.comm_d,
418 inst.core.comm_q,
419 inst.core.comm_a,
420 inst.comm_e,
421 ]);
422 curve_sponge.absorb_g(&[proof.quotient_comm]);
423
424 let evaluation_point = curve_sponge.challenge();
425
426 let mut scalar_sponge = CurveScalarSponge::new(Curve::sponge_params());
427 scalar_sponge.absorb(&curve_sponge.clone().digest());
428
429 let vanishing_poly_at_zeta = domain.d1.vanishing_polynomial().evaluate(&evaluation_point);
430 let quotient_eval = {
431 (inst.u * proof.answer_eval - proof.data_eval * proof.query_eval + proof.error_eval)
432 * vanishing_poly_at_zeta
433 .inverse()
434 .unwrap_or_else(|| panic!("Inverse fails only with negligible probability"))
435 };
436
437 for eval in [
438 proof.data_eval,
439 proof.query_eval,
440 proof.answer_eval,
441 proof.error_eval,
442 quotient_eval,
443 ]
444 .into_iter()
445 {
446 scalar_sponge.absorb(&eval);
447 }
448
449 let (_, endo_r) = Curve::endos();
450 let polyscale = scalar_sponge.challenge().to_field(endo_r);
452 let evalscale = scalar_sponge.challenge().to_field(endo_r);
453
454 let coms_and_evaluations = vec![
455 Evaluation {
456 commitment: PolyComm {
457 chunks: vec![inst.core.comm_d],
458 },
459 evaluations: vec![vec![proof.data_eval]],
460 },
461 Evaluation {
462 commitment: PolyComm {
463 chunks: vec![inst.core.comm_q],
464 },
465 evaluations: vec![vec![proof.query_eval]],
466 },
467 Evaluation {
468 commitment: PolyComm {
469 chunks: vec![inst.core.comm_a],
470 },
471 evaluations: vec![vec![proof.answer_eval]],
472 },
473 Evaluation {
474 commitment: PolyComm {
475 chunks: vec![inst.comm_e],
476 },
477 evaluations: vec![vec![proof.error_eval]],
478 },
479 Evaluation {
480 commitment: PolyComm {
481 chunks: vec![proof.quotient_comm],
482 },
483 evaluations: vec![vec![quotient_eval]],
484 },
485 ];
486 let combined_inner_product = {
487 let evaluations: Vec<_> = coms_and_evaluations
488 .iter()
489 .map(|Evaluation { evaluations, .. }| evaluations.clone())
490 .collect();
491
492 combined_inner_product(&polyscale, &evalscale, evaluations.as_slice())
493 };
494
495 srs.verify(
496 group_map,
497 &mut [BatchEvaluationProof {
498 sponge: curve_sponge,
499 evaluation_points: vec![evaluation_point],
500 polyscale,
501 evalscale,
502 evaluations: coms_and_evaluations,
503 opening: &proof.opening_proof,
504 combined_inner_product,
505 }],
506 rng,
507 )
508}
509
510pub mod testing {
511 use super::*;
512 use crate::{Curve, ScalarField};
513 use ark_ff::UniformRand;
514 use ark_poly::Evaluations;
515 use poly_commitment::ipa::SRS;
516 use rand::Rng;
517
518 pub fn generate_random_inst_wit_core<RNG>(
520 srs: &SRS<Curve>,
521 domain: R2D<ScalarField>,
522 rng: &mut RNG,
523 ) -> (CoreInstance, CoreWitness)
524 where
525 RNG: RngCore + CryptoRng,
526 {
527 let data: Vec<ScalarField> = {
528 let mut data = vec![];
529 (0..domain.size).for_each(|_| data.push(ScalarField::rand(rng)));
530 data
531 };
532
533 let data_comm: Curve = srs
534 .commit_evaluations_non_hiding(
535 domain,
536 &Evaluations::from_vec_and_domain(data.clone(), domain),
537 )
538 .chunks[0];
539
540 let query: Vec<ScalarField> = {
541 let mut query = vec![];
542 (0..domain.size)
543 .for_each(|_| query.push(ScalarField::from(rand::thread_rng().gen::<f64>() < 0.1)));
544 query
545 };
546
547 let answer: Vec<ScalarField> = data
548 .clone()
549 .iter()
550 .zip(query.iter())
551 .map(|(d, q)| *d * q)
552 .collect();
553
554 let comm_q = srs
555 .commit_evaluations_non_hiding(
556 domain,
557 &Evaluations::from_vec_and_domain(query.clone(), domain),
558 )
559 .chunks[0];
560
561 let comm_a = srs
562 .commit_evaluations_non_hiding(
563 domain,
564 &Evaluations::from_vec_and_domain(answer.clone(), domain),
565 )
566 .chunks[0];
567
568 let core_instance = CoreInstance {
569 comm_d: data_comm,
570 comm_q,
571 comm_a,
572 };
573
574 let core_witness = CoreWitness {
575 d: Evaluations::from_vec_and_domain(data, domain),
576 q: Evaluations::from_vec_and_domain(query, domain),
577 a: Evaluations::from_vec_and_domain(answer, domain),
578 };
579
580 (core_instance, core_witness)
581 }
582
583 pub fn generate_random_inst_wit_relaxed<RNG>(
587 srs: &SRS<Curve>,
588 domain: R2D<ScalarField>,
589 rng: &mut RNG,
590 ) -> (RelaxedInstance, RelaxedWitness)
591 where
592 RNG: RngCore + CryptoRng,
593 {
594 let (inst, wit) = generate_random_inst_wit_core(srs, domain, rng);
595 let u = ScalarField::rand(rng);
596 let e = &(&wit.d * &wit.q) - &(&wit.a * u);
597 let comm_e = srs.commit_evaluations_non_hiding(domain, &e).chunks[0];
598
599 let relaxed_instance = RelaxedInstance {
600 core: inst,
601 u,
602 comm_e,
603 };
604
605 let relaxed_witness = RelaxedWitness { core: wit, e };
606
607 assert!(relaxed_instance.check_in_language(srs, domain, &relaxed_witness));
608
609 (relaxed_instance, relaxed_witness)
610 }
611}
612
613#[cfg(test)]
614mod tests {
615 use super::{testing::generate_random_inst_wit_core, *};
616 use crate::{Curve, ScalarField};
617 use ark_ec::AffineRepr;
618 use ark_ff::One;
619 use kimchi::{circuits::domains::EvaluationDomains, groupmap::GroupMap};
620 use poly_commitment::commitment::CommitmentCurve;
621
622 #[test]
623 fn test_folding_read_proof_completeness_soundness() {
624 let mut rng = o1_utils::tests::make_test_rng(None);
625
626 let srs = poly_commitment::precomputed_srs::get_srs_test();
627 let domain: EvaluationDomains<ScalarField> =
628 EvaluationDomains::<ScalarField>::create(srs.size()).unwrap();
629 let group_map = <Curve as CommitmentCurve>::Map::setup();
630
631 let (core_instance_1, core_witness_1) =
632 generate_random_inst_wit_core(&srs, domain.d1, &mut rng);
633 let (core_instance_2, core_witness_2) =
634 generate_random_inst_wit_core(&srs, domain.d1, &mut rng);
635 let relaxed_instance_2 = core_instance_2.relax();
636 let relaxed_witness_2 = core_witness_2.relax(domain.d1);
637
638 assert!(relaxed_instance_2.check_in_language(&srs, domain.d1, &relaxed_witness_2));
639
640 let (relaxed_instance_3, relaxed_witness_3, cross_term_1) = folding_prover(
641 &srs,
642 domain.d1,
643 &core_instance_1,
644 &core_witness_1,
645 &relaxed_instance_2,
646 &relaxed_witness_2,
647 );
648
649 assert!(relaxed_instance_3.check_in_language(&srs, domain.d1, &relaxed_witness_3));
650
651 assert!(
652 folding_verifier(&core_instance_1, &relaxed_instance_2, cross_term_1)
653 == relaxed_instance_3
654 );
655
656 let (core_instance_4, core_witness_4) =
657 generate_random_inst_wit_core(&srs, domain.d1, &mut rng);
658 let (relaxed_instance_5, relaxed_witness_5, cross_term_2) = folding_prover(
659 &srs,
660 domain.d1,
661 &core_instance_4,
662 &core_witness_4,
663 &relaxed_instance_3,
664 &relaxed_witness_3,
665 );
666
667 assert!(relaxed_instance_5.check_in_language(&srs, domain.d1, &relaxed_witness_5));
668
669 assert!(
670 folding_verifier(&core_instance_4, &relaxed_instance_3, cross_term_2)
671 == relaxed_instance_5
672 );
673
674 let proof = prove_relaxed(
675 &srs,
676 domain,
677 &group_map,
678 &mut rng,
679 &relaxed_instance_5,
680 &relaxed_witness_5,
681 );
682 let res = verify_relaxed(
683 &srs,
684 domain,
685 &group_map,
686 &mut rng,
687 &relaxed_instance_5,
688 &proof,
689 );
690
691 assert!(res, "Completeness: Proof must verify");
692
693 let proof_malformed_1 = ReadProof {
694 quotient_comm: Curve::zero(),
695 ..proof.clone()
696 };
697
698 let res_1 = verify_relaxed(
699 &srs,
700 domain,
701 &group_map,
702 &mut rng,
703 &relaxed_instance_5,
704 &proof_malformed_1,
705 );
706
707 assert!(!res_1, "Soundness: Malformed proof #1 must NOT verify");
708
709 let proof_malformed_2 = ReadProof {
710 query_eval: ScalarField::one(),
711 ..proof.clone()
712 };
713
714 let res_2 = verify_relaxed(
715 &srs,
716 domain,
717 &group_map,
718 &mut rng,
719 &relaxed_instance_5,
720 &proof_malformed_2,
721 );
722
723 assert!(!res_2, "Soundness: Malformed proof #2 must NOT verify");
724 }
725}