hyperplonk/pcs/src/multilinear_kzg/batching.rs
pcs/src/multilinear_kzg/batching.rsRaw
1use super::{
2 open_internal,
3 srs::{MultilinearProverParam, MultilinearVerifierParam},
4 util::{build_l, compute_w_circ_l, merge_polynomials},
5 verify_internal, BatchProof,
6};
7use crate::{
8 multilinear_kzg::util::get_uni_domain,
9 prelude::{Commitment, UnivariateProverParam, UnivariateVerifierParam},
10 univariate_kzg::KZGUnivariatePCS,
11 PCSErrors, PolynomialCommitmentScheme,
12};
13use ark_ec::PairingEngine;
14use ark_poly::{DenseMultilinearExtension, EvaluationDomain, MultilinearExtension, Polynomial};
15use ark_std::{end_timer, rc::Rc, start_timer, vec::Vec};
16use transcript::IOPTranscript;
17
18/// Input
19/// - the prover parameters for univariate KZG,
20/// - the prover parameters for multilinear KZG,
21/// - a list of MLEs,
22/// - a commitment to all MLEs
23/// - and a same number of points,
24/// compute a multi-opening for all the polynomials.
25///
26/// For simplicity, this API requires each MLE to have only one point. If
27/// the caller wish to use more than one points per MLE, it should be
28/// handled at the caller layer.
29///
30/// Returns an error if the lengths do not match.
31///
32/// Returns the proof, consists of
33/// - the multilinear KZG opening
34/// - the univariate KZG commitment to q(x)
35/// - the openings and evaluations of q(x) at omega^i and r
36///
37/// Steps:
38/// 1. build `l(points)` which is a list of univariate polynomials that goes
39/// through the points
40/// 2. build MLE `w` which is the merge of all MLEs.
41/// 3. build `q(x)` which is a univariate polynomial `W circ l`
42/// 4. commit to q(x) and sample r from transcript
43/// transcript contains: w commitment, points, q(x)'s commitment
44/// 5. build q(omega^i) and their openings
45/// 6. build q(r) and its opening
46/// 7. get a point `p := l(r)`
47/// 8. output an opening of `w` over point `p`
48/// 9. output `w(p)`
49pub(super) fn multi_open_internal<E: PairingEngine>(
50 uni_prover_param: &UnivariateProverParam<E::G1Affine>,
51 ml_prover_param: &MultilinearProverParam<E>,
52 polynomials: &[Rc<DenseMultilinearExtension<E::Fr>>],
53 multi_commitment: &Commitment<E>,
54 points: &[Vec<E::Fr>],
55) -> Result<(BatchProof<E>, Vec<E::Fr>), PCSErrors> {
56 let open_timer = start_timer!(|| "multi open");
57
58 // ===================================
59 // Sanity checks on inputs
60 // ===================================
61 let points_len = points.len();
62 if points_len == 0 {
63 return Err(PCSErrors::InvalidParameters("points is empty".to_string()));
64 }
65
66 if points_len != polynomials.len() {
67 return Err(PCSErrors::InvalidParameters(
68 "polynomial length does not match point length".to_string(),
69 ));
70 }
71
72 let num_var = polynomials[0].num_vars();
73 for poly in polynomials.iter().skip(1) {
74 if poly.num_vars() != num_var {
75 return Err(PCSErrors::InvalidParameters(
76 "polynomials do not have same num_vars".to_string(),
77 ));
78 }
79 }
80 for point in points.iter() {
81 if point.len() != num_var {
82 return Err(PCSErrors::InvalidParameters(
83 "points do not have same num_vars".to_string(),
84 ));
85 }
86 }
87
88 let domain = get_uni_domain::<E::Fr>(points_len)?;
89
90 // 1. build `l(points)` which is a list of univariate polynomials that goes
91 // through the points
92 let uni_polys = build_l(num_var, points, &domain)?;
93
94 // 2. build MLE `w` which is the merge of all MLEs.
95 let merge_poly = merge_polynomials(polynomials)?;
96
97 // 3. build `q(x)` which is a univariate polynomial `W circ l`
98 let q_x = compute_w_circ_l(&merge_poly, &uni_polys)?;
99
100 // 4. commit to q(x) and sample r from transcript
101 // transcript contains: w commitment, points, q(x)'s commitment
102 let mut transcript = IOPTranscript::new(b"ml kzg");
103 transcript.append_serializable_element(b"w", multi_commitment)?;
104 for point in points {
105 transcript.append_serializable_element(b"w", point)?;
106 }
107
108 let q_x_commit = KZGUnivariatePCS::<E>::commit(uni_prover_param, &q_x)?;
109 transcript.append_serializable_element(b"q(x)", &q_x_commit)?;
110 let r = transcript.get_and_append_challenge(b"r")?;
111
112 // 5. build q(omega^i) and their openings
113 let mut q_x_opens = vec![];
114 let mut q_x_evals = vec![];
115 for i in 0..points_len {
116 let (q_x_open, q_x_eval) =
117 KZGUnivariatePCS::<E>::open(uni_prover_param, &q_x, &domain.element(i))?;
118 q_x_opens.push(q_x_open);
119 q_x_evals.push(q_x_eval);
120
121 // sanity check
122 let point: Vec<E::Fr> = uni_polys
123 .iter()
124 .rev()
125 .map(|poly| poly.evaluate(&domain.element(i)))
126 .collect();
127 let mle_eval = merge_poly.evaluate(&point).unwrap();
128 if mle_eval != q_x_eval {
129 return Err(PCSErrors::InvalidProver(
130 "Q(omega) does not match W(l(omega))".to_string(),
131 ));
132 }
133 }
134
135 // 6. build q(r) and its opening
136 let (q_x_open, q_r_value) = KZGUnivariatePCS::<E>::open(uni_prover_param, &q_x, &r)?;
137 q_x_opens.push(q_x_open);
138 q_x_evals.push(q_r_value);
139
140 // 7. get a point `p := l(r)`
141 let point: Vec<E::Fr> = uni_polys
142 .iter()
143 .rev()
144 .map(|poly| poly.evaluate(&r))
145 .collect();
146
147 // 8. output an opening of `w` over point `p`
148 let (mle_opening, mle_eval) = open_internal(ml_prover_param, &merge_poly, &point)?;
149
150 // 9. output value that is `w` evaluated at `p` (which should match `q(r)`)
151 if mle_eval != q_r_value {
152 return Err(PCSErrors::InvalidProver(
153 "Q(r) does not match W(l(r))".to_string(),
154 ));
155 }
156 end_timer!(open_timer);
157
158 Ok((
159 BatchProof {
160 proof: mle_opening,
161 q_x_commit,
162 q_x_opens,
163 },
164 q_x_evals,
165 ))
166}
167
168/// Verifies that the `multi_commitment` is a valid commitment
169/// to a list of MLEs for the given openings and evaluations in
170/// the batch_proof.
171///
172/// steps:
173///
174/// 1. push w, points and q_com into transcript
175/// 2. sample `r` from transcript
176/// 3. check `q(r) == batch_proof.q_x_value.last` and
177/// `q(omega^i) == batch_proof.q_x_value[i]`
178/// 4. build `l(points)` which is a list of univariate
179/// polynomials that goes through the points
180/// 5. get a point `p := l(r)`
181/// 6. verifies `p` is valid against multilinear KZG proof
182pub(super) fn batch_verify_internal<E: PairingEngine>(
183 uni_verifier_param: &UnivariateVerifierParam<E>,
184 ml_verifier_param: &MultilinearVerifierParam<E>,
185 multi_commitment: &Commitment<E>,
186 points: &[Vec<E::Fr>],
187 values: &[E::Fr],
188 batch_proof: &BatchProof<E>,
189) -> Result<bool, PCSErrors> {
190 let verify_timer = start_timer!(|| "batch verify");
191
192 // ===================================
193 // Sanity checks on inputs
194 // ===================================
195 let points_len = points.len();
196 if points_len == 0 {
197 return Err(PCSErrors::InvalidParameters("points is empty".to_string()));
198 }
199
200 // add one here because we also have q(r) and its opening
201 if points_len + 1 != batch_proof.q_x_opens.len() {
202 return Err(PCSErrors::InvalidParameters(
203 "openings length does not match point length".to_string(),
204 ));
205 }
206
207 if points_len + 1 != values.len() {
208 return Err(PCSErrors::InvalidParameters(
209 "values length does not match point length".to_string(),
210 ));
211 }
212
213 let num_var = points[0].len();
214 for point in points.iter().skip(1) {
215 if point.len() != num_var {
216 return Err(PCSErrors::InvalidParameters(format!(
217 "points do not have same num_vars ({} vs {})",
218 point.len(),
219 num_var,
220 )));
221 }
222 }
223
224 let domain = get_uni_domain::<E::Fr>(points_len)?;
225
226 // 1. push w, points and q_com into transcript
227 let mut transcript = IOPTranscript::new(b"ml kzg");
228 transcript.append_serializable_element(b"w", multi_commitment)?;
229 for point in points {
230 transcript.append_serializable_element(b"w", point)?;
231 }
232
233 transcript.append_serializable_element(b"q(x)", &batch_proof.q_x_commit)?;
234
235 // 2. sample `r` from transcript
236 let r = transcript.get_and_append_challenge(b"r")?;
237
238 // 3. check `q(r) == batch_proof.q_x_value.last` and `q(omega^i) =
239 // batch_proof.q_x_value[i]`
240 for (i, value) in values.iter().enumerate().take(points_len) {
241 if !KZGUnivariatePCS::verify(
242 uni_verifier_param,
243 &batch_proof.q_x_commit,
244 &domain.element(i),
245 value,
246 &batch_proof.q_x_opens[i],
247 )? {
248 #[cfg(debug_assertion)]
249 println!("q(omega^{}) verification failed", i);
250 return Ok(false);
251 }
252 }
253
254 if !KZGUnivariatePCS::verify(
255 uni_verifier_param,
256 &batch_proof.q_x_commit,
257 &r,
258 &values[points_len],
259 &batch_proof.q_x_opens[points_len],
260 )? {
261 #[cfg(debug_assertion)]
262 println!("q(r) verification failed");
263 return Ok(false);
264 }
265
266 // 4. build `l(points)` which is a list of univariate polynomials that goes
267 // through the points
268 let uni_polys = build_l(num_var, points, &domain)?;
269
270 // 5. get a point `p := l(r)`
271 let point: Vec<E::Fr> = uni_polys.iter().rev().map(|x| x.evaluate(&r)).collect();
272
273 // 6. verifies `p` is valid against multilinear KZG proof
274 let res = verify_internal(
275 ml_verifier_param,
276 multi_commitment,
277 &point,
278 &values[points_len],
279 &batch_proof.proof,
280 )?;
281
282 #[cfg(debug_assertion)]
283 if !res {
284 println!("multilinear KZG verification failed");
285 }
286
287 end_timer!(verify_timer);
288
289 Ok(res)
290}
291
292#[cfg(test)]
293mod tests {
294 use super::{
295 super::{util::get_batched_nv, *},
296 *,
297 };
298 use crate::{
299 multilinear_kzg::util::{compute_qx_degree, generate_evaluations},
300 prelude::UnivariateUniversalParams,
301 StructuredReferenceString,
302 };
303 use ark_bls12_381::Bls12_381 as E;
304 use ark_ec::PairingEngine;
305 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
306 use ark_std::{log2, rand::RngCore, test_rng, vec::Vec, UniformRand};
307 type Fr = <E as PairingEngine>::Fr;
308
309 fn test_multi_commit_helper<R: RngCore>(
310 uni_params: &UnivariateUniversalParams<E>,
311 ml_params: &MultilinearUniversalParams<E>,
312 polys: &[Rc<DenseMultilinearExtension<Fr>>],
313 rng: &mut R,
314 ) -> Result<(), PCSErrors> {
315 let merged_nv = get_batched_nv(polys[0].num_vars(), polys.len());
316 let qx_degree = compute_qx_degree(merged_nv, polys.len());
317 let log_qx_degree = log2(qx_degree) as usize;
318
319 let (uni_ck, uni_vk) = uni_params.trim(log_qx_degree)?;
320 let (ml_ck, ml_vk) = ml_params.trim(merged_nv)?;
321
322 let mut points = Vec::new();
323 for poly in polys.iter() {
324 let point = (0..poly.num_vars())
325 .map(|_| Fr::rand(rng))
326 .collect::<Vec<Fr>>();
327 points.push(point);
328 }
329
330 let evals = generate_evaluations(polys, &points)?;
331
332 let com = KZGMultilinearPCS::multi_commit(&(ml_ck.clone(), uni_ck.clone()), polys)?;
333 let (batch_proof, evaluations) =
334 multi_open_internal(&uni_ck, &ml_ck, polys, &com, &points)?;
335
336 for (a, b) in evals.iter().zip(evaluations.iter()) {
337 assert_eq!(a, b)
338 }
339
340 // good path
341 assert!(batch_verify_internal(
342 &uni_vk,
343 &ml_vk,
344 &com,
345 &points,
346 &evaluations,
347 &batch_proof,
348 )?);
349
350 // bad commitment
351 assert!(!batch_verify_internal(
352 &uni_vk,
353 &ml_vk,
354 &Commitment {
355 commitment: <E as PairingEngine>::G1Affine::default()
356 },
357 &points,
358 &evaluations,
359 &batch_proof,
360 )?);
361
362 // bad points
363 assert!(
364 batch_verify_internal(&uni_vk, &ml_vk, &com, &points[1..], &[], &batch_proof,).is_err()
365 );
366
367 // bad proof
368 assert!(batch_verify_internal(
369 &uni_vk,
370 &ml_vk,
371 &com,
372 &points,
373 &evaluations,
374 &BatchProof {
375 proof: Proof { proofs: Vec::new() },
376 q_x_commit: Commitment {
377 commitment: <E as PairingEngine>::G1Affine::default()
378 },
379 q_x_opens: vec![],
380 },
381 )
382 .is_err());
383
384 // bad value
385 let mut wrong_evals = evaluations.clone();
386 wrong_evals[0] = Fr::default();
387 assert!(!batch_verify_internal(
388 &uni_vk,
389 &ml_vk,
390 &com,
391 &points,
392 &wrong_evals,
393 &batch_proof
394 )?);
395
396 // bad q(x) commit
397 let mut wrong_proof = batch_proof.clone();
398 wrong_proof.q_x_commit = Commitment {
399 commitment: <E as PairingEngine>::G1Affine::default(),
400 };
401 assert!(!batch_verify_internal(
402 &uni_vk,
403 &ml_vk,
404 &com,
405 &points,
406 &evaluations,
407 &wrong_proof,
408 )?);
409 Ok(())
410 }
411
412 #[test]
413 fn test_multi_commit_internal() -> Result<(), PCSErrors> {
414 let mut rng = test_rng();
415
416 let uni_params = UnivariateUniversalParams::<E>::gen_srs_for_testing(&mut rng, 15)?;
417 let ml_params = MultilinearUniversalParams::<E>::gen_srs_for_testing(&mut rng, 15)?;
418
419 // normal polynomials
420 let polys1: Vec<_> = (0..5)
421 .map(|_| Rc::new(DenseMultilinearExtension::rand(4, &mut rng)))
422 .collect();
423 test_multi_commit_helper(&uni_params, &ml_params, &polys1, &mut rng)?;
424
425 // single-variate polynomials
426 let polys1: Vec<_> = (0..5)
427 .map(|_| Rc::new(DenseMultilinearExtension::rand(1, &mut rng)))
428 .collect();
429 test_multi_commit_helper(&uni_params, &ml_params, &polys1, &mut rng)?;
430
431 Ok(())
432 }
433}