Univariate Polynomials

Polynomials are mathematical tools that encode data and relationships between data. They are used in Zero-Knowledge Protocols (ZKPs) to verify knowledge without revealing details of the shared information.

Types of Polynomials

Different types of polynomials serve similar functions in ZKP protocols but differ in structure, affecting how they encode and handle data:

• Univariate polynomials: Involve one variable (e.g., $ f(x) = x^2 + 3x + 2$ ).

• Multivariate polynomials: Involve multiple variables (e.g., $f(x,y) = x^2 + xy + y^2$ ).

• Multilinear polynomials: A type of multivariate polynomial where each variable has an exponent of 0 or 1 (e.g., $f(x,y) = x + y + xy$ ).

Univariate Polynomial

A univariate polynomial is a finite sum of terms, where each term is a coefficient multiplied by a monomial (a polynomial with only one term).

Breakdown:

• Coefficient: A constant number that multiplies the variable.

• Variable: The variable raised to a non-negative integer power (e.g.,s, x^5).

  An example of a univariate polynomial: $3x^2 + 2x + 5$

  Here’s the breakdown:

  • $3x^2$ : "3" is the coefficient, and $x^2$ is the monomial.

  • $2x$ : "2" is the coefficient, and $x$ is the monomial.

  • 5: This term has no visible variable because x^0

Sample Implementation

Below is a minimal implementation of a univariate polynomial, including two key functions: evaluate and interpolate.

UnivariatePolynomial Structure

Represents a univariate polynomial where the coefficients are elements from a finite field F.

    // Represented as a vector of Field elements
    #[derive(Clone, PartialEq, Eq, Hash, Default, Debug)]
    pub struct UnivariatePolynomial<F: PrimeField> {
        pub coefficients: Vec<F>,
    }

Creating a New Instance

Instantiates a new UnivariatePolynomial by initializing its coefficients.

    // Initialize a new polynomial instance
    pub fn new(coefficients: Vec<F>) -> Self {
        UnivariatePolynomial { coefficients }
    }

Evaluating the Polynomial at a Given Point

Evaluates the polynomial at a point x using Horner's method, an efficient algorithm for polynomial evaluation.

    fn evaluate(&self, x: &F) -> F {
        self.coefficients.iter().rev().fold(F::zero(), |acc, c| acc * x + c)
    }

Lagrange Interpolation

This function constructs a polynomial that passes through known points using Lagrange interpolation.

    fn interpolate(point_ys: Vec<F>, domain: Vec<F>) -> Self {
        let langrange_poly_vec = langrange_basis(&domain, &point_ys);
        let langrange_poly = langrange_poly_vec
            .iter()
            .fold(UnivariatePolynomial::new(vec![]), |acc, x| acc + x.clone());
        langrange_poly
    }


    pub fn lagrange_basis<F:PrimeField>(points: &Vec<F>, y_s:&Vec<F>) -> Vec<UnivariatePolynomial<F>>{
        let mut basis = Vec::new();
        assert!(points.len() == y_s.len(), "Length of points and y_s should be the same");
        for i in 0..points.len(){
            let mut basis_element = UnivariatePolynomial::new(vec![F::one()]);
            for j in 0..points.len(){
                if i == j{
                    continue;
                }
                let numerator = UnivariatePolynomial::from_coefficients_vec(vec![-points[j], F::one()]);
                let denominator = points[i] - points[j];
                basis_element = basis_element * (numerator * UnivariatePolynomial::from_coefficients_vec(vec![denominator.inverse().unwrap()]) )
            }
            basis.push(basis_element * UnivariatePolynomial::from_coefficients_vec(vec![y_s[i]]))
        }
        basis
    }

Steps in the Function:

1. Inputs:

   point_ys: A vector of y-values (polynomial values at given x-values).

   domain: A vector of x-values (points on the x-axis).

2. Calculate Lagrange Basis Polynomials:

   langrange_basis(&domain, &point_ys) Computes a vector of Lagrange basis polynomials. Each polynomial is 1 at its corresponding x-value and 0 at the others.

3. Combine Basis Polynomials:

   The fold function sums the Lagrange basis polynomials to form the final interpolated polynomial.

4. Return:

   The final polynomial is returned

Use Case

Polynomials in ZKPs help build privacy and scalability. They are used in protocols such as sum-check and GKR Protocol(Goldwasser, Kalai, and Rothblum), which are critical in proving statements without revealing the underlying data.