Plonky2

Plonky2 is a recursive proving system combining TurboPLONK arithmetization with a FRI-based polynomial commitment scheme.

TurboPLONK Arithmetization

The PLONK arithmetization uses a global permutation argument to wire local constraints together. TurboPLONK introduces custom gates to PLONK, allowing for arbitrary local constraints to be defined.

Trace

The Plonky2 trace can be thought of as a matrix $\mathcal{M}={\mathbb{F}}_p^{n\times m}$, where each trace cell ${\mathcal{M}}_{ij}$ ($i\in [0,n),j\in [0,m)$) is an element in the prime field ${\mathbb{F}}_p$, with $p=2^{64}-2^{32}+1$.

Each row corresponds to the wires of one gate; and each column corresponds to a wire polynomial $w_j(X)$ such that

$$w_j({\omega }^i)={\mathcal{M}}_{ij},$$

where $\omega$ is a primitive $n^{th}$ root of unity in ${\mathbb{F}}_p$.

Custom gates

In Plonky2, custom gates are represented as constraints on wire polynomials $w_i(X)$. For instance, an addition gate

$${\text{gate}}_{\text{ADD}}:X_0-(X_1+X_2)=0$$

may be represented as the polynomial constraint

$$w_0(X)-(w_1(X)+w_2(X))=0.$$

Note: Here, each $X_i$ variable is mapped to the $w_i(X)$ wire polynomial; in general, however, any arbitrary mapping is possible.

Gates are toggled on and off by preprocessed "filter" polynomials $f_j(X)$. For instance, the filter $f_{\text{ADD}}$ should enforce ${\text{gate}}_{\text{ADD}}$ only on relevant rows of the trace:

