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::{
 17    build_eq_x_r_vec, fix_last_variables, DenseMultilinearExtension, VPAuxInfo, VirtualPolynomial,
 18};
 19use ark_ec::{AffineCurve, PairingEngine, ProjectiveCurve};
 20use ark_std::{end_timer, log2, start_timer, One, Zero};
 21use std::{marker::PhantomData, rc::Rc};
 22use transcript::IOPTranscript;
 23
 24#[derive(Clone, Debug, Default, PartialEq, Eq)]
 25pub struct BatchProof<E, PCS>
 26where
 27    E: PairingEngine,
 28    PCS: PolynomialCommitmentScheme<E>,
 29{
 30    /// A sum check proof proving tilde g's sum
 31    pub(crate) sum_check_proof: IOPProof<E::Fr>,
 32    /// f_i(point_i)
 33    pub f_i_eval_at_point_i: Vec<E::Fr>,
 34    /// proof for g'(a_2)
 35    pub(crate) g_prime_proof: PCS::Proof,
 36}
 37
 38/// Steps:
 39/// 1. get challenge point t from transcript
 40/// 2. build eq(t,i) for i in [0..k]
 41/// 3. build \tilde g(i, b) = eq(t, i) * f_i(b)
 42/// 4. compute \tilde eq
 43/// 5. run sumcheck on \tilde eq * \tilde g(i, b)
 44/// 6. build g'(a2) where (a1, a2) is the sumcheck's point
 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 = Rc<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    let merged_num_var = num_var + ell;
 68
 69    // challenge point t
 70    let t = transcript.get_and_append_challenge_vectors("t".as_ref(), ell)?;
 71
 72    // eq(t, i) for i in [0..k]
 73    let eq_t_i_list = build_eq_x_r_vec(t.as_ref())?;
 74
 75    // \tilde g(i, b) = eq(t, i) * f_i(b)
 76    let timer = start_timer!(|| format!("compute tilde g for {} points", points.len()));
 77    let mut tilde_g_eval = vec![E::Fr::zero(); 1 << (ell + num_var)];
 78    let block_size = 1 << num_var;
 79    for (index, f_i) in polynomials.iter().enumerate() {
 80        for (j, &f_i_eval) in f_i.iter().enumerate() {
 81            tilde_g_eval[index * block_size + j] = f_i_eval * eq_t_i_list[index];
 82        }
 83    }
 84    let tilde_g = Rc::new(DenseMultilinearExtension::from_evaluations_vec(
 85        merged_num_var,
 86        tilde_g_eval,
 87    ));
 88    end_timer!(timer);
 89
 90    let timer = start_timer!(|| format!("compute tilde eq for {} points", points.len()));
 91    let mut tilde_eq_eval = vec![E::Fr::zero(); 1 << (ell + num_var)];
 92    for (index, point) in points.iter().enumerate() {
 93        let eq_b_zi = build_eq_x_r_vec(point)?;
 94        let start = index * block_size;
 95        tilde_eq_eval[start..start + block_size].copy_from_slice(eq_b_zi.as_slice());
 96    }
 97    let tilde_eq = Rc::new(DenseMultilinearExtension::from_evaluations_vec(
 98        merged_num_var,
 99        tilde_eq_eval,
100    ));
101    end_timer!(timer);
102
103    // built the virtual polynomial for SumCheck
104    let timer = start_timer!(|| format!("sum check prove of {} variables", num_var + ell));
105
106    let step = start_timer!(|| "add mle");
107    let mut sum_check_vp = VirtualPolynomial::new(num_var + ell);
108    sum_check_vp.add_mle_list([tilde_g.clone(), tilde_eq], E::Fr::one())?;
109    end_timer!(step);
110
111    let proof = match <PolyIOP<E::Fr> as SumCheck<E::Fr>>::prove(&sum_check_vp, transcript) {
112        Ok(p) => p,
113        Err(_e) => {
114            // cannot wrap IOPError with PCSError due to cyclic dependency
115            return Err(PCSError::InvalidProver(
116                "Sumcheck in batch proving Failed".to_string(),
117            ));
118        },
119    };
120
121    end_timer!(timer);
122
123    // (a1, a2) := sumcheck's point
124    let step = start_timer!(|| "open at a2");
125    let a1 = &proof.point[num_var..];
126    let a2 = &proof.point[..num_var];
127    end_timer!(step);
128
129    // build g'(a2)
130    let step = start_timer!(|| "evaluate at a2");
131    let g_prime = Rc::new(fix_last_variables(&tilde_g, a1));
132    end_timer!(step);
133
134    let step = start_timer!(|| "pcs open");
135    let (g_prime_proof, _g_prime_eval) = PCS::open(prover_param, &g_prime, a2.to_vec().as_ref())?;
136    // assert_eq!(g_prime_eval, tilde_g_eval);
137    end_timer!(step);
138
139    let step = start_timer!(|| "evaluate fi(pi)");
140    end_timer!(step);
141    end_timer!(open_timer);
142
143    Ok(BatchProof {
144        sum_check_proof: proof,
145        f_i_eval_at_point_i: evals.to_vec(),
146        g_prime_proof,
147    })
148}
149
150/// Steps:
151/// 1. get challenge point t from transcript
152/// 2. build g' commitment
153/// 3. ensure \sum_i eq(t, <i>) * f_i_evals matches the sum via SumCheck
154/// verification 4. verify commitment
155pub(crate) fn batch_verify_internal<E, PCS>(
156    verifier_param: &PCS::VerifierParam,
157    f_i_commitments: &[Commitment<E>],
158    points: &[PCS::Point],
159    proof: &BatchProof<E, PCS>,
160    transcript: &mut IOPTranscript<E::Fr>,
161) -> Result<bool, PCSError>
162where
163    E: PairingEngine,
164    PCS: PolynomialCommitmentScheme<
165        E,
166        Polynomial = Rc<DenseMultilinearExtension<E::Fr>>,
167        Point = Vec<E::Fr>,
168        Evaluation = E::Fr,
169        Commitment = Commitment<E>,
170    >,
171{
172    let open_timer = start_timer!(|| "batch verification");
173
174    // TODO: sanity checks
175
176    let k = f_i_commitments.len();
177    let ell = log2(k) as usize;
178    let num_var = proof.sum_check_proof.point.len() - ell;
179
180    // challenge point t
181    let t = transcript.get_and_append_challenge_vectors("t".as_ref(), ell)?;
182
183    // sum check point (a1, a2)
184    let a1 = &proof.sum_check_proof.point[num_var..];
185    let a2 = &proof.sum_check_proof.point[..num_var];
186
187    // build g' commitment
188    let eq_a1_list = build_eq_x_r_vec(a1)?;
189    let eq_t_list = build_eq_x_r_vec(t.as_ref())?;
190
191    let mut g_prime_commit = E::G1Affine::zero().into_projective();
192    for i in 0..k {
193        let tmp = eq_a1_list[i] * eq_t_list[i];
194        g_prime_commit += &f_i_commitments[i].0.mul(tmp);
195    }
196
197    // ensure \sum_i eq(t, <i>) * f_i_evals matches the sum via SumCheck
198    // verification
199    let mut sum = E::Fr::zero();
200    for (i, &e) in eq_t_list.iter().enumerate().take(k) {
201        sum += e * proof.f_i_eval_at_point_i[i];
202    }
203    let aux_info = VPAuxInfo {
204        max_degree: 2,
205        num_variables: num_var + ell,
206        phantom: PhantomData,
207    };
208    let subclaim = match <PolyIOP<E::Fr> as SumCheck<E::Fr>>::verify(
209        sum,
210        &proof.sum_check_proof,
211        &aux_info,
212        transcript,
213    ) {
214        Ok(p) => p,
215        Err(_e) => {
216            // cannot wrap IOPError with PCSError due to cyclic dependency
217            return Err(PCSError::InvalidProver(
218                "Sumcheck in batch verification failed".to_string(),
219            ));
220        },
221    };
222    let mut eq_tilde_eval = E::Fr::zero();
223    for (point, &coef) in points.iter().zip(eq_a1_list.iter()) {
224        eq_tilde_eval += coef * eq_eval(a2, point)?;
225    }
226    let tilde_g_eval = subclaim.expected_evaluation / eq_tilde_eval;
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}