Protocol Overview

In this section, we start diving deeper before showing the formal protocol. If you haven't done so, we recommend reading the "Recap" section first.

At a high level, the protocol works as follows. The starting point is a matrix $T$ that encodes the trace of a valid execution of the program. This matrix needs to be in a particular format so that its correctness is equivalent to checking a finite number of polynomial equations on its rows. Transforming the execution to this matrix is what's called the arithmetization process.

Then a single polynomial $F$ is constructed that encodes the set of all the polynomial constraints. The satisfiability of all these constraints is equivalent to $F$ being divisible by some public polynomial $G$ . So the prover constructs $H$ as the quotient $F / G$ called the composition polynomial.

Then the verifier chooses a random point $z$ and challenges the prover to reveal the values $F (z)$ and $H (z)$ . Then the verifier checks that $H (z) = F (z) / G (z)$ , which convinces him that the same relation holds at a level of polynomials and, in consequence, convinces the verifier that the private trace $T$ of the prover is valid.

In summary, at a very high level, the STARK protocol can be organized into three major parts:

Arithmetization and commitment of execution trace.
Construction and commitment of composition polynomial $H$ .
Opening of polynomials at random $z$ .

Arithmetization

As the Recap mentions, the trace is a table containing the system's state at every step. In this section, we will denote the trace as $T$ . A trace can have several columns to store different aspects or features of a particular state at a specific moment. We will refer to the $j$ -th column as $T_{j}$ . You can think of a trace as a matrix $T$ where the entry $T_{ij}$ is the $j$ -th element of the $i$ -th state.

Most proving systems' primary tool is polynomials over a finite field $F$ . Each column $T_{j}$ of the trace $T$ will be interpreted as evaluations of such a polynomial $t_{j}$ . Consequently, any information about the states must be encoded somehow as an element in $F$ .

To ease notation, we will assume here and in the protocol that the constraints encoding transition rules depend only on a state and the previous one. Everything can be easily generalized to transitions that depend on many preceding states. Then, constraints can be expressed as multivariate polynomials in $2 m$ variables $P_{k}^{T} (X_{1}, \dots, X_{m}, Y_{1}, \dots, Y_{m})$ A transition from state $i$ to state $i + 1$ will be valid if and only if when we plug row $i$ of $T$ in the first $m$ variables and row $i + 1$ in the second $m$ variables of $P_{k}^{T}$ , we get $0$ for all $k$ . In mathematical notation, this is $P_{k}^{T} (T_{i, 0}, \dots, T_{i, m}, T_{i + 1, 0}, \dots, T_{i + 1, m}) = 0 for all k$

These are called transition constraints and check the trace's local properties, where local means relative to specific rows. There is another type of constraint, called boundary constraint, and denoted $P_{j}^{B}$ . These enforce parts of the trace to take particular values. It is helpful, for example, to verify the initial states.

So far, these constraints can only express the local properties of the trace. There are situations where the global properties of the trace need to be checked for consistency. For example, a column may need to take all values in a range but not in any predefined way. Several methods exist to express these global properties as local by adding redundant columns. Usually, they need to involve randomness from the verifier to make sense, and they turn into an interactive protocol called Randomized AIR with Preprocessing.

Polynomial commitment scheme

To make interactions possible, a crucial cryptographic primitive is the Polynomial Commitment Scheme. This prevents the prover from changing the polynomials to adjust them to what the verifier expects.

Such a scheme consists of the commit and the open protocols. STARK uses a univariate polynomial commitment scheme that internally combines a vector commitment scheme and a protocol called FRI. Let's begin with these two components and see how they build up the polynomial commitment scheme.

Vector commitments

Given a vector $Y = (y_{0}, \dots, y_{M})$ , commiting to $Y$ means the following. The prover builds a Merkle tree out of it and sends its root to the verifier. The verifier can then ask the prover to reveal, or open, the value of the vector $Y$ at some index $i$ . The prover won't have any choice except to send the correct value. The verifier will expect the corresponding value $y_{i}$ and the authentication path to the tree's root to check its authenticity. The authentication path also encodes the vector's position $i$ and its length $M$ .

The root of the Merkle tree is said to be the commitment of $Y$ , and we denote it here by $[Y]$ .

FRI

In STARKs, all commited vectors are of the form $Y = (p (d_{1}), \dots, p (d_{M}))$ for some polynomial $p$ and some fixed domain $D = (d_{1}, \dots, d_{M})$ . The domain is always known to the prover and the verifier. It can be proved, as long as $M$ is less than the total number of field elements, that every vector $(y_{0}, \dots, y_{M})$ is equal to $(p (d_{1}), \dots, p (d_{M}))$ for a unique polynomial $p$ of degree at most $M - 1$ . This is called the Lagrange interpolation theorem. It means, there is a unique polynomial of degree at most $M - 1$ such that $p (d_{i}) = y_{i}$ for all $i$ . And $M - 1$ is an upper bound to the degree of $p$ . It could be less. For example, the vector of all ones $Y = (1, 1, \dots, 1)$ is the evaluation of the constant polynomial $p = 1$ , which has degree $0$ .

