Skip to main content
In this section, we describe a multi-table variant of the circle FRI low degree test. This variant supports domains of different sizes, thereby avoiding excessive padding overhead. This section does not provide a detailed analysis of how FRI works, but instead focuses on the protocol as implemented in S-two. Analyzing soundness and explaining why FRI works is out of scope. Interested readers are advised to consult “A summary on the FRI low degree test”.

​
Introduction

Circle FRI tests the proximity of a function f∈FDf \in F^D over a canonical coset DD of size ∣D∣=2n+β|D|=2^{n + \beta} to some polynomial p(x,y)p(x, y) from the polynomial space Ln′(F)L'_n(F). The function f∈FDf \in F^D is represented as a vector of evaluations over the domain DD. Here:
  • FF is a field extension of M31\mathsf{M31}
  • β\beta is the log of blowup B=2βB = 2^\beta
  • Ln′(F)L'_n(F) is the space of polynomials interpolated by circle FFT, defined as follows:
Ln′(F)=F[x]<2n−1+y⋅F[x]<2n−1L'_n(F) = F[x]^{< 2^{n-1}} + y \cdot F[x]^{< 2^{n-1}} Let Ln−1(F)=F[x]<2n−1\mathcal{L}_{n-1}(F) = F[x]^{< 2^{n-1}}, then we can represent Ln′(F)L'_n(F) as: Ln′(F)=Ln−1(F)+y⋅Ln−1(F)L'_n(F) = \mathcal{L}_{n-1}(F) + y \cdot \mathcal{L}_{n-1}(F)
Why check proximity to a polynomial? The prover sends evaluations of a function to the verifier. However, the verifier does not know if this function is a polynomial, or if it satisfies a pre-specified degree bound. FRI allows the verifier to check that the evaluations sent by the prover are indeed “close” to some polynomial of bounded degree. Here, the verifier only checks for proximity; that is, the verifier accepts even if the evaluations sent by the prover are “close enough” to those of a polynomial of bounded degree. Thus, the evaluations sent by the prover need not be exactly equal to evaluations of some polynomial of bounded degree.
In S-two, we can represent the trace over multiple tables, with each trace table defined for a domain of different size. Thus, we are interested in circle FRI for the multi-table setting. We will now see an adaptation of circle FRI for the multi-table setting using an example. Consider three functions: h0h_{0} defined over the domain H0H_0, h1h_{1} defined over the domain H1H_1, and h2h_{2} defined over the domain H2H_2: h0∈FH0,h1∈FH1,h2∈FH2h_{0} \in F^{H_0} \quad, \quad h_{1} \in F^{H_1} \quad, \quad h_{2} \in F^{H_2} The domains H0,H1H_0, H_1, and H2H_2 are canonical cosets which form a chain using the squaring map π\pi: H0→πH1→πH2H_0 \xrightarrow{\pi} H_1 \xrightarrow{\pi} H_2 Suppose for the sake of our example, for ii in {0,1,2}\{0,1,2\} the domain Hi=D3−i+βH_i = D_{3-i + \beta}, where D3−i+βD_{3-i + \beta} is a canonical coset of size 23−i+β2^{3-i + \beta}. For each ii in {0,1,2}\{0,1,2\}, we need to check that the functions hi∈FHih_{i} \in F^{H_i} are “close” to the polynomial space L3−i′(F)L'_{3-i}(F). For example, for i=0i=0, we need to check that the function h0h_{0} defined over H0=D3+βH_0 = D_{3 + \beta} is close to the polynomial space L3′(F)L'_{3}(F). Circle FRI follows a similar divide-and-conquer strategy as the Circle FFT algorithm. The prover recursively decomposes the functions 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. We reduce the functions up to folded functions evaluated over a domain HrH_r. For the sake of our example, consider r=2r=2. Then the sequence of domains for circle FRI in the multi-domain setting is as follows:
Sequence of domains for Circle FRIFigure 1: Sequence of domains for Circle FRI
As shown in the above diagram, we use two different maps, as in the circle FFT algorithm: the projection map πx\pi_x and the squaring map π\pi. Here, IiI_i is the “line” domain; for every ii in {0,1,2}\{0,1,2\}, Ii=S3−iI_i = S_{3-i}, where S3−iS_{3-i} is the “line” domain of size ∣S3−i∣=∣D3−i∣/2=22−i+β|S_{3-i}| = |D_{3-i}| / 2 = 2^{2-i+\beta}. Using circle FRI, the prover will prove proximity of functions h0h_{0} to polynomial space L3′(F)L'_3(F), h1h_{1} to space L2′(F)L'_2(F), and h2h_{2} to space L1′(F)L'_1(F) by reducing these three checks into a single check i.e. checking proximity of function g2g_2 to the polynomial space L0(F)\mathcal{L}_0(F). The verifier will have oracle access to the evaluations h0∈FH0h_{0} \in F^{H_0}, h1∈FH1h_{1} \in F^{H_1}, h2∈FH2h_{2} \in F^{H_2}. The protocol proceeds as follows.

