Skip to main content

​
Circle Evaluations and Polynomials

A polynomial can be represented in two main ways:
  1. Point-value representation: as evaluations over a domain
  2. 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 S-two and the respective functions defined on them to interpolate and evaluate polynomials.

​
Point-value representation

In S-two, 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 FF be an extension of the Mersenne prime field M31\mathsf{M31}. Then F[x,y]F[x, y] represents the ring of bivariate polynomials with coefficients in FF. The circle polynomials are bivariate polynomials over FF quotient by the ideal (x2+y2−1)\left(x^2 + y^2 - 1\right). The space of these bivariate polynomials over the circle curve of total degree ≤N/2\leq N/2 is denoted by LN(F)L_N(F). LN(F)=F[x,y]/(x2+y2−1)L_N(F) = F\left[x, y\right] / \left(x^2 + y^2 - 1\right) For any polynomial p(x,y)∈LN(F)p(x, y) \in L_N(F), we can substitute all the higher degree terms of yy with the equation of circle y2=1−x2y^2 = 1 - x^2 and reduce p(x,y)p(x, y) to the form: p(x,y)=p0(x)+y⋅p1(x),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)∈LN(F)p(x, y) \in L_N(F). Since p(x,y)p(x, y) is of total degree ≤N/2\leq N/2, p0p_0 has degree ≤N/2\leq N/2 and p1p_1 has degree ≤N/2−1\leq N/2 - 1. Thus an alternate representation of the space LN(F)L_N(F) is as follows: LN(F)=F[x]≤N/2+y⋅F[x]≤N/2−1L_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 LN(F)L_N(F) is spanned by the following monomial basis: 1,x,…,xN/2,y,y⋅x,…,y⋅xN/2−11, x, \ldots, x^{N/2}, y, y \cdot x, \ldots, y \cdot x^{N/2 - 1} The dimension of LN(F)L_N(F) is the number of monomial basis elements, which is N+1N + 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 S-two 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 S-two.

​
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: bj(n)(x,y):=yj0⋅xj1⋅π(x)j2⋅π2(x)j3⋯πn−2(x)jn−1b^{(n)}_j(x, y) := y^{j_0} \cdot x^{j_1} \cdot \pi(x)^{j_2} \cdot \pi^2(x)^{j_3} \cdots \pi^{n-2}(x)^{j_{n-1}} where
  • π\pi is the squaring map on the xx-coordinate i.e. π(x)=2x2−1\pi(x) = 2x^2 - 1 and πi\pi^i is applying the squaring map ii times, for example π2(x)=π(π(x))\pi^2(x) = \pi(\pi(x))
  • nn is log of the size of the CircleDomain
  • 0≤j≤2n−10 \leq j \leq 2^n - 1 and (j0,…,jn−1)∈{0,1}n(j_0, \ldots, j_{n-1}) \in \{0, 1\}^n is the binary representation of jj, i.e., j=j0+j1⋅2+⋯+jn−1⋅2n−1j = j_0 + j_1 \cdot 2 + \cdots + j_{n-1} \cdot 2^{n-1}
Thus the interpolate function computes coefficients cjc_j for polynomials p(x,y)p(x, y) of the form: p(x,y)=∑j=02n−1cj⋅yj0⋅xj1⋅π(x)j2⋅π2(x)j3⋯πn−2(x)jn−1p(x, y) = \sum_{j=0}^{2^n-1} c_j \cdot y^{j_0} \cdot x^{j_1} \cdot \pi(x)^{j_2} \cdot \pi^2(x)^{j_3} \cdots \pi^{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.