Suppose the vector $Y = (y_{1}, \dots, y_{M})$ is the vector of evaluations of a polynomial $p$ of degree strictly less than $M - 1$ . Suppose one party holds the vector $Y$ and another party holds only the commitment $[Y]$ of it. The FRI protocol is an efficient interactive protocol with which the former can convince the latter that the commitment they hold corresponds to the vector of evaluations of a polynomial $p$ of degree strictly less than $M$ .

More precisely, the protocol depends on the following parameters

Powers of two $N = 2^{n}$ and $M = 2^{m}$ with $n < m$ .
A vector $D = (d_{1}, \dots, d_{M})$ , with $d_{i} = h ω^{i}$ , with $h$ a nonzero value in $F$ and $ω$ a primitive $M$ -root of unity

A prover holds a vector $Y = (y_{1}, \dots, y_{M})$ , and the verifier holds the commitment $[Y]$ of it. The result of the FRI protocol will be Accept if the unique polynomial $p$ of degree less than $M - 1$ such that $Y = (p (d_{1}), \dots, p (d_{M}))$ has degree less than $N - 1$ . Even more precisely, the protocol proves that $Y$ is very close to a vector $(p (d_{1}), \dots, p (d_{M}))$ with $p$ of degree less than $N - 1$ , but it may differ in negligible proportion of the coordinates.

The number $b = M / N = 2^{m - n}$ is called the blowup factor and the security of the protocol depends in part on this parameter. The specific shape of the domain set $D$ has some symmetric properties important for the inner workings of FRI, such as $- d_{i} \in D$ for all $i$ .

Variant useful for STARKs

FRI is usually described as above. In STARK, FRI is used as a building block for the polynomial commitment scheme of the next section. For that, a small variant of FRI is needed.

Suppose the prover holds a vector $Y = (y_{1}, \dots, y_{M})$ and the verifier holds its commitment $[Y]$ as before. Suppose further that both parties know a function $F$ that takes two field elements and outputs another field element. For example $F$ could be the function $F (a, b) = a + b^{- 1}$ . More precisely, the kind of functions we need are $F : F \times D \to F$ .

The protocol can be used to prove that the transformed vector $(F (y_{1}, d_{1}), \dots, F (y_{M}, d_{M}))$ is the vector of evaluations of a polynomial $q$ of degree at most $N - 1$ . Note that in this variant, the verifier holds originally the commitment of the vector $Y$ and not the commitment of the transformed vector. In the example, the verifier holds the commitment $[Y]$ and FRI will return Accept if $(y_{1} + d_{1}^{- 1}, \dots, y_{M} + d_{M}^{- 1})$ is the vector of evaluations of a polynomial of degree at most $N - 1$ .

Polynomial commitments

STARK uses a univariate polynomial commitment scheme. The following is what is expected from the commit and open protocols:

Commit: given a polynomial $p$ , the prover produces a sort of hash of it. We denote it here by $[p]$ , called the commitment of $p$ . This hash is unique to $p$ . The prover usually sends $[p]$ to the verifier.
Open: this is an interactive protocol between the prover and the verifier. The prover holds the polynomial $p$ . The verifier only has the commitment $[p]$ . The verifier sends a value $z$ to the prover at which he wants to know the value $y = p (z)$ . The prover sends a value $y$ to the verifier, and then they engage in the Open protocol. As a result, the verifier gets convinced that the polynomial corresponding to the hash $[p]$ evaluates to $y$ at $z$ .

Let's see how both of these protocols work in detail. The same configuration parameters of FRI are needed:

Powers of two $N = 2^{n}$ and $M = 2^{m}$ with $n < m$ .
A vector $D = (d_{1}, \dots, d_{M})$ , with $d_{i} = h ω^{i}$ , with $h$ a nonzero value in $F$ and $ω$ a primitive $M$ -root of unity

The commitment scheme will only work for polynomials of degree at most $N$ (polynomials of degree $N$ are allowed). This means: anyone can commit to any polynomial, but the Open protocol will pass only for polynomials satisfying that degree bound.

Commit

Given a polynomial $p$ , the commitment $[p]$ is just the commitment of the vector $(p (d_{1}), \dots, p (d_{M}))$ . That is, $[p]$ is the root of the Merkle tree of the vector of evaluations of $p$ at $D$ .

Open

It is an interactive protocol. So assume there is a prover and a verifier. We describe the process considering an honest prover. In the next section, we analyze what happens for malicious provers.

