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