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