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