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