CircleSTARK

Motivation

There is a trade-off between selecting finite fields that allow for:

  1. Efficient Arithmetic Implementations: Smaller prime fields, particularly those of special forms like Mersenne primes, enable faster arithmetic operations on standard hardware architectures.

  2. Efficient FFT Support: Fields need to have smooth multiplicative groups with large two-adic subgroups to support efficient FFTs, which are crucial for STARKs' encoding processes.

One of the most efficient fields for arithmetic seem to be Mersenne fields, defined by primes of the form p=2e1p = 2^e − 1. In particular, the prime p=2311p = 2^{31} − 1 enables very efficient arithmetic on 32-bit architectures. Since 232=2modp2^{32} = 2 \mod{p}, a widened product encoded as 232xhi+xlo2^{32} \cdot x_{hi} + x_{lo} is trivially reduced to a much smaller quantity, 2xhi+xlo2 \cdot x_{hi} + x_{lo}. However, as p1=23271131151331p − 1 = 2 \cdot 3^2 \cdot 7 \cdot 11 \cdot 31 \cdot 151 \cdot 331, the multiplicative group lacks two-adic subgroups, which are useful for efficient Cooley-Tukey Fast Fourier Transforms (FFTs).

Circle Group

For p=3mod4p=3\mod{4} , a complex extension field Fp/(X2+1)\mathbb{F}_p/(X^2+1) can be defined as:

C(Fp)={x+iy:x,yFp}\mathbb{C}(\mathbb{F}_p)=\{x + i\cdot y:x,y\in \mathbb{F}_p\}

For p=1mod4p = 1 \mod{4}, X2+1=0X^2 + 1=0 has a solution since by Legendre Symbol: 1p=(1)p12=1\frac{-1}{p}=(-1)^{\frac{p-1}{2}}=1. This means that 1-1 is a quadratic residue and X2+1X^2+1 can be written as (Xa)(X+a)(X-a)(X+a) making Fp/(X2+1)\mathbb{F}_p/(X^2+1) not a field.

The unit circle over Fp\mathbb{F}_p is the algebraic set C(Fp)={(x,y)Fp2:x2+y2=1}C(\mathbb{F}_p)=\{(x,y)\in \mathbb{F}_p^2 : x^2 + y^2 = 1\}, or in complex representation:

C(Fp)={zC(Fp)×:zzˉ=1}C(\mathbb{F}_p)=\{z\in \mathbb{C}(\mathbb{F}_p)^\times:z\cdot\bar{z}=1\}

where zˉ\bar{z} denotes the conjugate xiyx-iy of z=x+iyz=x+iy.

Lemma 1 (Unit circle group). Let Fp\mathbb{F}_p be a prime field with p=3mod4p = 3\mod{4}. Then the unit circle group C(Fp)C(\mathbb{F}_p) equals the group of (p+1)(p + 1)-th roots of unity in C(Fp)×\mathbb{C}(\mathbb{F}_p)^\times, and has order p+1p + 1.

Proof: Notice that zp=(x+iy)p=xp+(iy)p=x+(ip)y=xiy=zˉz^p=(x+iy)^p=x^p+(iy)^p=x + (i^p)y=x-iy=\bar{z} so x2+y2=zzˉ=zp+1x^2+ y^2=z\cdot\bar{z}=z^{p+1}. Therefore, C(Fp)={zC(Fp)×:zp+1=1}C(\mathbb{F}_p)=\{z\in C(\mathbb{F}_p)^\times:z^{p+1}=1\} which means C(Fp)C(\mathbb{F}_p) is set of all (p+1)(p+1)-th roots of unity. Since C(Fp)×=p21|\mathbb{C}(\mathbb{F}_p)^\times|=p^2-1 is divisible by p+1p+1, the unit circle group must be the unique subgroup of order p+1p + 1.

Group Operations

The p+1p + 1 points of C(Fp)C(\mathbb{F}_p) form a group with the group operation:

(x0,y0)(x1,y1):=(x0x1y0y1,x0y1+y0x1)(x_0, y_0) \cdot (x_1, y_1) := (x_0 \cdot x_1 − y_0 \cdot y_1, x_0 \cdot y_1 + y_0 \cdot x_1)

Notice that this equation resembles the cos(α+β)cos(\alpha + \beta) and sin(α+β)sin(\alpha+\beta) formulas and is equivalent to rotation over the unit circle.

