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