Circle STARKs

Luca Dall’Ava, 12th of June 2025

Aim of the talk

Present the main ideas behind Circle STARKs.

Table of contents

Recalls on STARKs:

See previous ZKP Seminar by Muhammed Ali Bingol on 23rd June 2025: STARK (Scalable Transparent Arguments of Knowledge) protocol.

STARK = Scalable Transparent ARgument of Knowledge.

  • Scalable =
    • the prover is at most quasilinear in the size of the computation, and
    • the verifier is poly-logarithmic in the size of the computation.
  • Transparent = all verifier messages are just publicly sampled random coins.
  • No trusted setup needed (hence, no cryptographic toxic waste to handle).

Note that non-interactive STARKs are a subclass of SNARKs (cf. Fiat-Shamir Heuristic). Moreover, STARKs are also (widely accepted to be) quantum-resistant.

Main ingredients of a STARK

  • Cryptographic Hash Functions: main cryptographic security assumption.
  • Low-Degree Polynomials: STARKs encode a computation into a set of polynomials. The core assumption is that these polynomials have a low degree: proving the correctness of the computation then becomes a matter of proving that these polynomials are indeed low-degree and satisfy certain relationships.
  • Commitment Schemes: Provers use a commitment scheme to commit to the polynomials (or more accurately, their evaluations); this is typically done using a Merkle tree (cf. Hash functions!). The verifier can then request and check specific values from the tree using a Merkle path.
  • FRI (Fast Reed-Solomon IOP of Proximity): This is the central protocol of a STARK. It is a highly efficient way for a verifier to check that a committed polynomial is, in fact, low-degree. FRI uses a recursive "split-and-fold" method to reduce the problem of checking a large polynomial to checking a much smaller one, a process that is repeated until the remaining polynomial can be verified directly.