The group has (1,0)(1, 0) as its identity element, and for any P=(Px,Py)C(Fp)P = (P_x, P_y) \in C(\mathbb{F}_p), we shall call

TP(x,y):=P(x,y)=(PxxPyy,Pxy+Pyx)T_P(x, y) := P \cdot (x, y) = (P_x \cdot x − P_y \cdot y, P_x \cdot y + P_y \cdot x)

the translation(rotation) by PP.

The squaring map with respect to the group operation is the quadratic map

π(x,y):=(x,y)(x,y)=(x2y2,2xy)=(2x21,2xy)\pi(x, y) := (x, y) \cdot (x, y) = (x^2 − y^2, 2 \cdot x \cdot y) = (2 · x^2 − 1, 2 \cdot x \cdot y)

and group inverses are given by the degree-one map J(x,y):=(x,y)J(x, y) := (x, −y)

Figure 1. Blue points under the square operation (left) and inverse operation (right) result in red points.

So you can think of π\pi as doubling the angle it forms with the xx-axis and JJ as a reflection by the xx-axis.

Twin-coset and Standard Position Coset

First, Figure 2 shows how the subgroups would look like in the circle group.

Figure 2. Subgroups of size 4, 2, 1 (left to right)

Taking a coset of a subgroup means that each point in the subgroup will be rotated by the same amount.

Definition Let Gn1G_{n-1} be a cyclic subgroup of C(Fp)C(\mathbb{F}_p) of size Gn1=2n1|G_{n-1}=2^{n-1}| for n1n\geq1. Any disjoint union D=QGn1Q1Gn1D=Q\cdot G_{n-1}\cup Q^{-1}\cdot G_{n-1} with QGn1Q1Gn1=Q\cdot G_{n-1}\cap Q^{-1}\cdot G_{n-1}=\varnothing is called twin-coset of size N=2nN=2^n.

Remark Twin-coset maps to itself under inverse, since

J(D)=J(QGn1)J(Q1Gn1)=Q1Gn1QGn1J(D)=J(Q\cdot G_{n-1})\cup J(Q^{-1}\cdot G_{n-1})=Q^{-1}\cdot G_{n-1}\cup Q\cdot G_{n-1}
Figure 3. Twin cosets of subgroups 4,2,1 (left to right). QGn1Q\cdot G_{n-1} is blue and Q1Gn1Q^{-1}\cdot G_{n-1} is red. If we take the union, it is a twin coset.

Definition In the exceptional case that a twin-coset DD of subgroup Gn1G_{n-1} is again a coset of the subgroup GnG_n, we call DD a standard position coset. Lemma 3 If DD is a twin-coset of size 2n,n22^n, n\geq2 then its image π(D)\pi(D) is a twin-coset of size 2n12^{n-1}. In addition, if DD is a standard position coset, so is π(D)\pi(D).

Figure 4. Notice that they are twin-cosets of subgroup 4, 2, 1 (left to right), but are also a coset of subgroup size 8, 4, 2 respectively.

Lemma 3 from the paper. If DD is a twin-coset of size 2n,n22^n, n\geq2 then its image π(D)\pi(D) is a twin-coset of size 2n12^{n-1}. In addition, if DD is a standard position coset, so is π(D)\pi(D).

Proof: π(D)=π(QGn1Q1Gn1)=π(Q)Gn2π(Q1)Gn2\pi(D)=\pi(Q\cdot G_{n-1}\cup Q^{-1}\cdot G_{n-1})=\pi(Q)\cdot G_{n-2}\cup\pi(Q^{-1})G_{n-2} and if D=QGnD=Q\cdot G_{n} is a standard position coset, then π(QGn)=π(Q)Gn1\pi(Q\cdot G_{n})=\pi(Q)\cdot G_{n-1}, which means π(D)\pi(D) is also a standard position coset.

Space of Polynomials

Definition Let FF be an extension field of Fp\mathbb{F}_p. Over the circle curve, for any even integer n0n\geq0 we define LN(F)\mathcal{L}_N(F) as the space of all bi-variate polynomials with coefficients in FF, and of total degree at most N/2N/2,

LN(F)={p(X,Y)F[X,Y]/(X2+Y21):deg pN/2}\mathcal{L}_N(F)=\{p(X,Y)\in F[X,Y]/(X^2 + Y^2 -1) : deg\ p \leq N/2 \}

