Circle STARKs: Arithmetizing Circles

This is Part IV of a four-part series on Circle STARKs. The original appeared on the ZK Security blog.

Recap#

• In Part I, we motivated Mersenne prime fields for fast modular arithmetic and detailed why the non-smooth multiplicative group prevents STARK instantiations.
• In Part II, we described the circle curve and the domains: twin-coset and standard position cosets. We also described polynomials over the circle curve and constructed vanishing polynomials over the two domains.
• In Part III, we described the Circle FFT algorithm as a Cooley–Tukey style algorithm that lets us move between evaluation and coefficient representations of bivariate polynomials over the circle curve. We also defined the basis induced by the Circle FFT algorithm and the dimension gap between the space of bivariate polynomials over the circle curve and the space of polynomials interpolated by Circle FFT.

Introduction#

This final post stitches everything together we built in Parts I–III. Our goal is to show how those ingredients combine into a complete Circle STARK.

We begin by describing the arithmetization over the circle curve. From there we introduce Circle FRI, the low-degree test to ensure polynomials satisfy a degree bound. Finally, we walk through the Circle STARK construction.

Arithmetization#

The execution trace is simply the record of the computation: each row captures a step or a clock cycle, each column records the evolution of a register and every entry lives in the Mersenne prime field $\mathbb{F}_p$. If the computation has $N$ cycles and operates on $w$ registers then the trace table is of size $N \times w$. Arithmetization is encoding the local transition rules of this table as polynomial identities that hold over the entire domain, so that reasoning about the computation reduces to checking evaluations of polynomials.

We define our computation in terms of a trace table with $N = 2^n$ rows and $w$ columns. Each cell in this table is an element from $\mathbb{F}_p$. We can define the entire trace using $w$ column vectors:

Suppose $H$ is a standard position coset of size $N = 2^n$. We will interpolate each trace column $t_i$ over the trace domain $H$ using Circle FFT to obtain bivariate polynomials $p_i$ over the circle curve. The polynomials $p_i$ belong to the space of bivariate polynomials over the circle curve i.e.

The prover commits to the column polynomials $p_i$ by committing to their evaluations over an evaluation domain $D$ which is a factor $2^B$ larger in size than the trace domain $H$ i.e.

where $B \geq 1$. The evaluations of $p_i$ over the evaluation domain $D$ are committed using a Merkle tree.

Now we want to add constraints over the trace table. Suppose we add a total of $C$ constraints. For simplicity, we only describe constraints over the neighboring rows as follows:

Here, $p_i \circ T_G$ denotes translation by the generator $G$ on the column polynomial $p_i$, where $T_G(P) = G \cdot P$. The trace domain is a coset $H = Q\cdot G_n$, where $G_n$ is a subgroup of size $N=2^n$ and $Q$ is an offset. Each column $p_i$ is interpolated over the trace domain $H$ represented as:

Thus $p_i \circ T_G$ pulls in the “next row” of the trace. The constraints $P_j$ are polynomials defined in terms of the column polynomials $p_i$ and a predefined selector polynomial $s_j$ which determines the rows on which the constraint $P_j$ should apply.

Now rather than proving all the $C$ constraints separately, we batch them into a single one. The verifier chooses a random $\beta$ from the extension field $\mathbb{F}$ of $\mathbb{F}_p$. The prover computes the following:

In order to prove validity of the above identity over the entire trace domain $H$, the prover computes the quotient polynomial $q$ as follows:

Such a quotient $q$ must exist because if all constraints are satisfied throughout $H$, the left-hand side vanishes on $H$ and is therefore divisible by $v_H$.

Now the prover will have to prove that the columns polynomials $p_i$ are of degree $\leq N/2$ and the quotient polynomial $q$ is of degree $\leq (d-1)N/2$. To make the degree bound uniform (i.e. $\leq N/2$) across all the polynomials, the quotient polynomial $q \in L_{(d-1)N}(\mathbb{F})$ is split into polynomials $q_1, \ldots, q_{d-1} \in L_N(\mathbb{F})$ as follows:

where $\bar{H} = \bigcup_{k=1}^{d-1} H_k$ is a disjoint union of twin-cosets of size $|H_k| = N$.

Thus the prover has to prove the validity of the following equation:

and prove that the polynomials $p_i$, $q_k$ are of degree $\leq N/2$. We will now describe Circle FRI to prove the latter.

Circle FRI#

