hyperplonk/pcs/src/multilinear_kzg/util.rs
pcs/src/multilinear_kzg/util.rsRaw
1//! Useful utilities for KZG PCS
2
3use crate::PCSErrors;
4use ark_ff::PrimeField;
5use ark_poly::{
6 univariate::DensePolynomial, DenseMultilinearExtension, EvaluationDomain, Evaluations,
7 MultilinearExtension, Polynomial, Radix2EvaluationDomain,
8};
9use ark_std::{end_timer, log2, start_timer};
10use std::cmp::max;
11
12/// Decompose an integer into a binary vector in little endian.
13#[allow(dead_code)]
14pub(crate) fn bit_decompose(input: u64, num_var: usize) -> Vec<bool> {
15 let mut res = Vec::with_capacity(num_var);
16 let mut i = input;
17 for _ in 0..num_var {
18 res.push(i & 1 == 1);
19 i >>= 1;
20 }
21 res
22}
23
24/// For an MLE w with `mle_num_vars` variables, and `point_len` number of
25/// points, compute the degree of the univariate polynomial `q(x):= w(l(x))`
26/// where l(x) is a list of polynomials that go through all points.
27// uni_degree is computed as `mle_num_vars * point_len`:
28// - each l(x) is of degree `point_len`
29// - mle has degree one
30// - worst case is `\prod_{i=0}^{mle_num_vars-1} l_i(x) < point_len * mle_num_vars`
31#[inline]
32#[allow(dead_code)]
33pub(crate) fn compute_qx_degree(mle_num_vars: usize, point_len: usize) -> usize {
34 mle_num_vars * point_len
35}
36
37/// get the domain for the univariate polynomial
38#[inline]
39pub(crate) fn get_uni_domain<F: PrimeField>(
40 uni_poly_degree: usize,
41) -> Result<Radix2EvaluationDomain<F>, PCSErrors> {
42 let domain = match Radix2EvaluationDomain::<F>::new(uni_poly_degree) {
43 Some(p) => p,
44 None => {
45 return Err(PCSErrors::InvalidParameters(
46 "failed to build radix 2 domain".to_string(),
47 ))
48 },
49 };
50 Ok(domain)
51}
52
53/// Compute W \circ l.
54///
55/// Given an MLE W, and a list of univariate polynomials l, generate the
56/// univariate polynomial that composes W with l.
57///
58/// Returns an error if l's length does not matches number of variables in W.
59pub(crate) fn compute_w_circ_l<F: PrimeField>(
60 w: &DenseMultilinearExtension<F>,
61 l: &[DensePolynomial<F>],
62) -> Result<DensePolynomial<F>, PCSErrors> {
63 let timer = start_timer!(|| "compute W \\circ l");
64
65 if w.num_vars != l.len() {
66 return Err(PCSErrors::InvalidParameters(format!(
67 "l's length ({}) does not match num_variables ({})",
68 l.len(),
69 w.num_vars(),
70 )));
71 }
72
73 let mut res_eval: Vec<F> = vec![];
74
75 // TODO: consider to pass this in from caller
76 // uni_degree is (product of each prefix's) + (2 * MLEs)
77 // = (l.len() - (num_vars - log(l.len())) + 2) * l[0].degree
78 let uni_degree = (l.len() - w.num_vars + log2(l.len()) as usize + 2) * l[0].degree();
79
80 let domain = match Radix2EvaluationDomain::<F>::new(uni_degree) {
81 Some(p) => p,
82 None => {
83 return Err(PCSErrors::InvalidParameters(
84 "failed to build radix 2 domain".to_string(),
85 ))
86 },
87 };
88 for point in domain.elements() {
89 // we reverse the order here because the coefficient vec are stored in
90 // bit-reversed order
91 let l_eval: Vec<F> = l.iter().rev().map(|x| x.evaluate(&point)).collect();
92 res_eval.push(w.evaluate(l_eval.as_ref()).unwrap())
93 }
94 let evaluation = Evaluations::from_vec_and_domain(res_eval, domain);
95 let res = evaluation.interpolate();
96
97 end_timer!(timer);
98 Ok(res)
99}
100
101/// Return the number of variables that one need for an MLE to
102/// batch the list of MLEs
103#[inline]
104pub(crate) fn get_batched_nv(num_var: usize, polynomials_len: usize) -> usize {
105 num_var + log2(polynomials_len) as usize
106}
107
108/// Return the SRS size
109// We require an SRS that is the greater of the two:
110// - Multilinear srs is bounded by the merged MLS size which is `get_batched_nv(num_var,
111// num_witnesses)`
112// - Univariate srs is bounded by q_x's degree which is `compute_uni_degree(num_vars,
113// num_witnesses)`
114#[inline]
115#[allow(dead_code)]
116pub(crate) fn get_srs_size(num_var: usize, num_wires: usize) -> usize {
117 max(
118 num_var + log2(num_wires) as usize,
119 (log2(num_var) as usize + 2) * num_wires,
120 )
121}
122/// merge a set of polynomials. Returns an error if the
123/// polynomials do not share a same number of nvs.
124pub fn merge_polynomials<F: PrimeField>(
125 polynomials: &[impl MultilinearExtension<F>],
126) -> Result<DenseMultilinearExtension<F>, PCSErrors> {
127 let nv = polynomials[0].num_vars();
128 for poly in polynomials.iter() {
129 if nv != poly.num_vars() {
130 return Err(PCSErrors::InvalidParameters(
131 "num_vars do not match for polynomials".to_string(),
132 ));
133 }
134 }
135
136 let merged_nv = get_batched_nv(nv, polynomials.len());
137 let mut scalars = vec![];
138 for poly in polynomials.iter() {
139 scalars.extend_from_slice(poly.to_evaluations().as_slice());
140 }
141 scalars.extend_from_slice(vec![F::zero(); (1 << merged_nv) - scalars.len()].as_ref());
142 Ok(DenseMultilinearExtension::from_evaluations_vec(
143 merged_nv, scalars,
144 ))
145}
146
147/// Given a list of points, build `l(points)` which is a list of univariate
148/// polynomials that goes through the points
149pub(crate) fn build_l<F: PrimeField>(
150 num_var: usize,
151 points: &[Vec<F>],
152 domain: &Radix2EvaluationDomain<F>,
153) -> Result<Vec<DensePolynomial<F>>, PCSErrors> {
154 let prefix_len = log2(points.len()) as usize;
155 let mut uni_polys = Vec::new();
156
157 // 1.1 build the indexes and the univariate polys that go through the indexes
158 let indexes: Vec<Vec<bool>> = (0..points.len())
159 .map(|x| bit_decompose(x as u64, prefix_len))
160 .collect();
161 for i in 0..prefix_len {
162 let eval: Vec<F> = indexes
163 .iter()
164 .map(|x| F::from(x[prefix_len - i - 1]))
165 .collect();
166
167 uni_polys.push(Evaluations::from_vec_and_domain(eval, *domain).interpolate());
168 }
169
170 // 1.2 build the actual univariate polys that go through the points
171 for i in 0..num_var {
172 let mut eval: Vec<F> = points.iter().map(|x| x[i]).collect();
173 eval.extend_from_slice(vec![F::zero(); domain.size as usize - eval.len()].as_slice());
174 uni_polys.push(Evaluations::from_vec_and_domain(eval, *domain).interpolate())
175 }
176
177 Ok(uni_polys)
178}
179
180/// Input a list of multilinear polynomials and a list of points,
181/// generate a list of evaluations.
182// Note that this function is only used for testing verifications.
183// In practice verifier does not see polynomials, and the `mle_values`
184// are included in the `batch_proof`.
185#[cfg(test)]
186pub(crate) fn generate_evaluations<F: PrimeField>(
187 polynomials: &[DenseMultilinearExtension<F>],
188 points: &[Vec<F>],
189) -> Result<Vec<F>, PCSErrors> {
190 if polynomials.len() != points.len() {
191 return Err(PCSErrors::InvalidParameters(
192 "polynomial length does not match point length".to_string(),
193 ));
194 }
195
196 let num_var = polynomials[0].num_vars;
197 let uni_poly_degree = points.len();
198 let merge_poly = merge_polynomials(polynomials)?;
199
200 let domain = get_uni_domain::<F>(uni_poly_degree)?;
201 let uni_polys = build_l(num_var, points, &domain)?;
202 let mut mle_values = vec![];
203
204 for i in 0..uni_poly_degree {
205 let point: Vec<F> = uni_polys
206 .iter()
207 .rev()
208 .map(|poly| poly.evaluate(&domain.element(i)))
209 .collect();
210
211 let mle_value = merge_poly.evaluate(&point).unwrap();
212 mle_values.push(mle_value)
213 }
214 Ok(mle_values)
215}
216
217#[cfg(test)]
218mod test {
219 use super::*;
220 use ark_bls12_381::Fr;
221 use ark_ff::field_new;
222 use ark_poly::UVPolynomial;
223 use ark_std::{One, Zero};
224
225 #[test]
226 fn test_w_circ_l() -> Result<(), PCSErrors> {
227 test_w_circ_l_helper::<Fr>()
228 }
229
230 fn test_w_circ_l_helper<F: PrimeField>() -> Result<(), PCSErrors> {
231 {
232 // Example from page 53:
233 // W = 3x1x2 + 2x2 whose evaluations are
234 // 0, 0 |-> 0
235 // 0, 1 |-> 2
236 // 1, 0 |-> 0
237 // 1, 1 |-> 5
238 let w_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
239 let w = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
240
241 // l0 = t + 2
242 // l1 = -2t + 4
243 let l0 = DensePolynomial::from_coefficients_vec(vec![F::from(2u64), F::one()]);
244 let l1 = DensePolynomial::from_coefficients_vec(vec![F::from(4u64), -F::from(2u64)]);
245
246 // res = -6t^2 - 4t + 32
247 let res = compute_w_circ_l(&w, [l0, l1].as_ref())?;
248 let res_rec = DensePolynomial::from_coefficients_vec(vec![
249 F::from(32u64),
250 -F::from(4u64),
251 -F::from(6u64),
252 ]);
253 assert_eq!(res, res_rec);
254 }
255 {
256 // A random example
257 // W = x1x2x3 - 2x1x2 + 3x2x3 - 4x1x3 + 5x1 - 6x2 + 7x3
258 // 0, 0, 0 |-> 0
259 // 0, 0, 1 |-> 7
260 // 0, 1, 0 |-> -6
261 // 0, 1, 1 |-> 4
262 // 1, 0, 0 |-> 5
263 // 1, 0, 1 |-> 8
264 // 1, 1, 0 |-> -3
265 // 1, 1, 1 |-> 4
266 let w_eval = vec![
267 F::zero(),
268 F::from(7u64),
269 -F::from(6u64),
270 F::from(4u64),
271 F::from(5u64),
272 F::from(8u64),
273 -F::from(3u64),
274 F::from(4u64),
275 ];
276 let w = DenseMultilinearExtension::from_evaluations_vec(3, w_eval);
277
278 // l0 = t + 2
279 // l1 = 3t - 4
280 // l2 = -5t + 6
281 let l0 = DensePolynomial::from_coefficients_vec(vec![F::from(2u64), F::one()]);
282 let l1 = DensePolynomial::from_coefficients_vec(vec![-F::from(4u64), F::from(3u64)]);
283 let l2 = DensePolynomial::from_coefficients_vec(vec![F::from(6u64), -F::from(5u64)]);
284 let res = compute_w_circ_l(&w, [l0, l1, l2].as_ref())?;
285
286 // res = -15t^3 - 23t^2 + 130t - 76
287 let res_rec = DensePolynomial::from_coefficients_vec(vec![
288 -F::from(76u64),
289 F::from(130u64),
290 -F::from(23u64),
291 -F::from(15u64),
292 ]);
293
294 assert_eq!(res, res_rec);
295 }
296 Ok(())
297 }
298
299 #[test]
300 fn test_merge_poly() -> Result<(), PCSErrors> {
301 test_merge_poly_helper::<Fr>()
302 }
303 fn test_merge_poly_helper<F: PrimeField>() -> Result<(), PCSErrors> {
304 // Example from page 53:
305 // W1 = 3x1x2 + 2x2 whose evaluations are
306 // 0, 0 |-> 0
307 // 0, 1 |-> 2
308 // 1, 0 |-> 0
309 // 1, 1 |-> 5
310 let w_eval = vec![F::zero(), F::from(2u64), F::zero(), F::from(5u64)];
311 let w1 = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
312
313 // W2 = x1x2 + x1 whose evaluations are
314 // 0, 0 |-> 0
315 // 0, 1 |-> 0
316 // 1, 0 |-> 1
317 // 1, 1 |-> 2
318 let w_eval = vec![F::zero(), F::zero(), F::from(1u64), F::from(2u64)];
319 let w2 = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
320
321 // W3 = x1 + x2 whose evaluations are
322 // 0, 0 |-> 0
323 // 0, 1 |-> 1
324 // 1, 0 |-> 1
325 // 1, 1 |-> 2
326 let w_eval = vec![F::zero(), F::one(), F::from(1u64), F::from(2u64)];
327 let w3 = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
328
329 {
330 // W = (3x1x2 + 2x2)(1-x0) + (x1x2 + x1)x0
331 // = -2x0x1x2 + x0x1 - 2x0x2 + 3x1x2 + 2x2
332 // with evaluation map
333 //
334 // x0 x1 x2
335 // 0, 0, 0 |-> 0
336 // 0, 0, 1 |-> 2
337 // 0, 1, 0 |-> 0
338 // 0, 1, 1 |-> 5
339 // 1, 0, 0 |-> 0
340 // 1, 0, 1 |-> 0
341 // 1, 1, 0 |-> 1
342 // 1, 1, 1 |-> 2
343 //
344 let w = merge_polynomials(&[w1.clone(), w2.clone()])?;
345 // w is [0,2,0,5,0,0,1,2]
346 let w_eval = vec![
347 F::zero(),
348 F::from(2u64),
349 F::zero(),
350 F::from(5u64),
351 F::zero(),
352 F::zero(),
353 F::from(1u64),
354 F::from(2u64),
355 ];
356 let w_rec = DenseMultilinearExtension::from_evaluations_vec(3, w_eval);
357
358 assert_eq!(w, w_rec);
359 }
360
361 {
362 // W = (3x1x2 + 2x2) * (1-y1) * (1-y2)
363 // + (x1x2 + x1) * (1-y1) * y2
364 // + (x1 + x2) * y1 * (1-y2)
365 //
366 // with evaluation map
367 //
368 // y1 y2 x1 x2
369 // 0, 0, 0, 0 |-> 0
370 // 0, 0, 0, 1 |-> 2
371 // 0, 0, 1, 0 |-> 0
372 // 0, 0, 1, 1 |-> 5
373 // 0, 1, 0, 0 |-> 0
374 // 0, 1, 0, 1 |-> 0
375 // 0, 1, 1, 0 |-> 1
376 // 0, 1, 1, 1 |-> 2
377 // 1, 0, 0, 0 |-> 0
378 // 1, 0, 0, 1 |-> 1
379 // 1, 0, 1, 0 |-> 1
380 // 1, 0, 1, 1 |-> 2
381 // 1, 1, 0, 0 |-> 0
382 // 1, 1, 0, 1 |-> 0
383 // 1, 1, 1, 0 |-> 0
384 // 1, 1, 1, 1 |-> 0
385 //
386 let w = merge_polynomials(&[w1, w2, w3])?;
387 // w is [0,2,0,5,0,0,1,2, 0,1,1,2]
388 let w_eval = vec![
389 F::zero(),
390 F::from(2u64),
391 F::zero(),
392 F::from(5u64),
393 F::zero(),
394 F::zero(),
395 F::from(1u64),
396 F::from(2u64),
397 F::zero(),
398 F::one(),
399 F::from(1u64),
400 F::from(2u64),
401 F::zero(),
402 F::zero(),
403 F::zero(),
404 F::zero(),
405 ];
406 let w_rec = DenseMultilinearExtension::from_evaluations_vec(4, w_eval);
407
408 assert_eq!(w, w_rec);
409 }
410 Ok(())
411 }
412
413 #[test]
414 fn test_build_l() -> Result<(), PCSErrors> {
415 test_build_l_helper::<Fr>()
416 }
417
418 fn test_build_l_helper<F: PrimeField>() -> Result<(), PCSErrors> {
419 // point 1 is [1, 2]
420 let point1 = vec![Fr::from(1u64), Fr::from(2u64)];
421
422 // point 2 is [3, 4]
423 let point2 = vec![Fr::from(3u64), Fr::from(4u64)];
424
425 // point 3 is [5, 6]
426 let point3 = vec![Fr::from(5u64), Fr::from(6u64)];
427
428 {
429 let domain = get_uni_domain::<Fr>(2)?;
430 let l = build_l(2, &[point1.clone(), point2.clone()], &domain)?;
431
432 // roots: [1, -1]
433 // l0 = -1/2 * x + 1/2
434 // l1 = -x + 2
435 // l2 = -x + 3
436 let l0 = DensePolynomial::from_coefficients_vec(vec![
437 Fr::one() / Fr::from(2u64),
438 -Fr::one() / Fr::from(2u64),
439 ]);
440 let l1 = DensePolynomial::from_coefficients_vec(vec![Fr::from(2u64), -Fr::one()]);
441 let l2 = DensePolynomial::from_coefficients_vec(vec![Fr::from(3u64), -Fr::one()]);
442
443 assert_eq!(l0, l[0], "l0 not equal");
444 assert_eq!(l1, l[1], "l1 not equal");
445 assert_eq!(l2, l[2], "l2 not equal");
446 }
447
448 {
449 let domain = get_uni_domain::<Fr>(3)?;
450 let l = build_l(2, &[point1, point2, point3], &domain)?;
451
452 // sage: q = 52435875175126190479447740508185965837690552500527637822603658699938581184513
453 // sage: P.<x> = PolynomialRing(Zmod(q))
454 // sage: root1 = 1
455 // sage: root2 = 0x8D51CCCE760304D0EC030002760300000001000000000000
456 // sage: root3 = -1
457 // sage: root4 = -root2
458 // Arkwork's code is a bit wired: it also interpolate (root4, 0)
459 // which returns a degree 3 polynomial, instead of degree 2
460
461 // ========================
462 // l0: [0, 0, 1]
463 // ========================
464 // sage: points = [(root1, 0), (root2, 0), (root3, 1), (root4, 0)]
465 // sage: P.lagrange_polynomial(points)
466 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x^3 +
467 // 39326906381344642859585805381139474378267914375395728366952744024953935888385*x^2 +
468 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x +
469 // 39326906381344642859585805381139474378267914375395728366952744024953935888385
470 let l0 = DensePolynomial::from_coefficients_vec(vec![
471 field_new!(
472 Fr,
473 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
474 ),
475 field_new!(
476 Fr,
477 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
478 ),
479 field_new!(
480 Fr,
481 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
482 ),
483 field_new!(
484 Fr,
485 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
486 ),
487 ]);
488
489 // ========================
490 // l1: [0, 1, 0]
491 // ========================
492 // sage: points = [(root1, 0), (root2, 1), (root3, 0), (root4, 0)]
493 // sage: P.lagrange_polynomial(points)
494 // 866286206518413079694067382671935694567563117191340490752*x^3 +
495 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x^2 +
496 // 52435875175126190478581454301667552757996485117855702128036095582747240693761*x +
497 // 39326906381344642859585805381139474378267914375395728366952744024953935888385
498 let l1 = DensePolynomial::from_coefficients_vec(vec![
499 field_new!(
500 Fr,
501 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
502 ),
503 field_new!(
504 Fr,
505 "52435875175126190478581454301667552757996485117855702128036095582747240693761"
506 ),
507 field_new!(
508 Fr,
509 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
510 ),
511 field_new!(
512 Fr,
513 "866286206518413079694067382671935694567563117191340490752"
514 ),
515 ]);
516
517 // ========================
518 // l2: [1, 3, 5]
519 // ========================
520 // sage: points = [(root1, 1), (root2, 3), (root3, 5), (root4, 0)]
521 // sage: P.lagrange_polynomial(points)
522 // 2598858619555239239082202148015807083702689351574021472255*x^3 +
523 // 13108968793781547619861935127046491459422638125131909455650914674984645296129*x^2 +
524 // 52435875175126190476848881888630726598608350352511830738900969348364559712256*x +
525 // 39326906381344642859585805381139474378267914375395728366952744024953935888387
526 let l2 = DensePolynomial::from_coefficients_vec(vec![
527 field_new!(
528 Fr,
529 "39326906381344642859585805381139474378267914375395728366952744024953935888387"
530 ),
531 field_new!(
532 Fr,
533 "52435875175126190476848881888630726598608350352511830738900969348364559712256"
534 ),
535 field_new!(
536 Fr,
537 "13108968793781547619861935127046491459422638125131909455650914674984645296129"
538 ),
539 field_new!(
540 Fr,
541 "2598858619555239239082202148015807083702689351574021472255"
542 ),
543 ]);
544
545 // ========================
546 // l3: [2, 4, 6]
547 // ========================
548 // sage: points = [(root1, 2), (root2, 4), (root3, 6), (root4, 0)]
549 // sage: P.lagrange_polynomial(points)
550 // 3465144826073652318776269530687742778270252468765361963007*x^3 +
551 // x^2 +
552 // 52435875175126190475982595682112313518914282969839895044333406231173219221504*x +
553 // 3
554 let l3 = DensePolynomial::from_coefficients_vec(vec![
555 Fr::from(3u64),
556 field_new!(
557 Fr,
558 "52435875175126190475982595682112313518914282969839895044333406231173219221504"
559 ),
560 Fr::one(),
561 field_new!(
562 Fr,
563 "3465144826073652318776269530687742778270252468765361963007"
564 ),
565 ]);
566
567 assert_eq!(l0, l[0], "l0 not equal");
568 assert_eq!(l1, l[1], "l1 not equal");
569 assert_eq!(l2, l[2], "l2 not equal");
570 assert_eq!(l3, l[3], "l3 not equal");
571 }
572 Ok(())
573 }
574
575 #[test]
576 fn test_qx() -> Result<(), PCSErrors> {
577 // Example from page 53:
578 // W1 = 3x1x2 + 2x2
579 let w_eval = vec![Fr::zero(), Fr::from(2u64), Fr::zero(), Fr::from(5u64)];
580 let w1 = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
581
582 // W2 = x1x2 + x1
583 let w_eval = vec![Fr::zero(), Fr::zero(), Fr::from(1u64), Fr::from(2u64)];
584 let w2 = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
585
586 // W3 = x1 + x2
587 let w_eval = vec![Fr::zero(), Fr::one(), Fr::from(1u64), Fr::from(2u64)];
588 let w3 = DenseMultilinearExtension::from_evaluations_vec(2, w_eval);
589
590 let r = Fr::from(42u64);
591
592 // point 1 is [1, 2]
593 let point1 = vec![Fr::from(1u64), Fr::from(2u64)];
594
595 // point 2 is [3, 4]
596 let point2 = vec![Fr::from(3u64), Fr::from(4u64)];
597
598 // point 3 is [5, 6]
599 let point3 = vec![Fr::from(5u64), Fr::from(6u64)];
600
601 {
602 let domain = get_uni_domain::<Fr>(2)?;
603 // w = (3x1x2 + 2x2)(1-x0) + (x1x2 + x1)x0
604 // with evaluations: [0,2,0,5,0,0,1,2]
605 let w = merge_polynomials(&[w1.clone(), w2.clone()])?;
606
607 let l = build_l(2, &[point1.clone(), point2.clone()], &domain)?;
608
609 // sage: P.<x> = PolynomialRing(ZZ)
610 // sage: l0 = -1/2 * x + 1/2
611 // sage: l1 = -x + 2
612 // sage: l2 = -x + 3
613 // sage: w = (3 * l1 * l2 + 2 * l2) * (1-l0) + (l1 * l2 + l1) * l0
614 // sage: w
615 // x^3 - 7/2*x^2 - 7/2*x + 16
616 //
617 // q(x) = x^3 - 7/2*x^2 - 7/2*x + 16
618 let q_x = compute_w_circ_l(&w, &l)?;
619
620 let point: Vec<Fr> = l.iter().rev().map(|poly| poly.evaluate(&r)).collect();
621
622 assert_eq!(
623 q_x.evaluate(&r),
624 w.evaluate(&point).unwrap(),
625 "q(r) != w(l(r))"
626 );
627 }
628
629 {
630 let domain = get_uni_domain::<Fr>(3)?;
631 // W = (3x1x2 + 2x2) * (1-y1) * (1-y2)
632 // + (x1x2 + x1) * (1-y1) * y2
633 // + (x1 + x2) * y1 * (1-y2)
634 let w = merge_polynomials(&[w1, w2, w3])?;
635
636 let l = build_l(2, &[point1, point2, point3], &domain)?;
637
638 // l0 =
639 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x^3 +
640 // 39326906381344642859585805381139474378267914375395728366952744024953935888385*x^2 +
641 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x +
642 // 39326906381344642859585805381139474378267914375395728366952744024953935888385
643 //
644 // l1 =
645 // 866286206518413079694067382671935694567563117191340490752*x^3 +
646 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x^2 +
647 // 52435875175126190478581454301667552757996485117855702128036095582747240693761*x +
648 // 39326906381344642859585805381139474378267914375395728366952744024953935888385
649 //
650 // l2 =
651 // 2598858619555239239082202148015807083702689351574021472255*x^3 +
652 // 13108968793781547619861935127046491459422638125131909455650914674984645296129*x^2 +
653 // 52435875175126190476848881888630726598608350352511830738900969348364559712256*x +
654 // 39326906381344642859585805381139474378267914375395728366952744024953935888387
655 //
656 // l3 =
657 // 3465144826073652318776269530687742778270252468765361963007*x^3 +
658 // x^2 +
659 // 52435875175126190475982595682112313518914282969839895044333406231173219221504*x +
660 // 3
661 //
662 // q_x = (3*l2*l3 + 2*l3) * (1-l0) *(1-l1)
663 // + (l2*l3+l2)*(1-l0)*l1
664 // + (l2+l3)*l0*(1-l1)
665 // q_x(42) = 42675783400755005965526147011103024780845819057955866345013183657072368533932
666 let q_x = compute_w_circ_l(&w, &l)?;
667
668 let point: Vec<Fr> = vec![
669 l[3].evaluate(&r),
670 l[2].evaluate(&r),
671 l[1].evaluate(&r),
672 l[0].evaluate(&r),
673 ];
674
675 assert_eq!(
676 q_x.evaluate(&r),
677 field_new!(
678 Fr,
679 "42675783400755005965526147011103024780845819057955866345013183657072368533932"
680 ),
681 );
682 assert_eq!(
683 q_x.evaluate(&r),
684 w.evaluate(&point).unwrap(),
685 "q(r) != w(l(r))"
686 );
687 }
688 Ok(())
689 }
690}