For a circle STARK the bi-variate polynomials from LN(F)\mathcal{L}_N(F) are what low-degree extensions are for classical univariate proofs. The crucial properties of LN(F)\mathcal{L}_N(F) are:

  1. rotation invariance, which is needed for the next-neighbour relation and efficient encoding

  2. good separability, leading to maximum distance separable codes.

Vanishing Polynomial

Definition Let DD be a subset of C(Fp)C(\mathbb{F}_p) of even size NN, where 2N<p+12\leq N < p + 1. We call any non-zero polynomial from LN=LN(Fp)\mathcal{L}_N=\mathcal{L}_N(\mathbb{F}_p), which evaluates to zero over DD a vanishing polynomial of the set DD. Decomposing DD into pairs of points Pk,Qk,1kN/2{P_k, Q_k},1\leq k\leq N/2 and taking the product of linear functions going through these pairs,

vD(x,y)=k((xPkx)(QkyPky)(yPky)(QkxPkx))v_D(x,y)=\prod_k{((x-P_{kx})\cdot(Q_{ky}-P_{ky})-(y-P_{ky})(Q_{kx}-P_{kx}))}

vD(x,y)=k((xPkx)(QkyPky)(yPky)(QkxPkx))v_D(x,y)=\prod_k{((x-P_{kx})\cdot(Q_{ky}-P_{ky})-(y-P_{ky})(Q_{kx}-P_{kx}))}shows that vanishing polynomials do exist.

Given a twin-coset D=QGn1Q1Gn1D=Q\cdot G_{n-1}\cup Q^{-1}\cdot G_{n-1}, using Lemma 3, we can see πn1(D)\pi^{n-1}(D) will result in a twin-coset of size 2. In other words, it is in the form of πn1(D)={(xD,yD),(xD,yD)}\pi^{n-1}(D)=\{(x_D, y_D),(x_D,-y_D)\} for some xD,yDDx_D, y_D\in D. We therefore may take

vD(x,y):=vn(x,y)xDv_D(x,y):=v_n(x,y)-x_D

with vn(x,y):=πxπn1(x,y)v_n(x,y):=\pi_x\circ\pi^{n-1}(x,y) where πx\pi_x is the projection onto the x-axis.

And when DD is a standard position coset, its image πn1(D)\pi^{n-1}(D) is again a standard position coset and thus xD=0x_D=0 (see Figure 4, rightmost image). In this case vD(x,y):=vn(x,y)v_D(x,y):=v_n(x,y) and vDv_D can be evaluated by only O(n)O(n) field operations (2 addition and 1 multiplication in each step).

v1(x)=πxπ0(x,y)=πx(x,y)=xv2(x)=2x21v3(x)=2(2x21)21=8x48x2+1v_1(x)=\pi_x\circ \pi^0(x,y)=\pi_x\circ(x,y)=x \\ v_2(x)=2x^2 - 1\newline v_3(x)=2(2x^2-1)^2-1=8x^4-8x^2+1\\ \dots

Definition The circle code with values in FF and evaluation domain DD, is linear code with code words from the space:

CN(F,D)={f(P)PD:fLN(F)}\mathcal{C}_N(F,D)=\{f(P)|_{P\in D}: f\in\mathcal{L}_N(F)\}

Circle FFT

Definition 1 from the paper. (CFFT-friendly prime). Any prime pp for which (p+1)(p + 1) is divisible by 2n+12^{n+1} for sufficiently large n1n \geq 1, will be called CFFT-friendly, and any such nn is a supported order, and N=2nN = 2^n a supported domain size.

Definition 4 from the paper. For any integer jj from the interval 0j2n10 \leq j \leq 2^n − 1, let (j0,...,jn1){0,1}n(j_0, . . . , j_{n−1}) \in\{0, 1\}^n denote its bit representation. The FFT-basis of order nn is the family Bn\mathcal{B}_n of polynomials:

bj(n)(x,y):=yj0v1(x)j1...vn1jn1(x), 0j2n1b^{(n)}_j (x, y) := y^{j_0} · v_1(x)^{j_1} · . . . v^{j_{n−1}}_{n−1}(x),\ 0 ≤ j ≤ 2n − 1

Consider bi-variate polynomials modulo x2+y21x^2 + y^2 -1: F[X,Y]/(x2+y21)F[X,Y]/(x^2 + y^2 - 1). Here y21x2y^2\equiv 1-x^2 so we can replace all y2y^2 by 1x21-x^2 and hence, all polynomials in F[X,Y]/(x2+y21)F[X,Y]/(x^2 + y^2 - 1) can be represented with polynomials with deg(y)1deg(y) \leq 1.

