Search Extension

API/RSS

Social

Vitalik’s latest article: Inside Circle STARKs

Vitalik Buterin

24-07-24 11:11

Read this article in 15 Minutes

AI summary

View the summary

Original title: Exploring circle STARKs

Original author: Vitalik Buterin,

Original translator: Kurt Pan, XPTY

This article assumes that you are familiar with the basics of how SNARKs and STARKs work; if you are not, I recommend reading the first few sections of this article. Special thanks to Eli ben-Sasson, Shahar Papini, Avihu Levy and others at starkware for feedback and discussions.

· https://vitalik.eth.limo/general/2024/04/29/binius.html

· https://en.wikipedia.org/wiki/Karatsuba_algorithm

· https://polygon.technology/blog/plonky2-a-deep-dive

· https://blog.icme.io/small-fields-for-zero-knowledge/

This shift has already resulted in massive speedups in proofs, most notably Starkware being able to prove 620,000 Poseidon2 hashes per second on an M3 laptop. What this means in concrete terms is that, as long as we’re willing to trust Poseidon2 as part of the hash function, one of the hardest parts of building an efficient ZK-EVM is already efficiently solved. But how do these techniques work, and how are cryptographic proofs (which typically require large integers for security) constructed over these domains? And how do these protocols compare to more exotic constructions like Binius? This post will explore some of these subtleties, with a particular focus on a construction called Circle STARKs (implemented in Starkware’s stwo, Polygon’s plonky3, and my own python implementation), which have some unique properties designed to be compatible with efficient Mersenne31 domains.

Common Problems with Small Domains

One of the most important "tricks" when doing hash-based proofs (or really any kind of proofs) is to replace proving something about the underlying polynomial with proving something about the evaluation of the polynomial at a random point.

· https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic

There are two natural solutions to this problem:

· Perform multiple random tests

· Expand the domain

· https://www2.clarku.edu/faculty/djoyce/complex/mult.html

This implementation is not optimal (you can use Karatsuba Optimization), just showing the principle

Conventional FRI

· https://eccc.weizmann.ac.il/report/2017/134/

Circle FRI

· https://elibensasson.blog/why-im-excited-by-circle-stark-and-stwo/ These points obey the addition law, which may look familiar to you if you’ve studied trigonometry or complex number multiplication recently: - https://unacademy.com/content/cbse-class-11/study-material/mathematics/algebra-of-complex-numbers-multiplication/

From the second round onwards, the mapping changes:

Circle FFTs

· https://vitalik.eth.limo/general/2019/05/12/fft.html https://www.researchgate.net/publication/353344649_Elliptic_Curve_Fast_Fourier_Transform_ECFFT_Part_I_Fast_Polynomial_Algorithms_over_all_Finite_Fields From here, let’s get into some of the more esoteric details that will be different for someone implementing a circle STARK compared to a regular STARK. · https://eprint.iacr.org/2019/336 Vanishing Polynomials Reversing Bit Order Efficiency So circle STARKs are actually pretty close to optimal! Binius is even more powerful because it allows mixing and matching fields of different sizes, giving more efficient bit packing for everything. Binius also provides the option to perform 32-bit additions without the overhead of a lookup table. However, these gains come at the cost of (in my opinion) significantly higher theoretical complexity, whereas circle STARKs (and regular STARKs based on BabyBear) are conceptually quite simple.

Conclusion: What do I think of circle STARKs?

Circle STARKs don’t introduce a lot of additional complexity to developers compared to regular STARKs. In implementing, the three issues above are basically the only differences I see compared to regular FRI. The math behind the “polynomials” that Circle FRI operates on is quite counter-intuitive and takes a while to understand and appreciate. But it happens that this complexity is hidden so that developers don’t see it too much. The complexity of Circle math is encapsulated, not systematic.

Understanding circle FRI and circle FFT is also a good intellectual gateway to understanding other “exotic FFTs”: most notably the binary domain FFT, previously used in Binius and LibSTARK, but also more exotic constructions like the elliptic curve FFT, which uses a few-to-one mappings that play nicely with elliptic curve point operations.

By combining Mersenne31, BabyBear, and binary domain techniques like Binius, we do feel like we are approaching the limits of STARK "base layer" efficiency. At this point in time, I expect the forefront of STARK optimization to shift to the most efficient arithmeticization of primitives like hash functions and signatures (and optimizing these primitives themselves for this purpose), recursive constructions to unlock more parallelization, arithmeticization of virtual machines to improve developer experience, and other upper-level tasks.