Paper 2024/278

Circle STARKs

Ulrich Haböck, Polygon Labs
David Levit, StarkWare
Shahar Papini, StarkWare

Traditional STARKs 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. The Elliptic Curve FFT (ECFFT, Part I and II) 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^2 + y^2 = 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^{31} − 1$, which has been recently advertised in the IACR eprint 2023:824, our preliminary benchmarks indicate a speed-up by a factor of $1.4$ compared to a traditional STARK using the Babybear prime $p = 2^{31} − 2^{27} + 1$.

Note: This version corrects a mistaken reference to the Galois FFT, and fixes a wrong citation of the weighted correlated agreement theorem.

Available format(s)
Cryptographic protocols
Publication info
STARKFFTReed-Solomon CodesAlgebraic Geometry Codes
Contact author(s)
uhaboeck @ polygon technology
david @ starkware co
spapini @ starkware co
2024-07-05: revised
2024-02-19: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Ulrich Haböck and David Levit and Shahar Papini},
      title = {Circle {STARKs}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/278},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.