This means f(X,Y)F[X,Y]/(x2+y21)f(X,Y)\in F[X,Y]/(x^2 + y^2 - 1) can be represented as canonical form:

f(X,Y)=f0(X)+Yf1(X)f(X,Y)=f_0(X) + Yf_1(X)

And we can calculate f0(X)f_0(X) and f1(X)f_1(X) by:

f0(X)=f(X,Y)+f(X,Y)2f1(X)=f(X,Y)f(X,Y)2Yf_{0}(X) = \frac{f(X,Y) + f(X,-Y)}{2}\\f_{1}(X)=\frac{f(X,Y)-f(X,-Y)}{2Y}

(JJ-folding) First step ϕJ\phi_J aka πx\pi_x:

f0(x)=f(x,y)+f(x,y)2f1(x)=f(x,y)f(x,y)2yf0(x)+yf1(x)=f(x,y)f_0(x) = \frac{f(x,y) + f(x,-y)}{2}\\f_1(x)=\frac{f(x,y)-f(x,-y)}{2y}\\f_0(x) + y\cdot f_1(x)=f(x,y)

More intuitively, f0f_0 is taking the average of ff and fJf\circ J while f1f_1 is the difference between them divided by 2y2y.

Figure 5. Given the evaluations (left), the result of JJ-folding is shown. Notice that f0f_0 and f1f_1 can be actually parametrized by only the x-axis.

(π\pi-folding) Next step:

fk00(2x21)=fk0(x)+fk0(x)2fk01(2x21)=fk0(x)fk0(x)2xfk00(2x21)+xfk01(2x21)=fk0(x)f_{k_00}(2\cdot x^2 - 1)=\frac{f_{k_0}(x) + f_{k_0}(-x)}{2}\\f_{k_01}(2\cdot x^2 - 1)=\frac{f_{k_0}(x) - f_{k_0}(-x)}{2x}\\f_{k_00}(2x^2 - 1) + xf_{k_01}(2x^2-1)=f_{k_0}(x)

This step is repeated recursively until we get constant functions of the form:

fk0k1k2kn1f_{k_0k_1k_2\dots k_{n-1}}

These make up a constant ck=fk0,...,kn1Fc_k = f_{k_0,...,k_{n−1}} \in F, for each kk in the interval 0k2n10 \leq k \leq 2^{n} −1, where k=k0+k12+...+kn12n1k = k_0 + k_1 2+. . .+k_{n−1}2^{n−1}.

Figure 6. Result of π\pi-folding on f0f_0. We do the same for f1f_1 to get f10f_{10} and f11f_{11}

In Figure 6, f0(x)f_0(x) suddenly has only 4 points. This is because f0(x)f_0(x) actually has only 4 evaluation points (A,B,B,A)(-A, -B, B, A) and is only parametrized by xx. It is visualized on a circle for easier group operation visualization. To elaborate:

  1. f00(C)f_{00}(C) is the average of f0(A)f_0(A) and f0(A)f_0(-A).

  2. f00(C)f_{00}(-C) is the average of f0(B)f_0(B) and f0(B)f_0(-B).

But where did CC come from? It denotes 2A212A^2-1, while C-C is 2B212B^2-1 since A2+B2=1A^2 + B^2=1 because they are from a standard position coset.

Theorem 2 Let pp be a CFFT-friendly prime supporting the order n1n\geq 1, take DC(Fp)D \subset C(\mathbb{F}_p) a twin-coset of size D=2n|D| = 2^n. Given fFDf \in F^D a function over DD with values in an extension field FF of Fp\mathbb{F}_p , the above described algorithm outputs the coefficients ckFc_k \in F, 0k2n10 \leq k \leq 2^n-1, with respect to the FFT basis Bn\mathcal{B_n}, so that 2n1k=0ckbk\sum^{2^n−1}{k=0}c_k \cdot b_k evaluates to ff over DD.

Low degree test over the Circle

Protocol 1 (Circle FRI). Let DD be a standard position coset of size D=2B+n|D| = 2^{B+n}, where B1B \geq 1 and n1n \geq 1, and let C=CN(F,D)\mathcal{C} = \mathcal{C}_N(F, D) be the circle code with rate ho=N+1Dho = \frac{N+1}{|D|}, where N=2nN = 2^n. For given proximity parameter θ(0,1ρ)\theta \in (0, 1 − \sqrt{ρ}), the interactive oracle proof of a function fFDf \in F^D being θ\theta-close to the circle code C\mathcal{C}, consists of a commit phase and a subsequent query phase, which are as follows.