​
Protocol

  1. Commit phase: Consists of r+1=3r+1 = 3 rounds.
    • Round 0: The prover will decompose the function h0h_0 over the domain H0H_0 into two functions h0,0  ,  h0,1h_{0,0}\;,\; h_{0,1} over the domain I0I_0 as follows
    h0(x,y)=h0,0(x)+y⋅h0,1(x)h_0(x, y) = h_{0,0}(x) + y \cdot h_{0,1}(x) The prover will find the evaluations of functions h0,0  ,  h0,1h_{0,0}\;,\; h_{0,1} over the domain I0I_0 using the evaluations of h0h_0 over domain H0H_0 as follows: h0,0(x)=h0(x,y)+h0(x,−y)2,h0,1(x)=h0(x,y)−h0(x,−y)2y.h_{0,0}(x) = \frac{h_0(x,y)+h_0(x,-y)}{2} \quad, \quad h_{0,1}(x) = \frac{h_0(x,y)-h_0(x,-y)}{2y}. Note that this decomposition and the process of finding evaluations of the decomposed functions is very similar to the circle FFT algorithm. Now the prover will fold the evaluations of h0,0h_{0,0} and h0,1h_{0,1} over the domain I0I_0 using the randomness λ0∈F\lambda_0 \in F from the verifier as follows: g0(x)=λ02⋅(h0,0(x)+λ0⋅h0,1(x))g_0(x) = {\lambda_0}^2 \cdot (h_{0,0}(x) + \lambda_0 \cdot h_{0, 1}(x)) The prover commits and gives the verifier oracle access to the evaluations g0∈FI0g_0 \in F^{I_0}.
    • Round 1: The prover will decompose the function h1h_1 over the domain H1H_1 into two functions h1,0  ,  h1,1h_{1,0}\;,\; h_{1,1} over the domain I1I_1, same as the decomposition of h0h_0 in Round 0. The prover will also decompose the function g0g_0 over domain I0I_0 into two functions g0,0g_{0,0} and g0,1g_{0,1} over the domain I1I_1 as follows:
    g0(x)=g0,0(2x2−1)+x⋅g0,1(2x2−1)g_0(x) = g_{0,0}(2x^2 - 1) + x \cdot g_{0,1}(2x^2 - 1) The prover will find the evaluations of functions g0,0g_{0,0} and g0,1g_{0,1} over the domain I1I_1 using the evaluations of g0g_0 over domain I0I_0 as follows: g0,0(2x2−1)=g0(x)+g0(−x)2,g0,1(2x2−1)=g0(x)−g0(−x)2x.g_{0,0}(2x^2 - 1) = \frac{g_0(x)+g_0(-x)}{2} \quad, \quad g_{0,1}(2x^2 - 1) = \frac{g_0(x)-g_0(-x)}{2x}. Now the prover will fold the evaluations of h1,0h_{1,0}, h1,1h_{1,1}, g0,0g_{0,0}, and g0,1g_{0,1} over the domain I1I_1 using the randomness λ1∈F\lambda_1 \in F from the verifier as follows: g1(x)=g0,0(x)+λ1⋅g0,1(x)+λ12⋅(h1,0(x)+λ1⋅h1,1(x))g_1(x) = g_{0,0}(x) + \lambda_1 \cdot g_{0, 1}(x) + \lambda_1^2 \cdot (h_{1,0}(x) + \lambda_1 \cdot h_{1,1}(x)) The prover commits and gives the verifier oracle access to the evaluations g1∈FI1g_1 \in F^{I_1}.
    • Round 2: This round is very similar to Round 1. The prover will decompose h2h_2 into h2,0h_{2,0} and h2,1h_{2,1}, then decompose the function g1g_1 into g1,0g_{1,0} and g1,1g_{1,1}. Then fold all their evaluations as follows:
    g2(x)=g1,0(x)+λ2⋅g1,1(x)+λ22⋅(h2,0(x)+λ2⋅h2,1(x))g_2(x) = g_{1,0}(x) + \lambda_2 \cdot g_{1, 1}(x) + \lambda_2^2 \cdot (h_{2,0}(x) + \lambda_2 \cdot h_{2,1}(x)) This is the final round, so the prover will send g2(x)∈FI2g_2(x) \in F^{I_2} to the verifier in plain. Let us describe the protocol for the general case. In each round i={0,…,r}i = \{0, \dots, r\}, the prover has previous evaluations gi−1∈FIi−1g_{i-1} \in F^{I_{i-1}} (for round i=0i = 0 we take g−1=0g_{-1} = 0). The verifier sends λi∈F\lambda_i \in F and the prover commits to gi∈FIig_i \in F^{I_i}, defined as follows: gi=gi−1,0+λi⋅gi−1,1+λi2⋅(hi,0+λi⋅hi,1)g_i = g_{i-1,0} + \lambda_i \cdot g_{i-1,1} + \lambda_i^2 \cdot (h_{i,0} + \lambda_i \cdot h_{i,1}) where gi−1,0,gi−1,1∈FIig_{i-1,0}, g_{i-1,1} \in F^{I_i} are the decomposition of gi−1∈FIi−1g_{i-1} \in F^{I_{i-1}} and hi,0,hi,1∈FIih_{i,0}, h_{i,1} \in F^{I_i} are the decompositions of hi∈FHih_i \in F^{H_i}. The prover gives the verifier oracle access to gig_i, and in the final round grg_r is sent in plain.
  2. 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≥1s \geq 1 rounds. In each round, the verifier samples P0=(x0,y0)∈H0P_0 = (x_0,y_0) \in H_0, and queries the oracles for their values to spot-check the folding identities along the projection trace Pi=(xi,yi)=πi(x0,y0)P_i = (x_i,y_i) = \pi^i(x_0,y_0). That is, for all i={0,1,2}i = \{0, 1, 2\} the verifier checks that: gi(xi)=gi−1(xi−1)+gi−1(−xi−1)2+λi⋅gi−1(xi−1)−gi−1(−xi−1)2⋅xi−1+λi2⋅(hi(xi,yi)+hi(xi,−yi)2+λi⋅hi(xi,yi)−hi(xi,−yi)2⋅yi)\begin{aligned} g_i(x_i) &= \frac{g_{i-1}(x_{i-1}) + g_{i-1}(-x_{i-1})}{2} + \lambda_i \cdot \frac{g_{i-1}(x_{i-1}) - g_{i-1}(-x_{i-1})}{2 \cdot x_{i-1}} \\ &\quad + \lambda_i^2 \cdot \left( \frac{h_i(x_i,y_i) + h_i(x_i,-y_i)}{2} + \lambda_i \cdot \frac{h_i(x_i,y_i) - h_i(x_i,-y_i)}{2 \cdot y_i} \right) \end{aligned} If in each of the query rounds all spot-checks hold, and if g2∈FI2g_2 \in F^{I_2} is “close” to the polynomial space L0\mathcal{L}_0, then the verifier accepts. Otherwise, it rejects.

​
Security Analysis

In this section, we analyze the security of the FRI protocol at a high level. There are roughly two ways a prover can cheat:
  • The functions hi∈FHih_{i} \in F^{H_i} are “far” from the polynomial space L3−i′(F)L'_{3-i}(F) but somehow the prover gets lucky and ends up with g2∈L0g_2 \in \mathcal{L}_0. The proximity gaps paper analyzes that this happens with negligible probability. That is, if even one of the functions hi∈FHih_{i} \in F^{H_i} is “far” from the polynomial space L3−i′(F)L'_{3-i}(F), then the function g2g_2 will be “far” from L0\mathcal{L}_0 with high probability.
  • Now suppose hi∈FHih_{i} \in F^{H_i} are “far” from the polynomial space L3−i′(F)L'_{3-i}(F), then the function g2g_2 will be “far” from L0\mathcal{L}_0, but to cheat the verifier, the prover cheats in the folding rounds and sends some valid g2∈L0g_2 \in \mathcal{L}_0. 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 β\beta (i.e. log of blowup BB) bits of security. Thus, for ss queries, the security is s⋅βs \cdot \beta bits.