nova_snark/spartan/polys/
univariate.rs

1//! Main components:
2//! - `UniPoly`: an univariate dense polynomial in coefficient form (big endian),
3//! - `CompressedUniPoly`: a univariate dense polynomial, compressed (omitted linear term), in coefficient form (little endian),
4use crate::{
5  errors::NovaError,
6  traits::{
7    evm_serde::{CustomSerdeTrait, EvmCompatSerde},
8    AbsorbInRO2Trait, Engine, Group, ROTrait, TranscriptReprTrait,
9  },
10};
11use ff::PrimeField;
12use rayon::prelude::{IntoParallelIterator, ParallelIterator};
13use serde::{Deserialize, Serialize};
14use serde_with::serde_as;
15
16/// A univariate dense polynomial in coefficient form (little endian).
17/// For example, ax^2 + bx + c is stored as vec![c, b, a]
18/// and ax^3 + bx^2 + cx + d is stored as vec![d, c, b, a]
19#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
20pub struct UniPoly<Scalar: PrimeField> {
21  /// Coefficients of the polynomial, from constant term to highest degree.
22  pub coeffs: Vec<Scalar>,
23}
24
25/// A compressed univariate polynomial with the linear term omitted (little endian).
26/// For example, ax^2 + bx + c is stored as vec![c, a]
27/// and ax^3 + bx^2 + cx + d is stored as vec![d, c, a]
28#[serde_as]
29#[derive(Clone, Debug, Serialize, Deserialize)]
30pub struct CompressedUniPoly<Scalar: PrimeField + CustomSerdeTrait> {
31  #[serde_as(as = "Vec<EvmCompatSerde>")]
32  coeffs_except_linear_term: Vec<Scalar>,
33}
34
35impl<Scalar: PrimeField + CustomSerdeTrait> UniPoly<Scalar> {
36  /// Constructs a polynomial directly from its coefficients (little endian).
37  /// For example, ax^2 + bx + c should be passed as vec![c, b, a].
38  ///
39  /// Trailing zero coefficients are removed, keeping at least one coefficient
40  /// so that the zero polynomial is represented as `[Scalar::ZERO]`.
41  ///
42  /// # Errors
43  ///
44  /// Returns [`NovaError::InvalidInputLength`] if `coeffs` is empty.
45  pub fn from_coeffs(mut coeffs: Vec<Scalar>) -> Result<Self, NovaError> {
46    if coeffs.is_empty() {
47      return Err(NovaError::InvalidInputLength);
48    }
49    // Normalize by trimming trailing zeros, but keep at least one coefficient.
50    while coeffs.len() > 1 && coeffs.last().is_some_and(|c| bool::from(c.is_zero())) {
51      coeffs.pop();
52    }
53    Ok(Self { coeffs })
54  }
55
56  /// Constructs a polynomial from its evaluations using Gaussian elimination.
57  /// Given evals: [P(0), P(1), ..., P(n-1)], constructs the polynomial P(x).
58  pub fn from_evals(evals: &[Scalar]) -> Self {
59    let n = evals.len();
60
61    // Special case for constant polynomial (degree 0)
62    if n == 1 {
63      return Self {
64        coeffs: vec![evals[0]],
65      };
66    }
67
68    let xs: Vec<Scalar> = (0..n).map(|x| Scalar::from(x as u64)).collect();
69
70    let mut matrix: Vec<Vec<Scalar>> = Vec::with_capacity(n);
71    for i in 0..n {
72      let mut row = Vec::with_capacity(n);
73      let x = xs[i];
74      row.push(Scalar::ONE);
75      row.push(x);
76      for j in 2..n {
77        row.push(row[j - 1] * x);
78      }
79      row.push(evals[i]);
80      matrix.push(row);
81    }
82
83    let coeffs = gaussian_elimination(&mut matrix);
84    Self { coeffs }
85  }
86
87  /// Constructs a degree-2 polynomial from its evaluations.
88  /// The polynomial a*x^2 + b*x + c is constructed from evals: [c, a + b + c, a]
89  pub fn from_evals_deg2(evals: &[Scalar]) -> Self {
90    let c = evals[0];
91    let a = evals[2];
92    let a_b_c = evals[1];
93    let b = a_b_c - a - c;
94    Self {
95      coeffs: vec![c, b, a],
96    }
97  }
98
99  /// Constructs a degree-3 polynomial from its evaluations.
100  /// The polynomial a*x^3 + b*x^2 + c*x + d is constructed from evals: [d, a + b + c, a, -a + b - c + d]
101  pub fn from_evals_deg3(evals: &[Scalar]) -> Self {
102    let d = evals[0];
103    let a = evals[2];
104    let a_b_c_d = evals[1];
105    let b2_d2 = a_b_c_d + evals[3];
106    let b = b2_d2 * Scalar::TWO_INV - d;
107    let c = a_b_c_d - a - d - b;
108    Self {
109      coeffs: vec![d, c, b, a],
110    }
111  }
112
113  /// Returns a reference to the coefficients (little-endian order).
114  pub fn coeffs(&self) -> &[Scalar] {
115    &self.coeffs
116  }
117
118  /// Returns the degree of the polynomial.
119  pub fn degree(&self) -> usize {
120    self.coeffs.len() - 1
121  }
122
123  /// Evaluates the polynomial at zero, returning the constant term.
124  pub fn eval_at_zero(&self) -> Scalar {
125    self.coeffs[0]
126  }
127
128  /// Evaluates the polynomial at one, returning the sum of all coefficients.
129  pub fn eval_at_one(&self) -> Scalar {
130    (0..self.coeffs.len())
131      .into_par_iter()
132      .map(|i| self.coeffs[i])
133      .sum()
134  }
135
136  /// Evaluates the polynomial at the given point using Horner's method.
137  pub fn evaluate(&self, r: &Scalar) -> Scalar {
138    let mut eval = self.coeffs[0];
139    let mut power = *r;
140    for coeff in self.coeffs.iter().skip(1) {
141      eval += power * coeff;
142      power *= r;
143    }
144    eval
145  }
146
147  /// Compresses the polynomial by omitting the linear term.
148  pub fn compress(&self) -> CompressedUniPoly<Scalar> {
149    let coeffs_except_linear_term = [&self.coeffs[0..1], &self.coeffs[2..]].concat();
150    assert_eq!(coeffs_except_linear_term.len() + 1, self.coeffs.len());
151    CompressedUniPoly {
152      coeffs_except_linear_term,
153    }
154  }
155}
156
157impl<Scalar: PrimeField + CustomSerdeTrait> CompressedUniPoly<Scalar> {
158  /// Decompresses the polynomial by recovering the linear term using the hint.
159  /// We require eval(0) + eval(1) = hint, so we can solve for the linear term as:
160  /// linear_term = hint - 2 * constant_term - deg2 term - deg3 term
161  pub fn decompress(&self, hint: &Scalar) -> UniPoly<Scalar> {
162    let mut linear_term =
163      *hint - self.coeffs_except_linear_term[0] - self.coeffs_except_linear_term[0];
164    for i in 1..self.coeffs_except_linear_term.len() {
165      linear_term -= self.coeffs_except_linear_term[i];
166    }
167
168    let mut coeffs: Vec<Scalar> = Vec::new();
169    coeffs.push(self.coeffs_except_linear_term[0]);
170    coeffs.push(linear_term);
171    coeffs.extend(&self.coeffs_except_linear_term[1..]);
172    assert_eq!(self.coeffs_except_linear_term.len() + 1, coeffs.len());
173    UniPoly { coeffs }
174  }
175}
176
177impl<G: Group> TranscriptReprTrait<G> for UniPoly<G::Scalar>
178where
179  G::Scalar: CustomSerdeTrait,
180{
181  fn to_transcript_bytes(&self) -> Vec<u8> {
182    let coeffs = self.compress().coeffs_except_linear_term;
183    #[cfg(not(feature = "evm"))]
184    {
185      coeffs
186        .iter()
187        .flat_map(|&t| t.to_repr().as_ref().to_vec())
188        .collect::<Vec<u8>>()
189    }
190    #[cfg(feature = "evm")]
191    {
192      coeffs
193        .iter()
194        .flat_map(|&t| {
195          t.to_repr()
196            .as_ref()
197            .iter()
198            .rev()
199            .cloned()
200            .collect::<Vec<u8>>()
201        })
202        .collect::<Vec<u8>>()
203    }
204  }
205}
206
207impl<E: Engine> AbsorbInRO2Trait<E> for UniPoly<E::Scalar> {
208  fn absorb_in_ro2(&self, ro: &mut E::RO2) {
209    for coeff in &self.coeffs {
210      ro.absorb(*coeff);
211    }
212  }
213}
214
215/// Performs Gaussian elimination on the given augmented matrix to solve a system of linear equations.
216/// This code is based on code from <https://github.com/a16z/jolt/blob/main/jolt-core/src/utils/gaussian_elimination.rs>,
217/// which itself is inspired by <https://github.com/TheAlgorithms/Rust/blob/master/src/math/gaussian_elimination.rs>
218pub fn gaussian_elimination<F: PrimeField>(matrix: &mut [Vec<F>]) -> Vec<F> {
219  let size = matrix.len();
220  assert_eq!(size, matrix[0].len() - 1);
221
222  for i in 0..size - 1 {
223    for j in i..size - 1 {
224      echelon(matrix, i, j);
225    }
226  }
227
228  for i in (1..size).rev() {
229    eliminate(matrix, i);
230  }
231
232  let mut result: Vec<F> = vec![F::ZERO; size];
233  for i in 0..size {
234    result[i] = div_f(matrix[i][size], matrix[i][i]);
235  }
236
237  result
238}
239
240fn echelon<F: PrimeField>(matrix: &mut [Vec<F>], i: usize, j: usize) {
241  let size = matrix.len();
242  if matrix[i][i] != F::ZERO {
243    let factor = div_f(matrix[j + 1][i], matrix[i][i]);
244    (i..size + 1).for_each(|k| {
245      let tmp = matrix[i][k];
246      matrix[j + 1][k] -= factor * tmp;
247    });
248  }
249}
250
251fn eliminate<F: PrimeField>(matrix: &mut [Vec<F>], i: usize) {
252  let size = matrix.len();
253  if matrix[i][i] != F::ZERO {
254    for j in (1..i + 1).rev() {
255      let factor = div_f(matrix[j - 1][i], matrix[i][i]);
256      for k in (0..size + 1).rev() {
257        let tmp = matrix[i][k];
258        matrix[j - 1][k] -= factor * tmp;
259      }
260    }
261  }
262}
263
264/// Division of two prime fields
265///
266/// # Panics
267///
268/// Panics if `b` is zero.
269pub fn div_f<F: PrimeField>(a: F, b: F) -> F {
270  let inverse_b = b.invert();
271
272  if inverse_b.into_option().is_none() {
273    panic!("Division by zero");
274  }
275
276  a * inverse_b.unwrap()
277}
278
279#[cfg(test)]
280mod tests {
281  use super::*;
282  use crate::provider::{bn256_grumpkin::bn256, pasta::pallas, secp_secq::secp256k1};
283
284  fn test_from_evals_quad_with<F: PrimeField + CustomSerdeTrait>() {
285    // polynomial is 2x^2 + 3x + 1
286    let e0 = F::ONE;
287    let e1 = F::from(6);
288    let e2 = F::from(2);
289    let evals = vec![e0, e1, e2];
290    let poly = UniPoly::from_evals_deg2(&evals);
291
292    assert_eq!(poly.eval_at_zero(), e0);
293    assert_eq!(poly.eval_at_one(), e1);
294    assert_eq!(poly.coeffs.len(), 3);
295    assert_eq!(poly.coeffs[0], F::ONE);
296    assert_eq!(poly.coeffs[1], F::from(3));
297    assert_eq!(poly.coeffs[2], F::from(2));
298
299    let hint = e0 + e1;
300    let compressed_poly = poly.compress();
301    let decompressed_poly = compressed_poly.decompress(&hint);
302    for i in 0..decompressed_poly.coeffs.len() {
303      assert_eq!(decompressed_poly.coeffs[i], poly.coeffs[i]);
304    }
305
306    let e3 = F::from(28);
307    assert_eq!(poly.evaluate(&F::from(3)), e3);
308  }
309
310  #[test]
311  fn test_from_evals_quad() {
312    test_from_evals_quad_with::<pallas::Scalar>();
313    test_from_evals_quad_with::<bn256::Scalar>();
314    test_from_evals_quad_with::<secp256k1::Scalar>();
315  }
316
317  fn test_from_evals_cubic_with<F: PrimeField + CustomSerdeTrait>() {
318    // polynomial is x^3 + 2x^2 + 3x + 1
319    let e0 = F::ONE; // f(0)
320    let e1 = F::from(7); // f(1)
321    let e2 = F::ONE; // cubic term
322    let e3 = -F::ONE; // f(-1)
323    let evals = vec![e0, e1, e2, e3];
324    let poly = UniPoly::from_evals_deg3(&evals);
325
326    assert_eq!(poly.eval_at_zero(), e0);
327    assert_eq!(poly.eval_at_one(), e1);
328    assert_eq!(poly.coeffs.len(), 4);
329
330    assert_eq!(poly.coeffs[1], F::from(3));
331    assert_eq!(poly.coeffs[2], F::from(2));
332    assert_eq!(poly.coeffs[3], F::from(1));
333
334    let hint = e0 + e1;
335    let compressed_poly = poly.compress();
336    let decompressed_poly = compressed_poly.decompress(&hint);
337    for i in 0..decompressed_poly.coeffs.len() {
338      assert_eq!(decompressed_poly.coeffs[i], poly.coeffs[i]);
339    }
340
341    let e4 = F::from(109);
342    assert_eq!(poly.evaluate(&F::from(4)), e4);
343  }
344
345  #[test]
346  fn test_from_evals_cubic() {
347    test_from_evals_cubic_with::<pallas::Scalar>();
348    test_from_evals_cubic_with::<bn256::Scalar>();
349    test_from_evals_cubic_with::<secp256k1::Scalar>()
350  }
351
352  fn test_from_evals_constant_with<F: PrimeField + CustomSerdeTrait>() {
353    // polynomial is 5 (constant)
354    let evals = vec![F::from(5)];
355    let poly = UniPoly::from_evals(&evals);
356
357    assert_eq!(poly.coeffs.len(), 1);
358    assert_eq!(poly.coeffs[0], F::from(5));
359    assert_eq!(poly.evaluate(&F::ZERO), F::from(5));
360    assert_eq!(poly.evaluate(&F::ONE), F::from(5));
361    assert_eq!(poly.evaluate(&F::from(100)), F::from(5));
362  }
363
364  #[test]
365  fn test_from_evals_constant() {
366    test_from_evals_constant_with::<pallas::Scalar>();
367    test_from_evals_constant_with::<bn256::Scalar>();
368    test_from_evals_constant_with::<secp256k1::Scalar>();
369  }
370
371  fn test_from_evals_linear_with<F: PrimeField + CustomSerdeTrait>() {
372    // polynomial is 3x + 2
373    let e0 = F::from(2); // f(0) = 2
374    let e1 = F::from(5); // f(1) = 3 + 2 = 5
375    let evals = vec![e0, e1];
376    let poly = UniPoly::from_evals(&evals);
377
378    assert_eq!(poly.coeffs.len(), 2);
379    assert_eq!(poly.coeffs[0], F::from(2)); // constant term
380    assert_eq!(poly.coeffs[1], F::from(3)); // linear term
381    assert_eq!(poly.evaluate(&F::ZERO), e0);
382    assert_eq!(poly.evaluate(&F::ONE), e1);
383    assert_eq!(poly.evaluate(&F::from(2)), F::from(8)); // 3*2 + 2 = 8
384  }
385
386  #[test]
387  fn test_from_evals_linear() {
388    test_from_evals_linear_with::<pallas::Scalar>();
389    test_from_evals_linear_with::<bn256::Scalar>();
390    test_from_evals_linear_with::<secp256k1::Scalar>();
391  }
392
393  fn test_from_evals_quadratic_with<F: PrimeField + CustomSerdeTrait>() {
394    // polynomial is 2x^2 + 3x + 1
395    let e0 = F::ONE; // f(0) = 1
396    let e1 = F::from(6); // f(1) = 2 + 3 + 1 = 6
397    let e2 = F::from(15); // f(2) = 8 + 6 + 1 = 15
398    let evals = vec![e0, e1, e2];
399    let poly = UniPoly::from_evals(&evals);
400
401    assert_eq!(poly.coeffs.len(), 3);
402    assert_eq!(poly.coeffs[0], F::ONE);
403    assert_eq!(poly.coeffs[1], F::from(3));
404    assert_eq!(poly.coeffs[2], F::from(2));
405    assert_eq!(poly.evaluate(&F::ZERO), e0);
406    assert_eq!(poly.evaluate(&F::ONE), e1);
407    assert_eq!(poly.evaluate(&F::from(2)), e2);
408    assert_eq!(poly.evaluate(&F::from(3)), F::from(28)); // 18 + 9 + 1 = 28
409  }
410
411  #[test]
412  fn test_from_evals_quadratic() {
413    test_from_evals_quadratic_with::<pallas::Scalar>();
414    test_from_evals_quadratic_with::<bn256::Scalar>();
415    test_from_evals_quadratic_with::<secp256k1::Scalar>();
416  }
417
418  fn test_from_evals_quartic_with<F: PrimeField + CustomSerdeTrait>() {
419    // polynomial is x^4 + 2x^3 + 3x^2 + 4x + 5
420    let e0 = F::from(5); // f(0) = 5
421    let e1 = F::from(15); // f(1) = 1 + 2 + 3 + 4 + 5 = 15
422    let e2 = F::from(57); // f(2) = 16 + 16 + 12 + 8 + 5 = 57
423    let e3 = F::from(179); // f(3) = 81 + 54 + 27 + 12 + 5 = 179
424    let e4 = F::from(453); // f(4) = 256 + 128 + 48 + 16 + 5 = 453
425    let evals = vec![e0, e1, e2, e3, e4];
426    let poly = UniPoly::from_evals(&evals);
427
428    assert_eq!(poly.coeffs.len(), 5);
429    assert_eq!(poly.coeffs[0], F::from(5)); // constant
430    assert_eq!(poly.coeffs[1], F::from(4)); // x
431    assert_eq!(poly.coeffs[2], F::from(3)); // x^2
432    assert_eq!(poly.coeffs[3], F::from(2)); // x^3
433    assert_eq!(poly.coeffs[4], F::from(1)); // x^4
434    assert_eq!(poly.evaluate(&F::ZERO), e0);
435    assert_eq!(poly.evaluate(&F::ONE), e1);
436    assert_eq!(poly.evaluate(&F::from(2)), e2);
437    assert_eq!(poly.evaluate(&F::from(3)), e3);
438  }
439
440  #[test]
441  fn test_from_evals_quartic() {
442    test_from_evals_quartic_with::<pallas::Scalar>();
443    test_from_evals_quartic_with::<bn256::Scalar>();
444    test_from_evals_quartic_with::<secp256k1::Scalar>();
445  }
446
447  fn test_from_coeffs_with<F: PrimeField + CustomSerdeTrait>() {
448    // polynomial is 2x^2 + 3x + 1, stored little-endian as [1, 3, 2]
449    let poly = UniPoly::from_coeffs(vec![F::ONE, F::from(3), F::from(2)]).unwrap();
450
451    // Verify coefficient ordering (little-endian: constant term first)
452    assert_eq!(poly.coeffs.len(), 3);
453    assert_eq!(poly.coeffs[0], F::ONE); // constant term
454    assert_eq!(poly.coeffs[1], F::from(3)); // linear term
455    assert_eq!(poly.coeffs[2], F::from(2)); // quadratic term
456
457    // Verify evaluations are consistent with the stored coefficients
458    assert_eq!(poly.eval_at_zero(), F::ONE); // P(0) = 1
459    assert_eq!(poly.eval_at_one(), F::from(6)); // P(1) = 2 + 3 + 1 = 6
460    assert_eq!(poly.evaluate(&F::from(2)), F::from(15)); // P(2) = 8 + 6 + 1 = 15
461    assert_eq!(poly.evaluate(&F::from(3)), F::from(28)); // P(3) = 18 + 9 + 1 = 28
462  }
463
464  #[test]
465  fn test_from_coeffs() {
466    test_from_coeffs_with::<pallas::Scalar>();
467    test_from_coeffs_with::<bn256::Scalar>();
468    test_from_coeffs_with::<secp256k1::Scalar>();
469  }
470
471  fn test_from_coeffs_edge_cases_with<F: PrimeField + CustomSerdeTrait>() {
472    // Edge case: empty vector — from_coeffs returns an error
473    let result: Result<UniPoly<F>, _> = UniPoly::from_coeffs(vec![]);
474    assert!(result.is_err());
475
476    // Edge case: trailing zeros are normalized away
477    // 2x^2 + 3x + 1 with an appended zero coefficient (i.e., 0*x^3 term)
478    let poly = UniPoly::from_coeffs(vec![F::ONE, F::from(3), F::from(2), F::ZERO]).unwrap();
479    assert_eq!(poly.coeffs.len(), 3); // trailing zero is trimmed
480    assert_eq!(poly.coeffs[2], F::from(2)); // highest non-zero coefficient
481
482    // Evaluation is still correct after normalization
483    assert_eq!(poly.eval_at_zero(), F::ONE); // P(0) = 1
484    assert_eq!(poly.eval_at_one(), F::from(6)); // P(1) = 1 + 3 + 2 = 6
485    assert_eq!(poly.evaluate(&F::from(2)), F::from(15)); // P(2) = 8 + 6 + 1 = 15
486
487    // All-zero coefficients: collapses to a single zero coefficient
488    let zero_poly = UniPoly::from_coeffs(vec![F::ZERO, F::ZERO, F::ZERO]).unwrap();
489    assert_eq!(zero_poly.coeffs.len(), 1);
490    assert!(bool::from(zero_poly.coeffs[0].is_zero()));
491  }
492
493  #[test]
494  fn test_from_coeffs_edge_cases() {
495    test_from_coeffs_edge_cases_with::<pallas::Scalar>();
496    test_from_coeffs_edge_cases_with::<bn256::Scalar>();
497    test_from_coeffs_edge_cases_with::<secp256k1::Scalar>();
498  }
499}
nova_snark/spartan/polys/univariate.rs

nova_snark/spartan/polys/
univariate.rs
