Circle Evaluations and Polynomials

A polynomial can be represented in two main ways:

Point-value representation: as evaluations over a domain
Coefficient representation: as coefficients with respect to some basis

The conversion from point-value representation to coefficient representation is called interpolation and the conversion from coefficient representation to point-value representation is called evaluation. Both these conversions are based on fast Fourier transform (FFT), which will be covered in the upcoming sections.

In this subsection, we will look at the implementations of both these representations in Stwo and the respective functions defined on them to interpolate and evaluate polynomials.

Point-value representation

In Stwo, the evaluations of a polynomial over a CircleDomain are stored using the struct CircleEvaluation, implemented as follows:

pub struct CircleEvaluation<B: ColumnOps<F>, F: ExtensionOf<BaseField>, EvalOrder = NaturalOrder> {
    pub domain: CircleDomain,
    pub values: Col<B, F>,
    _eval_order: PhantomData<EvalOrder>,
}

Here, the domain (i.e. CircleDomain) and the evaluations (i.e. values) have the same ordering (i.e. EvalOrder) which can either be NaturalOrder or BitReversedOrder.

Now given the evaluations over a domain as CircleEvaluation we can interpolate a circle polynomial using the following functions:

impl<B: PolyOps> CircleEvaluation<B, BaseField, BitReversedOrder> {
    /// Computes a minimal [CirclePoly] that evaluates to the same values as this evaluation.
    pub fn interpolate(self) -> CirclePoly<B> {
        let coset = self.domain.half_coset;
        B::interpolate(self, &B::precompute_twiddles(coset))
    }

    /// Computes a minimal [CirclePoly] that evaluates to the same values as this evaluation, using
    /// precomputed twiddles.
    pub fn interpolate_with_twiddles(self, twiddles: &TwiddleTree<B>) -> CirclePoly<B> {
        B::interpolate(self, twiddles)
    }
}

Here, PolyOps is a trait that defines operations on BaseField polynomials, such as interpolation and evaluation. Now before looking into the representation of the circle polynomial (i.e. CirclePoly), let us first look into some theory on polynomials over the circle.

Polynomials over the circle

Let $F$ be an extension of the Mersenne prime field $M31$ . Then $F [x, y]$ represents the ring of bivariate polynomials with coefficients in $F$ . The circle polynomials are bivariate polynomials over $F$ quotient by the ideal $(x^{2} + y^{2} - 1)$ . The space of these bivariate polynomials over the circle curve of total degree $\leq N /2$ is denoted by $L_{N} (F)$ .

$L_{N} (F) = F [x, y] / (x^{2} + y^{2} - 1)$

For any polynomial $p (x, y) \in L_{N} (F)$ , we can substitute all the higher degree terms of $y$ with the equation of circle $y^{2} = 1 - x^{2}$ and reduce $p (x, y)$ to the form:

$p (x, y) = p_{0} (x) + y \cdot p_{1} (x),$

The above form is called the canonical representation of any polynomial $p (x, y) \in L_{N} (F)$ . Since $p (x, y)$ is of total degree $\leq N /2$ , $p_{0}$ has degree $\leq N /2$ and $p_{1}$ has degree $\leq N /2 - 1$ . Thus an alternate representation of the space $L_{N} (F)$ is as follows:

$L_{N} (F) = F [x]^{\leq N /2} + y \cdot F [x]^{\leq N /2 - 1}$

From the above representation we can see that the space $L_{N} (F)$ is spanned by the following monomial basis:

$1, x, \dots, x^{N /2}, y, y \cdot x, \dots, y \cdot x^{N /2 - 1}$

The dimension of $L_{N} (F)$ is the number of monomial basis elements, which is $N + 1$ .

As a developer, you can usually ignore most of these details, since concepts like polynomial space and basis do not explicitly appear in the Stwo implementation. However, they do arise implicitly in the Circle FFT algorithm, as we will see in the next section.

Now let us describe the coefficient representation and how the circle polynomials are implemented in Stwo.

Coefficient representation

Given the evaluations over a domain (i.e. CircleEvaluation) we can compute the coefficients of a polynomial (i.e. CirclePoly) with respect to some basis using the interpolate function. The coefficients are stored as follows:

pub struct CirclePoly<B: ColumnOps<BaseField>> {
    /// Coefficients of the polynomial in the FFT basis.
    /// Note: These are not the coefficients of the polynomial in the standard
    /// monomial basis. The FFT basis is a tensor product of the twiddles:
    /// y, x, pi(x), pi^2(x), ..., pi^{log_size-2}(x).
    /// pi(x) := 2x^2 - 1.
    pub coeffs: Col<B, BaseField>,
    /// The number of coefficients stored as `log2(len(coeffs))`.
    log_size: u32,
}

The interpolate function computes the coefficients with respect to the following basis:

$b_{j}^{(n)} (x, y) := y^{j_{0}} \cdot x^{j_{1}} \cdot π (x)^{j_{2}} \cdot π^{2} (x)^{j_{3}} \dots π^{n - 2} (x)^{j_{n - 1}}$

where

$π$ is the squaring map on the $x$ -coordinate i.e. $π (x) = 2 x^{2} - 1$ and $π^{i}$ is applying the squaring map $i$ times, for example $π^{2} (x) = π (π (x))$
$n$ is log of the size of the CircleDomain
$0 \leq j \leq 2^{n} - 1$ and $(j_{0}, \dots, j_{n - 1}) \in {0, 1}^{n}$ is the binary representation of $j$ , i.e., $j = j_{0} + j_{1} \cdot 2 + \dots + j_{n - 1} \cdot 2^{n - 1}$

Thus the interpolate function computes coefficients $c_{j}$ for polynomials $p (x, y)$ of the form:

$p (x, y) = j = 0 \sum 2^{n} - 1 c_{j} \cdot y^{j_{0}} \cdot x^{j_{1}} \cdot π (x)^{j_{2}} \cdot π^{2} (x)^{j_{3}} \dots π^{n - 2} (x)^{j_{n - 1}}$

This polynomial form and its underlying basis are implicit in the Circle FFT construction, as we will see in the next section. However, as discussed earlier, you can largely ignore these details and simply view a polynomial as a set of evaluations over a domain, with its coefficients computed via the FFT algorithm.

Now given the coefficient representation as CirclePoly, we can evaluate the polynomial over a given domain (i.e. compute the CircleEvaluation) using the following functions:

    /// Evaluates the polynomial at all points in the domain.
    pub fn evaluate(
        &self,
        domain: CircleDomain,
    ) -> CircleEvaluation<B, BaseField, BitReversedOrder> {
        B::evaluate(self, domain, &B::precompute_twiddles(domain.half_coset))
    }

    /// Evaluates the polynomial at all points in the domain, using precomputed twiddles.
    pub fn evaluate_with_twiddles(
        &self,
        domain: CircleDomain,
        twiddles: &TwiddleTree<B>,
    ) -> CircleEvaluation<B, BaseField, BitReversedOrder> {
        B::evaluate(self, domain, twiddles)
    }

In the next section, we will see how the evaluations and polynomials are represented over the SecureField.

stwo-book

Circle Evaluations and Polynomials

Point-value representation

Polynomials over the circle

Coefficient representation