hyperplonk/pcs/src/multilinear_kzg/util.rs
pcs/src/multilinear_kzg/util.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
7//! Useful utilities for KZG PCS
8use crate::prelude::PCSError;
9use arithmetic::evaluate_no_par;
10use ark_ff::PrimeField;
11use ark_poly::{
12 univariate::DensePolynomial, DenseMultilinearExtension, EvaluationDomain, Evaluations,
13 MultilinearExtension, Polynomial, Radix2EvaluationDomain,
14};
15use ark_std::{end_timer, format, log2, start_timer, string::ToString, vec::Vec};
16use rayon::prelude::{IntoParallelIterator, ParallelIterator};
17
18/// For an MLE w with `mle_num_vars` variables, and `point_len` number of
19/// points, compute the degree of the univariate polynomial `q(x):= w(l(x))`
20/// where l(x) is a list of polynomials that go through all points.
21// uni_degree is computed as `mle_num_vars * point_len`:
22// - each l(x) is of degree `point_len`
23// - mle has degree one
24// - worst case is `\prod_{i=0}^{mle_num_vars-1} l_i(x) < point_len * mle_num_vars`
25#[inline]
26pub fn compute_qx_degree(mle_num_vars: usize, point_len: usize) -> usize {
27 mle_num_vars * ((1 << log2(point_len)) - 1) + 1
28}
29
30/// Compute W \circ l.
31///
32/// Given an MLE W, and a list of univariate polynomials l, generate the
33/// univariate polynomial that composes W with l.
34///
35/// Returns an error if l's length does not matches number of variables in W.
36pub(crate) fn compute_w_circ_l<F: PrimeField>(
37 w: &DenseMultilinearExtension<F>,
38 l: &[DensePolynomial<F>],
39 num_points: usize,
40 with_suffix: bool,
41) -> Result<DensePolynomial<F>, PCSError> {
42 let timer = start_timer!(|| "compute W \\circ l");
43
44 if w.num_vars != l.len() {
45 return Err(PCSError::InvalidParameters(format!(
46 "l's length ({}) does not match num_variables ({})",
47 l.len(),
48 w.num_vars(),
49 )));
50 }
51 let uni_degree = if with_suffix {
52 compute_qx_degree(w.num_vars() + log2(num_points) as usize, num_points)
53 } else {
54 compute_qx_degree(w.num_vars(), num_points)
55 };
56
57 let domain = match Radix2EvaluationDomain::<F>::new(uni_degree) {
58 Some(p) => p,
59 None => {
60 return Err(PCSError::InvalidParameters(
61 "failed to build radix 2 domain".to_string(),
62 ))
63 },
64 };
65
66 let step = start_timer!(|| format!("compute eval {}-dim domain", domain.size()));
67 let res_eval = (0..domain.size())
68 .into_par_iter()
69 .map(|i| {
70 let l_eval: Vec<F> = l.iter().map(|x| x.evaluate(&domain.element(i))).collect();
71 evaluate_no_par(w, &l_eval)
72 })
73 .collect();
74 end_timer!(step);
75
76 let evaluation = Evaluations::from_vec_and_domain(res_eval, domain);
77 let res = evaluation.interpolate();
78
79 end_timer!(timer);
80 Ok(res)
81}
82
83/// Input a list of multilinear polynomials and a list of points,
84/// generate a list of evaluations.
85// Note that this function is only used for testing verifications.
86// In practice verifier does not see polynomials, and the `mle_values`
87// are included in the `batch_proof`.
88#[cfg(test)]
89pub(crate) fn generate_evaluations_multi_poly<F: PrimeField>(
90 polynomials: &[std::rc::Rc<DenseMultilinearExtension<F>>],
91 points: &[Vec<F>],
92) -> Result<Vec<F>, PCSError> {
93 use arithmetic::{build_l, get_uni_domain, merge_polynomials};
94
95 if polynomials.len() != points.len() {
96 return Err(PCSError::InvalidParameters(
97 "polynomial length does not match point length".to_string(),
98 ));
99 }
100 let uni_poly_degree = points.len();
101 let merge_poly = merge_polynomials(polynomials)?;
102
103 let domain = get_uni_domain::<F>(uni_poly_degree)?;
104 let uni_polys = build_l(points, &domain, true)?;
105 let mut mle_values = vec![];
106
107 for i in 0..uni_poly_degree {
108 let point: Vec<F> = uni_polys
109 .iter()
110 .map(|poly| poly.evaluate(&domain.element(i)))
111 .collect();
112
113 let mle_value = merge_poly.evaluate(&point).unwrap();
114 mle_values.push(mle_value)
115 }
116 Ok(mle_values)
117}
118
119/// Input a list of multilinear polynomials and a list of points,
120/// generate a list of evaluations.
121// Note that this function is only used for testing verifications.
122// In practice verifier does not see polynomials, and the `mle_values`
123// are included in the `batch_proof`.
124#[cfg(test)]
125pub(crate) fn generate_evaluations_single_poly<F: PrimeField>(
126 polynomial: &std::rc::Rc<DenseMultilinearExtension<F>>,
127 points: &[Vec<F>],
128) -> Result<Vec<F>, PCSError> {
129 use arithmetic::{build_l, get_uni_domain};
130
131 let uni_poly_degree = points.len();
132
133 let domain = get_uni_domain::<F>(uni_poly_degree)?;
134 let uni_polys = build_l(points, &domain, false)?;
135 let mut mle_values = vec![];
136
137 for i in 0..uni_poly_degree {
138 let point: Vec<F> = uni_polys
139 .iter()
140 .map(|poly| poly.evaluate(&domain.element(i)))
141 .collect();
142
143 let mle_value = polynomial.evaluate(&point).unwrap();
144 mle_values.push(mle_value)
145 }
146 Ok(mle_values)
147}
148
149#[cfg(test)]
150mod test {
151 use super::*;
152 use arithmetic::{build_l, get_uni_domain, merge_polynomials};
153 use ark_bls12_381::Fr;
154 use ark_poly::UVPolynomial;
155 use ark_std::{One, Zero};
156 use std::rc::Rc;
157
158 #[test]
159 fn test_w_circ_l() -> Result<(), PCSError> {
160 test_w_circ_l_helper::<Fr>()
161 }
162
163 fn test_w_circ_l_helper<F: PrimeField>() -> Result<(), PCSError> {
164 {
165 // Example from page 53:
166 // W = 3x1x2 + 2x2 whose evaluations are
167 // 0, 0 |-> 0
168 // 1, 0 |-> 0
169 // 0, 1 |-> 2
170 // 1, 1 |-> 5
171 let w_eval = vec![F::zero(), F::zero(), F::from(2u64), F::from(5u64)];
172 let w = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
173
174 // l0 = t + 2
175 // l1 = -2t + 4
176 let l0 = DensePolynomial::from_coefficients_vec(vec![F::from(2u64), F::one()]);
177 let l1 = DensePolynomial::from_coefficients_vec(vec![F::from(4u64), -F::from(2u64)]);
178
179 // res = -6t^2 - 4t + 32
180 let res = compute_w_circ_l(&w, [l0, l1].as_ref(), 4, false)?;
181 let res_rec = DensePolynomial::from_coefficients_vec(vec![
182 F::from(32u64),
183 -F::from(4u64),
184 -F::from(6u64),
185 ]);
186 assert_eq!(res, res_rec);
187 }
188 {
189 // A random example
190 // W = x1x2x3 - 2x1x2 + 3x2x3 - 4x1x3 + 5x1 - 6x2 + 7x3
191 // 0, 0, 0 |-> 0
192 // 1, 0, 0 |-> 5
193 // 0, 1, 0 |-> -6
194 // 1, 1, 0 |-> -3
195 // 0, 0, 1 |-> 7
196 // 1, 0, 1 |-> 8
197 // 0, 1, 1 |-> 4
198 // 1, 1, 1 |-> 4
199 let w_eval = vec![
200 F::zero(),
201 F::from(5u64),
202 -F::from(6u64),
203 -F::from(3u64),
204 F::from(7u64),
205 F::from(8u64),
206 F::from(4u64),
207 F::from(4u64),
208 ];
209 let w = DenseMultilinearExtension::from_evaluations_vec(3, w_eval);
210
211 // l0 = t + 2
212 // l1 = 3t - 4
213 // l2 = -5t + 6
214 let l0 = DensePolynomial::from_coefficients_vec(vec![F::from(2u64), F::one()]);
215 let l1 = DensePolynomial::from_coefficients_vec(vec![-F::from(4u64), F::from(3u64)]);
216 let l2 = DensePolynomial::from_coefficients_vec(vec![F::from(6u64), -F::from(5u64)]);
217 let res = compute_w_circ_l(&w, [l0, l1, l2].as_ref(), 8, false)?;
218
219 // res = -15t^3 - 23t^2 + 130t - 76
220 let res_rec = DensePolynomial::from_coefficients_vec(vec![
221 -F::from(76u64),
222 F::from(130u64),
223 -F::from(23u64),
224 -F::from(15u64),
225 ]);
226
227 assert_eq!(res, res_rec);
228 }
229 Ok(())
230 }
231
232 #[test]
233 fn test_w_circ_l_with_prefix() -> Result<(), PCSError> {
234 test_w_circ_l_with_prefix_helper::<Fr>()
235 }
236
237 fn test_w_circ_l_with_prefix_helper<F: PrimeField>() -> Result<(), PCSError> {
238 {
239 // Example from page 53:
240 // W = 3x1x2 + 2x2 whose evaluations are
241 // 0, 0 |-> 0
242 // 1, 0 |-> 0
243 // 0, 1 |-> 2
244 // 1, 1 |-> 5
245 let w_eval = vec![F::zero(), F::zero(), F::from(2u64), F::from(5u64)];
246 let w = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
247
248 // l0 = t + 2
249 // l1 = -2t + 4
250 let l0 = DensePolynomial::from_coefficients_vec(vec![F::from(2u64), F::one()]);
251 let l1 = DensePolynomial::from_coefficients_vec(vec![F::from(4u64), -F::from(2u64)]);
252
253 // res = -6t^2 - 4t + 32
254 let res = compute_w_circ_l(&w, [l0, l1].as_ref(), 4, true)?;
255 let res_rec = DensePolynomial::from_coefficients_vec(vec![
256 F::from(32u64),
257 -F::from(4u64),
258 -F::from(6u64),
259 ]);
260 assert_eq!(res, res_rec);
261 }
262 {
263 // A random example
264 // W = x1x2x3 - 2x1x2 + 3x2x3 - 4x1x3 + 5x1 - 6x2 + 7x3
265 // 0, 0, 0 |-> 0
266 // 1, 0, 0 |-> 5
267 // 0, 1, 0 |-> -6
268 // 1, 1, 0 |-> -3
269 // 0, 0, 1 |-> 7
270 // 1, 0, 1 |-> 8
271 // 0, 1, 1 |-> 4
272 // 1, 1, 1 |-> 4
273 let w_eval = vec![
274 F::zero(),
275 F::from(5u64),
276 -F::from(6u64),
277 -F::from(3u64),
278 F::from(7u64),
279 F::from(8u64),
280 F::from(4u64),
281 F::from(4u64),
282 ];
283 let w = DenseMultilinearExtension::from_evaluations_vec(3, w_eval);
284
285 // l0 = t + 2
286 // l1 = 3t - 4
287 // l2 = -5t + 6
288 let l0 = DensePolynomial::from_coefficients_vec(vec![F::from(2u64), F::one()]);
289 let l1 = DensePolynomial::from_coefficients_vec(vec![-F::from(4u64), F::from(3u64)]);
290 let l2 = DensePolynomial::from_coefficients_vec(vec![F::from(6u64), -F::from(5u64)]);
291 let res = compute_w_circ_l(&w, [l0, l1, l2].as_ref(), 8, true)?;
292
293 // res = -15t^3 - 23t^2 + 130t - 76
294 let res_rec = DensePolynomial::from_coefficients_vec(vec![
295 -F::from(76u64),
296 F::from(130u64),
297 -F::from(23u64),
298 -F::from(15u64),
299 ]);
300
301 assert_eq!(res, res_rec);
302 }
303 Ok(())
304 }
305
306 #[test]
307 fn test_qx() -> Result<(), PCSError> {
308 // Example from page 53:
309 // W1 = 3x1x2 + 2x2
310 let w_eval = vec![Fr::zero(), Fr::from(2u64), Fr::zero(), Fr::from(5u64)];
311 let w = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
312
313 let r = Fr::from(42u64);
314
315 // point 1 is [1, 2]
316 let point1 = vec![Fr::from(1u64), Fr::from(2u64)];
317
318 // point 2 is [3, 4]
319 let point2 = vec![Fr::from(3u64), Fr::from(4u64)];
320
321 // point 3 is [5, 6]
322 let point3 = vec![Fr::from(5u64), Fr::from(6u64)];
323
324 {
325 let domain = get_uni_domain::<Fr>(2)?;
326 let l = build_l(&[point1.clone(), point2.clone()], &domain, false)?;
327
328 let q_x = compute_w_circ_l(&w, &l, 2, false)?;
329
330 let point: Vec<Fr> = l.iter().map(|poly| poly.evaluate(&r)).collect();
331
332 assert_eq!(
333 q_x.evaluate(&r),
334 w.evaluate(&point).unwrap(),
335 "q(r) != w(l(r))"
336 );
337 }
338
339 {
340 let domain = get_uni_domain::<Fr>(3)?;
341
342 let l = build_l(&[point1, point2, point3], &domain, false)?;
343 let q_x = compute_w_circ_l(&w, &l, 3, false)?;
344
345 let point: Vec<Fr> = vec![l[0].evaluate(&r), l[1].evaluate(&r)];
346
347 assert_eq!(
348 q_x.evaluate(&r),
349 w.evaluate(&point).unwrap(),
350 "q(r) != w(l(r))"
351 );
352 }
353 Ok(())
354 }
355
356 #[test]
357 fn test_qx_with_prefix() -> Result<(), PCSError> {
358 // Example from page 53:
359 // W1 = 3x1x2 + 2x2
360 let w_eval = vec![Fr::zero(), Fr::from(2u64), Fr::zero(), Fr::from(5u64)];
361 let w1 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
362
363 // W2 = x1x2 + x1
364 let w_eval = vec![Fr::zero(), Fr::zero(), Fr::from(1u64), Fr::from(2u64)];
365 let w2 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
366
367 // W3 = x1 + x2
368 let w_eval = vec![Fr::zero(), Fr::one(), Fr::from(1u64), Fr::from(2u64)];
369 let w3 = Rc::new(DenseMultilinearExtension::from_evaluations_vec(2, w_eval));
370
371 let r = Fr::from(42u64);
372
373 // point 1 is [1, 2]
374 let point1 = vec![Fr::from(1u64), Fr::from(2u64)];
375
376 // point 2 is [3, 4]
377 let point2 = vec![Fr::from(3u64), Fr::from(4u64)];
378
379 // point 3 is [5, 6]
380 let point3 = vec![Fr::from(5u64), Fr::from(6u64)];
381
382 {
383 let domain = get_uni_domain::<Fr>(2)?;
384 // w = (3x1x2 + 2x2)(1-x0) + (x1x2 + x1)x0
385 // with evaluations: [0,2,0,5,0,0,1,2]
386 let w = merge_polynomials(&[w1.clone(), w2.clone()])?;
387
388 let l = build_l(&[point1.clone(), point2.clone()], &domain, true)?;
389
390 // sage: P.<x> = PolynomialRing(ZZ)
391 // sage: l0 = -1/2 * x + 1/2
392 // sage: l1 = -x + 2
393 // sage: l2 = -x + 3
394 // sage: w = (3 * l1 * l2 + 2 * l2) * (1-l0) + (l1 * l2 + l1) * l0
395 // sage: w
396 // x^3 - 7/2*x^2 - 7/2*x + 16
397 //
398 // q(x) = x^3 - 7/2*x^2 - 7/2*x + 16
399 let q_x = compute_w_circ_l(&w, &l, 2, true)?;
400
401 let point: Vec<Fr> = l.iter().map(|poly| poly.evaluate(&r)).collect();
402
403 assert_eq!(
404 q_x.evaluate(&r),
405 w.evaluate(&point).unwrap(),
406 "q(r) != w(l(r))"
407 );
408 }
409
410 {
411 let domain = get_uni_domain::<Fr>(3)?;
412 let w = merge_polynomials(&[w1, w2, w3])?;
413
414 let l = build_l(&[point1, point2, point3], &domain, true)?;
415 let q_x = compute_w_circ_l(&w, &l, 3, true)?;
416
417 let point: Vec<Fr> = vec![
418 l[0].evaluate(&r),
419 l[1].evaluate(&r),
420 l[2].evaluate(&r),
421 l[3].evaluate(&r),
422 ];
423
424 assert_eq!(
425 q_x.evaluate(&r),
426 w.evaluate(&point).unwrap(),
427 "q(r) != w(l(r))"
428 );
429 }
430 Ok(())
431 }
432}