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