Commiting to polynomials in evaluation form

[mimoo]

Our commitment scheme, based on an inner-product argument, is defined on polynomials that are in monomial form (i.e. we know the coefficients in $f = a_0 + a_1 x + a_2 x^2 + \cdots$ ).

But often, we manipulate polynomials in evaluation form. We do this by maintaining a list of evaluations $(f(0), f(\omega), f(\omega^2), \cdots)$ of our polynomial where the points are the elements of the cyclic group generated by $\omega$. We just need more than the degree of the polynomial to be able to find back our polynomial (via interpolation).

We'd like to avoid having to interpolate in order to commit to our polynomial as the prover. This document describes a way to commit to polynomials which are in evaluation form.

Note that there are two schemes for that: a base scheme, and a chunked scheme for supporting chunked polynomials (when the URS/SRS is too small).

Base scheme

Preliminary: Lagrange basis

A lagrange basis is a polynomial $L_i(x)$ such that

$$ L_i(x) = \begin{cases}1 \text{ if } x = \omega^i \\ 0 \text{ if } x = w^j \text{ where } j \neq i\end{cases} $$

You can find more information in the section Lagrange basis in multiplicative subgroups of the Mina book.

Preliminary: Interpolating via the lagrange basis

Imagine that you have the following list of evaluations: $(a_0, a_1, a_2, \cdots)$, then the polynomial in monomial form can be obtained by computing:

$$ f(x) = a_0 \cdot L_0(x) + a_1 \cdot L_1(x) + a_2 \cdot L_2(x) + \cdots $$

(That is, if $a$ is the evaluation of $f$ at $0$, $b$ is the evaluation of $f$ at $\omega$, $c$ is the evaluation of $f$ at $\omega^2$, and so on...)

You can easily see that $f(0) = a_0, f(\omega) = a_1, f(\omega^2) = a_2$, and so on...

The final scheme

Since commitments are additively homomorphic in our scheme, we can take commitments to the lagrange basis and perform the same computation (in the form of a multi-scalar multiplication):

$$ a_0 \cdot com(L_0(x)) + a_1 \cdot com(L_1(x)) + a_2 \cdot com(L_2(x)) + \cdots $$

Chunked scheme

Preliminary: Chunked polynomials

Our domain can be larger than the SRS sometimes. This is because of two reasons:

1. either our circuit is larger than the SRS, and thus we had to find a larger domain
2. or one of our polynomial is of degree larger than the circuit. This is true for the permutation, the poseidon gate, and the quotient polynomial (all of degree $8(n-1)$ where $n$ is the size of the circuit/domain).

In the first case, the domain is not necessarily a multiple of the SRS. Whereas in the second case, it should be. (TODO: is this correct?)

Currently we only send a commitment of the quotient polynomial, and we interpolate that polynomial before committing to it (due to the lack of support for commiting chunked polynomials (TODO: can we do it now?)).

Chunked polynomials are supported in kimchi by default, due to the polynomial commitment data structure storing a vector of commitment, instead of a single commitment:

pub struct PolyComm<C> {
  pub unshifted: Vec<C>,
  // <omitted field>
}

Preliminary: Commiting to chunked polynomials

Imagine that our polynomial is evaluated over d8 (because its degree is getting close to d8-1). That is, we have a lot of evaluations and lagrange basis.
But our SRS is something smaller, like d1 (8 times smaller than d8). This means that our previous formula doesn't work anymore:

$$ f(x) = a_0 \cdot L_0(x) + a_1 \cdot L_1(x) + a_2 \cdot L_2(x) + \cdots + a_{d8 - 1} L_{d8 - 1}(x) $$

This is because:

1. commiting to this polynomial should give 8 chunked commitments (the unshifted part of our type PolyComm)
2. the lagrange basis are now of degree d8-1 and so we can't produce their commitment (but we can produce a chunked commitment of each lagrange basis)

