hyperplonk/arithmetic/src/univariate_polynomial.rs
arithmetic/src/univariate_polynomial.rsRaw
1// TODO: remove
2#![allow(dead_code)]
3
4use crate::{bit_decompose, ArithErrors};
5use ark_ff::PrimeField;
6use ark_poly::{
7 univariate::DensePolynomial, EvaluationDomain, Evaluations, Radix2EvaluationDomain,
8};
9use ark_std::log2;
10
11/// Given a list of points, build `l(points)` which is a list of univariate
12/// polynomials that goes through the points; extend the dimension of the points
13/// by `log(points.len())` if `with_suffix` is set.
14pub fn build_l<F: PrimeField>(
15 points: &[Vec<F>],
16 domain: &Radix2EvaluationDomain<F>,
17 with_suffix: bool,
18) -> Result<Vec<DensePolynomial<F>>, ArithErrors> {
19 let mut uni_polys = Vec::new();
20 if with_suffix {
21 // 1.1 build the indexes and the univariate polys that go through the indexes
22 let prefix_len = log2(points.len()) as usize;
23 let indexes: Vec<Vec<bool>> = (0..points.len())
24 .map(|x| bit_decompose(x as u64, prefix_len))
25 .collect();
26 for i in 0..prefix_len {
27 let eval: Vec<F> = indexes
28 .iter()
29 .map(|x| F::from(x[prefix_len - i - 1]))
30 .collect();
31
32 uni_polys.push(Evaluations::from_vec_and_domain(eval, *domain).interpolate());
33 }
34 }
35 // 1.2 build the actual univariate polys that go through the points
36 uni_polys.extend_from_slice(build_l_internal(points, domain)?.as_slice());
37
38 Ok(uni_polys)
39}
40
41/// Given a list of points, build `l(points)` which is a list of univariate
42/// polynomials that goes through the points.
43pub(crate) fn build_l_internal<F: PrimeField>(
44 points: &[Vec<F>],
45 domain: &Radix2EvaluationDomain<F>,
46) -> Result<Vec<DensePolynomial<F>>, ArithErrors> {
47 let mut uni_polys = Vec::new();
48 let num_var = points[0].len();
49 // build the actual univariate polys that go through the points
50 for i in 0..num_var {
51 let mut eval: Vec<F> = points.iter().map(|x| x[i]).collect();
52 eval.extend_from_slice(vec![F::zero(); domain.size as usize - eval.len()].as_slice());
53 uni_polys.push(Evaluations::from_vec_and_domain(eval, *domain).interpolate())
54 }
55 Ok(uni_polys)
56}
57
58/// get the domain for the univariate polynomial
59#[inline]
60pub fn get_uni_domain<F: PrimeField>(
61 uni_poly_degree: usize,
62) -> Result<Radix2EvaluationDomain<F>, ArithErrors> {
63 let domain = match Radix2EvaluationDomain::<F>::new(uni_poly_degree) {
64 Some(p) => p,
65 None => {
66 return Err(ArithErrors::InvalidParameters(
67 "failed to build radix 2 domain".to_string(),
68 ))
69 },
70 };
71 Ok(domain)
72}
73
74#[cfg(test)]
75mod test {
76 use super::*;
77 use ark_bls12_381::Fr;
78 use ark_ff::{field_new, One};
79 use ark_poly::UVPolynomial;
80
81 #[test]
82 fn test_build_l_with_suffix() -> Result<(), ArithErrors> {
83 test_build_l_with_suffix_helper::<Fr>()
84 }
85
86 fn test_build_l_with_suffix_helper<F: PrimeField>() -> Result<(), ArithErrors> {
87 // point 1 is [1, 2]
88 let point1 = vec![Fr::from(1u64), Fr::from(2u64)];
89
90 // point 2 is [3, 4]
91 let point2 = vec![Fr::from(3u64), Fr::from(4u64)];
92
93 // point 3 is [5, 6]
94 let point3 = vec![Fr::from(5u64), Fr::from(6u64)];
95
96 {
97 let domain = get_uni_domain::<Fr>(2)?;
98 let l = build_l(&[point1.clone(), point2.clone()], &domain, true)?;
99
100 // roots: [1, -1]
101 // l0 = -1/2 * x + 1/2
102 // l1 = -x + 2
103 // l2 = -x + 3
104 let l0 = DensePolynomial::from_coefficients_vec(vec![
105 Fr::one() / Fr::from(2u64),
106 -Fr::one() / Fr::from(2u64),
107 ]);
108 let l1 = DensePolynomial::from_coefficients_vec(vec![Fr::from(2u64), -Fr::one()]);
109 let l2 = DensePolynomial::from_coefficients_vec(vec![Fr::from(3u64), -Fr::one()]);
110
111 assert_eq!(l0, l[0], "l0 not equal");
112 assert_eq!(l1, l[1], "l1 not equal");
113 assert_eq!(l2, l[2], "l2 not equal");
114 }
115
116 {
117 let domain = get_uni_domain::<Fr>(3)?;
118 let l = build_l(&[point1, point2, point3], &domain, true)?;
119
120 // sage: q = 52435875175126190479447740508185965837690552500527637822603658699938581184513
121 // sage: P.<x> = PolynomialRing(Zmod(q))
122 // sage: root1 = 1
123 // sage: root2 = 0x8D51CCCE760304D0EC030002760300000001000000000000
124 // sage: root3 = -1
125 // sage: root4 = -root2
126 // Arkwork's code is a bit wired: it also interpolate (root4, 0)
127 // which returns a degree 3 polynomial, instead of degree 2
128
129 // ========================
130 // l0: [0, 0, 1]
131 // ========================
132 // sage: points = [(root1, 0), (root2, 0), (root3, 1), (root4, 0)]
133 // sage: P.lagrange_polynomial(points)
134 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x^3 +
135 // 39326906381344642859585805381139474378267914375395728366952744024953935888385*x^2 +
136 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x +
137 // 39326906381344642859585805381139474378267914375395728366952744024953935888385
138 let l0 = DensePolynomial::from_coefficients_vec(vec![
139 field_new!(
140 Fr,
141 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
142 ),
143 field_new!(
144 Fr,
145 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
146 ),
147 field_new!(
148 Fr,
149 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
150 ),
151 field_new!(
152 Fr,
153 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
154 ),
155 ]);
156
157 // ========================
158 // l1: [0, 1, 0]
159 // ========================
160 // sage: points = [(root1, 0), (root2, 1), (root3, 0), (root4, 0)]
161 // sage: P.lagrange_polynomial(points)
162 // 866286206518413079694067382671935694567563117191340490752*x^3 +
163 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x^2 +
164 // 52435875175126190478581454301667552757996485117855702128036095582747240693761*x +
165 // 39326906381344642859585805381139474378267914375395728366952744024953935888385
166 let l1 = DensePolynomial::from_coefficients_vec(vec![
167 field_new!(
168 Fr,
169 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
170 ),
171 field_new!(
172 Fr,
173 "52435875175126190478581454301667552757996485117855702128036095582747240693761"
174 ),
175 field_new!(
176 Fr,
177 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
178 ),
179 field_new!(
180 Fr,
181 "866286206518413079694067382671935694567563117191340490752"
182 ),
183 ]);
184
185 // ========================
186 // l2: [1, 3, 5]
187 // ========================
188 // sage: points = [(root1, 1), (root2, 3), (root3, 5), (root4, 0)]
189 // sage: P.lagrange_polynomial(points)
190 // 2598858619555239239082202148015807083702689351574021472255*x^3 +
191 // 13108968793781547619861935127046491459422638125131909455650914674984645296129*x^2 +
192 // 52435875175126190476848881888630726598608350352511830738900969348364559712256*x +
193 // 39326906381344642859585805381139474378267914375395728366952744024953935888387
194 let l2 = DensePolynomial::from_coefficients_vec(vec![
195 field_new!(
196 Fr,
197 "39326906381344642859585805381139474378267914375395728366952744024953935888387"
198 ),
199 field_new!(
200 Fr,
201 "52435875175126190476848881888630726598608350352511830738900969348364559712256"
202 ),
203 field_new!(
204 Fr,
205 "13108968793781547619861935127046491459422638125131909455650914674984645296129"
206 ),
207 field_new!(
208 Fr,
209 "2598858619555239239082202148015807083702689351574021472255"
210 ),
211 ]);
212
213 // ========================
214 // l3: [2, 4, 6]
215 // ========================
216 // sage: points = [(root1, 2), (root2, 4), (root3, 6), (root4, 0)]
217 // sage: P.lagrange_polynomial(points)
218 // 3465144826073652318776269530687742778270252468765361963007*x^3 +
219 // x^2 +
220 // 52435875175126190475982595682112313518914282969839895044333406231173219221504*x +
221 // 3
222 let l3 = DensePolynomial::from_coefficients_vec(vec![
223 Fr::from(3u64),
224 field_new!(
225 Fr,
226 "52435875175126190475982595682112313518914282969839895044333406231173219221504"
227 ),
228 Fr::one(),
229 field_new!(
230 Fr,
231 "3465144826073652318776269530687742778270252468765361963007"
232 ),
233 ]);
234
235 assert_eq!(l0, l[0], "l0 not equal");
236 assert_eq!(l1, l[1], "l1 not equal");
237 assert_eq!(l2, l[2], "l2 not equal");
238 assert_eq!(l3, l[3], "l3 not equal");
239 }
240 Ok(())
241 }
242
243 #[test]
244 fn test_build_l() -> Result<(), ArithErrors> {
245 test_build_l_helper::<Fr>()
246 }
247
248 fn test_build_l_helper<F: PrimeField>() -> Result<(), ArithErrors> {
249 // point 1 is [1, 2]
250 let point1 = vec![Fr::from(1u64), Fr::from(2u64)];
251
252 // point 2 is [3, 4]
253 let point2 = vec![Fr::from(3u64), Fr::from(4u64)];
254
255 // point 3 is [5, 6]
256 let point3 = vec![Fr::from(5u64), Fr::from(6u64)];
257
258 {
259 let domain = get_uni_domain::<Fr>(2)?;
260 let l = build_l(&[point1.clone(), point2.clone()], &domain, false)?;
261
262 // roots: [1, -1]
263 // l0 = -x + 2
264 // l1 = -x + 3
265 let l0 = DensePolynomial::from_coefficients_vec(vec![Fr::from(2u64), -Fr::one()]);
266 let l1 = DensePolynomial::from_coefficients_vec(vec![Fr::from(3u64), -Fr::one()]);
267
268 assert_eq!(l0, l[0], "l0 not equal");
269 assert_eq!(l1, l[1], "l1 not equal");
270 }
271
272 {
273 let domain = get_uni_domain::<Fr>(3)?;
274 let l = build_l(&[point1, point2, point3], &domain, false)?;
275
276 // sage: q = 52435875175126190479447740508185965837690552500527637822603658699938581184513
277 // sage: P.<x> = PolynomialRing(Zmod(q))
278 // sage: root1 = 1
279 // sage: root2 = 0x8D51CCCE760304D0EC030002760300000001000000000000
280 // sage: root3 = -1
281 // sage: root4 = -root2
282 // Arkwork's code is a bit wired: it also interpolate (root4, 0)
283 // which returns a degree 3 polynomial, instead of degree 2
284
285 // ========================
286 // l0: [1, 3, 5]
287 // ========================
288 // sage: points = [(root1, 1), (root2, 3), (root3, 5), (root4, 0)]
289 // sage: P.lagrange_polynomial(points)
290 // 2598858619555239239082202148015807083702689351574021472255*x^3 +
291 // 13108968793781547619861935127046491459422638125131909455650914674984645296129*x^2 +
292 // 52435875175126190476848881888630726598608350352511830738900969348364559712256*x +
293 // 39326906381344642859585805381139474378267914375395728366952744024953935888387
294 let l0 = DensePolynomial::from_coefficients_vec(vec![
295 field_new!(
296 Fr,
297 "39326906381344642859585805381139474378267914375395728366952744024953935888387"
298 ),
299 field_new!(
300 Fr,
301 "52435875175126190476848881888630726598608350352511830738900969348364559712256"
302 ),
303 field_new!(
304 Fr,
305 "13108968793781547619861935127046491459422638125131909455650914674984645296129"
306 ),
307 field_new!(
308 Fr,
309 "2598858619555239239082202148015807083702689351574021472255"
310 ),
311 ]);
312
313 // ========================
314 // l1: [2, 4, 6]
315 // ========================
316 // sage: points = [(root1, 2), (root2, 4), (root3, 6), (root4, 0)]
317 // sage: P.lagrange_polynomial(points)
318 // 3465144826073652318776269530687742778270252468765361963007*x^3 +
319 // x^2 +
320 // 52435875175126190475982595682112313518914282969839895044333406231173219221504*x +
321 // 3
322 let l1 = DensePolynomial::from_coefficients_vec(vec![
323 Fr::from(3u64),
324 field_new!(
325 Fr,
326 "52435875175126190475982595682112313518914282969839895044333406231173219221504"
327 ),
328 Fr::one(),
329 field_new!(
330 Fr,
331 "3465144826073652318776269530687742778270252468765361963007"
332 ),
333 ]);
334
335 assert_eq!(l0, l[0], "l0 not equal");
336 assert_eq!(l1, l[1], "l1 not equal");
337 }
338 Ok(())
339 }
340}