From AIRs to RAPs - how PLONK-style arithmetization works

We explain in this post how to think about and leverage the type of arithmetization used in PLONK. In its most general form, we refer to such an arithmetization as a Randomized Air with Preprocessing, RAP for short. However, in practice it will usually be convenient to work with restricted cases of RAPs, that we call turbo-Plonk and ultra-Plonk programs. We will explain all these terms!

Our starting point is Algebraic Intermediate Representations - AIRs; this is the arithmetization used by STARKWARE.

AIRs

An AIR^[1]

$P$ over a field

$F$ has a length

$n$, and width

$w$.

$P$ is defined by a set of constraint polynomials

$\{f_i\}$ of a certain predefined degree

$d$ in

$2w$ variables.
An execution trace

$T$ for

$P$ consists of

$n$ vectors of length

$w$ of elements of

$F$, that we think of as "rows of width

$w$".

$T$ is valid, if substituting the

$2w$ values from any two consecutive^[2] rows to any constraint polynomial

$f_i$ evaluates to zero.

A STARK enables proving we know a valid execution trace for

$P$ consistent with some verifier defined boundary constraints: For example, we can demand that the first value of the first row of the trace should be zero. (This is the same as what's called public inputs in the SNARK literature.)

Let's look at a classical example - the Fibonacci sequence.

We use width

$w=2$; as boundary conditions we require the first row to contain two ones.
And we use the constraint polynomials

$$f_1(X_1,X_2,Y_1,Y_2)=Y_1-X_2-X_1;f_2(X_1,X_2,Y_1,Y_2)=Y_2-Y_1-X_2$$

A valid trace of length

$n=4$ would look like this:

1	1
2	3
5	8
13	21

That is, a valid trace must contain consecutive elements of the Fibonacci sequence. So, for example, adding a boundary condition on the second value of the fourth row being 21 would validate this is indeed the correct 8'th Fibonacci element.

PAIRs - AIRs with preprocessed columns

In a Preprocessed AIR, or PAIR

$T$, we have an additional parameter

$t$, and

$t$ preprocessed/predefined columns

$c_1,\dots ,c_t\in F^n$.
An execution trace now consists of the

$\{c_i\}$ in addition to the

$w$ columns supplied by the prover.
(We refer to the columns supplied by the prover as the witness part of the execution trace.)

For example when

$t=1,w=2,n=4$ an execution trace could look like:

$c_{1,1}$	$a_1$	$b_1$
$c_{1,2}$	$a_2$	$b_2$
$c_{1,3}$	$a_3$	$b_3$
$c_{1,4}$	$a_4$	$b_4$

The constraint polynomials

$f_i$ will have

$2(t+w)$ variables - i.e. the predefined values

$c_{i,j}$ participate in the constraints.

To illustrate the power of PAIRs let's see how we can use them to simulate an AIR where the constraints are different for different rows.^[3]
A natural example is an AIR where for some rows we would like to perform an addition of the row values (and, say, obtain the addition result in the first column of the row below); and for the other rows we wish to perform multiplication.

For this purpose we define the PAIR

$P$ as follows: We set

$t=1$, and define the column

$c_1$ to be one on the rows where we want to add and zero when we want to multiply.
The single constraint polynomial of

$P$ is

$$C_1\cdot (Y_1-(X_1+X_2))+(1-C_1)\cdot (Y_1-X_1\cdot X_2)$$

The variable

$C_1$ is assigned from the predefined column

$c_1$.
It is clear that an addition or multiplication relation is enforced according to the value of

$c_1$.

For example, in a program where we wish to perform two additions and then a multiplication the execution trace could look like this (note that the last row is unconstrained):

$1$	$1$	$1$
$1$	$2$	$5$
$0$	$7$	$3$
$0$	$21$	$0$

Because the predefined columns can be used in this way to select the operation, they are often referred to as "selectors".^[4]

Alternating between gates:

The above example hints and suggests the typical way people design a PAIR: We predefine several sets of constraints, thinking of each one as a "gate".
Then, when designing our final program we assign one of these gates to each row. As in the above example, selectors will be used to "compile" our program into a PAIR.
It is worth noting that in addition to using the selectors to switch between gates, many times a gate itself will use selectors to enable more flexibility. A typical example is a gate for elliptic curve addition by a predefined point - the predefined point will be encoded in the selector values.

RAPs - PAIRs with interjected verifier randomness

Our final model allows rounds of interaction, where the verifier sends random field elements, and the prover can subsequently add more columns after seeing these field elements.
The constraint polynomials will now be able to use the verifier randomness as additional variables.

We'll call such a program a RAP - Randomized AIR with Preprocessing.

Let's illustrate RAPs with the following example. Suppose we had a width 2 AIR and wanted to check that the columns provided by the prover are a permutation of each other.

Suppose the values of these columns are

$a_1,\dots ,a_n,b_1,\dots ,b_n$.
From the Schwartz-Zippel Lemma we know that to check they are a permutation of each other it suffices to check that for a uniformly chosen

$\gamma \in F$ we have with high probability

$$\prod _{i\in [n]}(a_i+\gamma )=\prod _{i\in [n]}(b_i+\gamma )$$
With high probability over

$\gamma$, the factors of the RHS are all non-zero and in that case this is equivalent to

$$\prod _{i\in [n]}(a_i+\gamma )/(b_i+\gamma )=1$$

A RAP of length

$n+1$ and total width three can easily check this:

1. The prover first sends the columns
   $(a_1,\dots ,a_n,0),(b_1,\dots ,b_n,0)$
2. The verifier sends random
   $\gamma \in F$.
3. The prover send a third column
   $(1,z_1,\dots ,z_n)$ such that for each
   $i\in [n]$
   
   $$z_i=\prod _{1\le j\le i}(a_j+\gamma )/(b_j+\gamma ).$$

If

$z$ is defined in this way, our permutation check amounts to checking

$z_n=1$. We can add this as a boundary constraint.

Additonally, the program must check

$z$ was indeed defined in this way.
For this purpose

1. We add a boundary constraint that the third column starts with one.
2. We also add the constraint
   
   $$Y_3\cdot (X_2+\gamma )-X_3(X_1+\gamma )=0$$

Note that applying this on row

$i$ checks that

$$z_{i+1}\cdot (b_i+\gamma )=z_i\cdot (a_i+\gamma )$$
or assuming

$b_i+\gamma \ne 0$:

$$z_{i+1}=z_i(a_i+\gamma )/(b_i+\gamma ),$$
which inductively enforces the

$\{z_i\}$ are defined correctly.

For illustration, here's what a valid execution trace of this program what look like, when

$b$ is just a shift of

$a$:

$a_1$	$a_2$	$1$
$a_2$	$a_3$	$\frac{(a_1+\gamma )}{(a_2+\gamma )}$
$a_3$	$a_1$	$\frac{(a_1+\gamma )(a_2+\gamma )}{(a_2+\gamma )(a_3+\gamma )}$
$0$	$0$	$\frac{(a_1+\gamma )(a_2+\gamma )(a_3+\gamma )}{(a_2+\gamma )(a_3+\gamma )(a_1+\gamma )}=1$

What is perhaps philosophically interesting here, is that randomness enables a local constraint (between adjacent rows) to verify a global property (the columns being a permutation of each other).

turbo-PLONK and ultra-PLONK programs - convenient special cases of RAPs

RAPs are more powerful than PAIRs; however, for program design it is usually convenient to just think of a PAIR, while allowing oneself to use as a black box some special functionalites of a RAP. Later, the program will be compiled to the final RAP.

One such special functionality of a RAP that is very useful is enforcing copy constraints.

This means enforcing that certain elements of the trace are equal. For example "The second element of the first column

$a_2$ must equal the 40'th element of the second column

$b_{40}$". This gives the program a certain long-term memory ability.

A turbo-plonk program is a PAIR with the extra ability to define copy constraints between any two elements of the execution trace.

The practical way to "program in turbo-Plonk":

Copy constraints enable a designer to abstract away explicitly thinking about the execution trace and PAIR, and rather design a program like this:

• We have a set of witness variables, whose value can only be set once in the program.
• We choose at each step what gate to apply on which variables.

The above might seem trivial and not saying much. However, the reason copy constraints are essential for this simplified design approach, is that when a witness variable participates in two gates, a copy constraint will ensure the same value is indeed used in both gates, even though they might end up appearing in totally different rows in the actual RAP.

ultra-Plonk programs

An ultra-Plonk program^[5] is a turbo-Plonk program with an extra, very powerful, type of gate called a lookup gate.
What this means is that as part of designing the program, we define a set of tables

$T_1,\dots ,T_k$. The elements of these tables are tuples of field elements of a certain length

$t$ (This will be a parameter of the program.).
Now, when designing the program; we are allowed to use lookup gates that have the form: "Check that the tuple of these

$t$ witness variables are in the table

$T_4$ (for example)".

At this point, the leap from RAPs to programs with such functionalities might seem a bit magical. See this post for details on how copy constraints and lookup tables can indeed be implemented via the multiset check we showed in the previous section.

When to use lookup gates

Enabling lookup gates has a significant cost in the final SNARK; as a rule of thumb it pays off once the number of lookups is as large as the table.

Take home message:

For a program designer, it will usually be convenient to work with turbo and ultra-plonk programs, thinking what gates to apply on which witness variables. This is already pretty low-level and both complicated and versatile enough! However, it is good sometimes to remember there is a RAP under the hood, that when needed, might be used to get more specific/efficient functionality taking advantage of the verifier randomness.

How does all this relate to R1CS?

If you are familiar with SNARK development and literature you've probably seen the R1CS constraint format, where all constraints have the form

$$\left(\sum _{i\in [n]}{a}_i{x}_i\right)\cdot \left(\sum _{i\in [n]}{b}_i{x}_i\right)=\sum _{i\in [n]}{c}_i{x}_i$$

R1CS nicely captures the constraint format of a sequence of works starting from [GGPR] up to the optimized version of Groth. This line of work relies on checking verifier equations on a secret element in the exponent. As we currently have at our disposal cryptographic

$k$-linear maps only for

$k=2$ (via elliptic curve pairings), R1CS is truly the most general form of constraints these protocols can work with.

However the polynomial IOP approach to constructing SNARKs, that perhaps explicitly started with Sonic, enables a more flexible constraint format. In particular, it is possible to use constraints of degree larger than two.

When using the GGPR approach R1CS has a nice theoretical advatange - no need for the random oracle model; and a nice practical advantage - the number of prover group exponentiations doesn't depend on the number or fan-in of the addition gates. However, obtaining these advantages requires a per circuit trusted setup.

Assuming we are using universal setup systems like Sonic, Plonk and Marlin, it might be harder to argue we should restrict ourselves to R1CS.

By Ariel Gabizon. Thanks to Suyash Bagad, Eli Ben-Sasson and Daira Hopwood for comments and corrections.

---

1. See Definition 1 here for the fully general description of AIRs by STARKWARE. ↩︎

2. One could ask why have constraints just between elements of two consecutive rows? Indeed, the general definition of AIRs is parameterized by a set of "masks"

   $(i_1,j_1),\dots ,(i_s,j_s)$ and a constraint is imposed on the set of elements in the execution trace that are at these offsets from the beginning of some row. We stick with the two consecutive row version both for simplicty of presentation, and since there is an effciency price in the final SNARK for many offsets, usually mainly in proof length. ↩︎

3. In fact, STARKWARE's general definition of AIRs does have partial ability to have different constraints for different rows. The reason it is partial, is the verifier has to pay a price in the arithmetic complexity of the vanishing polynomial of that subset of rows. (Again, see here for exact details.) ↩︎

4. See Section 6 of the Plonk paper and the turbo-Plonk paper for more examples of using selectors. ↩︎

5. Electric Coin Company define a very similar notion of ultra-Plonk Arithmetization as part of the Halo 2 project. One main difference is both their definition and implementation allow constraints between rows in arbitrary offsets. ↩︎