Example of a statement (from https://vitalik.eth.limo/general/2017/11/09/starks_part_1.html)

  • Statement: Prove that you know the millionth Fibonacci number → Prove that you have knowledge of a polynomial PP which represents a computation tape, with P(x)P(x) representing the xx-th Fibonacci number.
  • Constraint checking polynomial: the polynomial C(X1,X2,X3)=X3−X2−X1C(X_1,X_2,X_3) = X_3 - X_2 - X_1 represent a constraint forcing the polynomial PP to represent the Fibonacci sequence; in fact (for fixed N≥1000000N \geq 1000000),
    P(X) represents the Fibonacci sequence   ⟺  C(P(x),P(x+1),P(x+2))=0 ∀ x∈[0,N].P(X) \text{ represents the Fibonacci sequence }\\ \iff\\ C(P(x),P(x+1),P(x+2)) = 0 \,\forall\, x\in[0,N].
  • Reformulate: this is true if and only if
CP(x):=C(P(x),P(x+1),P(x+2))=0 ∀ x∈[0,N]  ⟺  CP(X)=D(X)⋅∏n∈[0,N]∩Z(X−n), D(X)∈Z[X].C_{P}(x):= C(P(x),P(x+1),P(x+2)) = 0 \,\forall\, x\in[0,N] \\ \iff \\ C_P(X) = D(X)\cdot \prod_{n\in[0,N]\cap \mathbb{Z}} (X-n), \ D(X)\in \mathbb{Z}[X].
  • Commitments: the prover commits (Merkle tree commitments) to P(x)P(x), P(x+1)P(x+1), P(x+2)P(x+2), and D(x)D(x), x∈[0,N]x\in [0,N].
  • Apply the FRI protocol: the verifier does not check all the evaluations, but use the FRI IOPP to probabilistically check that the equality is satisfied.

Recalls on FRI

See previous ZKP Seminars: FRI -Base aggregation, Polynomial Commitments (Hyrax, KZG, FRI), STARK (Scalable Transparent Arguments of Knowledge) protocol.

FRI = Fast Reed-Solomon IOP of Proximity.

IOP = interactive oracle proof.

FRI is presented in the language of codewords (they are vectors in a vector space!) the prover sends codewords to the verifier who does not read them whole but who makes oracle-queries to read them in select locations. The codewords in this protocol are Reed-Solomon codewords, meaning that their values correspond to the evaluation of some low-degree polynomial in a list of points called the domain.

Goal of FRI

The goal of FRI is that the prover convinces verifier of the committed polynomial is close to a low degree polynomial.

Core of FRI: Split-and-Fold

The Split-and-Fold Technique is the core recursive process within the FRI protocol. It works by "folding" a polynomial into a new, smaller polynomial.

  1. Splitting: The prover splits the polynomial
    P(X)=∑i∈[0,M]aiXi,P(X) = \sum_{i\in [0,M]} a_i X^i,

    into P(X)P(X)’s even and odd degree coefficients polynomials

    Peven=∑i∈[0,M], i evenaiXi,Podd=∑i∈[0,M], i oddaiXi,P=Peven+Podd,P_{even} = \sum_{i\in [0,M],\, i \text{ even}} a_i X^i,\quad P_{odd} = \sum_{i\in [0,M],\, i \text{ odd}} a_i X^i,\\ P=P_{even} + P_{odd},

    or, in a slightly more general formulation

    Pe(X2):=P(X)+P(−X)2=∑i∈[0,M+12−1]a2i(X2)i,Po(X2)=P(X)−P(−X)2X=∑i∈[0,M+12−1]a2i+1(X2)i,P(X)=Pe(X2)+X⋅Po(X2).P_{e}(X^2) := \frac{P(X)+P(-X)}{2} = \sum_{i\in [0,\tfrac{M+1}{2}-1]} a_{2i} (X^2)^i,\\ P_{o}(X^2) = \frac{P(X)-P(-X)}{2X} = \sum_{i\in [0,\tfrac{M+1}{2}-1]} a_{2i+1} (X^2)^i,\\ P(X)=P_{e}(X^2) + X\cdot P_{o}(X^2).
  1. Commitment: The prover commits to PeP_e and PoP_o which are polynomials of degree <M/2< M/2.
  1. Folding: The prover combines PeP_e and PoP_o into a new polynomial for the next round: given a random scalar supplied by the verifier, say α\alpha, the prover defines a new polynomial
    P′(X):=Pe(X)+α⋅Po(X).P'(X):=P_e(X) + \alpha\cdot P_o(X).

    This new polynomial has roughly half the degree of P(X)P(X).

  1. Recursion: The process repeats. At each step ii, the prover commits to a polynomial of degree <M/2i< M/2^i, receives a challenge α_i\alpha\_i, and constructs Pi+1′P'_{i+1} of degree <M/2i+1< M/2^{i+1}.
  1. Final Check: After log⁡M\log M rounds, we end up with a polynomial of degree 0. The prover sends this constant, and the verifier can check it.
  1. (The verifier then performs a few random queries on the committed Merkle trees from each round to ensure the folding process was done correctly at those points.)

Key Remark: We can employ an FFT/NTT approach, like considering the Cooley–Tukey FFT algorithm during the recursion.

  • The FFT approach can be applied only if:
    • we work with polynomials of length which is a power of 22, and
    • by fixing a cyclic subgroup H=(ω)≤Fp×H=(\omega)\leq \mathbb{F}_p^\times of the invertible elements of the finite field we are employing, in fact, we look at evaluations of the form:
      P′(ω)=Pe(ω2)+α⋅Po(ω2).P'(\omega)=P_{e}(\omega^2) + \alpha\cdot P_{o}(\omega^2).

This FFT-like approach is highly efficient only if

  • the finite field Fp\mathbb{F}_p of prime cardinality pp is associated with a (so-called) smooth prime, that is, ∣F×∣=p−1|\mathbb{F}^\times| = p-1 is divisible by a high power of 22, and
  • HH has order exactly this power (or is close to it).

Example:

  • https://en.wikipedia.org/wiki/Fermat_number, numbers of the form 22n+12^{2^n}+1, but only known primes (3, 5, 17, 257, and 65537),
  • https://en.wikipedia.org/wiki/Proth_prime, primes of the form p=k⋅2n+1p=k\cdot 2^n + 1, with k<2nk<2^n, e.g.:
    • the BabyBear prime p=15⋅227+1p = 15 \cdot 2^{27} + 1, or
    • the Goldilocks prime p=264−232+1=(232−1)⋅232+1p = 2^{64} - 2^{32} + 1 = (2^{32} -1)\cdot 2^{32} + 1.
  • Non-example: Mersenne primes, primes of the form p=2n−1p=2^n-1 are not suitable.

Main issue: We must stick to a precise form of primes. There is a trade-off between easy arithmetic and highly efficient FFT (or FRI).

Elliptic curve STARK and Circle STARK

Let’s abstract a little

In the actual implementation of the Split-and-Fold technique we consider a cyclic subgroup H=(ω)≤Fp×H=(\omega)\leq \mathbb{F}_p^\times of order ∣H∣=2n|H|=2^n, what is happening is that we are considering the squaring group homomorphism:

(∙)2 ⁣:H→H,ω↦ω2.(\bullet)^2\colon H \to H, \quad \omega \mapsto \omega^2.

In particular,

  • This homomorphism is a 2-to-1 group endomorphism ((−ω)2=ω2(-\omega)^2=\omega^2),
  • whose image is a smaller subgroup H′H' of order 2n/2=2n−12^n/2 = 2^{n-1},

and this is actually everything that we need in order to split the polynomial in even and odd coefficients and proceed in a recursive fashion.

Question: can we replace HH with another group and avoid trade-offs with the field arithmetic?

Abstraction

The FFT can be generalized to any group GG of order 2k2^k as long as we can define an efficiently computable 2-to-1 endomorphism ϕ ⁣:G→G\phi\colon G \to G.

  • For Elliptic Curves: The group GG is the set of points on the curve. We can find special curves that have an efficient 2-to-1 endomorphism (a type of isogeny). This map plays the role of the squaring map, allowing the divide-and-conquer strategy to work.
  • For Circle STARKs: The circle curve x2+y2=1x^2+y^2=1 is chosen precisely because it possesses an extremely simple and fast 2-to-1 endomorphism, making the generalized FFT highly performant.

The core idea is that the FFT algorithm is not fundamentally about multiplication and powers of two, but about this recursive structure enabled by a 2-to-1 map.

Main change of paradigm: we work with algebraic geometry codes, rather than with Reed-Solomon codes over Fp\mathbb{F}_p, and considering cosets evaluations (that is, P′(ω)P'(\omega)) becomes more delicate in general.

Elliptic Curve STARKs (Ideas)

We work with:

  • the group GG of the set of points on an elliptic curve E/FpE/\mathbb{F}_p,
  • a suitable 2-to-1 isogeny (certain special curves have an efficient 2-to-1 isogeny, see §4.1 in [BSCKL22]).

The two papers, [BSCKL21] and [BSCKL22], deal with Elliptic Curve Fast Fourier Transform (ECFFT).

Pros:

  • ECFFT works over any finite field.

Cons:

  • A standard curve (like secp256k1) is not optimal for general-purpose STARK performance. These curves were designed for properties like pairing-friendliness or specific security levels, not for STARK efficiency. Their structure is not ideal for the FFT-like algorithms, and their underlying fields are often too large for fast CPU arithmetic.
  • Rather heavy on Algebraic Geometry (algebraic geometry codes evaluated on sub-groups of elliptic curves, that is, elliptic curve codes, on divisors).

Circle STARK (Circle FFT)

Instead of forcing a STARK onto a pre-existing, non-optimal curve, why don't we design a new curve that is perfectly and deliberately optimized for STARK performance?

cit. U. Haböck

We work with:

  • the group GG of the set of points on the circle curve x2+y2=1x^2+y^2=1 over Fp\mathbb{F}_p,
    G:={(x,y)∈Fp:x2+y2=1 in Fp},G:=\{(x,y)\in\mathbb{F}_p: x^2+y^2=1 \text{ in } \mathbb{F}_p\},

    with group operation

    (x0,y0)⋅(x1,y1):=(x0⋅x1−y0⋅y1,x0⋅y1+y0⋅x1),(x_0, y_0) \cdot (x_1, y_1) := (x_0 \cdot x_1 − y_0 \cdot y_1, x_0 \cdot y_1 + y_0 \cdot x_1),
  • the squaring morphism
(x,y):=(x,y)⋅(x,y)=(x2−y2,2⋅x⋅y)=(2⋅x2−1,2⋅x⋅y).(x, y) := (x, y) \cdot (x, y) = (x^2 − y^2, 2 \cdot x \cdot y) = (2 \cdot x^2 − 1, 2 \cdot x \cdot y).

Note that:

  • The inverse is computed as −(x,y)=(x,−y)-(x,y) = (x,-y),
  • The circle group is cyclic because the map (x,y)⟼x+i⋅y(x, y) \longmapsto x + i \cdot y is a group homomorphism between GG and a multiplicative subgroup of the field extension Fp(i)\mathbb{F}_p(i), where i2=−1i^2=-1.
  • Recall that Fp(i)⊃Fp\mathbb{F}_p(i)\supset\mathbb{F}_p strictly if and only if p≡3(mod4)p\equiv 3 \pmod{4}; e.g. p=2n+1⋅t−1p = 2^{n+1}\cdot t − 1 for integers n,t≥1n, t \geq 1. These are the so-called CFFT-friendly primes.
  • If p≡3(mod4)p\equiv 3 \pmod{4}, the order of the circle group is ∣G∣=p+1|G|=p+1.

Circle Encoding

Let P(x,y)P(x,y) be a polynomial in two variables. The polynomial encoding in Circle STARKs is given considering such polynomials, or, more precisely, polynomials in

LN:={P∈Fp[x,y]/(x2+y2−1):deg⁡(P)≤N/2}.\mathcal{L}_N:=\{P\in \mathbb{F}_p[x,y]/(x^2+y^2-1) : \deg(P)\leq N/2\}.

Note that, by repeatedly substituting y2=1−x2y^2 =1-x^2 in any polynomial P(x,y)∈Fp[x,y]/(x2+y2−1)P(x,y)\in \mathbb{F}_p[x,y]/(x^2+y^2-1), we can write

P(x,y)=P0(x)+y⋅P1(x),P(x,y)=P_0(x)+y\cdot P_1(x),

and if P∈LNP\in \mathcal{L}_N, then deg⁡(P0)≤N/2\deg(P_0)\leq N/2 and deg⁡(P1)≤N/2−1\deg(P_1)\leq N/2-1.

The collection of monomials

1,x,…,xN/2,y,y⋅x,…,y⋅xN/2−1 1,x,\ldots,x^{N/2}, y, y\cdot x,\ldots,y\cdot x^{N/2-1}

spans a basis of LN\mathcal{L}_N.

Circle Split-and-Fold Technique

⚠️

The procedure here is simplified to convey the basic ideas, but one should fix an evaluation domain (full group) and then consider projection maps to iterate quotient groups; see §4 in [HLP24] for full details.

Now, given a polynomial P(x,y)∈LNP(x,y)\in \mathcal{L}_N we can compute the Circle Split-and-Fold Technique as follows:

  1. We write P(x,y)P(x,y) as P(x,y)=P0(x)+y⋅P1(x),P(x,y)=P_0(x)+y\cdot P_1(x), by setting
    P0(x)=P(x,y)+P(x,−y)2,P1(x)=P(x,y)−P(x,−y)2⋅y;P_0(x)=\frac{P(x,y)+P(x,-y)}{2},\quad P_1(x)=\frac{P(x,y)-P(x,-y)}{2\cdot y};

    (note that we are considering the involution given by (x,y)→(x,−y)(x,y)\to (x,-y)).

  1. We batch the two polynomials together into P′(x):=P0(x)+α⋅P1(x)P'(x):=P_0(x) + \alpha\cdot P_1(x).
  1. We consider, for P′(x)P'(x) the decomposition
    P0′(π(x))=P′(x)+P′(−x)2,P1′(π(x))=P(x)−P(−x)2⋅x,P'_0(\pi(x))=\frac{P'(x)+P'(-x)}{2},\quad P_1'(\pi(x))=\frac{P(x)-P(-x)}{2\cdot x},

    for π(x)=2⋅x2−1\pi(x) = 2\cdot x^2−1, and hence

    P′(x)=P0′(π(x))+x⋅P1′(π(x)).P'(x) = P'_0(\pi(x)) + x\cdot P'_1(\pi(x)).
📢

For a nice explicit example, see https://hackmd.io/@nsoroush/Byxb9vlWxg#Circle-STARKs by Nil!

A few final considerations about Circle STARK

If we go back to STARK, we have two conflicting requirements for our prime pp:

  1. Fast Field Arithmetic (CPU Efficiency): For the prover to be fast, the underlying arithmetic (addition, multiplication) must be fast:
    1. This is best achieved when pp is close to a machine word size (like 2322^{32} or 2642^{64}), as operations can be performed with single CPU instructions.
    1. Primes with a special form, like Mersenne primes (2k−12^k-1), are even better because the expensive "modulo pp" operation can be replaced with extremely fast bit-shifting and additions.
  1. FFT-Friendly Domain (Cryptographic Requirement): For the FFT to work, the multiplicative group of the field, Fp×\mathbb{F}_p^\times, must have an order p−1p-1 that is divisible by a large power of two.

Example:

  • A "Goldilocks" Prime: The prime p=264−232+1p = 2^{64} - 2^{32} + 1 is a perfect example of a prime that satisfies both. It fits in a 6464-bit word, making arithmetic fast on modern CPUs. Its group order is p−1=264−232=232(232−1)p-1 = 2^{64} - 2^{32} = 2^{32}(2^{32}-1), which is divisible by 2322^{32}. It's "just right" for traditional STARKs.

Non-example:

  • The M31 Dilemma: The Mersenne prime p=231−1p = 2^{31}-1 (M31) is extremely fast for CPU arithmetic. However, its group order is p−1=231−2=2(230−1)p-1 = 2^{31}-2 = 2(2^{30}-1). It is only divisible by 212^1, making it completely unsuitable for a large FFT.

The Circle STARK Innovation

Circle STARKs resolve this conflict by separating the concerns.

  • Field (for speed): Use the ultra-fast M31 field (Fp\mathbb{F}_p where p=231−1p = 2^{31} - 1) for all base arithmetic.
  • Domain (for FFTs): Define a new domain using the points (x,y)(x, y) on the circle curve x2+y2=1x^2 + y^2 = 1. This group of points has order 2312^{31} which is a structure needed for an efficient FFT, even though the underlying field does not.

What’s next (maybe in another talk)?

Laurent STARKs, whose main point is to use Laurent polynomials (allow negative terms in a polynomial expansion ∑i=−mnaiXi\sum_{i=-m}^{n}a_iX^i) in order to encode polynomial constraints arising from STARK polynomial representations in a more efficient way.

References

Papers

  • [BSBHR18a] - Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon inter- active 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.
  • [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 Computational 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.
  • [HLP24] - Haböck, U., Levit, D., & Papini, S. (2024). Circle STARKs. Cryptology ePrint Archive, Paper 2024/278. Retrieved from https://eprint.iacr.org/2024/278

Talks and notes

Appendix: addendum after the talk

Stwo and complexity

Circle STARKs Efficiency (From [HLP24])

As seen above, Circle STARKs leverage a specialized Fast Fourier Transform (FFT) on the circle curve over the Mersenne prime field (p=231−1p=2^{31}−1). This approach provides a speedup over traditional FFTs used with other primes.

  • Speed-up Factor: Preliminary benchmarks show a 1.4x speed-up for the Circle FFT (CFFT) over the M31 prime compared to a traditional FFT over the Babybear prime (p=231−227+1p=2^{31}−2^{27}+1).
  • Computational Cost: The CFFT and its inverse for a domain of size N=2nN=2^n have a computational complexity of O(Nlog⁡N)O(N\log N). More specifically, the cost is around

    N⋅nN⋅n additions and N⋅n/2N⋅n/2 multiplications.

  • Proof Size: The size of the trace domain is N=2nN=2^n, and the evaluation domain size is M=2B+nM=2^{B+n} for a blow-up factor of 2B2^B. The resulting proof size and verification complexity are comparable to classical STARKs.

Stwo (“STARK Two”, pronounced “Stoo”)

Stwo is a next-generation STARK prover that incorporates the efficiency gains of Circle STARKs and other advancements to achieve a significant speedup. While Circle STARKs focused on a new algebraic structure for a specific class of fields, Stwo is a full-fledged prover implementation (https://github.com/starkware-libs/stwo?tab=readme-ov-file) that leverages these ideas.

From the StarkWare blog (15th Mar 2024): Stwo is the name of Starknet’s next-generation prover, set to augment, speed up, and ultimately replace the current prover – Stone (“STARK One”). Stwo’s efficiency, anticipated at 100x the speed of Stone, will use Circle STARKs over M31 (explained above) but also a lot more. Additional innovations include the “log-up” and sum-check protocols (as in this recent work by Haböck and Papini), working simultaneously with several polynomials of different degrees (“mixed degrees”) and new infrastructure for encoding circuits and virtual machines. So, while the expected improvement in STARK proving scale is roughly 100x over Stone, expect additional benefits such as more agile adoption of new compilers and virtual machines, leading to higher development velocity. Read here for more information about Stwo.

Stwo Prover Efficiency

The key performance metrics of Stwo are primarily driven by the underlying M31 field arithmetic.

  • FFT Runtime: Benchmarks of Stwo's CFFT show significant performance gains on modern hardware. For an FFT size of 2202^{20} with a single thread, the M31 CFFT takes about 1700 ms, whereas the Babybear FFT takes about 2384 ms, confirming the 1.4x speed-up ratio.
  • Multi-threading: With 8 threads, the performance gap narrows or disappears due to memory bandwidth becoming the bottleneck. For instance, at an FFT size of 2202^{20}, both M31 CFFT and Babybear FFT take around 1400 ms.
  • Overall Prover Speed: Stwo boasts a complete prover that is significantly faster than its predecessors, StarkEx and Stone, achieving an order of magnitude speedup for typical proof sizes. This speed is attributed to the combination of the CFFT, M31 field optimizations, and architectural improvements.
  • Complexity: Stwo maintains the quasi-linear complexity of STARKs, with prover runtime being roughly O(Tlog⁡T)O(T \log T), where TT is the trace length.

These numbers demonstrate a clear advantage for Stwo and Circle STARKs, driven by the strategic choice of the M31 prime and careful implementation of the CFFT algorithm.

References:

  • [PH23] - Papini, S., & Haböck, U. (2023). Improving logarithmic derivative lookups using GKR. Cryptology ePrint Archive, Paper 2023/1284. Retrieved from https://eprint.iacr.org/2023/1284.
  • [HLP24] - Haböck, U., Levit, D., & Papini, S. (2024). Circle STARKs. Cryptology ePrint Archive, Paper 2024/278. Retrieved from https://eprint.iacr.org/2024/278

Fourier transform: Polynomial encoding in Circle STARK (an idea)

Classical Fourier transform and its inverse over a field

Given a function f:H→Ff: H \to \mathbb{F} over a multiplicative subgroup HH of a finite field F\mathbb{F} with generator gg and order NN, the (discrete) Fourier transform is defined as:

f^(gk)=1N∑j=0N−1f(gj)⋅g−k⋅jfor k=0,…,N−1.\hat{f}(g^k) = \frac{1}{N} \sum_{j=0}^{N-1} f(g^j) \cdot g^{-k \cdot j} \quad \text{for } k=0, \dots, N-1.

The inverse Fourier transform is the unique polynomial P(X)P(X) of degree less than NN that interpolates ff over HH. Its values are computed from the Fourier transform coefficients f^\hat{f} as:

f(gi)=∑k=0N−1f^(gk)⋅gk⋅ifor all i=0,…,N−1.f(g^i) = \sum_{k=0}^{N-1} \hat{f}(g^k) \cdot g^{k \cdot i} \quad \text{for all } i=0, \dots, N-1.

Circle Fourier Transform (brief idea)

Similarly, instead of indexing the values of our polynomial over H<F×H<\mathbb{F}^\times, we index them over the points of the circle, obtaining a function f:C(F)→Ff:C(\mathbb{F})\to \mathbb{F}.

Again in a similar fashion, we want to write a function f:C(F)→Ff:C(\mathbb{F})\to \mathbb{F}, and the CFFT process involves the evaluation of the monomials

{1,x,…,xN/2,y,y⋅x,…,y⋅xN/2−1}=:{pi(x,y)}i=0,N\Big\{ 1,x,\ldots,x^{N/2}, y, y\cdot x,\ldots,y\cdot x^{N/2-1}\Big\}=:\Big\{ p_i(x,y)\Big\}_{i=0,N}

(in ) on the circle point gg, in order to have (naively and slightly wrong, but it provides the correct intuition behind) a formula which resembles

f(gi)=∑k=0Nf^(gk)⋅pk(gi)for all i=0,…,N−1.f(g^i) = \sum_{k=0}^{N} \hat{f}(g^k) \cdot p_k(g^{i}) \quad \text{for all } i=0, \dots, N-1.

References:

  • [HLN23] - Haböck, U., Lubarov, D., & Nabaglo, J. (2023). Reed-Solomon Codes over the Circle Group. Cryptology ePrint Archive, Paper 2023/824. Retrieved from https://eprint.iacr.org/2023/824.
  • [HLP24] - Haböck, U., Levit, D., & Papini, S. (2024). Circle STARKs. Cryptology ePrint Archive, Paper 2024/278. Retrieved from https://eprint.iacr.org/2024/278
Inline comments

Block text: The verifier can then request and check specific values from the tree using a Merkle path.

  • Luca Dall'Ava
    Recall that that is based on an IOPP.

Block text: in fact

  • Luca Dall'Ava
    E.g. prove it by induction on integer points.

Block text: These are the so-called CFFT-friendly primes.

  • Luca Dall'Ava
    Note: otherwise we are back with dealing with Fp\mathbb{F}_p arithmetic!
  • Luca Dall'Ava
    Note that a priori one needs to work with a field extension of Fp\mathbb{F}_p.

Block text: repeatedly substituting y2=1−x2y^2 =1-x^2 in any polynomial

  • Luca Dall'Ava
    A polynomial of the form P(x,y)=∑i∈[0,N],j∈[0,M]ai,jxiyjP(x,y)=\sum_{i\in [0,N], j\in [0,M]} a_{i,j}x^iy^j can be written as P(x,y)=∑i∈[0,N],j∈[0,M]ai,jxiyj=∑i∈[0,N],j∈[0,M/2]ai,jxi(y2)j+y⋅∑i∈[0,N],j∈[0,M/2]ai,jxi(y2)jP(x,y)=\sum_{i\in [0,N], j\in [0,M]} a_{i,j}x^iy^j=\sum_{i\in [0,N], j\in [0,M/2]} a_{i,j}x^i(y^2)^j + y\cdot \sum_{i\in [0,N], j\in [0,M/2]} a_{i,j}x^i (y^2)^j, then substitute y2=1−x2y^2=1-x^2 everywhere.

Block text: https://hackmd.io/@nsoroush/Byxb9vlWxg#Circle-STARKs

  • Luca Dall'Ava
    By Nil Soroush!:)

Block text: Fourier transform: Polynomial encoding in Circle STARK (an idea)

  • Luca Dall'Ava
    Disclaimer: this is my take on the matter.

Block text: Key point: LDE = low degree extension (see LDE (Low Degree Extension): Helps encode our sequence. ).

  • Luca Dall'Ava
    It makes use of cosets: groups G>HG> H, g∈G−Hg\in G-H, coset is g⋅Hg\cdot H, which is not necessarily a subgroup.

Block text: Reed-Solomon codewords

  • Luca Dall'Ava
    See, for example, the Wikipedia page.

Block text: algebraic geometry codes

Block text: at most quasilinear

  • Luca Dall'Ava
    SNARKs allow the prover is allowed to even have a prohibitively expensive complexity.