The prover holds the polynomial $p$ , and the verifier only the commitment $[p]$ of it. There is also an element $z$ chosen by the verifier. The prover evaluates $p (z)$ and sends the result back. As we mentioned, the goal is to generate proof of the validity of the evaluation. Let us denote $y$ the value received by the verifier.

Now they engage in the variant of the FRI protocol for the function $F (a, b) = (a - y) / (b - z)$ . The verifier accepts the value $y$ if and only if the result of FRI is Accept.

Let's see why this makes sense.

Completeness

If the prover is honest, $p$ is of degree at most $N$ and $y$ equals $p (z)$ . That means that $p - y = (X - z) q$ for some polynomial $q$ . Since $p$ is of degree at most $N$ , then $q$ is of degree at most $N - 1$ . The vector $(q (d_{1}), \dots, q (d_{M}))$ is then a vector of evaluations of a polynomial of degree at most $N - 1$ . And it is equal to $(F (p (d_{1}), d_{1}), \dots, F (p (d_{M}), d_{M}))$ . So the FRI protocol will succeed.

Soundness

Let's sketch an idea of the soundness. Note that the value $z$ is chosen by the verifier after receiving the commitment $[p]$ of $p$ . So the prover does not know in advance, at the moment of sending $[p]$ , what $z$ will be.

Suppose the prover is trying to cheat and sends the commitment $[Y]$ of a vector $Y = (y_{1}, \dots, y_{M})$ that's not the vector of evaluations of a polynomial of degree at most $N$ . Then the coordinates of the transformed vector are $(y_{i} - y) / (d_{i} - z)$ . Since $z$ was chosen by the verifier, dividing by $d_{i} - z$ shuffles all the elements in a very unpredictable way for the prover. So it is extremely unlikely that the cheating prover can craft an invalid vector $Y$ such that the transformed vector turns out to be of degree at most $N - 1$ . The expected degree of the polynomial associated with a random vector is $M - 1$ .

Batch

During proof generation, polynomials are committed and opened several times. Computing these for each polynomial independently is costly. In this section, we'll see how batching polynomials can reduce the amount of computation. Let $P = {p_{1}, \dots, p_{L}}$ be a set of polynomials. We will commit and open $P$ as a whole. We note this batch commitment as $[P]$ .

We need the same configuration parameters as before: $N = 2^{n}$ , $M = 2^{m}$ with $N < M$ , a vector $D = (d_{1}, \dots, d_{M})$ .

As described earlier, to commit to a single polynomial $p$ , a Merkle tree is built over the vector $(p (d_{1}), \dots, p (d_{m}))$ . When committing to a batch of polynomials $P = {p_{1}, \dots, p_{n}}$ , the leaves of the Merkle tree are instead the concatenation of the polynomial evaluations. That is, in the batch setting, the Merkle tree is built for the vector $(p_{1} (d_{1}) ∣∣ \dots ∣∣ p_{L} (d_{1}), \dots, p_{L} (d_{m}) ∣∣ \dots ∣∣ p_{n} (d_{m})) .$ The commitment $[P]$ is the root of this Merkle tree. This reduces the proof size: we only need one Merkle tree for $L$ polynomials. The verifier can then only ask for values in batches. When the verifier chooses an index $i$ , the prover sends $p_{1} (d_{i}), \dots, p_{L} (d_{i})$ along with one authentication path. The verifier on his side computes the concatenation $p_{1} (d_{i}) ∣∣ \dots ∣∣ p_{L} (d_{i})$ and validates it with the authentication path and $[P]$ . This also reduces the computational time. By traversing the Merkle tree one time, it can reveal several components simultaneously.

The batch open protocol proceeds similarly to the case of a single polynomial. The verifier sends evaluations points $z_{1}, \dots, z_{L}$ to the prover at which they wish to know the value of $p_{1} (z_{1}), \dots, p_{k} (z_{L})$ . The prover will try to convince the verifier that the committed polynomials $P$ , evaluate to some values $y_{i} = p_{i} (z_{i})$ . There is a generalization of the variant of FRI where the function $F$ takes more parameters, and in this case is $F (a_{1}, \dots, a_{L}, b) = i = 1 \sum L γ_{i} (a_{i} - y_{i}) / (b - z_{i}) .$ Where $γ_{i}$ are challenges provided by the verifier. Then FRI return Accept if and only if the vector $(F (p_{1} (d_{1}), \dots, p_{L} (d_{1}), d_{1}), \dots, F (p_{1} (d_{M}), \dots, p_{L} (d_{M}), d_{M}))$ is close to the vector of evaluations of a polynomial $q$ of degree at most $N - 1$ . If this is the case, the verifier accepts the openings. In the context of STARKs, the polynomial $q$ is called the DEEP composition polynomial.