Circle FRI tests the proximity of a function $f \in \mathbb{F}^D$ over the evaluation domain $D$ of size $|D|=2^{n + B}$ to some polynomial $p(x, y)$ from the polynomial space $L_N(\mathbb{F})$. The function $f \in \mathbb{F}^D$ is represented as a vector of evaluations over the domain $D$.

Here:

• $\mathbb{F}$ is a field extension of $\mathbb{F}_p$
• $B$ is the log of blowup factor $2^B$
• $L_N(\mathbb{F})$ is the space of bivariate polynomials over the circle curve, which can be decomposed as follows (as described in Dimension Gap, Part III): $$L_N(\mathbb{F}) = L'_N(\mathbb{F}) + \langle v_n \rangle$$

Circle FRI follows a similar divide-and-conquer strategy as the Circle FFT algorithm. The prover recursively decomposes the function and folds the odd and even parts using randomness sent by the verifier. This reduction continues until the proximity test of the folded function to the polynomial space is small enough for the verifier to check directly; in this case, the prover sends the folded function directly to the verifier.

The following figure shows the sequence of domains for the circle FRI algorithm with $r$ folding rounds using a chain of $2$-to-$1$ maps.

As shown in the above diagram, we use two different maps, as in the circle FFT algorithm: the projection map $\pi_x$ and the squaring map $\pi$. The protocol starts with a standard position coset $D_m$ of size $2^m$ where $m = B+n$ and then takes projection onto the $x$-axis using map $\pi_x$ to compute the quotient $D_m/J$. Then subsequently apply the map $\pi$ for $(r-1)$ rounds to get the quotient $D_{m-r+1}/J$ with $2^{m-r}$ elements. To know more about these maps, please refer Sequence of Domains for Circle FFT, Part III. For notational convenience, we have defined the domain and map for the $j$th round as $S_j$ and $\pi_j$, respectively.

At each step of Circle FRI, the prover will decompose and fold functions over the sequence of domains as described above. But before folding, the prover decomposes $f \in L_N(\mathbb{F})$ as:

where $g$ is from the FFT space $L'_N(\mathbb{F})$, $\lambda \in \mathbb{F}$, and $v_n$ is the vanishing polynomial of the standard position coset of size $N = 2^n$. This reduces the proximity claim of $f$ to $L_N(\mathbb{F})$ to that of $g$ to the FFT space $L'_N(\mathbb{F})$, which is checked through repeated folding of $g$.

We start with the proximity claim of $g = g_0 \in \mathbb{F}^{S_0}$ to the FFT space $L^{(0)} = L'_N(\mathbb{F})$. In each round $j = 1, \ldots, r$, we reduce the previous proximity claim of $g_{j-1} \in \mathbb{F}^{S_{j-1}}$ to $L^{(j-1)}$ to a new proximity claim of $g_{j} \in \mathbb{F}^{S_{j}}$ to the FFT space $L^{(j)}$ where

We will now explain the complete protocol and the above reduction in detail. The prover has a function $f \in \mathbb{F}^D$ and the verifier is given an oracle to $f$. The protocol consists of a commit phase and a query phase.

Commit Phase#