$$\begin{array}{c}{f}_{\text{ADD}}({\omega }^i)=\{\begin{array}{ll}1& \text{if the ith row is an addition gate;}\\ 0& \text{otherwise.}\end{array}\end{array}$$

The filtered addition gate thus looks like $f_{\text{ADD}}\cdot {\text{gate}}_{\text{ADD}}=0.$

In practice, a filter $f_{\text{ADD}}$ can be a composite of multiple binary filters. Plonky2 automates the construction of filter expressions for its custom gates, optimizing for an arrangement that minimizes constraint degree [see Section 3.1.1 of the Plonky2 paper].

Permutation argument

[Parts of this section have been adapted from the halo2 book.]

PLONK's permutation argument sets up routes between wires: i.e., it can constrain the value of one wire to equal that of another. In the below example, $w_2[0]$ is constrained to equal $w_0[1]$. We can write this as a permutation $\sigma (\text{column, row})=({\text{column}}^{\prime },{\text{row}}^{\prime })$ such that $\sigma (2,0)=(0,1)$.

$$\begin{array}{cccc}{\mathbf{w}}_0& {\mathbf{w}}_1& {\mathbf{w}}_2& \text{gate}\\ w_0[0]& w_1[0]& w_2[0]& G0\\ w_0[1]& w_1[1]& w_2[1]& G1\end{array}$$

We will label each trace cell $w_j[i]$ using a unique field element ${\delta }^j\cdot {\omega }^i\in {\mathbb{F}}_p$. Then, we can represent $\sigma$ by a vector of $r$ polynomials $s_j(X)$ such that $s_j({\omega }^i)={\delta }^{j^{\prime }}\cdot {\omega }^{i^{\prime }}$.

Now, given our permutation represented by $s_0,\dots ,s_{r-1}$ over $r$ routed wires $w_0,\dots ,w_{r-1}$, we want to ensure that this "grand product" evaluates to 1:

$$\begin{array}{rl}& \prod _{j=0}^{r-1}\prod _{i=0}^{n-1}\left(\frac{w_j({\omega }^i)+\beta \cdot {\delta }^j\cdot {\omega }^i+\gamma }{w_j({\omega }^i)+\beta \cdot s_j({\omega }^i)+\gamma }\right)\\ \equiv & \prod _{j=0}^{r-1}\prod _{i=0}^{n-1}\frac{f_j^{\prime }({\omega }^i)}{g_j^{\prime }({\omega }^i)}=1,\end{array}$$

where $\beta ,\gamma$ are random challenges.

Checking this "grand product" reduces to checking relations between coefficients of polynomials at "neighboring monomials". To see this, define a "running product" polynomial $Z_P$ such that $Z_P({\omega }^0)=Z_P({\omega }^n)=1$, and for $0\le i<n:$

$$\begin{array}{rl}{Z}_P({\omega }^{i+1})& =\prod _{k=0}^i\prod _{j=0}^{r-1}\frac{f_j^{\prime }({\omega }^k)}{g_j^{\prime }({\omega }^k)}\\ & =Z_P({\omega }^i)\prod _{j=0}^{r-1}\frac{f_j^{\prime }({\omega }^i)}{g_j^{\prime }({\omega }^i)}.\end{array}$$

Then it is sufficient to enforce the constraints: $$\begin{array}{rl}{Z}_P(\omega X)\cdot \prod _{j=0}^{r-1}{g}_j^{\prime }(X)-Z_P(X)\cdot \prod _{j=0}^{r-1}{f}_j^{\prime }(X)=0,& \text{ (ZP is correctly constructed)}\\ {\ell }_0(X)\cdot (1-Z_P(X))=0,& \text{ (starting condition ZP(ω0)=1)}\end{array}$$

where ${\ell }_0(X)=1$ when $X={\omega }^0$, and $0$ otherwise.

Note: To handle a large number $r$ of routed wires, Plonky2 splits the permutation product constraint into cumulative products [see Section 3.3 of the Plonky2 paper].

Combining constraints

The final polynomial that goes into FRI is a linearised form of a composite of the circuit's constraints. (See the Protocol section for details.)

The prover constructs the composite polynomial $p(X)$ from the wire commitments, permutation product commitments, and vanishing argument commitments, and evaluates it at a verifier challenge point $z$ to get a claimed evaluation $p(z)=y$.

The $\text{final\_poly}(X)$ that goes into the FRI protocol is a linearized version of the composite $p(X)$:

$$\text{final\_poly}(X)=\frac{p(X)-y}{X-z}.$$

Notice that $\text{final\_poly}(X)$ is a polynomial if and only if $p(z)=y$; in other words, if $p(z)\ne y$, then $\text{final\_poly}(X)$ is not a polynomial and will fail the FRI protocol.

FRI-based polynomial commitment

FRI is an efficient protocol for proving proximity to a low-degree polynomial. It proceeds in two phases: $\text{COMMIT}$ and $\text{QUERY}$. Plonky2 further includes a proof-of-work $\text{PoW}$ phase.

The prover has a function $f^{(0)}:L^{(0)}\to \mathbb{F}$, where $\mathbb{F}$ is a finite field, and the evaluation domain $L^{(0)}\subset \mathbb{F}$ is a coset of a group contained in $\mathbb{F}$.

Note: The size of the evaluation domain is much larger than the degree $d$. More precisely, $|L^{(0)}|=\frac{d}{\rho }$, where $\rho$ is the Reed-Solomon code rate.

The prover claims that $f^{(0)}$ is an evaluation of a polynomial $p(X),\mathrm{deg}(p(X))<d$. In other words, they claim that $\forall x\in L^{(0)},f^{(0)}(x)=p(x).$

COMMIT phase

To commit to $f^{(0)}(X)$, the prover begins by expressing it as a linear combination of two functions, each purportedly corresponding to a degree $\frac{d}{2}$ polynomial:

$$f^{(0)}(X)=g^{(0)}(X^2)+X\cdot h^{(0)}(X^2).$$

Here, $g^{(0)}(X)$ and $h^{(0)}(X)$ correspond to the even and odd coefficients of $p(X)$, i.e. $f^{(0)}(X)=p(X)=p_{even}(X^2)+X\cdot p_{odd}(X^2).$ The intuition here is similar to that behind the arity-2 FFT (Fast Fourier Transform). This algorithm can be generalised to other arities.

Suppose now that $f^{(0)}(X)$ is far from the degree-$d$ polynomial. This means that a significant fraction of queries on $f^{(0)}(X)$ will not yield points on $p(X)$. The proximity gap result implies that, with high probability, any linear combination of $g^{(0)}(X)$ and $h^{(0)}(X)$ will be equally far from a degree-$\frac{d}{2}$ polynomial.

The prover now sends the verifier a commitment to $f^{(0)}$. Next, Plonky2 instantiates $\mathsf{Commit}(f^0)$ as the root of a Merkle tree whose leafs are the evaluations of $f^{(0)}$, and whose hash function is Poseidon in a sponge. Using $\mathsf{Commit}(f^0)$, the verifier derives a random challenge ${\alpha }^{(0)}$. This is then used to construct a random linear combination of $g^{(0)}(X)$ and $h^{(0)}(X)$:

$$f^{(1)}(X)=g^{(0)}(X)+{\alpha }^{(0)}\cdot h^{(0)}(X).$$

Observe that our new function is half the degree: $\mathrm{deg}(f^{(1)}(X))=\frac{d}{2}$.

Further, we can halve the size of our evaluation domain through a clever choice of $L^{(0)}$. We choose $L^{(0)}$ to be a finite field, such that $x\in L^{(0)}\leftrightarrow -x\in L^{(0)}.$ For a function on $x^2$, the symmetry $f(x^2)=f((-x{)}^2)$ means that half of the output values will be superfluous. In other words, we need only evaluate $f$ over half the domain:

$$\begin{array}{r}{f}^{(1)}(X)=g^{(0)}(X^2)+{\alpha }^{(0)}\cdot h^{(0)}(X^2),\\ f^{(1)}(-X)=g^{(0)}(X^2)-{\alpha }^{(0)}\cdot h^{(0)}(X^2),\end{array}$$

where $x\in L^{(1)},|L^{(1)}|=\frac{|L^{(0)}}{2}$.

At each round $i$ in the $\text{COMMIT}$ phase, the verifier sends the prover a new random challenge ${\alpha }^{i-1}$. Then the prover uses it to make a new function $f^{(i)}$ and merkle commitment $\mathsf{Commit}(f^i)$, halving the degree and evaluation domain size of the previous round's $f^{(i-1)}$. Finally, at $r=\log d$ rounds, we are left with the constant function (degree 0) $f^{(r)}\in \mathbb{F}$.

PoW phase

TODO

QUERY phase

The $\text{QUERY}$ phase consists of $\ell$ rounds. In each round, the verifier makes $2r=2\log d$ oracle queries to read the prover's $f^{(i)}$'s in select locations.

$$\begin{array}{l}1.\text{ Repeat ℓ times: }\\ a.\text{ Pick s(0)∈L(0) uniformly at random.}\\ b.\text{ For i=0 to r−1:}\\ i.\text{ Define s(i+1)∈L(i+1) by s(i+1)=(s(i))2.}\\ ii.\text{ Make two queries, g(i)(s(i+1)) and h(i)(s(i+1)).}\\ iii.\text{ Check that}\\ f^{(i+1)}(X)\stackrel{?}{=}{g}^{(i)}(s^{(i+1)})+{\alpha }^{(i)}\cdot h^{(i)}(s^{(i+1)}).\\ iv.\text{ Check the Merkle proof at the leaf representing s(i+1).}\\ c.\text{ If either of the checks fail, }\text{REJECT}.\\ 2.\text{ ACCEPT}.\end{array}$$

Protocol

$$\begin{array}{ll}\text{Prover}& \\ \text{commit to wire polynomials}:W\leftarrow \mathsf{Commit}(w_i),i\in [0,m)& \underrightarrow{W}\\ & \underleftarrow{\beta ,\gamma }\\ \text{compute permutation partial product and Z’s}& \\ \text{commit to permutation partial products and Z’s}:& \\ Z\leftarrow \mathsf{Commit}(\text{zs\_partial\_products})& \underrightarrow{Z}\\ & \underleftarrow{\alpha }\\ \text{compute quotient polynomial t(X)}& \\ \text{commit to }t(X):T\leftarrow \mathsf{Commit}(t)& \underrightarrow{T}\\ & \underleftarrow{\zeta }\\ \text{evaluate the wire commitments, partial product and Z’s commitments, }& \\ \text{and quotient poly commitment at opening locations }\{\zeta ,\zeta \cdot g\}& \underrightarrow{\text{opening evals}}\\ & \underleftarrow{\alpha }\\ \text{construct }\text{final\_poly}& \\ \text{compute FRI proof for }\text{final\_poly}& \\ \text{COMMIT phase: fold codewords in the commitment phase}& \\ \text{PoW phase: find proof-of-work witness}& \\ \text{QUERY phase}& \end{array}$$

FRI-based recursion

The recursive verifier circuit is a subcircuit encoding the constraints needed to verify a FRI proof. About 75% of the recursive circuit is taken up by verifying Merkle proofs, i.e. Poseidon hashes.

The diagram below shows how the FRI proof of one instance can be submitted to a later recursive verifier as part of the next instance:

Starky

Starky shares Plonky2's FRI-based polynomial commitment scheme, but replaces TurboPLONK with the Algebraic Intermediate Representation ($\mathsf{AIR}$), an arithmetization used in STARKs. $\mathsf{AIR}$ is optimized for traces with repeating structure, where the same state transition function applies on all states in the trace. Here, each row in the matrix corresponds to a single state in the execution trace; and each column corresponds to a register.

The $\mathsf{AIR}$ arithmetization is a special case of TurboPLONK arithmetization. This note explains their relationship in more detail.

Starky expresses the constraints of the computation using the following types of constraints:

• Boundary constraints: these are applicable on only the first and last rows, and are often used to load the expected inputs and outputs of the computation. As in Plonky2, these are specified using preprocessed filters: $$\begin{array}{rl}{f}_{\mathsf{first}}(X)\cdot {\mathsf{constraint}}_{\mathsf{first}}(X)& =0,\\ f_{\mathsf{last}}(X)\cdot {\mathsf{constraint}}_{\mathsf{last}}(X)& =0,\end{array}$$ where $f_{\mathsf{first}}$ only evaluates to $1$ on the first row, and $f_{\mathsf{last}}$ only on the last.

• Transition constraints: these define a valid transition from the current state to the next state of the execution trace. These are valid on all rows except the last.

• Constraints that are valid on all rows.

Starky additionally allows for permutations between pairs of columns.