This is equivalent to running the open protocol $L$ times, one for each term $p_{i}$ and $y_{i}$ . Note that this optimization makes a huge difference, as we only need to run the FRI protocol once instead of running it once for each polynomial.

References

High-level description of the protocol

The protocol is split into rounds. Each round more or less represents an interaction with the verifier. Each round will generally start by getting a challenge from the verifier.

The prover will need to interpolate polynomials, and he will always do it over the set $D_{S} = {g^{i}}_{i = 0}^{2^{n} - 1} \subseteq F$ , where $g$ is a $2^{n}$ root of unity in $F$ . Also, the vector commitments will be performed over the set $D_{L D E} = (h, hω, h ω^{2}, \dots, h ω^{2^{n + l}})$ where $ω$ is a $2^{n + l}$ root of unity and $h$ is some field element. This is the set we denoted $D$ in the commitment scheme section.

Round 1: Arithmetization and commitment of the execution trace

In round 1, the prover commits to the columns of the trace $T$ . He does so by interpolating each column $j$ and obtaining univariate polynomials $t_{j}$ . Then the prover commits to $t_{j}$ over $D_{L D E}$ . In this way, we have $T_{i, j} = t_{j} (g^{i})$ . From now on, the prover won't be able to change the trace values $T$ . The verifier will leverage this and send challenges to the prover. The prover cannot know in advance what these challenges will be. Thus he cannot handcraft a trace to deceive the verifier.

As mentioned before, if some constraints cannot be expressed locally, more columns can be added to make a constraint-friendly trace. This is done by committing to the first set of columns, then sampling challenges from the verifier and repeating round 1. The sampling of challenges serves to add new constraints. These constraints will ensure the new columns have some common structure with the original trace. In the protocol, extended columns are referred to as the RAP2 (Randomized AIR with Preprocessing). The matrix of the extended columns is denoted $M_{RAP2}$ .

Round 2: Construction of composition polynomial $H$

round 2 aims to build the composition polynomial $H$ . This function will have the property that it is a polynomial if and only if the trace that the prover committed to at round 1 is valid and satisfies the agreed polynomial constraints. That is, $H$ will be a polynomial if and only if $T$ is a trace that satisfies all the transition and boundary constraints.

Note that we can compose the polynomials $t_{j}$ , the ones that interpolate the columns of the trace $T$ , with the multivariate constraint polynomials as follows. $Q_{k}^{T} (x) = P_{k}^{T} (t_{1} (x), \dots, t_{m} (x), t_{1} (gx), \dots, t_{m} (ω x))$ These result in univariate polynomials. The same can be done for the boundary constraints. Since $T_{i, j} = t_{j} (g^{i})$ , these univariate polynomials vanish at every element of $D$ if and only if the trace $T$ is valid.

As we already mentioned, this is assuming that transitions only depend on the current and previous state. But it can be generalized to include frames with three or more rows or more context for each constraint. For example, in the Fibonacci case, the most natural way is to encode it as one transition constraint that depends on a row and the two preceding it, as we already did in the Recap section. The STARK protocol checks whether the function $\frac{Q _{k}^{T}}{X ^{2^{n}} - 1}$ is a polynomial instead of checking that the polynomial is zero over the domain $D = {g_{i}}_{i = 0}^{2^{n} - 1}$ . The two statements are equivalent.

The verifier could check that all $\frac{Q _{k}^{T}}{X ^{2^{n}} - 1}$ are polynomials one by one, and the same for the polynomials coming from the boundary constraints. However, this is inefficient; the same can be obtained with a single polynomial. To do this, the prover samples challenges and obtains a random linear combination of these polynomials. The result of this is denoted by $H$ and is called the composition polynomial. It integrates all the constraints by adding them up. So after computing $H$ , the prover commits to it and sends the commitment to the verifier. The rest of the protocol aims to prove that $H$ was constructed correctly and is a polynomial, which can only be true if the prover has a valid extension of the original trace.

Round 3: Evaluation of polynomials at $z$

The verifier must check that $H$ was constructed according to the protocol rules. That is, $H$ has to be a linear combination of all the functions $\frac{Q _{k}^{T}}{X ^{2^{n}} - 1}$ and similar terms for the boundary constraints. To do so, in round 3 the verifier chooses a random point $z \in F$ and the prover computes $H (z)$ , $t_{j} (z)$ and $t_{j} (g z)$ for all $j$ . With all these, the verifier can check that $H$ and the expected linear combination coincide, at least when evaluated at $z$ . Since $z$ was chosen randomly, this proves with overwhelming probability that $H$ was properly constructed.

Round 4: Run batch open protocol

In this round, the prover and verifier engage in the batch open protocol of the polynomial commitment scheme described above to validate all the evaluations at $z$ from the previous round.

docs