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.


The Plonky2 trace can be thought of as a matrix , where each trace cell () is an element in the prime field , with .

Each row corresponds to the wires of one gate; and each column corresponds to a wire polynomial such that

where is a primitive root of unity in .

Custom gates

In Plonky2, custom gates are represented as constraints on wire polynomials . For instance, an addition gate

may be represented as the polynomial constraint

Note: Here, each variable is mapped to the wire polynomial; in general, however, any arbitrary mapping is possible.

Gates are toggled on and off by preprocessed "filter" polynomials . For instance, the filter should enforce only on relevant rows of the trace:

The filtered addition gate thus looks like

In practice, a filter 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, is constrained to equal . We can write this as a permutation such that .


We will label each trace cell using a unique field element . Then, we can represent by a vector of polynomials such that .

Now, given our permutation represented by over routed wires , we want to ensure that this "grand product" evaluates to 1:

where 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 such that , and for

Then it is sufficient to enforce the constraints:

where when , and otherwise.

Note: To handle a large number 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 from the wire commitments, permutation product commitments, and vanishing argument commitments, and evaluates it at a verifier challenge point to get a claimed evaluation .

The that goes into the FRI protocol is a linearized version of the composite :

Notice that is a polynomial if and only if ; in other words, if , then 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: and . Plonky2 further includes a proof-of-work phase.

The prover has a function , where is a finite field, and the evaluation domain is a coset of a group contained in .

Note: The size of the evaluation domain is much larger than the degree . More precisely, , where is the Reed-Solomon code rate.

The prover claims that is an evaluation of a polynomial . In other words, they claim that

COMMIT phase

To commit to , the prover begins by expressing it as a linear combination of two functions, each purportedly corresponding to a degree polynomial:

Here, and correspond to the even and odd coefficients of , i.e. 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 is far from the degree- polynomial. This means that a significant fraction of queries on will not yield points on . The proximity gap result implies that, with high probability, any linear combination of and will be equally far from a degree- polynomial.

The prover now sends the verifier a commitment to . Next, Plonky2 instantiates as the root of a Merkle tree whose leafs are the evaluations of , and whose hash function is Poseidon in a sponge. Using , the verifier derives a random challenge . This is then used to construct a random linear combination of and :

Observe that our new function is half the degree: .

Further, we can halve the size of our evaluation domain through a clever choice of . We choose to be a finite field, such that For a function on , the symmetry means that half of the output values will be superfluous. In other words, we need only evaluate over half the domain:

where .

At each round in the phase, the verifier sends the prover a new random challenge . Then the prover uses it to make a new function and merkle commitment , halving the degree and evaluation domain size of the previous round's . Finally, at rounds, we are left with the constant function (degree 0) .

PoW phase


QUERY phase

The phase consists of rounds. In each round, the verifier makes oracle queries to read the prover's 's in select locations.


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:

RecursionWitnessCircuitTurboPLONK arithmetizationapplication constraintsFRI verifier constraintsWitness->CircuitwitnessFinalfinal polynomialCircuit->Finalwire commitments permutation commitments challenges evaluations PIPI->Circuitpublic inputsFRIFRI polynomial commitmentCOMMIT phasePoW phaseQUERY phaseFinal->FRIFRIProofFRI proofFRI:s->FRIProof:wFRIProof:ne->Circuit:seFRI proof submitted in the next instance


Starky shares Plonky2's FRI-based polynomial commitment scheme, but replaces TurboPLONK with the Algebraic Intermediate Representation (), an arithmetization used in STARKs. 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 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: where only evaluates to on the first row, and 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.