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