COMMIT phase:

  1. (Decomposition) The prover compute the decomposition of fLN(F)f\in\mathcal{L}_N(F) into f=f(0)+λvnf=f^{(0)} +\lambda\cdot v_n with f(0)L(0):=LN(F)f^{(0)}\in \mathcal{L}^{(0)}:=\mathcal{L}'_N(F) and λF\lambda\in F. It sends λ\lambda and commitment to f(0)f^{(0)} to the verifier.

  2. (JJ-folding) For i=1i = 1:

    1. The verifier picks uniformly random βiF\beta_i \in F and sends it to the prover.

    2. The prover commits to a function f(i)L(i)f^{(i)}\in \mathcal{L}^{(i)} (In the case of an honest prover, f(i)=f0(i1)+βif1(i1)f^{(i)} = f^{(i-1)}_{0} + \beta_i f^{(i-1)}_{1} where f0(i1)πx=f(i1)+f(i1)J2f1(i1)πx=f(i1)f(i1)J2yf^{(i-1)}_0\circ\pi_x=\frac{f^{(i-1)}+f^{(i-1)}\circ J}{2}\\f^{(i-1)}_1\circ\pi_x=\frac{f^{(i-1)}-f^{(i-1)}\circ J}{2y}

  3. (π\pi-folding) For i=2i = 2 to rr:

    1. The verifier picks uniformly random βiF\beta_i \in F and sends it to the prover.

    2. The prover commits to a function f(i):L(i)Ff^{(i)} : L^{(i)} \rightarrow F. (In the case of an honest prover, f(i)=f0(i1)+βif1(i1)f^{(i)} = f^{(i-1)}_{0} + \beta_i f^{(i-1)}_{1} where

      f0(i1)π=f(i1)+f(i1)T2f0(i1)π=f(i1)f(i1)T2xf^{(i-1)}_0\circ\pi=\frac{f^{(i-1)}+f^{(i-1)}\circ T}{2}\\f^{(i-1)}_0\circ\pi=\frac{f^{(i-1)}-f^{(i-1)}\circ T}{2x}

      where T(x)=xT(x)=-x.

  4. The prover sends a value f(r)L(r)f^{(r)} \in \mathcal{L}^{(r)} in plain.

QUERY phase: (executed by the Verifier)

  1. Repeat ll times where ll is the number of times you want to query to achieve target soundness:

    1. Pick x0L(0)x_0 \in L^{(0)} uniformly at random.

    2. (JJ-folding) For i=1i = 1:

      1. Query ff at x0x_0 and J(x0)J(x_0). Compute f(0)(x0)=f(x0)λvn(x0)f(0)(J(x0))=f(J(x0))λvn(J(x0))f^{(0)}(x_0)=f(x_0)-\lambda\cdot v_n(x_0)\\f^{(0)}(J(x_0))=f(J(x_0)) - \lambda\cdot v_n(J(x_0))

      2. Compute f0(0)(πx(x0))=f(0)(x0)+f(0)(J(x0))2f1(0)(πx(x0))=f(0)(x0)+f(0)(J(x0))2yf^{(0)}_0(\pi_x(x_0)) = \frac{f^{(0)}(x_0) + f^{(0)}(J(x_0))}{2}\\f^{(0)}_1(\pi_x(x_0)) = \frac{f^{(0)}(x_0) + f^{(0)}(J(x_0))}{2y}

      3. Query f(1)f^{(1)} at x1=πx(x0)x_1=\pi_x(x_0) and check if f(1)(πx(x0))=f0(0)(πx(x0))+β1f1(0)(πx(x0))f^{(1)}(\pi_x(x_0)) = f^{(0)}_{0}(\pi_x(x_0)) + \beta_1 f^{(0)}_{1}(\pi_x(x_0))

    3. (π\pi-folding) For i=2ri = 2\dots r:

      1. Calculate xi=π(xi1)=2xi121x_i=\pi(x_{i-1})=2x^2_{i-1}-1

      2. Query f(i1)f^{(i-1)} at xi1-x_{i-1}. (the value at xi1x_{i-1} is queried in the previous round)

      3. Compute f0(i1)(xi)=f(i1)(xi1)+f(i1)(xi1)2f1(i1)(xi)=f(i1)(xi1)f(i1)(xi1))2xi1f^{(i-1)}_0(x_i) = \frac{f^{(i-1)}(x_{i-1}) + f^{(i-1)}(-x_{i-1})}{2}\\f^{(i-1)}_1(x_i) = \frac{f^{(i-1)}(x_{i-1}) - f^{(i-1)}(-x_{i-1}))}{2x_{i-1}}

      4. Query f(i)f^{(i)} at xix_i and check if f(i)(xi)=f0(i1)(xi)+βif1(i1)(xi)f^{(i)}(x_i) = f^{(i-1)}_{0}(x_i) + \beta_i f^{(i-1)}_{1}(x_i)

  2. ACCEPT if all checks passed. REJECT otherwise