So this is what we want to do. For each lagrange basis we had previously, we want to produce 8 commitments that represent different chunks of it (the same way we've already chunked polynomials to commit to them).

More specifically, if a lagrange polynomial looks like this:

$$ L_0(x) = l_{0,0} + l_{0,1} x + l_{0,2} x^2 + l_{0,3} x^3 + l_{0,4} x^4 + \cdots $$

and our previous computation started with:

$$ a_0 \cdot L_0(x) = a_0 \cdot (l_{0,0} + l_{0,1} x + l_{0,2} x^2 + l_{0,3} x^3 + l_{0,4} x^4 + \cdots) $$

then we should be able to chunk that however we want. For example in chunks of degree 1:

$$ a_0 \cdot (l_{0,0} + l_{0,1} x) + x^2 \cdot a_0 \cdot (l_{0,2} + l_{0,3} x) + \cdots $$

Now imagine $f$ can be divided into a number of chunks of degree 1 like so:

$$ f(x) = f_0(x) + x \cdot f_1(x) + x^2 \cdot f_2(x) + \cdots $$

then we should have

$$ f_0(x) = a_0 \cdot (l_{0, 0} + l_{0, 1} x) + a_1 \cdot (l_{1, 0} + l_{1, 1} x) + \cdots $$

and

$$ f_1(x) = a_0 \cdot (l_{0, 2} + l_{0, 3} x) + a_1 \cdot (l_{1, 2} + l_{1, 3} x) + \cdots $$

and so on...

The chunked scheme

We produce the list of lagrange basis as with the previous scheme, but this time we commit to them in chunks (let's say $i$ chunks per lagrange basis).

Thus, the first lagrange basis should now look like $i$ commitments to the $i$ chunks $L_{0, 0}, L_{0, 1}, L_{0, 2}, \cdots$.

Then to commit to a polynomial via its evaluations, we produce $i$ chunks. Where each chunk is computed as:

$$ a_0 \cdot com(L_{0, i}(x)) + a_1 \cdot com(L_{1, i}(x)) + a_2 \cdot com(L_{2, i}(x)) + \cdots $$

Bonus: how to efficiently compute commitments to the lagrange basis

For the base scheme

We have an implementation of an algorithm making use of the IFFT to speed this up. It's in poly-commitment/src/srs.rs. There's a comment from Izaak there that I've copied here:

Let $V$ be a vector space over the field $\mathbb{F}$.

Given:

• a domain $[ 1, w, w^2, ..., w^{n - 1} ]$
• a vector $v = [ v_0, ..., v_{n - 1} ]$ in $V^n$

the FFT algorithm computes the matrix application

$$ u = M(w) * v $$

where

M(w) =
  1 1       1           ... 1
  1 w       w^2         ... w^{n-1}
  ...
  1 w^{n-1} (w^2)^{n-1} ... (w^{n-1})^{n-1}

The IFFT algorithm computes

$$ v = M(w)^{-1} * u $$

Let's see how we can use this algorithm to compute the lagrange basis
commitments.

Let $V$ be the vector space $\mathbb{F}[x]$ of polynomials in $x$ over $F$.
Let $v$ in $V$ be the vector $[ L_0, ..., L_{n - 1} ]$ where $L_i$ is the $i^{th}$
normalized Lagrange polynomial (where L_i(w^j) = j == i ? 1 : 0).

Consider the rows of $M(w) * v$. Let me write out the matrix and vector so you
can see more easily.

  | 1 1       1           ... 1               |   | L_0     |
  | 1 w       w^2         ... w^{n-1}         | * | L_1     |
  | ...                                       |   | ...     |
  | 1 w^{n-1} (w^2)^{n-1} ... (w^{n-1})^{n-1} |   | L_{n-1} |

The 0th row is $L_0 + L1 + ... + L_{n - 1}$. So, it's the polynomial
that has the value 1 on every element of the domain.
In other words, it's the polynomial 1.

The 1st row is $L_0 + w L_1 + ... + w^{n - 1} L_{n - 1}$. So, it's the
polynomial which has value $w^i$ on $w^i$.
In other words, it's the polynomial $x$.

In general, you can see that row i is in fact the polynomial $x^i$.

Thus, $M(w) * v$ is the vector $u$, where $u = [ 1, x, x^2, ..., x^n ]$.

Therefore, the IFFT algorithm, when applied to the vector $u$ (the standard
monomial basis) will yield the vector $v$ of the (normalized) Lagrange polynomials.

Now, because the polynomial commitment scheme is additively homomorphic, and
because the commitment to the polynomial $x^i$ is just self.g[i], we can obtain
commitments to the normalized Lagrange polynomials by applying IFFT to the
vector self.g[0..n].

For the chunked scheme

Copying Matthew's comment:

Further still, we can do the same trick for 'chunked' polynomials.

Recall that a chunked polynomial is some $f$ of degree $k \cdot n - 1$ with

$$ f(x) = f_0(x) + x^n f_1(x) + ... + x^{(k-1) n} f_{k-1}(x) $$

where each $f_i$ has degree $n-1.$

In the above, if we set $u = [ 1, x^2, ... x^{n-1}, 0, 0, .., 0 ]$
then we effectively 'zero out' any polynomial terms higher than $x^{n-1}$, leaving
us with the 'partial Lagrange polynomials' that contribute to $f_0$.

Similarly, $u = [ 0, 0, ..., 0, 1, x^2, ..., x^{n-1}, 0, 0, ..., 0]$ with $n$ leading
zeros 'zeroes out' all terms except the 'partial Lagrange polynomials' that
contribute to $f_1$, and likewise for each $f_i$.

By computing each of these, and recollecting the terms as a vector of polynomial
commitments, we obtain a chunked commitment to the $L_i$ polynomials.

Dealing with shifted

Copying Matthew's comment:

Our chunk size is always let k = srs.g.len(). If that doesn't divide the domain size, we want to ensure that the prover hasn't committed to a polynomial larger than the domain. Thus, we need to do an 'upper bound check' by shifting the most significant chunk of the polynomial all the way to the right.

Consider a chunked polynomial commitment of degree n, where 3 * k < n < 4 * k.

PolyComm { shifted: Some(s_comm), unshifted: [a_comm, b_comm, c_comm, d_comm] }

which corresponds to some evaluations at a point p of

[a_p, b_p, c_p, d_p]

So, we can check using an opening proof that

• a_comm opens at a_p,
• b_comm opens at b_p,
• c_comm opens at c_p,
• d_comm opens at d_p

to confirm that the user has committed to some polynomial of maximum degree 4 * k which evaluates at p to a + p^k * b + p^(2k) * c + p^(3k) * d. However, if k doesn't divide the domain size, the prover's polynomial may be too large, which may allow them to create an invalid proof by cheating the vanishing polynomial division check.

To circumvent this, we make sure that the maximum degree of d_comm is n%k by providing s_comm that opens at p to d_p * p^{k - n%k}.

Since p is sampled randomly after d_comm and s_comm are committed to, we know that, with overwhelming probability, for that relationship to hold true we must have

d_comm = comm(d(X))
s_comm = comm(X^{k - n%k} * d(X))

and thus the prover could only have constructed both commitments if there are commitments to the deg(d(X)) + k - n%k powers of X available in the srs. Equivalently, deg(d(X)) + k - n%k <= k, and so deg(d(X) <= n%k.

Putting it all together, we have a polynomial of degree 3*k + n%k = n, as desired.