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