Batch Circle FRI

Protocol 2 (batch Circle FRI). Under the same assumptions as Protocol 1, the interactive oracle proof for a batch of functions f1,,fLFDf_1,\dots,f_L \in F^D having correlated (1θ)(1 − \theta)-agreement to a codeword from CN(F,D)C_N(F, D), is as follows. In the first step, given a random challenge λbF\lambda_b \leftarrow F from the verifier, the prover computes the values of the linear combination:

f=i=1Lλbk1fif=\sum^L_{i=1}\lambda_b^{k-1}\cdot f_i

over DD. Now, both prover and verifier run Protocol 1 on ff , with its query phase extended by a check of the batching at each of the queries.

CircleSTARK

In circle STARK, the trace domain is the standard position coset HC(Fp)H\subset C(\mathbb{F}_p) of a cyclic and proper subgroup G=GnG = G_n of the circle curve C(Fp)C(\mathbb{F}_p), of size N=2nN = 2^n, with n1n \geq 1, and the trace is organised column-wise t1,,twFpNt_1, \dots, t_w \in \mathbb{F}_p^N, each placed over the domain HH in the usual manner, using the group translation TT by a generator of GG for the timeline. The trace columns are interpolated by polynomials

p1,,pwFp[x,y]/(x2+y21)p_1,\dots,p_w\in\mathbb{F}_p[x,y]/(x^2+y^2 -1)

of total degree at most N/2N/2, meaning that piLN(Fp)p_i\in\mathcal{L}_N(\mathbb{F}_p) (actually, they are from the FFT-space LN(Fp))\mathcal{L}'_N(\mathbb{F}_p)), and these polynomials are subject to set of constraints, say

Pi(si,p1,,pw,p1T,,pwT)=0P_i(s_i,p_1,\dots,p_w,p_1\circ T,\dots,p_w\circ T)=0

for i=1,,Ci=1,\dots,C, holding over the entire domain HH, where siLN(Fp)s_i\in \mathcal{L}_N(\mathbb{F}_p) is a predefined selector polynomial.

Each constraint is a polynomial

PiFp[S,X1,,Xw,Y1,,Yw]P_i\in\mathbb{F}_p[S,X_1,\dots,X_w,Y_1,\dots,Y_w]

PiFp[S,X1,,Xw,Y1,,Yw]P_i\in\mathbb{F}_p[S,X_1,\dots,X_w,Y_1,\dots,Y_w]of total degree at most the maximum number of twin-coset of size NN, degPip2+1N1\mathsf{deg} P_i\leq\frac{p^2+1}{N} - 1 and the degree in the selector variable SS is at most degSPi1\mathsf{deg}_S P_i \leq 1.

Definition. The evaluation domain is a standard position coset DC(Fp)D\subseteq C(\mathbb{F}_p), of at least double the size of trace domain HH. The polynomials in the circle STARK will be generally committed by their values over this domain.

Lemma 2 from the paper. Let pp be a CFFT-friendly prime supporting the order m1m \geq 1, and GkG_k denote the subgroup of order 2k2^k for kmk \leq m. Then any subset of DC(Fp)/GmD\subseteq C(\mathbb{F}_p) / G_m which is invariant under and JJ can be decomposed into twin-cosets of size N=2nN = 2^n, for any nmn \leq m. In particular for a standard position coset DD of size M=2mM = 2^m,

D=QGm=k=0M/N1(Q4k+1Gn1Q4k1Gn1)D = Q \cdot G_m = \bigcup^{M/N-1}_{k=0}(Q^{4k+1}\cdot G_{n−1} \cup Q^{−4k−1}\cdot G_{n−1})