• Decomposition: The prover decomposes $f = g + \lambda \cdot v_n$ and send $\lambda$ to the verifier.
• Folding: The prover holds the function $g = g_0 \in \mathbb{F}^{S_0}$ which it wants to prove proximity to $L^{(0)} = L'_N(\mathbb{F})$.
  • For the first round of folding i.e. $j=1$,
    • The verifier sends a random challenge $\lambda_1 \in \mathbb{F}$.
    • The prover decomposes the function $g_0$ using the map $\pi_1 = \pi_x$ as follows: $$g_0(X, Y) = g_{0,0}(\pi_1(X, Y)) + Y \cdot g_{0,1}(\pi_1(X, Y))$$ $$g_0(X, Y) = g_{0,0}(X) + Y \cdot g_{0,1}(X)$$ where $g_{0,0}, g_{0,1} \in \mathbb{F}^{S_1}$ are as follows: $$g_{0,0}(X) = \frac{g_0(X, Y) + g_0(X, -Y)}{2}, \quad g_{0,1}(X) = \frac{g_0(X, Y) - g_0(X, -Y)}{2 \cdot Y}$$ As we have seen in Dimension Gap, Part III, we can also decompose the space of polynomials interpolated by Circle FFT $L'_N(\mathbb{F})$ as: $$L'_N(\mathbb{F}) = \mathbb{F}[X]^{< N/2} + Y \cdot \mathbb{F}[X]^{< N/2}$$ Thus we have reduced the task of checking proximity of $g_0$ to $L^{(0)} = L'_N(\mathbb{F})$ to checking proximity of $g_{0,0}$ and $g_{0,1}$ to $L^{(1)} = \mathbb{F}[X]^{< N/2}$. But rather than checking two proximity claims, we fold them into a single proximity claim using the random challenge $\lambda_1$ from the verifier. $$g_1(X) = g_{0,0}(X) + \lambda_1 \cdot g_{0,1}(X) \tag{2}$$ Thus after first round, we have reduced the proximity claim of $g_0 \in \mathbb{F}^{S_0}$ to $L^{(0)} = L'_N(\mathbb{F})$ to that of $g_1 \in \mathbb{F}^{S_1}$ to $L^{(1)} = \mathbb{F}[X]^{< N/2}$.
  • For subsequent rounds i.e. $j=2, \ldots, r$ we use the same procedure. The only difference is that we use the squaring map $\pi$ in each round i.e. $\pi_j = \pi$. For the $j$th round,
    • The verifier sends a random challenge $\lambda_j \in \mathbb{F}$.
    • The prover decomposes the function $g_{j-1} \in \mathbb{F}^{S_{j-1}}$ from the previous round as: $$g_{j-1}(X) = g_{j-1,0}(\pi_j(X)) + X \cdot g_{j-1,1}(\pi_j(X))$$ $$g_{j-1}(X) = g_{j-1,0}(2X^2 - 1) + X \cdot g_{j-1,1}(2X^2 - 1)$$ where $g_{j-1,0}, g_{j-1,1} \in \mathbb{F}^{S_{j-1}}$ are as follows: $$g_{j-1,0}(2X^2 - 1) = \frac{g_{j-1}(X) + g_{j-1}(-X)}{2}, \quad g_{j-1,1}(2X^2 - 1) = \frac{g_{j-1}(X) - g_{j-1}(-X)}{2 \cdot X}$$ The prover folds the functions $g_{j-1,0}, g_{j-1,1} \in \mathbb{F}^{S_j}$ as follows: $$g_j(X) = g_{j-1,0}(X) + \lambda_j \cdot g_{j-1,1}(X) \tag{3}$$ Thus after $j$th round, we have reduced the proximity claim of $g_{j-1} \in \mathbb{F}^{S_{j-1}}$ to $L^{(j-1)} = \mathbb{F}[X]^{< N/2^{j-1}}$ to that of $g_j \in \mathbb{F}^{S_j}$ to $L^{(j)} = \mathbb{F}[X]^{< N/2^j}$.
  • For each round, the prover sends an oracle for $g_j$ to the verifier. In the final round, the prover sends $g_{r} \in \mathbb{F}^{S_{r}}$ in plain which the verifier can directly check the proximity claim of $g_{r}$ to the polynomial space $L^{(r)}$.

Query Phase#

In the query phase, the verifier checks that the prover computed the folding correctly using the oracles sent by the prover. It consists of $s \geq 1$ rounds. In each round:

• The verifier samples $(x_0, y_0) \in D$ and applies each map to the element $(x_0, y_0)$ to get an element of each domain along the projection trace, shown as follows: $$x_j = \pi_j(x_{j-1}), \qquad \text{for } j \in \{1, \ldots, r\}$$ Then the verifier queries the oracles for values of $f$ and $g_j$ on the points along the above projection trace.
• The verifier checks the first folding round i.e. equation $(2)$ at $(x_0, y_0)$ as follows. Note that here $X_1 = \pi_1(x_0) = x_0$, since $\pi_1$ is the projection map $\pi_x$. $$g_1(x_0) \stackrel{?}{=} \Bigg( \frac{g_0(x_0, y_0) + g_0(x_0, -y_0)}{2} \Bigg) + \lambda_1 \cdot \Bigg( \frac{g_0(x_0, y_0) - g_0(x_0, -y_0)}{2 \cdot y_0} \Bigg)$$
• The verifier checks equation $(3)$ for subsequent folding rounds i.e. for all $j = \{2, \ldots, r\}$ check: $$g_j(x_j) \stackrel{?}{=} \Bigg( \frac{g_{j-1}(x_{j-1}) + g_{j-1}(-x_{j-1})}{2} \Bigg) + \lambda_j \cdot \Bigg( \frac{g_{j-1}(x_{j-1}) - g_{j-1}(-x_{j-1})}{2 \cdot x_{j-1}} \Bigg)$$

