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::{MontFp, One};
85 use ark_poly::DenseUVPolynomial;
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::<Fr>(&[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 MontFp!(
146 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
147 ),
148 MontFp!(
149 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
150 ),
151 MontFp!(
152 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
153 ),
154 MontFp!(
155 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
156 ),
157 ]);
158
159 // ========================
160 // l1: [0, 1, 0]
161 // ========================
162 // sage: points = [(root1, 0), (root2, 1), (root3, 0), (root4, 0)]
163 // sage: P.lagrange_polynomial(points)
164 // 866286206518413079694067382671935694567563117191340490752*x^3 +
165 // 13108968793781547619861935127046491459422638125131909455650914674984645296128*x^2 +
166 // 52435875175126190478581454301667552757996485117855702128036095582747240693761*x +
167 // 39326906381344642859585805381139474378267914375395728366952744024953935888385
168 let l1 = DensePolynomial::from_coefficients_vec(vec![
169 MontFp!(
170 "39326906381344642859585805381139474378267914375395728366952744024953935888385"
171 ),
172 MontFp!(
173 "52435875175126190478581454301667552757996485117855702128036095582747240693761"
174 ),
175 MontFp!(
176 "13108968793781547619861935127046491459422638125131909455650914674984645296128"
177 ),
178 MontFp!("866286206518413079694067382671935694567563117191340490752"),
179 ]);
180
181 // ========================
182 // l2: [1, 3, 5]
183 // ========================
184 // sage: points = [(root1, 1), (root2, 3), (root3, 5), (root4, 0)]
185 // sage: P.lagrange_polynomial(points)
186 // 2598858619555239239082202148015807083702689351574021472255*x^3 +
187 // 13108968793781547619861935127046491459422638125131909455650914674984645296129*x^2 +
188 // 52435875175126190476848881888630726598608350352511830738900969348364559712256*x +
189 // 39326906381344642859585805381139474378267914375395728366952744024953935888387
190 let l2 = DensePolynomial::from_coefficients_vec(vec![
191 MontFp!(
192 "39326906381344642859585805381139474378267914375395728366952744024953935888387"
193 ),
194 MontFp!(
195 "52435875175126190476848881888630726598608350352511830738900969348364559712256"
196 ),
197 MontFp!(
198 "13108968793781547619861935127046491459422638125131909455650914674984645296129"
199 ),
200 MontFp!("2598858619555239239082202148015807083702689351574021472255"),
201 ]);
202
203 // ========================
204 // l3: [2, 4, 6]
205 // ========================
206 // sage: points = [(root1, 2), (root2, 4), (root3, 6), (root4, 0)]
207 // sage: P.lagrange_polynomial(points)
208 // 3465144826073652318776269530687742778270252468765361963007*x^3 +
209 // x^2 +
210 // 52435875175126190475982595682112313518914282969839895044333406231173219221504*x +
211 // 3
212 let l3 = DensePolynomial::from_coefficients_vec(vec![
213 Fr::from(3u64),
214 MontFp!(
215 "52435875175126190475982595682112313518914282969839895044333406231173219221504"
216 ),
217 Fr::one(),
218 MontFp!("3465144826073652318776269530687742778270252468765361963007"),
219 ]);
220
221 assert_eq!(l0, l[0], "l0 not equal");
222 assert_eq!(l1, l[1], "l1 not equal");
223 assert_eq!(l2, l[2], "l2 not equal");
224 assert_eq!(l3, l[3], "l3 not equal");
225 }
226 Ok(())
227 }
228
229 #[test]
230 fn test_build_l() -> Result<(), ArithErrors> {
231 test_build_l_helper::<Fr>()
232 }
233
234 fn test_build_l_helper<F: PrimeField>() -> Result<(), ArithErrors> {
235 // point 1 is [1, 2]
236 let point1 = vec![Fr::from(1u64), Fr::from(2u64)];
237
238 // point 2 is [3, 4]
239 let point2 = vec![Fr::from(3u64), Fr::from(4u64)];
240
241 // point 3 is [5, 6]
242 let point3 = vec![Fr::from(5u64), Fr::from(6u64)];
243
244 {
245 let domain = get_uni_domain::<Fr>(2)?;
246 let l = build_l(&[point1.clone(), point2.clone()], &domain, false)?;
247
248 // roots: [1, -1]
249 // l0 = -x + 2
250 // l1 = -x + 3
251 let l0 = DensePolynomial::from_coefficients_vec(vec![Fr::from(2u64), -Fr::one()]);
252 let l1 = DensePolynomial::from_coefficients_vec(vec![Fr::from(3u64), -Fr::one()]);
253
254 assert_eq!(l0, l[0], "l0 not equal");
255 assert_eq!(l1, l[1], "l1 not equal");
256 }
257
258 {
259 let domain = get_uni_domain::<Fr>(3)?;
260 let l = build_l(&[point1, point2, point3], &domain, false)?;
261
262 // sage: q = 52435875175126190479447740508185965837690552500527637822603658699938581184513
263 // sage: P.<x> = PolynomialRing(Zmod(q))
264 // sage: root1 = 1
265 // sage: root2 = 0x8D51CCCE760304D0EC030002760300000001000000000000
266 // sage: root3 = -1
267 // sage: root4 = -root2
268 // Arkwork's code is a bit wired: it also interpolate (root4, 0)
269 // which returns a degree 3 polynomial, instead of degree 2
270
271 // ========================
272 // l0: [1, 3, 5]
273 // ========================
274 // sage: points = [(root1, 1), (root2, 3), (root3, 5), (root4, 0)]
275 // sage: P.lagrange_polynomial(points)
276 // 2598858619555239239082202148015807083702689351574021472255*x^3 +
277 // 13108968793781547619861935127046491459422638125131909455650914674984645296129*x^2 +
278 // 52435875175126190476848881888630726598608350352511830738900969348364559712256*x +
279 // 39326906381344642859585805381139474378267914375395728366952744024953935888387
280 let l0 = DensePolynomial::from_coefficients_vec(vec![
281 MontFp!(
282 "39326906381344642859585805381139474378267914375395728366952744024953935888387"
283 ),
284 MontFp!(
285 "52435875175126190476848881888630726598608350352511830738900969348364559712256"
286 ),
287 MontFp!(
288 "13108968793781547619861935127046491459422638125131909455650914674984645296129"
289 ),
290 MontFp!("2598858619555239239082202148015807083702689351574021472255"),
291 ]);
292
293 // ========================
294 // l1: [2, 4, 6]
295 // ========================
296 // sage: points = [(root1, 2), (root2, 4), (root3, 6), (root4, 0)]
297 // sage: P.lagrange_polynomial(points)
298 // 3465144826073652318776269530687742778270252468765361963007*x^3 +
299 // x^2 +
300 // 52435875175126190475982595682112313518914282969839895044333406231173219221504*x +
301 // 3
302 let l1 = DensePolynomial::from_coefficients_vec(vec![
303 Fr::from(3u64),
304 MontFp!(
305 "52435875175126190475982595682112313518914282969839895044333406231173219221504"
306 ),
307 Fr::one(),
308 MontFp!("3465144826073652318776269530687742778270252468765361963007"),
309 ]);
310
311 assert_eq!(l0, l[0], "l0 not equal");
312 assert_eq!(l1, l[1], "l1 not equal");
313 }
314 Ok(())
315 }
316}