Circle STARKs

Ulrich Haböck, David Levit, Shahar Papini uhaboeck@polygon.technology, david@starkware.co, spapini@starkware.co

December 17, 2024^∗

Abstract

Traditional STARKs \[BSBHR18b, BSCR⁺19, [COS20\]](#page-32-1) require a cyclic group of a smooth order in the field. This allows efficient interpolation of points using the FFT algorithm, and writing constraints that involve neighboring rows. ECFFT \[BSCKL21, [BSCKL22\]](#page-31-2) introduced a way to make efficient STARKs for any finite field, by using a cyclic group of an elliptic curve. We show a simpler construction in the lines of ECFFT over the circle curve x ² +y ² = 1. When p+ 1 is divisible by a large power of 2, this construction is as efficient as traditional STARKs and ECFFT. Applied to the Mersenne prime p = 2³¹ −1, which has been recently advertised in [\[HLN23\]](#page-33-0), our preliminary benchmarks indicate a speed-up by a factor of 1.4 compared to a traditional STARK using the Babybear prime p = 2³¹ − 2 ²⁷ + 1 from [\[BG\]](#page-31-3).

Contents

^∗This version corrects minor typos in Section 5.3 and adds an optimized treatment of constraints with punctuated activation domains.

Scalable and Transparent Arguments of Knowledge (STARKs) [\[BSBHR18b\]](#page-31-0) are succinct, general purpose argument systems which allow for efficient proof composition, and moreover do not require any trust assumptions for their setup. While technically, the original definition of a STARK also covers argument systems with a trustless setup elliptic curve commitment scheme, such as [\[BGH19\]](#page-31-5) and the entire track of folding schemes initiated by it, the term has become synonymous to univariate argument systems which rely on the FRI low-degree test \[BSBHR18a, BSCI+20], a proof of proximity for Reed-Solomon codes. STARKs are widely adopted in practice \[Sta23, Pola, Polc, Pold, [BG\]](#page-31-3), mainly because of their smaller embedding overhead in the arithmetization step (they are not bound to cryptographically large fields), and their simplicity compared to the aforementioned aggregation and folding schemes.

In univariate STARKs witness data is encoded into polynomials over a univariate domain, thereby demanding a smooth arithmetization field which supports fast Fourier transform (FFT) techniques; either the classical multiplicative Fourier transform [\[CT65\]](#page-32-2), or the additive FFT [\[LCH14\]](#page-33-5). This restriction was lifted by the Elliptic Curve Fourier Transform (ECFFT) [\[BSCKL21\]](#page-31-1), which uses smooth subgroups of elliptic curves as the underlying domain for the Fourier transform. Although tightly connected with the group structure of elliptic curves, the ECFFT is an algebraic transform similar to the additive FFT, and it is constructed along a chain of curves over the non-smooth field,

with 2-to-1 maps between them (each of algebraic degree 2), halving the sizes of the domains in each step. The ECFFT permits efficient interpolation by (certain) low-degree rational functions over the curve. The basic design principles of STARKs – the interactive oracle proof and the low-degree test – can be carried over to these rational function spaces and their algebraic geometry codes [\[BSCKL22\]](#page-31-2). ECFFT-based STARKs, which we shall call elliptic curve STARKs, are as efficient as classical STARKs, in the concrete sense and not just asymptotically, and by dropping the smoothness assumption on the finite field, they uncover an unprecedented freedom in the choice of the concrete prime for arithmetization.

In a recent note [\[HLN23\]](#page-33-0), the authors consider a different approach for the Mersenne prime p = 2³¹ − 1, a non-smooth prime with exceptionally fast arithmetic. They consider the circle curve

as a smooth multiplicative subgroup of the "complex extension" of the prime field (i.e. the quadratic extension with respect to the irreducible polynomial x ² + 1), and apply well-known optimizations for the classical FFT of real-valued functions, diminishing the extension field costs to only a small overhead in the number of additions. Furthermore, they observe that the extrapolated values lie in a linear subspace of the complex plane, a line which essentially depends only on the target coset, thereby reducing the commitment cost of Reed-Solomon code words to that of their "rectified" representation of half the size. While the approach from [\[HLN23\]](#page-33-0) is much more elementary than the one from \[BSCKL21, [BSCKL22\]](#page-31-2), its main drawback is a limited usefulness for constraint evaluation, when computing the overall quotient polynomial in the STARK. Similar to polar coordinates, the rectified representation is beneficial for computing products of polynomials. However, evaluating the overall constraint involves products and sums in quite arbitrary order, and demands – rather sooner than later – a conversion back to the ordinary complex representation. While this drawback is not drastic when dealing only with a small number of polynomials, it matters to STARKs with wide traces (such as \[Pola, [Polb\]](#page-33-6)), thwarting the advantage of that prime over ordinary two-adic primes of comparable size.

Motivated by [\[HLN23\]](#page-33-0), we propose a simpler construction along the lines of \[BSCKL21, [BSCKL22\]](#page-31-2), tailored to the Mersenne prime p = 2³¹ − 1 and the circle curve. As every (smooth) quadratic curve, the circle curve is isomorphic to the projective line over the prime field and thus of size (p + 1) (this is a wellknown fact but we will recapitulate it below). And it is a cyclic group, with its operation inherited from the action of the rotation group SO(2) over the field. The circle curve has the following benefits over the elliptic curve approach:

• 1. Firstly, and contrary to elliptic curves, the group squaring map (in the sense of a multiplicative group notation) is of quadratic degree and 2-to-1, dropping the need of a chain of curves.
• 2. Second, because rotation carries polynomials to polynomials in a degree-preserving manner, we may choose an FFT that is again with respect to a polynomial basis, instead of one comprised of rational functions. (Similar to the additive FFT and elliptic curve FFT, this polynomial basis is not the standard monomial one, and there is no known efficient conversion between the two).
• 3. Thirdly, and perhaps most importantly, simplicity: The reader does not need to have any background in algebraic geometry. Taking advantage of the above mentioned projective line view of the curve (in algebraic geometry terms, it has genus zero) the proofs are elementary and self-contained, without assuming knowledge on divisor calculus and the Riemann-Roch theorem. All that is needed is familiarity with the notion of a projective space, and not even that if one does not intend going through the proofs.

Although many of these features (if not all) are due to the genus of the circle curve, there is one point where the circle curve causes extra considerations. There is a gap of dimension one, between the image space of the FFT and the space of all polynomials of corresponding degree bound, the latter of which turns out the natural space for STARKs over the circle. In other words, FFT domains are one point too small to uniquely determine a polynomial of that degree bound, and this anomaly needs to be taken into account in a few places of the protocol: First, when computing the overall quotient, and second, in a preparatory step for the low-degree test. It turns out that in both cases the dimension gap can be treated cheaply (i.e. the computational cost is negligible) and without any loss in security.

Overall, circle STARKs are as efficient as classical STARKs over smooth fields (or an ECFFT-based STARK), and their mathematical foundation is "as close as can be" to the classical case. The entire interactive oracle proof over the circle uses polynomials (bivariate, though1 ) and the low-degree test is similar to the well-known FRI for Reed-Solomon codes. We believe that this helps a wider adoption in practice.

The document is organized as follows. In the first part we provide all relevant preliminaries:

• Section 2 and 3 introduce basic notions and discuss properties of the circle curve, its space of polynomials and Circle Codes, the Reed-Solomon type of code generated by them. In particular, we cover vanishing polynomials and quotients, the key ingredients for STARKs.

¹Although we do not dwell on it, we stress the fact that the projective line view allows the entire circle STARK to be seen as a univariate one based on generalized Reed-Solomon codes.

• In Section 4 we describe the FFT over the circle, the circle FFT and its inverse. We investigate the image space of the circle FFT and the aforementioned dimension gap.

With the complete FFT tool-set ready, we are able to approach our target application, circle STARKs.

• In Section 5 we describe the interactive oracle proof for an elementary system of constraints, a restricted algebraic intermediate representation yet expressive enough to highlight the general principle. We discuss the extra measures needed to deal with the aforementioned dimension gap.
• Eventually, in Section 6, we describe the low-degree test for polynomials over the circle curve. That proof of proximity is similar to FRI, with the folding steps in circle FFT style.

The second part is largely informal, focusing on the protocol steps, the involved polynomial arithmetic, and the few differences to univariate STARKs. A fully formal treatment, including security notions as well as their proofs (in the ordinary oracle model) is postponed to the appendix: In Appendix A we cite the celebrated correlated agreement theorem for Reed-Solomon codes \[BSCI⁺20], and explain how it is taken over to circle Codes. In Appendix B we prove soundness (in the oracle model) of both circle FRI and the circle STARK from Section 5. In Appendix C we further sketch a variant of the circle STARK in which the evaluation domain is a superset of the trace domain. While this variant is not able to support zero-knowledge, it optimizes the extrapolation effort of the prover for certain parameter settings.

We conclude the paper with a final section on implementation remarks, Appendix D, in which we provide preliminary benchmarks of the circle FFT over the Mersenne prime p = 2³¹ − 1. Compared to the classical FFT over the equally sized Babybear prime p = 2³¹ −2 ²⁷ + 1 from [\[BG\]](#page-31-3), our measurements indicate a speedup by a factor of 1.4, and we expect to achieve the same advantage in a fully optimized implementation of the FFT and the entire STARK.

Although our main target is the Mersenne prime p = 2³¹ − 1, we note that our considerations apply to arbitrary primes p with (p + 1) being smooth, and the entire document takes this into account2 . We point out that the circle FFT is related, yet different to the recent Galois-FFT [\[LX23\]](#page-33-7), which (up to isomorphism) shares the same underlying space and group action. The Galois-FFT is concretely less efficient than the circle FFT (it costs the double of multiplications), and beyond that not as useful for STARKs, since its function spaces are not invariant under action of their corresponding subgroup. A detailed comparison of the two FFTs is given in the companion note [\[Hab24\]](#page-32-3).

2 Notations and definitions

Let us start with the central property of the primes we consider.

Definition 1 (CFFT-friendly prime). Any prime p for which (p+ 1) is divisible by 2 ⁿ+1 for sufficiently large n ≥ 1, will be called CFFT-friendly, and any such n is a supported order, and N = 2ⁿ a supported domain size.

Remark 1. The reason for demanding 2 ⁿ+1 instead of 2 ⁿ being a factor (p + 1) in Definition 1 is due to the existence of suitable FFT domains and will become clear in Section 4.

Which n ≥ 1 is considered sufficiently large depends on the application. In the context of STARK one typically wants a small prime p with p + 1 being as smooth as possible. A compelling choice is the Mersenne prime

called M31 in [\[HLN23\]](#page-33-0), which for its exceptionally efficient arithmetic is also our main target. However, other choices of CFFT friendly primes might be useful in practice, and for this reason why we keep our exposition as general as possible.

² In fact, this approach can be generalized to non-prime finite fields F^q with (q + 1) being smooth as well.

CFFT-friendly primes are of the form p = 2^{n+1} \cdot t - 1 for integers n, t \ge 1 . In particular, p - 1 = 2 \cdot t' with t' = 2^n \cdot t - 1 being odd, or equivalently

p \equiv 3 \mod 4 ,

meaning that -1 does not have a square root modulo p. For any such prime, the polynomial x^2 + 1 has no roots in the prime field \mathbb{F}_p .

We shall denote the algebraic closure of \mathbb{F}_p by K, and \pm i the roots of x^2 + 1 in K. Finite extensions of \mathbb{F}_p will be denoted by F, and considered as a subfield of K. In rare cases it will be useful to work with F(i), the field that results from F by adjoining the root i. If i is contained in F then F(i) = F; otherwise F(i) is a quadratic extension of F.

For any finite extension F of \mathbb{F}_p we will write F[x] and F[x,y] for the ring of polynomials in one and two variables, respectively. Likewise, we use the notation F[x]^{\leq d} and F[x,y]^{\leq d} of all polynomials over F of total degree at most d. Polynomials from F[x,y] will be often denoted as p(x,y), which will not cause confusion with the prime p although we override notation. Given a polynomial p(x,y) from F[x,y], the ideal generated by it is denoted as (p(x,y)).

For certain aspects, mostly within proofs, the one and two-dimensional projective spaces P^1(F) and P^2(F) over a finite extension F of \mathbb{F}_p will be useful. We consider them contained in the corresponding projective space P^1(K) and P^2(K) over the algebraic closure K, and we use the common notation (t:s) and (x:y:z) for points in P^1(K) and P^2(K) , respectively. Points with non-zero last coordinate, s \neq 0 or z \neq 0 , are affine points.

3 The circle curve

Although we target CFFT-friendly primes p (cf. Definition 1), most of this section depends only on the property p \equiv 3 \mod 4 . Thus, unless stated otherwise, let \mathbb{F}_p be the prime field with modulus p \equiv 3 \mod 4 .

We define the Circle Curve, denoted by C = C(\mathbb{F}_p) , to be the (smooth) algebraic variety over \mathbb{F}_p defined by the equation

or equivalently, in projective coordinates

Remark 2. By the condition on the modulus p, there are no \mathbb{F}_p -rational points at infinity Z=0, and the projective view seems of not much use. However, the complete geometric picture unfolds when considering the curve over the algebraic closure K of \mathbb{F}_p , in which there are two points at infinity, \infty=(1:i:0) and \bar{\infty}=(1:-i:0) , with \pm i being the square roots of -1. These two points, which are \mathbb{F}_p(i) -rational, will play a prominent role in our construction.

The arithmetization of circle STARK takes place over the circle curve domain. Witnesses are encoded into low-degree polynomials over that domain, and subjected to certain algebraic relations, the constraints.

Proof. The isomorphism is the stereographic projection onto the y-axis with center (-1,0), defined by the equations

Under this isomorphism (-1,0) is identified with infinity of the projective line, and the two curve points \infty = (1:+i:0), \bar{\infty} = (1:-i:0) from Remark 2 correspond to t=\pm i .

Although we pivot to the bivariate representation of the circle curve, the projective line view will be extremely useful within proofs. The isomorphism from Lemma 1 allows a direct translation of bivariate function fields into univariate ones, and consequently a much more elementary treatment, avoiding general tools from algebraic geometry such as the Riemann-Roch theorem. Nevertheless, whenever useful we provide complementing remarks addressed to the reader with background in algebraic geometry.

3.1 The circle curve as a group

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

(We somewhat override notation here, but as we do not use entry-wise multiplication this will not cause confusion.) For this reason, we shall call C(\mathbb{F}_p) also the circle group. The circle group is cyclic because the map (x,y) \mapsto x + i \cdot y is a group homomorphism between C(\mathbb{F}_p) and a multiplicative subgroup of the extension \mathbb{F}_p(i) . The group has (1,0) as its neutral element, and for any P = (P_x, P_y) in C(\mathbb{F}_p) we shall call

the rotation, or translation by P. The squaring map with respect to the group operation is the quadratic map

and group inverses are given by the degree-one map

Note that, as in any group, the map J is an involution, i.e. J(J(P)) = P for every P \in C(\mathbb{F}_p) , and that J and \pi commute, i.e. \pi(J(P)) = J(\pi(P)) for every P \in C(\mathbb{F}_p) .

Remark 3. The definition of T_P extends to the entire projective variety over K, and it is easily verified that both \infty and \bar{\infty} from Remark 2 are fixed points under the action of the circle group. We stress the fact that the existence of fixed points is in stark contrast to the elliptic curve case. We will see below that these fixed points allow a more elegant choice of rotation-invariant Riemann-Roch spaces.

Remark 4. Under the isomorphism from Lemma 1, the circle group law translates to the projective line as (t_1:s_1) \oplus (t_2:s_2) = (t_1 \cdot s_2 + t_2 \cdot s_1:s_1 \cdot s_2 - t_1 \cdot t_2) , or in affine coordinates t_1 \oplus t_2 = \frac{t_1 + t_2}{1 - t_1 \cdot t_2} . In other words, the circle group is isomorphic to a subgroup of linear automorphisms of the projective line, those which leave \pm i invariant. This is exactly the subgroup chosen in the Galois-FFT [LX23].

Since C(\mathbb{F}_p) is cyclic, for each N \geq 1 which divides (p+1) there is a unique cyclic subgroup of size N. In the case of a two-adic order N=2^n we shall denote that unique subgroup by G_n . The following type of sets are the suitable domains of the circle FFT described in Section 4.

Twin-cosets are composed of those pairs in the quotient group C(\mathbb{F}_p)/G_{n-1} which are mapped to one another under the inverse map J. This particularly excludes fixed points of J, which are those elements Q \cdot G_{n-1} with Q^{-1} \cdot G_{n-1} = Q \cdot G_{n-1} , or Q^2 \in G_{n-1} . In other words, fixed points of J in the quotient group are either the trivial element or an element of order two, if it exists. In the latter case, the union of the two fixed points form the subgroup G_n of size 2^n . See Figure 1 for an illustration of standard position cosets and twin-cosets.

Proposition 1. Let p be a prime such that p \equiv 3 \mod 4 , and let n \ge 1 . The existence of standard position cosets of size 2^n is equivalent to that p is CFFT-friendly supporting the order n. In this case, standard position cosets are unique and of the form

with Q \in C(\mathbb{F}_p) being an element of order 2^{n+1} .

Proof. Since C(\mathbb{F}_p)/G_{n-1} is cyclic, and excluding fixed points of J, there is at most one J-invariant pair \{Q \cdot G_{n-1}, Q^{-1} \cdot G_{n-1}\} , with Q \cdot G_{n-1} \neq Q^{-1} \cdot G_{n-1} , which forms a coset in C(\mathbb{F}_p)/G_{n-1} . In fact, since the two elements of the pair are different, we must have Q^2 \notin G_{n-1} , and since it is a coset of order two, their difference Q \cdot G_{n-1} \cdot (Q^{-1} \cdot G_{n-1})^{-1} = Q^2 \cdot G_{n-1} must be of order two, meaning that Q \cdot G_{n-1} has order four. The existence of order four elements in C(\mathbb{F}_p)/G_{n-1} is equivalent to that 2^{n+1} divides (p+1), completing the proof of the proposition.

Although breaking with the group structure, twin-cosets are natural evaluation domains for the FFT. They are used to work around the non-smooth behaviour of the circle FFT under rotation, and are the typical extrapolation target in our application. Similar to the decomposition of univariate evaluation domains into cosets of smaller size, twin-coset domains, and in particular standard position cosets, can be decomposed into twin-cosets of smaller size.

Lemma 2. Let p be a CFFT-friendly prime supporting the order m \geq 1 , and G_k denote the subgroup of order 2^k for k \leq m . Then any subset of D \subseteq C(\mathbb{F}_p) \setminus G_m which is invariant under G_{m-1} and J can be decomposed into twin-cosets of size N = 2^n , for any n \leq m . In particular for a standard position coset D of size M = 2^m ,

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

Proof. Since n \leq m the subset D is also invariant under G_{n-1} and disjoint from G_n . Thus, as a J-invariant subset of C(\mathbb{F}_p)/G_{n-1} which does not contain fixed points of J, it is a union of J-invariant pairs in C(\mathbb{F}_p)/G_{n-1} . This proves the first assertion. The second claim follows from D = Q \cdot G_{m-1} \cup Q^{-1} \cdot G_{m-1} , where Q is an element of order 2^{m+1} , and the decomposition

taking Q^4 as a generator of G_{m-1} .

Lemma 3. If D is a twin-coset of size N = 2^n , n \ge 2 , then its image \pi(D) under the squaring map \pi is a twin-coset of size N/2. More specifically, if D is a standard position coset, so is \pi(D) .

Proof. Since \pi is a group endomorphism which maps G_{n-1} onto the subgroup G_{n-2} , the image of a twin-coset D = Q \cdot G_{n-1} \cup Q^{-1} \cdot G_{n-1} is

Moreover, as \pi(Q)^2 = \pi(Q^2) , and Q^2 \notin G_{n-1} , also \pi(Q)^2 \notin G_{n-2} , showing that the two cosets of G_{n-2} are disjoint. Hence \pi(D) is a twin-coset, and its size is N/2. Finally, if D is invariant under G_n , then \pi(D) is invariant under \pi(G_n) = G_{n-1} . Together with the first assertion, this proves that standard position cosets are mapped onto standard position cosets.

Figure 1: A schematic illustration of the three smallest standard position cosets in the affine plane over \mathbb{F}_p , and general twin-cosets of the same size.

3.2 The space of polynomials and Circle Codes

Let F be an extension field of \mathbb{F}_p . Over the circle curve, for any even integer N \geq 0 we define \mathcal{L}_N(F) as the space of all bivariate polynomials with coefficients in F, and of total degree at most N/2,

\mathcal{L}_N(F) = \left\{ p(x, y) \in F[x, y] / (x^2 + y^2 - 1) : \deg p \le \frac{N}{2} \right\}, (3)

where deg p in (3) means the smallest total degree of a representative within the class p(x, y) + (x^2 + y^2 - 1) . (Recall that (x^2 + y^2 - 1) denotes the ideal in F[x, y] generated by x^2 + y^2 - 1 ). Even though the functions in \mathcal{L}_N(F) are polynomials, we shall often use f and g for elements from \mathcal{L}_N(F) .

Remark 5. In terms of algebraic geometry, \mathcal{L}_N(F) equals the Riemann-Roch space over C(F) for the \mathbb{F}_p -rational divisor \frac{N}{2} \cdot \infty + \frac{N}{2} \cdot \bar{\infty} . In other words, \mathcal{L}_N(F) consists of all F-rational functions with poles only at \infty and \bar{\infty} , each at most of order N/2. It is due to the specific structure of the circle curve (in hand-wavy geometric terms, its projective closure is the Riemann sphere and not a group) that unlike in the elliptic curve case, the relevant function space can be again chosen as a space of polynomials instead of rational functions (under the bivariate view). However, we emphasize that this is not an essential feature.

For a circle STARK the bivariate polynomials from \mathcal{L}_N(F) are what low-degree extensions are for classical univariate proofs. The crucial properties of \mathcal{L}_N(F) , as shown by the following proposition, are (1) rotation invariance, which is needed for the next-neighbour relation and efficient encoding, and (2) good separability, leading to maximum distance separable codes.

Proposition 2. For even integer N \geq 0 the space of polynomials \mathcal{L}_N(F) has the following properties.

• 1. It is invariant under rotation, i.e. for each f \in \mathcal{L}_N(F) and P \in C(\mathbb{F}_p) , also f \circ T_P \in \mathcal{L}_N(F) . (Here and in the sequel, \circ denotes functional composition.)
• 2. Its dimension is N+1, and every non-trivial f \in \mathcal{L}_N(F) , i.e. f \notin (x^2+y^2-1) , has at most N zeros over C(F).

^<sup>3We consider a divisor D = \sum n_P \cdot P to be \mathbb{F}_p -rational, if it is invariant under every automorphism of the Galois group of K over \mathbb{F}_p , where K is the algebraic closure of \mathbb{F}_p . That is, if \alpha is such an automorphism, then n_{\alpha(P)} = n_P .

Proof. Property 1 is trivial, since T_P is linear and hence does not change the total degree of a polynomial.

To prove Property 2, we make use of the fact that under the isomorphism from Lemma 1 the space \mathcal{L}_N(F) is carried over to

L_N(F) = \left\{ \frac{p(t)}{(1+t^2)^{\frac{N}{2}}} : p \in F[t], \deg p(t) \le N \right\}. (4)

As this representation will be useful in other proofs, we elaborate it in detail: The univariate representation of a bivariate monomial x^j \cdot y^k of degree j + k \le N/2 , where j, k \ge 0 , is

which is of the claimed form. Conversely, let us compute the bivariate representation of a function t^k/(1+t^2)^{N/2} with 0 \le k \le N . Writing k = 2 \cdot j + \varepsilon , with 0 \le j \le N/2 and \varepsilon \in \{0,1\} (where in the edge case j = N/2 we have \varepsilon = 0 ), the function corresponds to

which over the circle x^2 + y^2 = 1 is equal to

which is a polynomial of total degree at most N/2.

From the univariate representation (4) of \mathcal{L}_N(F) , we eventually conclude that \dim \mathcal{L}_N(F) = N+1 . Moreover, every fractional function p(t)/(1+t^2)^{N/2} with p(t) of degree \leq N and N+1 zeros (possibly including infinity) must be trivial. This completes the proof of the Proposition.

Remark 6. The above proof reduces to a three-liner when using results from algebraic geometry: The \mathbb{F}_p -rational divisor \frac{N}{2} \cdot \infty + \frac{N}{2} \cdot \bar{\infty} is invariant under the group action, and so is its Riemann-Roch space. As the degree of the divisor is equal to N, the Riemann-Roch theorem tells us that \dim \mathcal{L}_N(F) = N + 1 - g , where g = 0 is the genus of the circle curve. (This is in fact the most notable difference from elliptic curves, where g = 1 and the dimension of space equals the degree of the divisor.) In regards of the number of zeros, any non-trivial function over the circle curve has the same number of zeros as poles in the algebraic closure K, with multiplicities taken into account.

Note that by repeatedly substituting y^2 = 1 - x^2 every polynomial p(x, y) from \mathcal{L}_N(F) can be reduced to the form

p(x,y) = p_0(x) + y \cdot p_1(x), \tag{5}

with p_0 \in F[x]^{\leq N/2} and p_1 \in F[x]^{\leq \frac{N}{2}-1} . We shall call the representation (5) the canonical form of a polynomial from \mathcal{L}_N(F) . The canonical form shows that the collection of monomials

1, x, \dots, x^{\frac{N}{2}}, \quad y, y \cdot x, \dots, y \cdot x^{\frac{N}{2} - 1} (6)

spans the space \mathcal{L}_N(F) , and by the dimension of \mathcal{L}_N(F) , it must be a basis. We call it the monomial basis of \mathcal{L}_N .

For subsets D of the circle curve, typically a standard position coset or a twin-coset, we eventually define circle codes as the linear codes which stem from the space of polynomials of degree at most N/2.

Remark 7. The circle code is the algebraic geometry code generated by the Riemann-Roch space of the divisor \frac{N}{2} \cdot \infty + \frac{N}{2} \cdot \bar{\infty} , with an evaluation domain of \mathbb{F}_p -rational points. In particular, due to the genus of the circle curve (Lemma 1) it is a generalized Reed-Solomon code. See also Theorem 1 below.

and the minimum distance of the code is

The following theorem is an immediate consequence of Lemma 1 but nevertheless important for our purposes, as it allows for ordinary Reed-Solomon techniques.

Proof. Choose Q be from C(\mathbb{F}_p) so that T_Q(D) = Q \cdot D does not contain the point (-1,0). (Since D is a proper subset of the circle such a Q exists.) Then \phi \circ T_Q , where \phi is as in Lemma 1, is also an isomorphism between the circle curve and the projective line, which maps the set D one-to-one onto the affine set S = \phi(Q \cdot D) . Under this isomorphism the space of polynomials \mathcal{L}_N(F) is again carried over to the univariate space L_N(F) as described by Equation (4). Overall, the map which takes a word w from F^D to the word (1+t^2)^{N/2} \cdot (w \circ (\phi \circ T_Q)^{-1}) over S is the claimed isomorphism between the linear codes. \square

In the application of circle STARKs, we will consider purely two-adic N=2^n, n \geq 1 , and encoding will be done by FFT-based extrapolation, extending the set of values given over a standard position coset of size N (or more generally, a twin-coset), to those over the evaluation domain D, a union of other twin-cosets. Since the dimension of the code is N+1, such an encoder necessarily addresses only a subspace of the entire code, having codimension one. This dimension gap is the most notable difference to both the classical univariate as well as the elliptic curve case. Luckily, it turns out that this tiny gap is "tame" and will lead to only a few changes in the way computations are done, with no significant impact to both soundness and performance.

3.3 Vanishing polynomials and quotients

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

shows that vanishing polynomials do exist. With respect to the degree bound of \mathcal{L}_N , vanishing polynomials are essentially unique, as shown by the following lemma.

Proof. The statements are an immediate consequence of Proposition 2 saying that every non-zero f \in \mathcal{L}_N(\mathbb{F}_p) has at most N zeros. Thus any non-zero v \in \mathcal{V} must be non-zero outside D. Second, if v and v' are non-zero polynomials from \mathcal{V}(D) , take a point P \in C(\mathbb{F}_p) outside D and \lambda \in \mathbb{F}_p so that v' - \lambda \cdot v vanishes also at P. Again, by the number of zeros v' - \lambda \cdot v must be throughout zero over the circle curve.

Remark 8. We point out that Lemma 4 does not hold for odd set sizes N, since \mathbb{F}_p -rational vanishing polynomials of odd degree do not exist. In the context of single-point quotients as needed in the DEEP algebraic linking step of the STARK, we will work around this issue by moving to the complex extension. See Proposition 4 below.

We are mostly interested in vanishing polynomials of FFT domains, which are standard position cosets, or more generally twin-cosets. Given a twin-coset D = Q \cdot G_{n-1} \cup Q^{-1} \cdot G_{n-1} , where n \geq 1 , we know from Lemma 3 that its image under the power map \pi^{n-1} is a twin-coset of size two, and thus of the form \pi^{n-1}(D) = \{(x_D, \pm y_D)\} . We therefore may take

v_D(x,y) := v_n(x,y) - x_D, (7)

with

v_n(x,y) := \pi_x \circ \pi^{n-1}(x,y), (8)

where \pi_x is the projection onto the x-axis, as vanishing polynomial of D.

Note that since \pi commutes with J, the x-coordinate of \pi^{n-1}(x,y) does not depend on y, and both v_n and v_D polynomials are from \mathbb{F}_p[x] ,

v_D(x,y) = v_D(x) \in \mathbb{F}_p[x]^{\leq N/2}, (10)

^&lt;sup>4By non-zero we mean that the polynomial is not contained in (x^2 + y^2 - 1) .

since their degree is equal to 2 ⁿ−¹ = N/2. By construction v^D evaluates to zero over D. We shall call it the vanishing polynomial of D. Notice that whenever D is a standard position coset, its image π n−1 (D) is again a standard position coset and thus x^D = 0. In this case the vanishing polynomial v^D is vⁿ itself. The vanishing polynomial v^D can be evaluated succinctly, i.e. by only O(n) field operations: Keeping track of the x-coordinates only, each application of the squaring map costs 1 multiplication and 2 additions. The first few polynomials are

It follows directly from the defining Equation \(7\) and \(8\) that the vanishing polynomial of a twin-coset D of size 2 ⁿ is invariant under both Gn−¹ and the involution J. In the particular case of (standard position) cosets, vanishing polynomials do alternate under the action of Gn.

Proof. Observe that under π n−1 the subgroup Gⁿ is mapped onto the two-element subgroup G¹ = {(±1, 0)}, and a generator P of Gⁿ is mapped onto the generator (−1, 0) of G1. Thus

since π^x changes the sign under rotation by (−1, 0).

Remark 9. The alternating behaviour naturally extends to vanishing polynomials of arbitrary rotations of standard position cosets.

We eventually show the existence of domain quotient polynomials.

Proposition 3 (Domain quotients). Let D be a subset of C(Fp) of even size N, where 2 ≤ N < p+ 1. Take F any extension field of Fp, and any even integer M, N ≤ M < p + 1. Then every polynomial f ∈ LM(F) which vanishes over D is of the form f = q · v with q from LM−^N (F) and v from V(D).

Proof. The property follows from the univariate representation \(4\) of the function spaces as used in the proof of Proposition 2. In univariate coordinates, the polynomial v(t) ∈ L^N (F) is a rational function with simple zeros over D, poles at ±i of order N/2 each, and no other zeros and poles in the algebraic closure K of Fp. Likewise, f has only poles at ±i at order at most M/2 each, and no other poles in K. Altogether, the pole set of the univariate quotient q(t) = ^f(t)/^vD(t) is contained in ±i, each of order at most M/2 − N/2. This shows that q(t) ∈ LM−^N (F), and so its bivariate representation is contained in LM−^N (F).

For the single-point quotients as needed in the context of DEEP algebraic linking, we move over to Fp(i) rational polynomials. (However, we stress the fact that there are alternative and equally efficient approaches, see Remark 20.) As building block we take the linear function

and

for an arbitrary F-rational affine point P = (Px, Py) on the circle curve. (This function has only one zero on the curve over F, a simple zero at P, and only one pole, a simple pole at ∞¯ .)

Proposition 4 (DEEP quotients). Let F be an extension field of \mathbb{F}_p , and take an even N < (p+1). Then for every f \in \mathcal{L}_N(F) , and every F-rational point P = (P_x, P_y) on the circle curve, the single-point quotient q = (f - f(P))/v_P , with v_P as defined above, is in \mathcal{L}_N(F(i)) . Consequently both "real" and "imaginary" parts in the decomposition into F-rational functions

where in the case F(i) = F we take \operatorname{Re}\left(\frac{f - f(P)}{v_P}\right) := \frac{f - f(P)}{v_P} and \operatorname{Im}\left(\frac{f - f(P)}{v_P}\right) := 0 , are polynomials from \mathcal{L}_N(F) .

Proof. The proof goes along the lines of that of Proposition 3, with the difference that by definition the univariate representation v_P(t) = c \cdot (t-t_P)/(t+i) has a simple zero at the univariate parameter t_P of P, and a simple pole at -i corresponding to \bar{\infty} . (In the case that P = (-1,0), we have v_P(t) = c \cdot 1/(t+i) , which has a simple zero at t_P = \infty .) It has no other zeros and poles in the algebraic closure K of \mathbb{F}_p . The univariate representation of f has only poles at \pm i of order at most \frac{N}{2} each, and no other poles in K. The quotient (f(t)-f(t_P))/v_P(t) has only poles at \pm i , each of order at most \frac{N}{2} . Thus (f(t)-f(t_P))/v_P(t) is the univariate representation of a polynomial q from \mathcal{L}_N(F(i)) , satisfying that f-f(P)=q \cdot v_P over the circle curve. \square

4 The circle FFT

with Q \in C(\mathbb{F}_p) \setminus G_n , interpolates functions from F^D by polynomials from the space \mathcal{L}_N(F) , via computing the coefficients with respect to a specific basis, the FFT-basis \mathcal{B}_n of the circle, an N-dimensional basis of polynomials which only depends on the size of the domain.

Definition 4. For any integer j from the interval 0 \le j \le 2^n - 1 , let (j_0, \ldots, j_{n-1}) \in \{0, 1\}^n denote its bit representation, satisfying j = j_0 + j_1 \cdot 2 + \ldots + j_{n-1} \cdot 2^{n-1} . The FFT-basis of order n is the family \mathcal{B}_n of polynomials

where v_k(x) , 1 \le k \le n-1 , is the vanishing polynomial of the standard position coset of size 2^k defined in Section 3.3. (In cases where n is obvious from the context, we shall omit the superscript.)

Since \deg v_k(x) = 2^{k-1} the total degree of the polynomials from \mathcal{B}_n is bounded by \leq 2^{n-1} , and thus in fact \mathcal{B}_n \subseteq \mathcal{L}_N(F) . That they are linearly independent will be a consequence of the FFT itself. (See Corollary 2.)

Let us gather the main result in a single statement.

Similar to the ECFFT, the circle FFT is an non-harmonic FFT, although the group structure of the domain place a central role. Its construction is inherently related to two group endomorphisms of the circle curve, the group squaring map \pi and the inversion map J. The need for two endomorphisms, one of quadratic degree and another one which is linear, is intertwined with the goal of obtaining interpolants from a space of low-degree functions (in algebraic geometry terms, a G_n -invariant Riemann-Roch space) the dimension of which fits as tight as possible the size of the domain. Whereas in the elliptic curve case this fit is met perfectly, the circle FFT faces a tiny dimension gap between the image of the FFT and the full space of polynomials of given degree bound. By Proposition 2

and \mathcal{L}'_N(F) = \langle \mathcal{B}_n \rangle the image space of the transform, has

and thus is a subspace of \mathcal{L}_N(F) of co-dimension one. We devote an extra Section 4.3 for investigating this gap. The findings in that section will provide the necessary tools for treating it in a circle STARK.

4.1 The sequence of domains

Although everything in this section applies in full generality to twin-coset domains, we recommend to think of it as standard position cosets during a first read.

By definition, a twin-coset D = Q \cdot G_{n-1} \cup Q^{-1} \cdot G_{n-1} is invariant under the involution J, and moreover each J-orbit in D has exactly two points. Thus the quotient map

is 2-to-1. By Lemma 3, with D_n=D being a twin-coset of size 2^n , the recursively obtained images D_j=\pi(D_{j+1}) , for j=n-1 down to 1, are twin-cosets with respect to the decreasing chain of subgroups

Note that the involution J has orbits of the form \{(x, \pm y)\} , and thus we may regard the quotients S_j = D_j/J as subsets of the x-axis, and \phi_J = \pi_x as the projection onto it, as illustrated by the following diagram.

C(\mathbb{F}_p) \subseteq \mathbb{F}_p^2 \qquad D_n \xrightarrow{\pi} D_{n-1} \xrightarrow{\pi} D_{n-2} \xrightarrow{\pi} \cdots \xrightarrow{\pi} D_1

In this diagram, the squaring endomorphism \pi: S_j \longrightarrow S_{j-1} is the 2-to-1 map x \mapsto 2 \cdot x^2 - 1 . This univariate view on the quotients D_j/J will be particularly convenient in the description of the circle FFT.

4.2 The circle FFT and its inverse

as in (13), considering S_j = D_j/J as subsets of the x-axis, 1 \le j \le n .

In the first step, we decompose the given function f over D_n into "even" and "odd" part with respect to the involution J, using

t_0(x,y) = y

as our "reference odd function". (This terminology is justified by t_0 \circ J = -t_0 .) Concretely, we split f \in F^{D_n} into the unique functions f_0, f_1 \in F^{S_n} over the univariate domain S_n , defined by

and satisfying

f(x,y) = f_0(x) + y \cdot f_1(x). \tag{16}

(Note that the right hand sides of (14) and (15) do not depend on which of the two preimages of x are taken.) We then proceed with f_0 and f_1 separately and as follows.

In the other steps, we receive a function f_{k_0,...,k_{n-j}} \in F^{S_j} from a previous step, where 2 \leq j \leq n . We choose

t_1(x,y) = x

as the "reference odd function" (in the sense that it is odd along the fibres of \pi , which are parametrized by action of T(x) = -x). Overriding notation and writing again f for f_{k_0,...,k_{n-j}} , we split it into f_0 = f_{k_0,...,k_{n-j},0} and f_1 = f_{k_0,...,k_{n-j},1} from F^{S_{j-1}} over the projected domain S_{j-1} = \pi(S_j) , defined by

and hence

f(x) = f_0(\pi(x)) + x \cdot f_1(\pi(x)), \tag{19}

where \pi(x) = 2 \cdot x^2 - 1 . (The right hand sides (17) and (18) are independent on the choice \pm x from the same preimage, thus f_0 and f_1 are well-defined.) These two functions f_0 = f_{k_0,\dots,k_{n-j},0} , f_1 = f_{k_0,\dots,k_{n-j},1} are then processed separately and in the same manner, until one ends up with constant functions

over the single-point domain S_1 . The output of the algorithm are the constants c_k = f_{k_0,\dots,k_{n-1}} \in F , for each k in the interval 0 \le k \le 2^n - 1 , where (k_0,\dots,k_{n-1}) \in \{0,1\}^n are the bits of k = k_0 + k_1 \cdot 2 + \dots + k_{n-1} \cdot 2^{n-1} .

Proof. We first show, by induction on 1 \leq j \leq n , that for every function over S_j = D_j/J , the algorithm outputs its coefficients with respect to

that are those polynomials from \mathcal{B}_j , which only depend on x. For j=1, the quotient S_1 consists of a single point and the claim is trivial. Assume that the claim holds for some j \geq 1 , and let f be a function over S_{j+1} , and decompose it into f_0 , f_1 \in F^{S_j} defined by (17) and (18) such that (19) holds. By the induction hypothesis the algorithm outputs their coefficients with respect to the basis \mathcal{B}_j^{(0)} ,

over S_i , for both i = 0, 1. Therefore,

with c_{k'} = c_{i+2 \cdot k} = c_k^{(i)} , since by the definition of the vanishing polynomials, we have that x^i \cdot b_{2k}^{(j)}(\pi(x)) = b_{2 \cdot (i+2 \cdot k)}^{(j+1)} for i \in \{0,1\} and 0 \le k \le 2^{j-1} - 1 .

The final step, corresponding to the projection from D_n to S_n = D_n/J , is proven in the same manner, using the even-odd decomposition into (14) and (15) satisfying (16). We leave the details to the reader. \square

Remark 10. In practice one omits the factor 2 in the denominator of odd and even parts, both with respect to J and T. This scaled FFT yields the coefficients with respect to the scaled basis \frac{1}{2^n} \cdot b_k , 0 \le k < 2^n . It consumes n \cdot 2^{n-1} multiplications of elements from F with precomputed elements from the base field \mathbb{F}_p , and n \cdot 2^n additions of elements from F.

The inverse FFT is obtained along the lines of the proof of Theorem 2. At the "bottom level" of the recursion, one starts with given coefficients c_k = c_{k_0,\dots,k_{n-1}} \in F , where (k_0,\dots,k_{n-1}) \in \{0,1\}^n are the bits of k, all regarded as constant functions f_{k_0,\dots,k_{n-1}} over the single-point domain S_1 , and recursively combines their values into the ones over the domain of double the size using Equation (19) Leveraging anti-symmetry of the odd parts along the fibers of the projection, each level of the tree consumes in total 2^n additions, but only the half number of multiplications. We leave the details to the reader, and only cite the following theorem.

Remark 11. The cost of the inverse FFT is the same as for the scaled FFT described in Remark 10: It consumes n \cdot 2^{n-1} multiplications of elements from F with (precomputed) elements from \mathbb{F}_p , and n \cdot 2^n additions of elements from F.

As the Cooley-Tukey FFT, both the circle FFT and its inverse can be implemented as a butterfly network, with a similar layout as in a classical FFT. An explicit description is given in Appendix D.

Let us discuss an immediate consquence of Theorem 2.

Corollary 2 (FFT basis). Under the assumption of Theorem 2, the polynomials from \mathcal{B}_n (Definition 4) form the basis of an N-dimensional subspace \mathcal{L}'_N(F) of \mathcal{L}_N(F) , where N=2^n .

Proof. We have already seen that total degree of each b_k(x,y) = y^{k_0} \cdot v_1(x)^{k_1} \cdot \dots \cdot v_{n-1}(x)^{k_{n-1}} , 0 \le k \le 2^n - 1 , is bounded by 2^{n-1} . By Theorem 2 their values over D form a basis of F^D , where D is a twin-coset of size 2^n , proving that their span is at least N-dimensional. Since there are only N such polynomials, the dimension is thus equal to N.

We call the image space \mathcal{L}'_N(F) spanned by the basis \mathcal{B}_n the FFT-space of order n, or of dimension N=2^n . Its description with respect to the standard monomial basis is as follows.

Lemma 6. Let p be a CFFT-friendly prime supporting the domain size N = 2^n , n \ge 1 , and F be a finite extension field of \mathbb{F}_p . Then

\mathcal{L}'_{N}(F) = \left\{ p_{0}(x) + y \cdot p_{1}(x) : p_{i}(x) \in F[x], \deg p_{i}(x) \le \frac{N}{2} - 1, \ i = 0, 1 \right\}. (20)

Proof. By the definition of b_k , each function from \mathcal{L}'_N(F) is of the claimed form p_0(x) + y \cdot p_1(x) with \deg p_i \leq \frac{N}{2} - 1 . In particular, \mathcal{L}'_N(F) is contained in the span of the N monomials 1, x, \ldots, x^{\frac{N}{2}-1} and y, y \cdot x, \ldots, y \cdot x^{\frac{N}{2}-1} . Since \mathcal{L}'_N(F) is N-dimensional, the span of the monomials cannot be larger than \mathcal{L}'_N(F) , proving the claim of the lemma.

Recall that dim \mathcal{L}_N(F) = N+1 and thus the FFT space \mathcal{L}'_N(F) is a subspace of \mathcal{L}_N(F) with co-dimension one. In terms of the monomial basis, \mathcal{L}_N(F) misses the highest order monomial in x, i.e.

Since vanishing polynomial v_n(x) is of degree \deg v_n(x) = N/2 , we may also decompose the full space of polynomials as

which turns out the more useful view for our purposes. See Section 4.3 for details on this decomposition.

Remark 13. In univariate coordinates the involution is expressed as J(t) = -t, the doubling map is \pi(t) = \frac{2 \cdot t}{1 - t^2} , and the generator T of its kernel group (i.e. the translation by (-1,0)) is T(t) = -\frac{1}{t} . Twincosets are carried over to twin-cosets with respect to group law of the projective line (cf. Remark 4), invariant under J and without fixed points. The FFT basis with respect to such a coset D of size N = 2^n is now composed from the twiddles

t_0 = \frac{2 \cdot t}{1 + t^2} and t_1 = \frac{1 - t^2}{1 + t^2} ,

yielding a basis of an N-dimensional subspace L'_N(F) of the univariate Riemann-Roch space L_N(F) = F[t]^{\leq N}/(1+t^2)^{N/2} .

4.3 Properties of the FFT space

As before, p is a CFFT-friendly prime supporting the order n \ge 1 , and N = 2^n . In this section we shall investigate the decomposition

and provide a characterization of \mathcal{L}'_N(F) in terms of its behaviour at infinity which will be useful for the analysis of the various quotients involved in the IOP of the circle STARK.

The most remarkable property is that, although the circle FFT is a non-harmonic transform, the FFT space is invariant under rotation.

Proposition 5. The FFT space \mathcal{L}'_N(F) is invariant under the action of G_n , the cyclic subgroup of order N=2^n .

Proof. Recall that by Lemma 6, \mathcal{L}'_N(F) is the span of the monomials 1, x, \ldots, x^{N/2-1} and y, y \cdot x, \ldots, y \cdot x^{N/2-1} . Consider following vanishing polynomial of G = G_n the cyclic subgroup of order 2^n ,

where x_k runs through the x-coordinates of half of the powers P^k of a generator P of G_n , except the two outermost ones on the x-axis. By the degree in x, the polynomial v_G belongs to \mathcal{L}'_N(F) , and its only term of maximum degree, belonging to y \cdot x^{\frac{N}{2}-1} , is non-zero. Hence v_G is linearly independent from the monomials of lower total degree, altogether forming a basis of \mathcal{L}'_N(F) ,

By degree, a rotation of a monomial of degree < N/2 is again of degree < N/2, and by Remark 9, v \circ T_P is a scalar multiple of v. This proves the claim of the lemma.

Proposition 5 together with Lemma 5 shows that \mathcal{L}_N(F) = \mathcal{L}'_N(F) + \langle v_n \rangle is a decomposition into G_n -invariant subspaces (which moreover are J-invariant). The following orthogonality result will be useful for determining the decomposition of polynomials from \mathcal{L}_N(F) .

Lemma 7. Over every G_n -invariant and J-invariant domain D \subseteq C(\mathbb{F}_p) , the vanishing polynomial v_n is orthogonal to the FFT space \mathcal{L}'_N(F) , i.e.

for every f from \mathcal{L}'_{N}(F) , where the inner product is taken over D.

Proof. We keep track of the inner product \langle v_n, f \rangle_D while repeatedly decomposing f into even and odd parts as in the FFT. In the first step, we write f = f_0(x) + y \cdot f_1(x) , where f_0 , f_1 are polynomials of degree \leq N/2 - 1 . By the discussion preceding Lemma 5 the vanishing polynomial v_n is invariant under the involution J, thus

as the product y \cdot f_1(x) \cdot v_n(x) alternates under J, and hence its sum over D vanishes. (Note that this holds also if D includes fixed points of J, since there y = 0.)

In the next step we decompose f_0 = (f_{0,0} \circ \pi) + x \cdot (f_{0,1} \circ \pi) with f_{0,0} , f_{0,1} being polynomials of degree \leq N/4 - 1 . If n \geq 2 , then v_n = v_{n-1} \circ \pi , and thus

since x \cdot (f_{0,1} \circ \pi) \cdot (v_{n-1} \circ \pi) alternates under the action of T = T_{(-1,0)} and thus its sum over D is zero. The latter inner product can be written as one over the projected domain \pi(D) ,

thereby reducing the orthogonality claim to that of v_{n-1} with the polynomial f_{0,0} of degree \leq N/4-1 , over the G_{n-1} -invariant domain \pi(D) .

Continuing in this manner, we eventually end up with an inner product of the vanishing polynomial v_1 with the constant function f_{0,\dots,0} , taken over the G_1 -invariant set \pi^{n-1}(D) . As v_1 alternates under G_1 , that inner product must be zero, proving the claim of the Lemma.

Let us investigate the behaviour of polynomials from \mathcal{L}_N(F) at infinity. For that we consider the limits of their quotients with the monomial x^{N/2} at the two \mathbb{F}_p(i) -rational points at infinity, i.e. \infty = (1:+i:0) and \bar{\infty} = (1:-i:0) . However, in order to avoid explicitly referring to these projective points, we use the following formula as definition for these limits. Given a polynomial f in \mathcal{L}_N(F) , we set

and

where f^{(N/2)} is the homogeneous part of degree N/2. These limits pick out the coefficients of the two terms of degree N/2, and combines their coefficients by taking (x,y) = (1,i) and (x,y) = (1,-i), respectively. Their value is in F(i), which depending on F might be an extension, or not.

Lemma 8. Take f \in \mathcal{L}'_N(F) , and let c_{N-1} \in F be its coefficient with respect to the highest-order basis function b_{N-1} of the FFT basis. Then

\frac{f}{x^{N/2}}(\bar{\infty}) = -\frac{f}{x^{N/2}}(\infty) = -i \cdot \frac{2^{\frac{N}{2}}}{N} \cdot c_{N-1}. (23)

On the other hand, the vanishing polynomial v_n of the standard position coset of size N=2^n , satisfies

and the same limits hold for the vanishing polynomial of a twin-coset of size N.

Proof. The coefficient c = c_{N-1} of a polynomial f \in \mathcal{L}'_N(F) belongs to the basis function b_{N-1}(x,y) = y \cdot v_1(x) \cdot v_2(x) \cdot \ldots \cdot v_{n-1}(x) , which is the only basis function with a term of total degree equal to N/2. Concretely,

where p(x) is a polynomial of degree < N/2 - 1. Evaluating the quotient with x^{N/2} at \infty = (1:i:0) and \bar{\infty} = (1:-i:0) yields Equation (23). The limits of the vanishing polynomial are proven similarly, using that

for some polynomial p(x) of degree \deg p(x) \leq N/2 - 1 .

Remark 14. As circle STARKs typically use transitional constraints, the explicit limit of a function under rotation is useful. For arbitrary g from the full space of polynomials \mathcal{L}_N(F) , and P = (P_x, P_y) \in C(\mathbb{F}_p) , we have

and likewise at \bar{\infty} , with i replaced by -i. These limits are a consequence of that \infty and \bar{\infty} are fixed points under T_P , and the monomial h(x,y) = x^{N/2} satisfies that

\frac{h}{h \circ T_P^{-1}} = \frac{x^{N/2}}{(P_x \cdot x + P_y \cdot y)^{N/2}},

which evaluates to (P_x + i \cdot P_y)^{-N/2} at \infty , and to the conjugate expression at \bar{\infty} . In particular if P is a generator of G_n the cyclic subgroup of order N, then (P_x + i \cdot P_y)^{-N/2} = -1 , which together with Proposition 6 from below yields an alternative proof of rotation invariance of \mathcal{L}'_N(F) .

Motivated by Lemma 8 we define the linear subspaces

and

\mathcal{L}_{N}^{+}(F) = \left\{ f \in \mathcal{L}_{N}(F) : \frac{f}{x^{N/2}}(\infty) = +\frac{f}{x^{N/2}}(\bar{\infty}) \right\}. (27)

These are the spaces of polynomials having alternating or non-alternating limits at infinity, both with respect to the action of the involution J on \{\infty, \bar{\infty}\} .

Lemma 9. Suppose that N, M \geq 2 are even integers. If f \in \mathcal{L}_N^-(F) and g \in \mathcal{L}_M^+(F) , or vice-versa, then f \cdot g \in \mathcal{L}_{N+M}^-(F) . For all other combinations of f and g, having either alternating or non-alternating limits at infinity, their product f \cdot g \in \mathcal{L}_{N+M}^+(F) .

Proof. The claim follows from the degree of the product, and that it has alternating limits at infinity if and only if exactly one of the two functions has alternating limits at infinity. \Box

Proposition 6. The FFT space is characterized by having alternating limits at infinity, \mathcal{L}_N^-(F) = \mathcal{L}_N'(F) .

Proof. Write g \in \mathcal{L}_N(F) as g = f + \lambda \cdot v_n , with f \in \mathcal{L}'_N(F) and v_n the vanishing polynomial of a standard position coset of size N, and \lambda \in F . By Lemma 8 f \in \mathcal{L}_N^-(F) and v_n \in \mathcal{L}_N^+(F) , and we obtain that

which is zero if and only if \lambda = 0 , or equivalently g \in \mathcal{L}'_N(F) .

5 STARK over the circle

Circle STARKs are similar to univariate STARKs, with the only difference that the underlying algebraic function space is the space of bivariate polynomials over the circle curve, i.e. \mathbb{F}_p[x,y]/(x^2+y^2-1) , rather than univariate polynomials over the "line". Circle STARKs address arithmetic circuits over prime fields \mathbb{F}_p where (p-1) is not acceptably smooth but (p+1) is, meaning that it is CFFT-friendly (recall Definition 1) for sufficiently large order. Witness data is encoded into bivariate polynomials, by means of the circle FFT from Section 4, and constraint satisfaction is carried over to algebraic relations imposed on these polynomials. The interactive oracle proof is essentially the same as in the univariate case, with just a

few changes which are related to the dimension gap between the output space of the circle FFT and the full space of polynomials. For the sake of simplicity we restrict our exposition to algebraic intermediate representations (AIR) with constraints between neighbouring rows only. Generalizations like arbitrary row offset, non-periodic constraints, permutation and lookup arguments are done in the usual manner, and are shortly discussed in Section 5.4. The protocol of the STARK is described in an informal style, but this does not mean that we neglect rigor. A formal treatment, including a fully-fledged security analysis is moved to Appendix B.

Let p be CFFT-friendly prime, supporting sufficiently large orders so that each of the domains below are supported by p. In circle STARK, the trace\ domain is the standard position coset

of a cyclic and proper subgroup G = G_n of the circle curve C(\mathbb{F}_p) , of size N = 2^n , with n \ge 1 , and the trace is organised column-wise t_1, \ldots, t_w \in \mathbb{F}_p^N , each placed over the domain H in the usual manner, using the group translation T by a generator of G for the timeline. The trace columns are interpolated by polynomials

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

P_i(s_i, p_1, \dots, p_w, p_1 \circ T, \dots, p_w \circ T) = 0, (28)

for i = 1, ..., C, holding over the entire domain H, and where s_i \in \mathcal{L}_N(\mathbb{F}_p) is a predefined selector polynomial. Each constraint is a polynomial

of total degree ^5 at most the maximum number of twin-cosets of size N.

and the degree in the selector variable S is at most \deg_S P_i \leq 1 . Algebraic intermediate representations allow for periodic constraints only, meaning that each constraint C_i is enforced on a subdomain H_i \subseteq H , a coset of a subgroup of G, with optionally one point removed for boundary conditions, and will be described in detail in Section 5.1. Their selector polynomials s_i \in \mathcal{L}_N(\mathbb{F}_p) are built from domain vanishing polynomials and are succinctly evaluable. (It turns out that these are again from the FFT space \mathcal{L}'_N(\mathbb{F}_p) .) Consequently there is no need to provide and verify them in a precomputation phase.

The polynomials p_1, \ldots, p_w , as well as further ones provided in the course of the protocol, are committed by their values over a larger evaluation domain D \subseteq C(\mathbb{F}_p) , a standard position coset of at least double the size of H. In other words, the prover commits to code words of the circle code C_N(D) with values in the prime field \mathbb{F}_p , or some finite extension F of it. Being again in standard position, D is disjoint from H, and we assume that

for some B \geq 1 . The degree of the algebraic intermediate representation is

5.1 Constraint selectors

Let us discuss the selector polynomials for subdomains H' \subset H , which are an arbitrary position coset of a proper subgroup G' \subset G , the group of the trace domain H. Recall the definition of \mathcal{V}(S) of any even-sized set S, as given in Lemma 4.

Lemma 10. Let H be a standard position coset of size N=2^n and H' \subset H an arbitrary position coset of a subgroup G' of size N'=2^{n'} , where 1 \leq n' < n . Then for any two non-zero v_H \in \mathcal{V}(H) , v_{H'} \in \mathcal{V}(H') the quotient

is a polynomial from \mathcal{V}(H \setminus H') which alternates under the action of G'. In particular, since \mathcal{V}(H \setminus H') \subseteq \mathcal{L}_{N-N'}(\mathbb{F}_p) the polynomial s_{H'} belongs to the FFT space \mathcal{L}'_N(\mathbb{F}_p) .

Proof. Proposition 3 already implies that the quotient s_{H'} is equal to a polynomial q from \mathcal{L}_{N-N'}(\mathbb{F}_p) satisfying v_H = q \cdot v_{H'} over the circle curve. Since v_H is a non-zero polynomial, so must be q. By Lemma 4 v_{H'} is non-zero outside H', hence every point from H \setminus H' is a zero of q. This shows that q \in \mathcal{V}(H \setminus H') and thus is throughout non-zero outside H \setminus H' .

To see the alternating behaviour under G', let P' be a generator of G'. Since n' < n, that generator is an even power of a generator of G, and hence by Lemma 5 the vanishing polynomial v_H is invariant under P'. For the vanishing polynomial of H' itself, we have alternating behaviour under T_{P'} , i.e. v_{H'} \circ T_{P'} = -v_{H'} . (Cf. Remark 9.) Therefore s_{H'} \circ T_{P'} = -s_{H'} on its set of definition C(\mathbb{F}_p) \setminus H' , in other words

for every P \in C(\mathbb{F}_p) \setminus H' . Since q \circ T_{P'} + q \in \mathcal{L}_{N-N'}(\mathbb{F}_p) and there are more than N points outside H', Proposition 2 yields that q \circ T_{P'} + q = 0 everywhere on the circle curve, proving the claimed alternating behaviour of q.

Remark 15. By their degree, domain selectors have trivial limits at infinity,

If one takes v_n as the vanishing polynomial of H and a suitable rotation v_{H'} = v_m \circ T_Q^{-1} , m = n', as vanishing polynomial of H', then one can show that the concrete value for P = (P_x, P_y) \in H' is

where v_n' and v_m' are the (formal) derivatives of v_n and v_m . That is, v_1'(x) = 1 , and for k \geq 2 , we have v_k'(x) = 4^{k-1} \cdot \prod_{j=1}^{k-1} v_j(x) .

As DEEP quotients, selectors of singleton domains need a separate treatment.

Lemma 11. Let H be a standard position coset of size N=2^n , and P be an arbitrary point from H. Taking v_0(x,y)=\frac{y}{1+x} , the quotient

is a polynomial from \mathcal{L}_N(\mathbb{F}_p) , which has a non-zero value at P and is zero elsewhere on H. Furthermore, s_P is contained in the FFT-space \mathcal{L}'_N(\mathbb{F}_p) .

Proof. In univariate coordinates v_n(t) \in L_N(\mathbb{F}_p) has throughout simple zeros, in particular at t_P corresponding to the point P \in H . The reference function v_0 translates to v_0(t) = t , which has a simple zero at t = 0 and a simple pole at infinity. Its rotation v_0 \circ T_P^{-1} thus has a simple zero at t_P and a simple pole at -1/t_P . Altogether, we conclude that the quotient v_H(t)/v(t) \in L_N(\mathbb{F}_p) and it has a non-zero value at t_P . This proves the first assertion.

To see that s_P belongs to the FFT space, we investigate its limit with respect to x^{N/2} at infinity. Consider

By Lemma 8 the vanishing polynomial v_n belongs to \mathcal{L}_N^+(\mathbb{F}_p) , whereas v_0(\infty) = -v_0(\bar{\infty}) which by Remark 14 also holds for the rotated function v_P . Therefore s_P \in \mathcal{L}_N^-(\mathbb{F}_p) , which by Proposition 6 is the FFT space.

Remark 16. It follows from the proof of Lemma 11 that

which by Lemma 8 is non-zero. It can be shown that the concrete value at P = (P_x, P_y) is

with v'_n as the derivative of v_n as described in Remark 15, and the statement of Lemma 11 extends to twin-coset domains H with vanishing function v_H = v_n - x_H . The normalized single-point quotient

is the "Lagrangian" for the FFT space \mathcal{L}'_N(F) and may be taken for evaluating any f \in \mathcal{L}'_N(F) at arbitrary outside points Q via the inner product formula

f(Q) = \langle f(P), \ell_P(Q) \rangle_{P \subset H} .

With precomputed normalizing factors⁶, the values of \ell_P(Q) for P \in H can be computed efficiently by decomposing the twin-coset H into twin-cosets of size four, over each of which the same four products Q_x \cdot P_x , Q_y \cdot P_x , Q_x \cdot P_y , Q_y \cdot P_y are involved in the formula for Q \cdot P^{-1} , and taking Montgomery batch inversion for the values of 1/v_0 over Q \cdot H .

Remark 17. In an optimization of the circle STARK, discussed in Remark 22, the selector polynomial of a punctuated domain H' = H \setminus \{P\} , with P = (P_x, P_y) \in H , is taken as the tangent functional at P instead,

That selector polynomial has a zero of multiplicity 2 at P, and no other zeroes on the circle. In the particular case that P = (1, 0), the functional is contained in the space \mathcal{L}_2^+(\mathbb{F}_p) defined in Section 4.3

5.2 The interactive oracle proof for AIR

The interactive oracle proof for the satisfiability of the AIR, i.e. the existence of low-degree polynomials p_1, \ldots, p_w \in \mathbb{F}_p[X,Y]/(X^2+Y^2-1) which satisfy each of the constraints (28) over the trace domain H, i=1,\ldots,C , goes as follows.

^&lt;sup>6By the invariance of v_n under G_{n-1} and J, the alternating behaviour of v_0 under J, and J \circ T_P = T_{P^{-1}} \circ J , the normalizing factors are invariant under G_{n-1} and alternate under J.

In the first round, the prover computes the values of its trace polynomials p1, . . . p^w ∈ L^N (Fp) over the evaluation domain D using its decomposition into twin-cosets from Lemma 2, and shares their oracles, denoted by

with the verifier. (That is, it gives the verifier access to the oracles.)

In the second round the verifier sends a random challenge β ←\$ F, drawn uniformly from a suitably large extension field F of Fp, which is used to reduce the C domain identities into a single one,

to hold over the trace domain H. (The soundness error of this step is a usual, and depends on the size of the extension field F and C.) In order to prove this identity, the prover uses Proposition 3 and computes the quotient polynomial q ∈ L(d−1)·^N (F) subject to the overall identity

\sum_{i=1}^{C} \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, (29)

q = \lambda \cdot v_{\bar{H}} + \sum_{k=1}^{d-1} \frac{v_{\bar{H}}}{v_{H_k}} \cdot q_k. \tag{30}

This extra parameter λ attributes the aforementioned dimension gap, and is the main difference to the classical univariate as well as the elliptic curve case. We will describe the details of the decomposition, and how to compute it, in Section 5.3 below. The prover sets up the oracles

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

Having all the oracles in place, the next step is the DEEP algebraic linking, which reduces satisfiability of the overall identity \(29\) to a low-degree test on single-point quotients. (In lose terms, this step turns the low-degree test into a polynomial commitment scheme.) The verifier responds with a random point

from the circle curve over the extension field F, which is the DEEP query at which the overall identity \(29\) is checked. In return, the prover claims the values vi,0, vi,¹ of pⁱ at the points γ and T(γ) respectively, for each i = 1, . . . , w, as well as the values v1, . . . , vd−¹ of q1, . . . , qd−¹ at γ. Eventually, both prover and verifier then engage in a low-degree test for the real and imaginary parts of the DEEP quotients defined in Proposition 4,

for each i = 1, . . . , w, and

which is a joint proximity test to the circle code C^N (F, D). The proximity test is explained in Section 6. If the proximity test passes, and if the claimed values satisfy the overall identity \(29\) at γ, using \(30\), and computing the values of the selectors si(γ) by itself, then the verifier accepts.

Remark 18. Taking real and imaginary parts reduces the low degree test for F(i)-rational functions to a low-degree test for F-rational functions, and is done to avoid larger fields than demanded by soundness. Although this doubles the number of functions subject to the test, we shall see that it does not cause significant computational overhead, for both the prover and the verifier. (Cf. Remark 23.)

The formal treatment of the protocol, including a clarification of security notions is given in Appendix B. We simply state its soundness error in the (ordinary) oracle model.

Theorem (Summary of Theorem 7 and 8, Appendix B). Let n, w, C, d, B \ge 1 , and let p be a CFFT-friendly prime supporting the order n+B, and so that d \cdot 2^n < p+1 , and select F any finite extension of \mathbb{F}_p . Consider the simple AIR from above, with trace length N=2^n and w columns, subject to the given C constraints of maximum degree d. Then the above described interactive oracle proof for the satisfiability of the AIR has soundness and knowledge-soundness error

Remark 19. The above IOP follows the common design principle being a chain of probabilistic reductions, and hence the proofs in Appendix B elaborate the soundness errors of the separate protocol rounds. By means of the [BSCS16] transform, the interactive oracle proof can be turned into a SNARK in the random oracle model. We postpone an explicit treatment, similar to that in the most recent update of [Sta23], to a future version of the paper.

Theorem 7 asserts that, if a (possibly computationally unbounded) algorithm P^ succeeds the verifier with a probability larger than \varepsilon_{AIR} , then there exist low-degree polynomials p_1,\ldots,p_w\in\mathbb{F}_p[X,Y]/(X^2+Y^2-1) which satisfy each of the C constraints (28) over the trace domain H. Furthermore, P^ can be turned into an algorithm which extracts such a solution, and which has comparable running-time: Once sampled a first round message [f_1],\ldots,[f_w] on which P^* is able to succeed with that probability, then this solution is one of the at most \ell^+ many collections of degree \leq N/2+1 polynomials, which jointly agree with f_1,\ldots,f_w over a set A\subseteq D of density \geq \alpha . The at most \ell^+ many candidate collections are obtained by the Guruswami-Sudan list decoder over a suitable finite extension of \mathbb{F}_p . See Appendix B for details.

Let us quickly explain the ingredients of Equation (47) to the advanced reader. The part in the brackets is the soundness error of the protocol in the polynomial oracle model. Its first term is subject to the batching step of the C constraints, which amounts to zero-testing an ordinary univariate polynomial of degree C-1 over the extension field F. The second term is the soundness error bound of the DEEP algebraic linking step, which is a zero test for a polynomial from \mathcal{L}_{d\cdot(N+2)}(F) at a random point \gamma \in C(F) \setminus D . The slightly increased degree bound in \mathcal{L}_{d\cdot(N+2)}(F) attributes the step of passing from DEEP quotients to the non-quotients, which is also responsible for the slightly different list size bound \ell^+ .

Remark 20. As in the construction of singleton selectors (Lemma 11) one may alternatively choose the rational function

where v_0(x,y) = y/(1+x) , for DEEP quotients. These quotients stay in the field F, but to assure that the non-quotients have no (affine) pole, one needs to run the low-degree test on both the quotients and the non-quotients. This approach leads again to a batch of double the size and hence comparable computational cost. Without proof we state that the soundness error of this variant is the same as in Theorem 7.

5.3 Computing the overall quotient

The quotient q \in \mathcal{L}_{(d-1)\cdot N}(F) is computed by value from those of f_1, \ldots, f_w over a union of twin-cosets H_k of size N,

for some c_k \in \mathbb{F}_p .

Lemma 12 (Decomposition Lemma). Consider disjoint twin-cosets H_k , k = 1, ..., d-1, of size N = 2^n , and take v_{\bar{H}} = \prod_{k=1}^{d-1} v_{H_k} as a vanishing polynomial of the union \bar{H} = \bigcup_{k=1}^{d-1} H_k . Then every q \in \mathcal{L}_{(d-1) \cdot N}(F) is uniquely decomposed into

q = \lambda \cdot v_{\bar{H}} + \sum_{k=1}^{d-1} \frac{v_{\bar{H}}}{v_{H_k}} \cdot q_k, \tag{31}

with \lambda \in F and q_k \in \mathcal{L}'_N(F) , for each k = 1, \dots, d-1 .

Remark 21. Recall that by Lemma 5, and the discussion preceding it, the selector \frac{v_{\bar{H}}}{v_{H_k}} = \prod_{j \neq k} v_{H_j} is invariant under J and G_{n-1} , and hence constant over twin-cosets of size N. In practice one chooses a normalized variant of the selector, which evaluates to 1 over H_k . With such a choice no extra multiplications are needed to obtain the values of q_k over H_k from those of q.

To uniquely determine q we additionally consider its limit at infinity, as introduced in Section 4.3. This leads to a limit-at-infinity calculus for deriving the scalar \lambda in the decomposition (31). Dividing the overall identity (29) by the monomial of maximum degree, i.e. x^{d \cdot N/2} where d is the degree of the algebraic intermediate representation, we get

and evaluating it at \infty yields

\sum_{i=1}^{L} \beta^{i-1} \cdot P_i^{(d)} \left( \frac{s_i}{x^{N/2}}(\infty), \frac{p_1}{x^{N/2}}(\infty), \dots, \frac{p_w}{x^{N/2}}(\infty), \frac{p_1 \circ T}{x^{N/2}}(\infty), \dots, \frac{p_w \circ T}{x^{N/2}}(\infty) \right) \\ = \left( \lambda \cdot \prod_{k=1}^{d-1} \frac{v_{H_k}}{x^{N/2}}(\infty) + \sum_{k=1}^{d-1} \frac{q_k}{x^{N/2}}(\infty) \cdot \prod_{j \neq k} \frac{v_{H_j}}{x^{N/2}}(\infty) \right) \cdot \frac{v_H}{x^{N/2}}(\infty), \tag{32}

and likewise at \bar{\infty} , where P_i^{(d)} denotes the homogeneous part of degree d of the constraint P_i . Using Lemma 8 the values at \infty are easily determined:

• The values of \frac{v_H}{x^{N/2}}(\infty) , \frac{v_H}{x^{N/2\cdot(d-1)}}(\infty) and \frac{s_i}{x^{N/2}}(\infty) , are determined using Lemma 8 and Remark 15 and 16, and may be precomputed. Since \frac{s_i}{h}(\infty) = 0 whenever the constraint selection domain H_i is a proper non-singleton subgroup of H, we only need to take into account those terms of degree d, which correspond to global or single-point constraints.
• The values \frac{p_i}{h}(\infty) , i=1,\ldots,w , as well as \frac{q_k}{h}(\infty) , k=1,\ldots,d-1 , are computed from the highest-order coefficients of their Fourier transforms using Lemma 8. (Recall that the transform of q_k is needed anyway to compute its values over the entire evaluation domain D.)
• The values \frac{p_i \circ T}{x^{N/2}}(\infty) , 1 \le i \le M , are also determined from the limits of the non-rotated functions using Equation 25. In particular, since T = T_P for a generator P of the subgroup G, we have that

and the same holds at \bar{\infty} .

Since \frac{v_H}{x^{N/2}}(\infty) and \frac{v_{\bar{H}}}{x^{(d-1)\cdot N/2}}(\infty) \neq 0 we can always extract \lambda from (32).

A closer inspection of the overall identity at infinity shows that the limit-at-infinity calculus can be simplified or even omitted. The polynomials s_i, p_i, p_i \circ T belong to the FFT space \mathcal{L}'_N(\mathbb{F}_p) and hence have alternating limits at infinity,

whereas the vanishing polynomial v_H belongs to \mathcal{L}_N^+(F) . Since the limits of q at infinity are only determined by the terms of order d, we obtain that

(A product of an odd number of polynomials which are odd at infinity is again odd at infinity, and likewise a product of an even number of such polynomials is even at infinity.) On the other hand, each v_{H_k} belongs to \mathcal{L}_N^+(F) (they are polynomials in x only) and every q_k \in \mathcal{L}_N^-(F) (as they belong to \mathcal{L}_N'(F) , showing that in the decomposition

the term belonging to \lambda is from \mathcal{L}^+_{(d-1)\cdot N}(F) , whereas the sum involving the q_k belongs to \mathcal{L}^-_{(d-1)\cdot N}(F) . Since F^{\{\infty,\infty\}} is a direct sum of the space of odd and even functions (under the action of J), and since the limits of \prod_{k=1}^{d-1} v_{H_j} are non-zero, we conclude that in the case d is odd we must have \lambda = 0 , and in the case d is even, it holds that

Therefore, if d is odd one can omit the limit-at-infinity calculus. In the other case when d is even, no limits of q^k are needed.

Remark 22. The quotient decomposition and the limit-at-infinity calculus extends to the case where one takes the linear tangent polynomial from Remark 17 as the selector for a punctuated domain H′ = H\{(1, 0)}. (We choose the exceptional point P = (1, 0) for simplicity. The general case follows by rotation.) In this case we may allow a constraint Pⁱ subject to H′ to be of maximum degree without selector, i.e. of total degree

where d is the degree of the AIR, at negligible extra cost for the prover. With the tangent selector belonging to L2(F), the overall quotient q is then in the slightly larger space L(d−1)·N+2(F), and can be computed from the values over the extended domain

Again, in the case d is odd, the term with respect to the vanishing polynomial of the extended domain vanishes, and in the case when d is even, no limits of the q^k are needed.

5.4 A note on generalizations

Our restrictive notion of AIR can be generalized to transitional constraints of arbitrary offset, involving arbitrary powers T ^k of the shift. The limit-at-infinity calculus from Section 5.3, and in particular its analysis how it can be simplified or dropped, remains unchanged. The same holds when moving to a "plonkish" arithmetization taking non-succinct precomputed selector polynomials which are naturally from the FFT space.

Univariate sumcheck techniques (\[BSCR+19, CHM+20] or the one that uses running sums \[HGdB21, [GK22\]](#page-32-8)) as well as the grand product argument from Plonk [\[GWC19\]](#page-32-9) can be carried over to an IOP over the circle curve, with a negligible change of the soundness error. The same is true for lookup arguments such as [\[GW20\]](#page-32-10) or [\[Hab22a\]](#page-32-11), and the recent improvement [\[PH23\]](#page-33-8).

Zero-knowledge is obtained in the usual manner, by inserting sufficient randomness in the encoding of the trace polynomials, and using the \[BSCR+19] randomization of FRI, which carries over to the circle without changes. We refer to [\[HK24\]](#page-32-12) for a detailed description of the randomization, including the component polynomials of the quotient decomposition.

Note that using the tweaked inverse FFT from Remark 12 allows to efficiently evaluate a representation with respect to the FFT basis over a domain in "group position", the only target not covered by twin-cosets. In Appendix C we make use of this exception, and describe an optimized variant of the STARK in which the evaluation domain D is a superset of the trace domain. In this context, we point out that arbitrary cosets can be handled by means of the "Mersenne FFT" from [\[HLN23\]](#page-33-0), which is a regular FFT over the complex extension Fp(i) optimized for "real" functions. By the rotation invariance of the FFT space, Proposition 5, the extrapolation map from a standard position coset H to any other coset of the same size is of convolutional (i.e. circulant) form, and thus can be evaluated by the Mersenne FFT. Compared to a regular FFT, the Mersenne FFT costs the same number of multiplication but causes a significant overhead in the number of additions, essentially thwarting the advantage of Mersenne arithmetics. It is for this reason why we do not advertise this approach, although a coset-centric view would bring circle STARKs even closer to the univariate case.

We further point out that circle codes (and variants of it) may be used in the construction of efficient diffusion layers in arithmetic hash functions such as Poseidon [GKR⁺21], Rescue [AAB⁺20], Rescue Prime [SAD20] and Monolith [GKL⁺23]. We shall elaborate on this in an upcoming writeup [HS24].

6 Low-degree test over the Circle

Given a proximity parameter \theta \in (0,1) , the interactive oracle proof of proximity (IOPP) to \mathcal{C} is an interactive oracle protocol that proves a given word f \in F^D being \theta -close to a word from the circle code, i.e.

where d denotes the relative Hamming distance over D. In other words, the IOPP proves the existence of a polynomial q from \mathcal{L}_N(F) which agrees with f on a set of density at least 1 - \theta ,

Circle codes are closely related to Reed-Solomon codes. In fact, due to the projective line representation of the circle curve they essentially are Reed-Solomon codes (cf. Theorem 1) although their rate

is slightly off the common use case of \rho=2^{-B} . The Circle Proof of Proximity is an adaption of FRI [BSBHR18a] to this generalized code, and its soundness analysis will be taken, in large parts verbatim, from that for Reed-Solomon codes [BSCI⁺20] in the list decoding regime. That is, the proximity parameter will be bounded by

the Johnson-Guruswami-Sudan list decoding radius.

In the bivariate representation of the circle, the circle proof of proximity with r rounds, where 0 \le r \le n , carries over the folding procedure of FRI to the chain of 2-to-1 projections

C(\mathbb{F}_p) \subseteq \mathbb{F}_p^2 \qquad D_m \xrightarrow{\pi} D_{m-1} \xrightarrow{\pi} D_{m-2} \xrightarrow{\pi} D_{m-2} \xrightarrow{\pi} D_{m-r+1}

which starts with the standard position coset D_m of size 2^m , where m = B + n, then takes the quotient with respect to the involution J, i.e. the projection onto the x-axis, and subsequently continues by (r-1) repeated application of the \pi(x) = 2 \cdot x^2 - 1 , until ending up with quotient of the standard position coset D_{m-r+1} , consisting of 2^{m-r} elements. (Choosing the maximum number of rounds r = n, the chain would end with the quotient D_{B+1}/J of size 2^B .) However, before applying the folding steps, the prover uses Lemma 7 from Section 4.3 to decompose f \in \mathcal{L}_N(F) into

where g is from the FFT space \mathcal{L}'_N(F) , \lambda \in F , and v_n is the vanishing polynomial of the standard position coset of size N=2^n . This decomposition is crucial, as the function spaces need to halve under folding to eventually end up with the trivial space of constant functions. Taking function spaces synonymous for their domain evaluations, the proximity claim of f to \mathcal{L}_N(F) reduces to that of g to the FFT space \mathcal{L}'^{(0)} := \mathcal{L}'_N(F) , which under repeated folding of "even" and "odd" parts as in the circle FFT, is step-wise reduced to proximity claims to the spaces

for j = 1, ..., r, until one ends up with the space \mathcal{L}^{(r)} of polynomials in x of degree \leq 2^{n-r} .

For notational convenience we will write

for the chain in (33), even though this conflicts the notation used in Section 4, and we set T_1 = J and T_j(x) = -x otherwise. Likewise, we use the unified notation t_i for the twiddle used in each step, which is t_1 = y in the first step, and t_j = x in the other cases.

1. Commit phase:

• (a) (Decomposition.) The prover uses Lemma 7 to compute the decomposition of f \in \mathcal{L}_N(F) into f = g + \lambda \cdot v_n with g \in \mathcal{L}'_N(F) and \lambda \in F . It sends \lambda to the verifier.
• (b) (Folding.) For each j=1,\ldots,r , corresponding to \pi_j:S_{j-1}\longrightarrow S_j as above, the prover holds a function g_{j-1}\in F^{S_{j-1}} from the previous round. (In the first round g_0=g .) It receives a random challenge \lambda_j \leftarrow F from the verifier, and uses it to build the random linear combination

g_j = g_{j-1,0} + \lambda_j \cdot g_{j-1,1} \tag{34}

of g_{j-1,0}, g_{j-1,1} \in F^{S_j} from the "even-odd" decomposition with respect to T_j , i.e.

g_{j-1,0} \circ \pi_j = \frac{g_{j-1} + (g_{j-1} \circ T_j)}{2}, (35)

using the corresponding twiddle t_j as defined above. The prover sets up the oracle for g_j , and sends it to the verifier. (In the last round, the prover sends g_{r+1} \in \mathcal{L}^{(r)} , in plain.)

2. Query phase:

(a) The verifier samples s \geq 1 queries uniformly from D. For each query Q, we write Q_0 = Q and consider its trace Q_j \in S_j , j = 1 \dots, n , under the chain of projections \pi_j : S_{j-1} \longrightarrow S_j . The verifier asks the oracle for the values of f at Q_0 and T_1(Q_0) , and of g_j at Q_j and T_j(Q_j) , for j = 1, \dots, r . It takes the answers to check whether each g_j was properly formed from g_{j-1} via the folding (34), using g_0 = f - \lambda \cdot v_n and the equations (35), (36) for j = 1, \dots, r .

If the oracle answers satisfy these checks for each of the s queries, then the verifier accepts. (Otherwise, it rejects.)

For STARKs, where one faces a batch of DEEP quotients, proximity alone is not good enough (unless one works in the unique decoding regime) and the stronger notion of correlated agreement is crucial. We say that a batch of functions f_1, \ldots, f_L \in F^D has (1-\theta) -correlated agreement with a codeword from C, if the set of joint agreement has density at least 1-\theta , i.e.

As for FRI, correlated agreement already plays a central role in the soundness analysis of Protocol 1, and its generalization to several functions comes without additional difficulties.

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

f = \sum_{k=1}^{L} \lambda_0^{k-1} \cdot f_i \tag{37}

over D. Now, both prover and verifier run Protocol 1 on f, with its query phase extended by a check of (37) at each of the s queries Q.

Remark 23. In our STARK we need to batch both real and imaginary parts of DEEP quotients for a typically large collection of code words g_k \in F^D , k = 1, ..., L, overall doubling the batch size. (Actually, most of the words are over \mathbb{F}_p , but this does not play a role for what follows.) Leveraging linearity one can essentially halve the batching effort, resulting in comparable costs as if the quotients where over F instead of F(i). Let us illustrate this for a single fixed point \gamma \in C(F) , a generalization to several points is straightforward. Both real and imaginary part of the quotienting map, which sends g to (g - g(\gamma))/v_{\gamma} , are linear maps from \mathcal{L}_N(F) to \mathcal{L}_N(F) , which we denote by \text{Re}_{\gamma} and \text{Im}_{\gamma} . For any batching randomness \mu \in F ,

For this type of linear combination the prover only needs to compute the values of \bar{g} = \sum_{k=0}^{L-1} \mu^k \cdot g_k over D, the linear combination of the claims \bar{v}_{\gamma} = \sum_{k=0}^{L-1} \mu^k \cdot g_k(\gamma) , and computes the values of g over D according to

Hence for large batches, the computational overhead introduced by the extension F(i) is negligible, essentially reducing the batching cost to that of computing \bar{g} . For the same reason the effort of the verifier is reduced to essentially that of computing \bar{g} at the sample points from the query phase of the proximity test.

We eventually are able to state the soundness error of the batch IOP of proximity. Its proof, which relies on the correlated agreement theorem for Reed-Solomon codes, is postponed to Appendix B.

Theorem (Summary Theorem 6, Appendix B). If an adversary passes the batch IOP of proximity (Protocol 2) for f_1, \ldots, f_L \in F^D and agreement parameter \alpha = \sqrt{\rho} \cdot \left(1 + \frac{1}{2m}\right) , for some m \geq 3 , with a probability larger than

As for standard FRI, we note that the protocol can be generalized to reduction steps of higher two-adic size, and the round-by-round soundness analysis from Appendix B is adapted accordingly.

We would like to thank Eli Ben-Sasson, Dan Carmon, Alessandro Chiesa, Angus Gruen, Swastik Kopparty, and Elijah Riggs for helpful discussion and feedback. We also thank Liam Eagen and Jeroen Zuiddam for pointing out the work of [LX23], and Ariel Gabizon for pointing out typos. Special thanks to Jacqueline Nabaglo for finalizing the Babybear AVX2 code right in time for our benchmarks.

References

• [AAB⁺20] Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, and Alan Szepieniec. Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols. IACR Trans. Symmetric Cryptol., 2020(3):1–45, 2020.
• [BG] Jeremy Bruestle and Paul Gafni. RISC Zero zkVM: scalable, transparent arguments of RISC-V integrity. https://www.risczero.com/proof-system-in-detail.pdf.
• [BGH19] Sean Bowe, Jack Grigg, and Daira Hopwood. Recursive proof composition without a trusted setup. In IACR ePrint Archive 2019/1021, 2019. https://eprint.iacr.org/2019/1021.
• [BSBHR18a] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon interactive oracle proofs of proximity. In ICALP 2018, 2018. Full paper: https://eccc.weizmann.ac.il/report/2017/134/.
• [BSBHR18b] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. In IACR ePrint Archive 2018/046, 2018. https://eprint.iacr.org/2018/046.
• [BSCI⁺20] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for Reed-Solomon codes. In FOCS 2020, 2020. Full paper: https://eprint.iacr.org/2020/654.
• [BSCKL21] Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, and David Levit. Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast polynomial algorithms over all finite fields. In Electronic Colloquium on Compputational Complexity, volume TR21-103, 2021. https://eccc.weizmann.ac.il/report/2021/103/.
• [BSCKL22] Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, and David Levit. Scalable and transparent proofs over all large fields, via elliptic curves (ECFFT part II). In IACR ePrint Archive 2022/1542, 2022. https://eprint.iacr.org/2022/1542.

• [BSCR⁺19] Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. In Y. Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, volume 11476 of LNCS. Springer, 2019.
• [BSCS16] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In TCC 2016, pages 31–60, 2016.
• [CHM⁺20] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In EUROCRYPT 2020, volume 12105 of LNCS, 2020. Full paper: .
• [COS20] Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. In EUROCRYPT 2020, volume 12105 of LNCS, 2020. Full paper: .
• [CT65] James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. In Mathematics of Computation, volume 19 (90), pages 297–301, 1965.
• [GK22] Ariel Gabizon and Dmitry Khovratovich. flookup: Fractional decomposition-based lookups in quasi-linear time independent of the table size. In IACR ePrint Archive 2022/1447, 2022. .
• [GKL+23] Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, Markus Schofnegger, and Roman Walch. Monolith: Circuit-friendly hash functions with new nonlinear layers for fast and constant-time implementations. IACR Cryptol. ePrint Arch., page 1025, 2023.
• [GKR+21] Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roz, and Markus Schofnegger. POSEIDON: A new hash function for zero-knowledge proof systems. In USENIX Security Symposium 2021, 2021.
• [GS99] Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraicgeometry codes. In IEEE Trans. on Information Theory, volume 45(6), 1999.
• [GW20] Ariel Gabizon and Zachary J. Williamson. Plookup: A simplified polynomial protocol for lookup tables. In IACR ePrint Archive 2020/315, 2020. https://eprint.iacr.org/2020/ 315.
• [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for oecumenical non-interactive arguments of knowledge. In IACR ePrint Archive 2019/953, 2019. .
• [Hab22a] Ulrich Haböck. Multivariate lookups based on logarithmic derivatives. In IACR ePrint Archive 2022/1530, 2022. .
• [Hab22b] Ulrich Haböck. A summary on the FRI low-degree test. In IACR ePrint Archive 2022/1216, 2022. .
• [Hab24] Ulrich Haböck. A note on the G-FFT. In IACR ePrint Archive 2024/1036, 2024. https: //eprint.iacr.org/2024/1036.
• [HGdB21] Ulrich Haböck, Alberto Garoffolo, and Daniele di Benedetto. Darlin: Recursive proofs based on Marlin. In IACR ePrint Archive 2021/930, 2021. .
• [HK24] Ulrich Haböck and Al Kinde. A note on adding zero-knowledge to STARKs. In IACR ePrint Archive 2024/1037, 2024. .

• [HLN23] Ulrich Haböck, Daniel Lubarov, and Jacqueline Nabaglo. Reed-Solomon Codes over the Circle Group. In IACR ePrint Archive 2023/82, 2023. .
• [HS24] Ulrich Haböck and Markus Schofnegger. Efficient MDS matrices from linear codes. In preparation, 2024.
• [LCH14] Sian-Jheng Lin, Wei-Ho Chung, and Yunghsiang S. Han. Novel polynomial basis and its application to Reed-Solomon erasure codes. In FOCS 2014, 2014.
• [LX23] Songsong Li and Chaoping Xing. Fast Fourier transform via automorphicsm groups of rational function fields. In arXiv:2310.14462, 2023. .
• [PH23] Shahar Papini and Ulrich Haböck. Improving logarithmic derivative lookups using GKR. In IACR ePrint Archive 2023/1284, 2023. .
• [Pola] Polygon Labs / Polygon Zero. Plonky2: Fast recursive arguments with PLONK and FRI. .
• [Polb] Polygon Labs / Polygon Zero. Plonky3: A toolkit for implementing polynomial IOPs. https: //github.com/Plonky3/Plonky3.
• [Polc] Polyogon Labs. Polygon Hermez. https://github.com/orgs/0xPolygonHermez/ repositories.
• [Pold] Polyogon Labs. Polygon Miden: A STARK-based virtual machine. https://github.com/ maticnetwork/miden.
• [SAD20] Alan Szepieniec, Tomer Ashur, and Siemen Dhooghe. Rescue-Prime: a standard specification (SoK). IACR Cryptol. ePrint Arch., page 1143, 2020.
• [Sta23] StarkWare Team. ethSTARK documentation – version 1.2. In IACR ePrint Archive 2021/582, 2023. .

A Correlated agreement

To simplify notation, we shall call any polynomial p \in F[X] of \deg p \leq k-1 to belong to the code \mathsf{RS}_k[F,D] , and we will not distinguish between the polynomial itself and the code word generated from it.

where

(39)

The proof of the correlated agreement theorem is an algebraic analysis of the Guruswami-Sudan list decoder over the rational function field K = F(Z). It uses the Polichuk-Spielmann lemma to "glue together" the outputs of the decoder for f_1 + \lambda \cdot f_2 + \ldots + \lambda^{N-1} \cdot f_N over the "small" field F by means of the decoder result for the word

over the infinite field K: If for a noticeable fraction of \lambda 's the distance to the Reed-Solomon code is \leq \theta , then the same holds over F(Z).

In FRI the oracles are tested jointly across the rounds, and one wishes to control the fraction of "good points" (where a query would succeed) under each further folding step. For this purpose [BSCI⁺20] prove a refinement of the correlated agreement theorem, which works with weighted Hamming distances. Given a vector of weights \mu: S \longrightarrow [0,1] over S, we define the (relative) weight of subset A \subset S as

A function f \in F^S is said to have (relative) \mu -agreement of at least \alpha with another function g \in F^S , if

and we write

if there exists a p \in \mathsf{RS}_k[F,S] for which agree_\mu(f,p) > \alpha .

Theorem 5. (Weighted correlated agreement theorem, full version of [BSCI⁺20], Theorem 7.2) Let \theta \in \left(\frac{1-\rho}{2}, 1-\sqrt{\rho}\right) , where \theta = 1-\sqrt{\rho} \cdot \left(1+\frac{1}{2m}\right) , for some integer m \geq 3 , and assume that \mu: S \longrightarrow [0,1] is a vector of weights over S with common denominator M \geq 1 , i.e. for all x in S

for an integer value m_x \in [0, M] . Suppose that for f_1, f_2, \ldots, f_L \in F^S ,

with \varepsilon as in (39). Then there exist polynomials p_0(X) , p_1(X) , ..., p_{L-1}(X) from \mathsf{RS}_k[F,S] , and a set A of relative weight \mu(A) > \alpha on which f_i coincides with p_i for all i = 0, \ldots, L-1 .

Both Theorem 4 and Theorem 5 do not make any assumptions on the form of the evaluation domain S and hence, by Theorem 1, they also apply to circle codes (Definition 3).

B Soundness in the oracle model

Let \mathbb{F}_p be a CFFT-friendly prime. An interactive oracle proof over the circle curve C(\mathbb{F}_p) (in short, a circle IOP) is an interactive protocol, in which one party, the prover, wants to convince a second party, the verifier, upon that given words f_1, \ldots, f_w \in \mathbb{F}_p^D over some domain D \subseteq C(\mathbb{F}_p) satisfy certain properties. These properties are of the form

where \alpha \in [0,1] is an agreement parameter, and \mathcal{L}_R \subseteq \left(F[X,Y]^{\leq d}\right)^w is a set of low-degree polynomials defined by certain algebraic relations. (That is, \mathcal{L}_R is an algebraic set.) In each round of the oracle proof, the verifier sends a public random coin (a challenge) and the prover responds with a new set of words, over D or another specified domain of the circle, having values in \mathbb{F}_p , or in a specified finite extension of it. As an information theoretic model for an ideal vector commitment scheme, the words from the prover are not sent in plain but provided to the verifier via a secure and trusted channel, the oracle. Upon receiving, the verifier is merely given oracle access to the words for a specified (and typically small) number of queries, asking for the word entry at an arbitrary (typically random) position, immediately or at any later step of the protocol. After a certain number of rounds, the verifier accepts or rejects, based on the answers of the oracle queries and the random challenge. In our IOPs the queries to the oracle are deferred to a separate query stage at the end of the protocol.

The discussed circle IOPs follow the common design principle of probabilistic proofs: They form a chain of probabilistic reductions stepwise simplifying the assertion to be proven,

We omit a discussion of asymptotic security and restrict our results to the concrete soundness errors. This is justified by that in our application, it is natural not to step beyond a fixed CFFT-friendly field \mathbb{F}_p (such as the Mersenne field M31), making an asymptotic analysis with respect to the relation to be proven useless.

B.1 Soundness of the IOP of proximity to circle codes

which under repeated folding along the chain of projections

is turned into polynomials from

for 1 \leq j \leq r , where the number of rounds r \leq n . We consider the quotient map \pi_1 = \phi_J as the projection onto the x-axis, \pi_1 = \pi_x , and hence S_1, \ldots, S_r as univariate domains. The codes corresponding to the function spaces \mathcal{L}^{(j)} , except for j = 0, are therefore ordinary Reed-Solomon codes

Fix an agreement parameter \alpha \in (0,1) . Given g_0 \in F^{S_0} , we say that a prover P^* succeeds the commitment phase, if it is able to respond with round oracles g_1, g_2, \ldots, g_r on the respective verifier challenges \lambda_1, \ldots, \lambda_r , which \alpha -consistently fold down to a codeword from \mathcal{C}^{(r)} . That is, there exists p_r \in \mathcal{C}^{(r)} for which

Any such transcript (or more generally any set of oracles) (g_0, \lambda_1, g_1, \dots, \lambda_r, g_r) will be called \alpha -good for the code \mathcal{C}^{(r)} . (We demand proximity of g_r to \mathcal{C}^{(r)} instead of being a member of it for proof reasons. In the protocol, the verifier rejects any final g_r which is not equal in full length to a Reed-Solomon codeword.)

The soundness error of the commitment phase goes along the following lines. Starting with the relation

The error of such a reduction step will be given by the weighted correlated agreement theorem (Theorem 5), and overall error is dominated by the sum of the round-wise errors.

Lemma 13 (Soundness commit phase). Take an agreement parameter \alpha = \left(1 + \frac{1}{2 \cdot m}\right) \cdot \sqrt{\rho} , where m \geq 3 . Suppose that a (possibly computationally unbounded) algorithm P^* succeeds the commitment phase of r \geq 1 rounds with probability larger than

Proof. We prove the Lemma by induction in r the number of rounds, 1 \le r \le n . We start by proving the base case r = 1. If with probability greater than \varepsilon_1 = \varepsilon(S_1, M_1, \rho, m) , with M_1 , \rho and m as above, the prover is able to answer with g_1 so that (g_0, \lambda_1, g_1) is \alpha -good for the Reed-Solomon code \mathcal{C}^{(1)} , then in particular

By Theorem 5 (or, in this case also Theorem 4) both g_{0,0} and g_{0,1} jointly agree with corresponding polynomials p_0(X), p_1(X) of degree < 2^{n-1} , over a set A \subseteq S_1 of density > \alpha . The preimage \pi_1^{-1}(A) has density > \alpha , and over this set the word g_0 agrees with the polynomial p_0(X) + Y \cdot p_1(X) , which is from the FFT space \mathcal{L}^{(0)}(F) .

has probability \Pr[\mathfrak{T}] > \varepsilon_1 + \ldots + \varepsilon_r . Since consistency of a folding step is a property of the fiber of the projection (the even and odd functions are constant over fibers), the latter probability is equal to

for y \in S_{r+1} . Notice that the numerator of \nu is constant over fibers of \pi_1 , hence the weights have common denominator M_{r+1} = 2^r . By our assumption the conditional success probability is greater than \varepsilon_{r+1} = \varepsilon(S_{r+1}, M_{r+1}, \rho, m) , and we conclude from Theorem 5 that both g_{r,0} and g_{r,1} jointly agree with the values of respective polynomials p_0, p_1 \in \mathcal{L}^{(r+1)} over a set A_{r+1} \subseteq S_{r+1} of relative weight \nu(A_{r+1}) > \alpha . (Recall that \mathcal{L}^{(r+1)} is the space of polynomials in x of degree < 2^{n-(r+1)} .) Over the preimage A_r = \pi_{r+1}^{-1}(A_{r+1}) , the word g_r coincides with the values of p_0(\pi_{r+1}(X)) + X \cdot p_1(\pi_{r+1}(X)) \in \mathcal{L}^{(r)} , and the set of good P \in (\pi_r \circ \ldots \circ \pi_1)^{-1}(A_r) , on which all folding checks against (g_1, \ldots, g_r) hold, is of density

In other words, the restricted trace (\lambda_1, g_1, \ldots, \lambda_r, g_r) is \alpha -good for \mathcal{C}^{(r)} . Since the probability of P^* producing such a trace is greater than \varepsilon_1 + \ldots + \varepsilon_r , we conclude from the induction hypothesis that g_0 has \alpha -agreement with \mathcal{C}^{(0)} . This completes the proof of the Lemma.

The batch proof of proximity has an additional preceding batching step, and we define a successful pass of the commit phase in a similar manner, taking into account the folding check of the batching round.

Lemma 14 (Soundness error commit phase, batch FRI). Take an agreement parameter \alpha = \left(1 + \frac{1}{2 \cdot m}\right) \cdot \sqrt{\rho} , where m \geq 3 . Suppose that a (possibly computationally unbounded) algorithm P^* succeeds the commitment phase of batch circle FRI (Protocol 2) with r \geq 1 rounds, with probability larger than \varepsilon_C = \varepsilon_0 + \varepsilon_1 + \ldots + \varepsilon_r , where

Proof. Including round j=0 for the batching step into the notion of \alpha -goodness of a transcript \mathsf{tr}=(\lambda_0,g_0,\lambda_1,g_1,\ldots,\lambda_r,g_r) , the proof is almost identical to that of Lemma 13. We hence only point out the key differences.

The soundness error of the query phase is the probability that s \geq 1 queries fail to detect a transcript (\lambda_0, g_0, \lambda_1, g_1, \dots, \lambda_r, g_r) with a consistency set A \subseteq S_0 of only at most density \alpha . Since the samples are uniformly and independently drawn from S_0 , that soundness error is

\varepsilon_Q = \alpha^s .

Combining the soundness error of the commitment phase with the soundness error of the query phase eventually leads the soundness error as stated in Section 5.

\varepsilon = \varepsilon_C + \varepsilon_O ,

Remark 25. Taking the correlated agreement decoder from Proposition 7 yields such claimed polynomials within strictly bounded polynomial time.

Remark 26. The soundness error bound as stated in Section 6 is derived from Theorem 6 as follows. Taking the sum as upper bound for the max in Equation 40, we obtain

Together with \varepsilon_Q = \alpha^s and taking \theta = 1 - \alpha , we arrive at the claimed soundness error bound.

B.2 Soundness of the IOP for AIR

The entire section takes the same assumptions as used in Section 5. That is, p is CFFT-friendly for sufficiently large orders so that the circle curve C(\mathbb{F}_p) is large enough to host the trace domain H and the evaluation domain D, both standard position cosets of size N=2^n and M=2^B\cdot N , where B\geq 1 . We say that a collection of low-degree polynomials p_1,\ldots,p_w\in \mathbb{F}_p[X,Y]/(X^2+Y^2-1) a solution of the AIR (with w columns of length N=2^n ) if each of the C\geq 1 polynomial constraints

P_i(s_i, p_1, \dots, p_w, p_1 \circ T, \dots, p_w \circ T) = 0, (43)

for 1 \leq i \leq C , is satisfied over the trace domain H. (Here, T is the rotation by a generator of H.) The selector polynomials s_i \in \mathcal{L}_N(\mathbb{F}_p) are combinations of the ones described in Section 5.1, expressive enough to cover periodic constraints and their boundary conditions. The degree of the algebraic intermediate representation,

is such that there exist sufficiently many twin-cosets of the size of H to determine the polynomial in (43) by means of the circle FFT.

The parameter setup of the circle STARK for the specific AIR over \mathbb{F}_p is as follows. Given the security parameter \mathfrak{l} \in \mathbb{N} , one chooses the wished multiplicity parameter m for the proximity test to \mathcal{C} = \mathcal{C}_N(F, D) ,

3 \le m \le N/2 ,

the smallest such is the one to be used in Equation (47). This slightly larger agreement set size is needed in the soundness proof to assure that the non-quotiented words are within list-decodable distance to the slightly larger code C_{N^+}(F,D) , with N^+=N+2 .

Protocol 3 (Circle IOP for AIR). Let p_1(X,Y), \ldots, p_w(X,Y) \in \mathbb{F}_p[X,Y]^{\leq N/2} be polynomials of degree deg p_i \leq N/2 satisfying the AIR constraints (43) over the trace domain H, for every i = 1, \ldots, C .

• 0. The prover sets up the domain evaluation oracles [p_1], \ldots, [p_w] for the values of p_1(X, Y), \ldots, p_w(X, Y) over D, and sends them to the verifier.

for their values over D, and \lambda to the verifier. The overall identity to be proven is therefore

\sum_{i=1}^{C} \beta^{i-1} \cdot P_i(s_i, p_1, \dots, p_w, (p_1 \circ T), \dots, (p_w \circ T)) = v_H \cdot \left(\lambda \cdot v_{\bar{H}} + \sum_{j=1}^{d-1} \frac{v_{\bar{H}}}{v_{H_j}} \cdot q_{\beta, j}\right). \tag{46}

• 2. The verifier samples a random DEEP query, i.e. a random point \gamma \leftarrow C(F) \setminus (D \cup H) drawn uniformly from the circle curve over the extension field F, and sends it to the prover. The prover answers with the evaluation claims (\gamma, v_{i,1}) , (T(\gamma), v_{i,2}) , i = 1, ..., w, for the witness polynomials p_i(X, Y) , and (\gamma, v_j) , j = 1, ..., d-1, for the segment polynomials q_{\beta,j}(X, Y) .
• 3. Both prover and verifier engage in the batch circle FRI (Protocol 2) for the real and imaginary parts of the DEEP quotients defined in Proposition 4,

for each i = 1, ..., w, and

If circle FRI passes, and if the evaluation claims satisfy the overall identity (46) at (X,Y) = \gamma , the verifier accepts. (Otherwise, it rejects.)

Remark 27. In regards to query phase of batch circle FRI, it is assumed that the verifier aborts if one of the values responded by the oracle is not from the specified field. This is necessary to conclude a solution over \mathbb{F}_p and not only the extension field F.

We finally show the concrete soundness error of Protocol 3 in the oracle model. The proof is almost identical to that for the univariate case in [Hab22b], with minor adaptions to the circle setting. Round 1 reduces the initial relation, i.e.

by means of the verifier challenge \beta to

Theorem 7 (Soundness). Suppose that a (possibly computationally unbounded) algorithm P^* provides a first message [f_1], \ldots, [f_w] on which it is able to succeed Protocol 3 with a probability greater than

Proof. Without loss of generality, we assume that the prover P^ oracles are over the specified field, and in particular first round oracles are from \mathbb{F}_p^D . Otherwise, modify P^ to take arbitrary values wherever it does not comply. Since the verifier rejects values outside the non-specified field anyway, the success probability of this modified algorithm does not decrease.

Likewise, for every such "good" \beta (by the definition of \varepsilon_1 , there are more than \ell^+ \cdot (C-1) many) there exists a second message of P^* , i.e. words q_{\beta,0}, \ldots, q_{\beta,d-1} \in F^D such that

For each such "good" \gamma \in C(F) \setminus (D \cup H) (by the definition of \varepsilon_2 , there are more than \ell \cdot d \cdot (N+2) such) the evaluation claims pass the verifier checks, and moreover the soundness of circle FRI enforces the DEEP quotients

In what follows we shall call an element (h_1(X,Y),\ldots,h_l(X,Y)) from F[X,Y]^l , with component polynomials of degree \leq N^+/2 , having correlated agreement with a vector of functions (\phi_1,\ldots,\phi_l) on a set of density \geq \alpha , an \alpha -configuration for that vector of functions. Note that since \alpha > (1 + \frac{1}{2m^+}) \cdot \sqrt{\rho^+} , the Guruswami-Sudan list size bound (for the correlated agreement code, c.f. Proposition 7) tells us there are at most

\alpha -configurations for (\phi_0(x), \dots, \phi_{l-1}(x)) .

Let us keep a combination of "good" first and second messages (f_1,\ldots,f_w) , (q_{\beta,1},\ldots,q_{\beta,d-1}) fixed. We have seen above that the existence of a single "good" \gamma implies the existence of an \alpha -configuration for (f_1,\ldots,f_w,q_{\beta,0},\ldots,q_{\beta,d-1}) . By the Guruswami-Sudan list size bound for \mathcal{C}_{N^+}(K,D) there are at most \ell^+ such \alpha -configurations. However, since there are more than \ell^+ \cdot d \cdot N^+ many "good" \gamma , and each establishes an \alpha -configuration which moreover evaluates to the claimed values, we conclude from the pigeon-hole principle that there is at least one \alpha -configuration,

for which the overall identity (46) holds at more than d \cdot N^+ many \gamma . By the maximum number of zeros of a polynomial from F[X,Y]^{\leq d \cdot N^+/2} (Proposition 2) this configuration is a solution of it, hence (p_1,\ldots,p_w) \in F[X,Y]^w is an \alpha -configuration for (f_1,\ldots,f_w) which satisfies

\sum_{i=1}^{C} \alpha^{i-1} \cdot P_i(s_i, p_1, \dots, p_w, p_1 \circ T, \dots, p_w \circ T) = 0 (48)

over the trace domain H.

We have seen that for each "good" \alpha there exists an \alpha -configuration for (f_1, \ldots, f_w) which is a solution of (48). Again, by the Guruswami-Sudan list size bound for \mathcal{C}_{N^+}[K,D] , there can be at most \ell^+ many w-configurations. Since there are more than \ell^+ \cdot (C-1) many "good" \alpha , we conclude again from the pigeon-hole principle that there is at least one \alpha -configuration, which we again denote by (p_1,\ldots,p_w) , for which there are at least C many "good" \alpha for which (48) holds. By linear algebra (the Vandermonde matrix is invertible) we conclude that this configuration satisfies

over H, for every i = 1, \ldots, C . This completes the proof.

B.3 Witness extraction

Witness extraction is based on the correlated agreement decoder, which essentially is the Guruswami-Sudan list decoder on the isomorphic generalized Reed-Solomon code, over a suitably extended alphabet.

\vec{f} = (f_1, \dots, f_L) \in (F^D)^L jointly agree with \vec{p} = (p_1, \dots, p_L) \in \mathcal{L}_N(F)^L over a set of density > \alpha , denoted by \operatorname{agree}(\vec{f}, \vec{p}) > \alpha , where \alpha = (1 + \frac{1}{2m}) \cdot \sqrt{\rho} . Then there at most

Proof. Take F_L a finite extension of F of degree \dim(F_L/F) \geq L , and \zeta_1, \ldots, \zeta_L \in F_L any choice of elements which are linearly independent over F. Then \vec{f} = (f_1, \ldots, f_L) \in (F^D)^L jointly agree with a \vec{p} = (p_1, \ldots, p_L) \in \mathcal{L}_N(F)^L on a set A of density > \alpha , if and only if the word f = \sum_{j=1}^L \zeta_j \cdot f_j \in F_L^D agrees with a word from the circle code \mathcal{C}_N(F_L, D) , over the same set A. Corollary 1) applied to the circle code over the extended alphabet yields the assertion of the proposition.

With the correlated agreement decoder one is able to extract witnesses from any prover that succeeds the circle IOP for AIR with a probability beyond the soundness error.

Theorem 8 (Knowledge Soundness). Assume that a prover P^ passes Protocol 3 with a probability \varepsilon^ greater than the soundness error \varepsilon_{AIR} from Theorem 7. Then there is probabilistic algorithm \mathcal{E} = \mathcal{E}^{P^}(aux) with oracle access to the first round function of P^ , that outputs a solution (p_1, \ldots, p_w) \in \mathcal{L}_{N^+}(\mathbb{F}_p)^w of the AIR, within an expected number of O(1/(\varepsilon^ - \varepsilon)) calls to P^ .

Proof. The extractor \mathcal{E} samples a first round message [f_1], \ldots, [f_w] of P^ , reads out f_1, \ldots, f_w \in \mathbb{F}_p^D in full length, applies the correlated agreement decoder from Proposition 7, and eventually tests each of its outputs \vec{p} \in L_{N^+}(\mathbb{F}_p)^w on being a solution to the AIR. The set of "good" first round messages [f_1], \ldots, [f_w] on which P^ is able to succeed with a probability greater than \varepsilon_{AIR} , is at least of probability \varepsilon^ - \varepsilon_{AIR} . Thus the extractor \mathcal{E} needs to sample on average 1/(\varepsilon^ - \varepsilon_{AIR}) first round messages to obtain such a good first round message. On such a message, the correlated agreement decoder ouputs (at least) one solution of the AIR.

for 1 \le k \le m-1 , except for k=m/2 which corresponds to H itself, and the exceptional case G_n ,

However, the exception H_0 = G_n is no drawback for efficiency. For computing the values of f_i \in \mathcal{L}'_N(\mathbb{F}_p) over H_0 one takes the variant of the inverse FFT from Remark 12, and for extrapolating values over H_0 to the full domain D one uses rotated coordinates under which H_0 is in standard position. This yields words which stem from the function space

since Q^{m/2} \cdot H_0 is in standard position. According to this mixed-type decomposition of D \setminus H , the overall quotient q splits into

with q_0 \in \mathcal{L}'_N(F, H_0) and all other q_k \in \mathcal{L}'_N(F) , and \lambda \in F . (Here, k ranges from 0 \le k \le m-1 , except k = m/2.) The analysis of the overall identity at infinity is as before, with the following differences. Recall that by Equation (25) we have

Therefore q_0 as a function from \mathcal{L}'_N(F) \circ T_Q^{m/2} belongs to \mathcal{L}_N^+(F) , and the vanishing polynomial v_{H_0} = v_H \circ T_Q^{m/2} belongs to \mathcal{L}_N^-(F) . All other component polynomials q_k belong to \mathcal{L}_N^-(F) , and all other vanishing polynomials v_{H_k} belong to \mathcal{L}_N^+(F) . Thus the product of all vanishing polynomials \prod_k v_{H_k} is odd at infinity, whereas each product q_k \cdot \prod_{j \neq k} v_{H_j} in the sum is even at infinity. From this we conclude that in the case d is even, where q \in \mathcal{L}_{(d-1)\cdot N}^+ , we must have \lambda = 0 , and in the case d is odd, where q \in \mathcal{L}_{(d-1)\cdot N}^- ,

For the final low-degree test over D one again uses rotated coordinates, this time using an element of order 2^{n+B+1} which moves D into standard position.

At the time of writing, a full implementation of the circle STARK is not yet ready. As a preview of what to expect in terms of performance, we provide preliminary benchmarks of the circle FFT over the Mersenne prime field M31, compared to the regular FFT over the equally sized Babybear field, see Table 1. The advantage of vectorized M31 arithmetics (AVX2 multiplications are about 40% faster than with BabyBear, see also [HLN23]) directly translates to the single-threaded FFT cost. With high thread count, our current implementation becomes memory-bound, and thus, M31 CFFT and BabyBear performance is similar. Take note that the current implementation does not apply memory optimizations (such as Radix 2^k FFT or 4-step). With such optimizations, memory bandwidth is expected to be much less of a bottleneck on personal hardware.

Let us discuss some details of the circle FFT implementation. When ordered correctly, the circle FFT algorithm is almost identical to the radix-2 FFT algorithm, only with different twiddle factors. For a twin coset D = Q \cdot G_{n-1} \cup Q^{-1} \cdot G_{n-1} , define this ordering as P : \{0, \ldots, 2^n - 1\} \longrightarrow D :

https://github.com/Plonky3/Plonky3/commit/86d13ddf269427c4788cdd41f413308a6050f9f3

^&lt;sup>8Babybear code used for the benchmarks:

Table 1: FFT algorithm runtime comparison8 between Babybear and M31, for a batch FFT of 128 polynomials. Measured 100 iterations on Intel i7-1165G7, at a fixed 1.5 Ghz frequency, single threaded, using AVX2 vectorization. Our current multi-threaded implementation becomes memory bottlenecked at domain sizes ≥ 2 ¹⁶ (emphasized by a gray background), but this will be optimized in future.

where G is a generator of order 2 n−1 . An evaluation of a function f : D → F is f ◦ P. Algorithm 1 takes such an evaluation and computes coefficients of the interpolating function in the FFT space. For a small number of columns, we recommend the CFFT interpolation to use precomputed inverse twiddles. Unlike for the regular FFT, it is unclear how to efficiently compute these on the fly without doing an expensive inverse operation. However, for batched CFFT, this is less of an issue. For the evaluation implementation (inverse of interpolation), computing the twiddles can be done on the fly, though it is more expansive than a regular FFT, since it involves operations in the complex extension Fp(i) of Fp.

Algorithm 1 Circle FFT (interpolation)

1: procedure CFFT(a)
2: # First layer
3: step ← N/2
4: for k = 0, 1, . . . , step − 1 do
5: twiddle ← (QGk
                       ).y
6: butterfly(a[k], a[k + step], twiddle)
7:
8: # Rest of the layers
9: for l = 0, 1, . . . , n − 2 do
10: step ← step/2
11: for i = 0, 1, . . . , N/(2 · step) − 1 do
12: j ← i · 2 · step
13: for k = 0, 1, . . . , step − 1 do
14: twiddle ← ((QGk
                              )
                               2
                                ).x
15: butterfly(a[j + k], a[j + k + step], twiddle)
16: procedure butterfly(a, b, t)
17: a, b ← a + b,(a − b)/t