1//! Sumcheck based batch opening and verify commitment.
  2// TODO: refactoring this code to somewhere else
  3// currently IOP depends on PCS because perm check requires commitment.
  4// The sumcheck based batch opening therefore cannot stay in the PCS repo --
  5// which creates a cyclic dependency.
  6
  7use crate::{
  8    pcs::{
  9        multilinear_kzg::util::eq_eval,
 10        prelude::{Commitment, PCSError},
 11        PolynomialCommitmentScheme,
 12    },
 13    poly_iop::{prelude::SumCheck, PolyIOP},
 14    IOPProof,
 15};
 16use arithmetic::{build_eq_x_r_vec, DenseMultilinearExtension, VPAuxInfo, VirtualPolynomial};
 17use ark_ec::{AffineCurve, PairingEngine, ProjectiveCurve};
 18use ark_std::{end_timer, log2, start_timer, One, Zero};
 19use std::{marker::PhantomData, rc::Rc};
 20use transcript::IOPTranscript;
 21
 22#[derive(Clone, Debug, Default, PartialEq, Eq)]
 23pub struct BatchProof<E, PCS>
 24where
 25    E: PairingEngine,
 26    PCS: PolynomialCommitmentScheme<E>,
 27{
 28    /// A sum check proof proving tilde g's sum
 29    pub(crate) sum_check_proof: IOPProof<E::Fr>,
 30    /// f_i(point_i)
 31    pub f_i_eval_at_point_i: Vec<E::Fr>,
 32    /// proof for g'(a_2)
 33    pub(crate) g_prime_proof: PCS::Proof,
 34}
 35
 36/// Steps:
 37/// 1. get challenge point t from transcript
 38/// 2. build eq(t,i) for i in [0..k]
 39/// 3. build \tilde g_i(b) = eq(t, i) * f_i(b)
 40/// 4. compute \tilde eq_i(b) = eq(b, point_i)
 41/// 5. run sumcheck on \sum_i=1..k \tilde eq_i * \tilde g_i
 42/// 6. build g'(X) = \sum_i=1..k \tilde eq_i(a2) * \tilde g_i(X) where (a2) is
 43/// the sumcheck's point 7. open g'(X) at point (a2)
 44pub(crate) fn multi_open_internal<E, PCS>(
 45    prover_param: &PCS::ProverParam,
 46    polynomials: &[PCS::Polynomial],
 47    points: &[PCS::Point],
 48    evals: &[PCS::Evaluation],
 49    transcript: &mut IOPTranscript<E::Fr>,
 50) -> Result<BatchProof<E, PCS>, PCSError>
 51where
 52    E: PairingEngine,
 53    PCS: PolynomialCommitmentScheme<
 54        E,
 55        Polynomial = Rc<DenseMultilinearExtension<E::Fr>>,
 56        Point = Vec<E::Fr>,
 57        Evaluation = E::Fr,
 58    >,
 59{
 60    let open_timer = start_timer!(|| format!("multi open {} points", points.len()));
 61
 62    // TODO: sanity checks
 63    let num_var = polynomials[0].num_vars;
 64    let k = polynomials.len();
 65    let ell = log2(k) as usize;
 66
 67    // challenge point t
 68    let t = transcript.get_and_append_challenge_vectors("t".as_ref(), ell)?;
 69
 70    // eq(t, i) for i in [0..k]
 71    let eq_t_i_list = build_eq_x_r_vec(t.as_ref())?;
 72
 73    // \tilde g_i(b) = eq(t, i) * f_i(b)
 74    let timer = start_timer!(|| format!("compute tilde g for {} points", points.len()));
 75    let mut tilde_gs = vec![];
 76    for (index, f_i) in polynomials.iter().enumerate() {
 77        let mut tilde_g_eval = vec![E::Fr::zero(); 1 << num_var];
 78        for (j, &f_i_eval) in f_i.iter().enumerate() {
 79            tilde_g_eval[j] = f_i_eval * eq_t_i_list[index];
 80        }
 81        tilde_gs.push(Rc::new(DenseMultilinearExtension::from_evaluations_vec(
 82            num_var,
 83            tilde_g_eval,
 84        )));
 85    }
 86    end_timer!(timer);
 87
 88    let timer = start_timer!(|| format!("compute tilde eq for {} points", points.len()));
 89    let mut tilde_eqs = vec![];
 90    for point in points.iter() {
 91        let eq_b_zi = build_eq_x_r_vec(point)?;
 92        tilde_eqs.push(Rc::new(DenseMultilinearExtension::from_evaluations_vec(
 93            num_var, eq_b_zi,
 94        )));
 95    }
 96    end_timer!(timer);
 97
 98    // built the virtual polynomial for SumCheck
 99    let timer = start_timer!(|| format!("sum check prove of {} variables", num_var));
100
101    let step = start_timer!(|| "add mle");
102    let mut sum_check_vp = VirtualPolynomial::new(num_var);
103    for (tilde_g, tilde_eq) in tilde_gs.iter().zip(tilde_eqs.into_iter()) {
104        sum_check_vp.add_mle_list([tilde_g.clone(), tilde_eq], E::Fr::one())?;
105    }
106    end_timer!(step);
107
108    let proof = match <PolyIOP<E::Fr> as SumCheck<E::Fr>>::prove(&sum_check_vp, transcript) {
109        Ok(p) => p,
110        Err(_e) => {
111            // cannot wrap IOPError with PCSError due to cyclic dependency
112            return Err(PCSError::InvalidProver(
113                "Sumcheck in batch proving Failed".to_string(),
114            ));
115        },
116    };
117
118    end_timer!(timer);
119
120    // a2 := sumcheck's point
121    let a2 = &proof.point[..num_var];
122
123    // build g'(X) = \sum_i=1..k \tilde eq_i(a2) * \tilde g_i(X) where (a2) is the
124    // sumcheck's point \tilde eq_i(a2) = eq(a2, point_i)
125    let step = start_timer!(|| "evaluate at a2");
126    let mut g_prime_evals = vec![E::Fr::zero(); 1 << num_var];
127    for (tilde_g, point) in tilde_gs.iter().zip(points.iter()) {
128        let eq_i_a2 = eq_eval(a2, point)?;
129        for (j, &tilde_g_eval) in tilde_g.iter().enumerate() {
130            g_prime_evals[j] += tilde_g_eval * eq_i_a2;
131        }
132    }
133    let g_prime = Rc::new(DenseMultilinearExtension::from_evaluations_vec(
134        num_var,
135        g_prime_evals,
136    ));
137    end_timer!(step);
138
139    let step = start_timer!(|| "pcs open");
140    let (g_prime_proof, _g_prime_eval) = PCS::open(prover_param, &g_prime, a2.to_vec().as_ref())?;
141    // assert_eq!(g_prime_eval, tilde_g_eval);
142    end_timer!(step);
143
144    let step = start_timer!(|| "evaluate fi(pi)");
145    end_timer!(step);
146    end_timer!(open_timer);
147
148    Ok(BatchProof {
149        sum_check_proof: proof,
150        f_i_eval_at_point_i: evals.to_vec(),
151        g_prime_proof,
152    })
153}
154
155/// Steps:
156/// 1. get challenge point t from transcript
157/// 2. build g' commitment
158/// 3. ensure \sum_i eq(a2, point_i) * eq(t, <i>) * f_i_evals matches the sum
159/// via SumCheck verification 4. verify commitment
160pub(crate) fn batch_verify_internal<E, PCS>(
161    verifier_param: &PCS::VerifierParam,
162    f_i_commitments: &[Commitment<E>],
163    points: &[PCS::Point],
164    proof: &BatchProof<E, PCS>,
165    transcript: &mut IOPTranscript<E::Fr>,
166) -> Result<bool, PCSError>
167where
168    E: PairingEngine,
169    PCS: PolynomialCommitmentScheme<
170        E,
171        Polynomial = Rc<DenseMultilinearExtension<E::Fr>>,
172        Point = Vec<E::Fr>,
173        Evaluation = E::Fr,
174        Commitment = Commitment<E>,
175    >,
176{
177    let open_timer = start_timer!(|| "batch verification");
178
179    // TODO: sanity checks
180
181    let k = f_i_commitments.len();
182    let ell = log2(k) as usize;
183    let num_var = proof.sum_check_proof.point.len();
184
185    // challenge point t
186    let t = transcript.get_and_append_challenge_vectors("t".as_ref(), ell)?;
187
188    // sum check point (a2)
189    let a2 = &proof.sum_check_proof.point[..num_var];
190
191    // build g' commitment
192    let eq_t_list = build_eq_x_r_vec(t.as_ref())?;
193
194    let mut g_prime_commit = E::G1Affine::zero().into_projective();
195
196    for (i, point) in points.iter().enumerate() {
197        let eq_i_a2 = eq_eval(a2, point)?;
198        let tmp = eq_i_a2 * eq_t_list[i];
199        g_prime_commit += &f_i_commitments[i].0.mul(tmp);
200    }
201
202    // ensure \sum_i eq(t, <i>) * f_i_evals matches the sum via SumCheck
203    let mut sum = E::Fr::zero();
204    for (i, &e) in eq_t_list.iter().enumerate().take(k) {
205        sum += e * proof.f_i_eval_at_point_i[i];
206    }
207    let aux_info = VPAuxInfo {
208        max_degree: 2,
209        num_variables: num_var,
210        phantom: PhantomData,
211    };
212    let subclaim = match <PolyIOP<E::Fr> as SumCheck<E::Fr>>::verify(
213        sum,
214        &proof.sum_check_proof,
215        &aux_info,
216        transcript,
217    ) {
218        Ok(p) => p,
219        Err(_e) => {
220            // cannot wrap IOPError with PCSError due to cyclic dependency
221            return Err(PCSError::InvalidProver(
222                "Sumcheck in batch verification failed".to_string(),
223            ));
224        },
225    };
226    let tilde_g_eval = subclaim.expected_evaluation;
227
228    // verify commitment
229    let res = PCS::verify(
230        verifier_param,
231        &Commitment(g_prime_commit.into_affine()),
232        a2.to_vec().as_ref(),
233        &tilde_g_eval,
234        &proof.g_prime_proof,
235    )?;
236
237    end_timer!(open_timer);
238    Ok(res)
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244    use crate::pcs::{
245        prelude::{MultilinearKzgPCS, MultilinearUniversalParams},
246        StructuredReferenceString,
247    };
248    use arithmetic::get_batched_nv;
249    use ark_bls12_381::Bls12_381 as E;
250    use ark_ec::PairingEngine;
251    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
252    use ark_std::{
253        rand::{CryptoRng, RngCore},
254        test_rng,
255        vec::Vec,
256        UniformRand,
257    };
258
259    type Fr = <E as PairingEngine>::Fr;
260
261    fn test_multi_open_helper<R: RngCore + CryptoRng>(
262        ml_params: &MultilinearUniversalParams<E>,
263        polys: &[Rc<DenseMultilinearExtension<Fr>>],
264        rng: &mut R,
265    ) -> Result<(), PCSError> {
266        let merged_nv = get_batched_nv(polys[0].num_vars(), polys.len());
267        let (ml_ck, ml_vk) = ml_params.trim(merged_nv)?;
268
269        let mut points = Vec::new();
270        for poly in polys.iter() {
271            let point = (0..poly.num_vars())
272                .map(|_| Fr::rand(rng))
273                .collect::<Vec<Fr>>();
274            points.push(point);
275        }
276
277        let evals = polys
278            .iter()
279            .zip(points.iter())
280            .map(|(f, p)| f.evaluate(p).unwrap())
281            .collect::<Vec<_>>();
282
283        let commitments = polys
284            .iter()
285            .map(|poly| MultilinearKzgPCS::commit(&ml_ck.clone(), poly).unwrap())
286            .collect::<Vec<_>>();
287
288        let mut transcript = IOPTranscript::new("test transcript".as_ref());
289        transcript.append_field_element("init".as_ref(), &Fr::zero())?;
290
291        let batch_proof = multi_open_internal::<E, MultilinearKzgPCS<E>>(
292            &ml_ck,
293            polys,
294            &points,
295            &evals,
296            &mut transcript,
297        )?;
298
299        // good path
300        let mut transcript = IOPTranscript::new("test transcript".as_ref());
301        transcript.append_field_element("init".as_ref(), &Fr::zero())?;
302        assert!(batch_verify_internal::<E, MultilinearKzgPCS<E>>(
303            &ml_vk,
304            &commitments,
305            &points,
306            &batch_proof,
307            &mut transcript
308        )?);
309
310        Ok(())
311    }
312
313    #[test]
314    fn test_multi_open_internal() -> Result<(), PCSError> {
315        let mut rng = test_rng();
316
317        let ml_params = MultilinearUniversalParams::<E>::gen_srs_for_testing(&mut rng, 20)?;
318        for num_poly in 5..6 {
319            for nv in 15..16 {
320                let polys1: Vec<_> = (0..num_poly)
321                    .map(|_| Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)))
322                    .collect();
323                test_multi_open_helper(&ml_params, &polys1, &mut rng)?;
324            }
325        }
326
327        Ok(())
328    }
329}