where QQ is an element from C(Fp)C(\mathbb{F}_p) of order 2m+12^{m+1}.

IOP for AIR

Now, once we have all these, the interactive oracle proof for the satisfiability of the AIR can be constructed as follows:

In the first round, the prover computes the values of its trace polynomials p1,,pwLN(Fp)p_1,\dots,p_w\in\mathcal{L}_N(\mathbb{F}_p) over the evaluation domain DD using its decomposition into twin-cosets and shares their oracles denoted by

[p1],,[pw][p_1],\dots,[p_w]

with their verifier.

In the second round, the verifier sends random challenge βF\beta \leftarrow F, drawn uniformly from a suitably large extension field FF of Fp\mathbb{F}_p, which is used to reduce the constraint polynomials into a single one:

i=1Cβi1Pi(si,p1,,pw,p1T,,pwT)=0\sum^C_{i=1}\beta^{i-1}\cdot P_i(s_i,p_1,\dots,p_w,p_1\circ T,\dots,p_w\circ T)=0

which should hold over trace domain HH. To prove this, the vanishing polynomial over HH, vHv_H, is computed so the composite constraint polynomial can now be written as:

i=1Cβi1Pi(si,p1,,pw,p1T,,pwT)=qvH\sum^C_{i=1}\beta^{i-1}\cdot P_i(s_i,p_1,\dots,p_w,p_1\circ T,\dots,p_w\circ T)=q\cdot v_H

To keep with the degree bound imposed by the size of HH, the quotient qL(d1)N(F)q\in\mathcal{L}_{(d-1)N}(F) needs to be split into polynomials q1,,qd1LN(F)q_1,\dots,q_{d-1}\in\mathcal{L}_N(F):

q=λvHˉ+k=1d1vHˉvHkqkq=\lambda\cdot v_{\bar H} + \sum^{d-1}_{k=1}\frac{v_{\bar H}}{v_{H_k}}\cdot q_k

Recall that L(d1)NL_{(d-1)N} has (d1)N+1(d-1)N + 1 dimension. On the other hand, the quotient qL(d1)N(F)q\in\mathcal{L}_{(d-1)N}(F) is computed by value from those of f1,,fwf_1,\dots,f_w over a union of twin-cosets HkH_k of size NN. Thus the union Hˉ=k=1d1Hk\bar{H}=\bigcup^{d-1}_{k=1}H_k is one point too small to uniquely determine a polynomial from L(d1)N\mathcal{L}_{(d-1)N}. In our decomposition, this missing point is characterized by an additional scalar multiple of the vanishing polynomial of Hˉ\bar{H}.

Then, the prover sets up the oracles

[q1],,[qd1][q_1],\dots,[q_{d-1}]

for their values over the evaluation domain DD, and sends them, together with λ\lambda, to the verifier.

Having all oracles in place, the next step is DEEP ALI, which reduces satisfiability of the constraints to a low-degree test on single-point quotients. (In lose terms, this step turns low-degree test into a polynomial commitment scheme.)

In this step, the verifier responds with a random point γC(F)(DH)\gamma\rightarrow C(F)\setminus (D\cup H). In return, the prover opens the values vi,0=pi(γ),vi,1=pi(T(γ))v_{i,0}=p_i(\gamma), v_{i,1}=p_i(T(\gamma)) for each i=1,,wi=1,\dots,w as well as v1,,vd1v_1,\dots,v_{d-1} of q1,,qd1q_1,\dots,q_{d-1} at γ\gamma. Eventually, both prover and verifier engage in a low-degree test for the real and imaginary parts of the DEEP quotients:

Re/Im(pivi,0vγ),Re/Im(pivi,1vT(γ))Re/Im(qivivγ)\mathsf{Re/Im}(\frac{p_i-v_{i,0}}{v_\gamma}),\mathsf{Re/Im}(\frac{p_i-v_{i,1}}{v_{T(\gamma)}})\\\mathsf{Re/Im}(\frac{q_i-v_i}{v_\gamma})

Conclusion

The initial implementation of CircleFFT demonstrated a performance improvement by a factor of 1.4 in a single-threaded setup. Building on this foundation, Starknet’s next-generation prover, Stwo (“STARK Two”), is designed to enhance and eventually replace the current prover, Stone (“STARK One”).

Figure 7. Initial benchmark result of CFFT

Written by Batzorig Zorigoo from A41

Last updated