background

We have a computation from [S F] -> P. The first step is to unroll it. We build a table, which we also call the trace, where each column is basically a register and each row is one step of the processor. The first row contains the input and the final row contains the product. So how can the verifier know that this table is correct, and that P is really the product of .*(S F)?

First idea- the prover can send the entire table to the verifier and the verifier can check every row. This works but its equivalent to the verifier just running the computation himself.

Next idea- the verifier can randomly check rows to see if they are correct. This fails because computation is inherently fragile- the prover could change a single row to be wrong and the final product will be wrong. But the verifier will only catch this if he happens to check that exact row.

What we do instead is we encode the trace as polynomials and turn the problem of 'is this computation correct' into a problem of 'is this polynomial zero over a certain set'. Polynomials are rigid and this can be done succinctly.

How does this work?

We write constraints, which are polynomials that we wrote by hand which encode nock computation. Each polynomial constraint takes as variables all the columns in two consecutive rows and is zero if and only if those two rows are a correct step in the nock computation. Now the prover just has to convince the verifier that the constraints are zero over the rows.

This is all based on the ridiculously useful fact that low degree polynomials don't have too many roots. An n-degree polynomial can have at most n roots.

For all of this we are working over a finite field, which means we chose a large prime number p and only use the integers 0 to p-1 with all arithmetic done modulo p. This is a field which means you can divide and so all the results for polynomials carry over.

So say we have a polynomial p(x) of degree one million, and we are working in a field of size say 2^300. How can the verifier check if this polynomial is zero?

One way is for the prover to send all the million coefficients over and the verifier can check that each one is zero.

Another is that the verifier can evaluate the polynomial at a random point in the field and check if it is zero. There are 2^20 zeroes and 2^300 possible guesses, so the chance of accidentally picking a zero is 2^-280 ie basically zero.

So you can succinctly test if a polynomial is zero by evaluating it at one random point.

This generalizes. How can you check if two polynomals

$p(x)$ and

$q(x)$ are equal?

If

$p(x)=q(x)$ then the polynomial

$p(x)-q(x)$ must be identically zero. So just evaluate each polynomial at the same random point and check if they are equal.

In this way you can succinctly verify polynomial identities by evaluating each side at the same random point in the field.

Another trick is to check if a polynomial is zero over a set and not just at one point.

If

$p(a)=0$, then

$(x-a)$ divides

$p(x)$, and so

$p(x)/(x-a)$ is a polynomial and not just a rational function and has degree one less than

$p(x)$.

Similarly, if

$p(x)$ is zero at every point

$s\in S\subseteq {\mathbb{F}}_p$, then

$(x-s)$ divides

$p(x)$ for every s in S, and so their product divides

$p(x)$.

$\frac{p(x)}{\prod _{s\in S}(x-s)}$ (1)

is a polynomial of degree

$deg(p)-|S|$

Another trick is to use an n-th root of unity. This just means an element of the field

$g$ such that

$g^n=1$ but

$g^m\ne 1$ for

$m<n$. This has a nice property that if your set S is just

$\{g^m:0<=m<=n\}$, ie all powers of g, then

$\prod _{0<=m<=n}(x-g^m)=(x^n-1)$

And so you can replace the denominator in (1) by

$x^n-1$ which is very easy to compute.

$\frac{p(x)}{(x^n-1)}$

how the prover works

We run the nock computation and write out a table and fill the cells with elements from our finite field. We have a bunch of hand-written constraints which are multivariate polynomials with exactly twice the variables as the number of columns because they evaluate on consecutive pairs of rows.

We turn each column of the table into a polynomial by interpolating a polynomial through the values of the column. For the x-values we use a root of unity that matches the height of the table. We only have roots of unity that are powers of 2 so we have to first pad the table out to a power of 2. These are called the trace polynomials. If you pass in

$g^n$ to a trace polynomial it will return the value in the cell in the n-th row of the table.

Now we plug these trace polynomials directly into the contraint polynomials. This produces univariate polynomials which, if given

$g^n$, will evaluate to zero if and only if the nth and n+1-th rows are a correct step in computing nock. Now the verifier needs to check if these new polynomials are zero over all the powers of the roots of unity, which as we saw above means dividing by

$x^n-1$ and checking that this new polynomial is low degree.

So if

$C_j(x_0,x^1,...,x^{2m})$ are the constraint polynomials where there are m rows, then the prover plugs in the trace polynomials

$t_i(x)$ and forms

$\frac{C_j(t_0(x),t_1(x),...,t_{2m}(x))}{x^n-1}$.

There are a bunch of constraints and so the prover takes a random linear combination of these to produce one final univariate polynomial.

$C(x)=\sum {\lambda }^j\frac{C_j(t_0(x),t_1(x),...,t_{2m}(x))}{x^n-1}$

This is called the Composition Polynomial. It will be low degree if and only if the table is a correct nock computation.

The next step is to break this Composition Polynomial up into multiple pieces- one piece for each degree of the constraints. Our constraints have degree 4 so we break it up into 4 pieces

$h_i(x)$ such that

$C(x)=h_0(x^4)+x{h}_1(x^4)+x^2{h}_2(x^4)+x^3{h}_3(x^4)$

Each

$h_i(x)$ will be of degree at most t where t is the length of the trace. This is also the degree of all the trace polynomials.

The prover commits to the trace polynomials and these piece polynomials and sends the commitments to the verifier.

The verifier responds by chosing a random element from the field called the DEEP Challenge Point. It wants to evaluate both sides of this identity at this random point to check that they are equal.

Th verifire has the constraints but it does not have the trace. So the prover responds by evaluating all the trace polynomials and the piece polynomials at this DEEP Challeng Point and sending these values to the verifier. Then the verifier plugs them in and checks that both sides are equal.

Now it has two things left to check- that these evaluations that the prover sent are actually correct, and that the trace and piece polynomials are all low degree. If they are low degree, then that means the Composition Polynomial is low degree, which means the constraints are zero over the rows of the trace, which means the trace is a valid nock computation, which means .*(S F) is P after all.

Check that evaluations are correct

The prover sent the evaluations of the trace and piece polynomials at the DEEP Challenge Point to the verifier, but it could have just made them up. How does the verifier check that they are correct?

Say the prover said that the trace polynomial

$t_i(x)$ evaluates to

$a$ at the deep point

$d$. So

$t_i(d)=a$. In that case,

$t_i(d)-a=0$, and so

$d$ is a root of

$t_i(x)-a$, and thus

$\frac{t_i(x)-a}{x-d}$ is a low degree polynomial.

The prover computes these quotients for every trace and piece polynomial and forms (what else) a linear combination.

$\sum {\lambda }^i\frac{t_i(x)-a_i}{x-d}+\sum {\lambda }^i\frac{h_i(x)-b_i}{x-d}$