If all the above checks pass for all rounds $s$ then the verifier accepts, otherwise reject.

Security Analysis#

In this section, we give some intuition on the security of the FRI protocol. There are roughly two ways a prover can cheat:

• The function $f \in \mathbb{F}^D$ is “far” from the polynomial space $L_N(\mathbb{F})$ but somehow the prover gets lucky and ends up with $g_r$ which is “close” to $L^{(r)}$. The proximity gaps paper analyzes that this happens with negligible probability. That is, if even one of the functions $f$ is “far” from the polynomial space $L_N(\mathbb{F})$, then the function $g_r$ will be “far” from $L^{(r)}$ with high probability.
• Now suppose $f \in \mathbb{F}^D$ is “far” from the polynomial space $L_N(\mathbb{F})$, then the function $g_r$ will be “far” from $L^{(r)}$, but to cheat the verifier, the prover cheats in the folding rounds and sends some valid $g_r \in L^{(r)}$. Now the verifier must ensure that the prover has performed the folding correctly in each round using the oracles sent by the prover. This is exactly what the verifier checks in the query phase. From the “Toy Problem Conjecture” (ethSTARK, Section 5.9), each query done by the verifier gives $B$ (i.e. log of blowup $2^B$) bits of security. Thus, for $s$ queries, the security is $s \cdot B$ bits.

Circle STARKs#

In this section, we will combine all the ideas we have covered so far in this series to construct the Circle STARK protocol. Given the trace table as $w$ columns of length $N = 2^n$ i.e.

The protocol proceeds as follows:

1. Trace Commitment: The prover interpolates each trace column $t_i$ as a bivariate polynomial $p_i$ over the trace domain $H$ using circle FFT. Then evaluates the polynomials $p_i$ over the evaluation domain $D$ and commits to the evaluation vector using a Merkle tree. The prover sends the Merkle commitment to evaluations of each $p_i$ to the verifier.
2. Arithmetization: The verifier sends the random $\beta$ to batch all the constraints. The prover computes $q$ and decomposes it to obtain $\lambda$ and $q_k$ polynomials. Each $q_k$ is committed over $D$ like the trace polynomials. The prover sends the Merkle commitment to evaluations of each $q_k$ and $\lambda$ to the verifier. Now the prover has to prove validity of equation $(1)$ i.e. $$\sum_{j=1}^{C} \beta^{i-1} P_j\big(s_j,p_1,\ldots,p_w,p_1 \circ T_G,\ldots,p_w \circ T_G\big) \stackrel{?}{=} \bigg(\lambda \cdot v_{\bar{H}} + \sum_{k=1}^{d-1} \frac{v_{\bar{H}}}{v_{H_k}} \cdot q_k\bigg) \cdot v_H$$
3. Opening: The above identity is checked on an out-of-domain point on the circle over the extension field. The verifier samples $\gamma \in C(\mathbb{F}) \setminus (D \cup H)$ and requests openings of $p_i$ and $q_k$ from the prover. The prover responds with claimed values $v_{i,0}, v_{i,1}$ of $p_i$ at the points $\gamma$ and $T_G(\gamma)$, respectively, for each $i = 1, \dots, w$, as well as the values $v_1, \dots, v_{d-1}$ of $q_1, \dots, q_{d-1}$ at $\gamma$. The verifier checks the identity using these claimed values. Note that other values like evaluations of the vanishing polynomials can be succinctly computed by the verifier.
4. Low-Degree Test: The prover and verifier engage in a low-degree test on the following quotients using the Circle FRI protocol. $$\frac{p_i - v_{i,0}}{v_\gamma},\; \frac{p_i - v_{i,1}}{v_{T_G(\gamma)}}, \; \frac{q_k - v_{k}}{v_\gamma}$$ where $v_\gamma$ and $v_{T_G(\gamma)}$ are the vanishing polynomials over $\gamma$ and $T_G(\gamma)$, respectively. All the above proximity tests can be batched into a single proximity test using randomness from the verifier. If the proximity test passes and if the claimed values satisfy the overall identity, the verifier accepts.

Conclusion#

This final post connected all the ideas from arithmetization, quotienting and Circle FRI low-degree test to describe the Circle STARK construction. This concludes the four part series on Circle STARKs.