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