Introduce to Circle Stark
Introduction
Zero-Knowledge Scalable Transparent Argument of Knowledge (zkSTARK) is an advanced cryptographic protocol that facilitates verifiable computations without revealing any underlying data. Developed as a scalable and transparent alternative to zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge), zkSTARKs eliminate the need for trusted setups, thereby enhancing security and trustworthiness. Leveraging the power of polynomial commitments and error-correcting codes, zkSTARKs provide robustness against quantum attacks and offer greater efficiency in terms of proof generation and verification. These characteristics make zkSTARKs highly suitable for applications in blockchain, privacy-preserving computations, and secure data sharing, where maintaining confidentiality and integrity is paramount.
In recent years, the most pivotal trend in STARK protocol design has been the transition from utilizing large finite fields to small finite fields. This shift is driven by several compelling advantages, notably the enhancement of computational efficiency and reduction in resource consumption. Working over small fields simplifies the arithmetic operations involved, leading to faster and more efficient proof generation. Additionally, small field operations are better suited for modern hardware, allowing for improved parallelization and optimization. This trend also addresses scalability concerns, enabling STARKs to handle larger datasets and more complex computations without compromising performance. As a result, the adoption of small fields has significantly contributed to the practical deployment and widespread acceptance of STARKs in various cryptographic applications, including blockchain scalability solutions and privacy-preserving protocols.
The Mersenne prime 2³¹ -1 is exceptionally well-suited for arithmetic operations on existing 32-bit CPU and GPU architectures due to its alignment with the native word size of these processors. As a prime number, it ensures that the arithmetic performed within this field is both efficient and secure, avoiding issues such as overflow or the need for complex modular reduction operations. The structure of 2³¹ -1 allows for fast modular arithmetic, which is crucial for cryptographic algorithms and other computational tasks that require frequent multiplications, additions, and reductions. This prime also enables optimizations in hardware implementations, taking full advantage of the 32-bit architecture’s capabilities, thus maximizing performance while minimizing the computational overhead. As a result, the use of the Mersenne prime 2³¹ -1 in small field arithmetic is not only convenient but also highly efficient, making it a preferred choice in various applications, including cryptography and error-correcting codes.
Despite the computational advantages offered by the Mersenne prime 2³¹-1, it is not considered a smooth prime. A field is classified as smooth if it satisfies the condition p-1 = 2^m ᐧ c, where m is sufficiently large and c is an odd number. The lack of smoothness in the Mersenne prime cannot be adapted in classical STARK, which rely on smoothness for FRI and FFT. To address this, the classical STARK would need to be upgraded to a Circle STARK, a variant designed to handle non-smooth fields by leveraging additional algebraic structures. Furthermore, the security requirements of STARK protocols cannot be met by the small field defined by 2³¹ -1. To ensure security, it is necessary to transition to an extension field when selecting random numbers. This adjustment helps maintain the necessary cryptographic properties, such as unpredictability and collision resistance, which are critical for the security of the STARK protocol. Thus, while the Mersenne prime offers convenience in some aspects, it necessitates careful modifications and enhancements to meet the stringent requirements of STARK.
Circle FRI
When constructing a classical STARK, the initial step involves arithmetization, which is the process of transforming an arbitrary computation problem into a mathematical equation where the variables and coefficients are represented as polynomials. This step is crucial as it converts the computational problem into a form that can be analyzed and verified within the framework of algebraic geometry. To demonstrate that the proposed solution is valid, one must prove that the values involved are indeed a fixed polynomial and that they adhere to a specified maximum degree. To achieve this, the random linear combination trick is employed iteratively. This technique involves creating random linear combinations of two polynomials. By repeatedly applying this method, the probability that a non-polynomial or incorrect polynomial would pass as valid becomes negligibly small, thereby ensuring the soundness of the proof. This approach is central to the STARK protocol’s ability to efficiently verify complex computations while maintaining rigorous consistency.
Consider a scenario where you have evaluations of a polynomial A(x) and need to prove that its degree is not greater than 2^{20}. To accomplish this, you can construct two auxiliary polynomials as follows:
B(x²) = A(x) + A(-x),
C(x²) = (A(x) — A(-x))/x.
The polynomial B(x²) isolates the even-degree coefficients of A(x), while C(x²) isolates the odd-degree coefficients. By forming a random linear combination
D = B + rC,
where r is a randomly chosen scalar, you combine these even and odd components in a way that retains the essential properties of A(x). Since B(x²) and C(x²) each have a degree not greater than 2¹⁹ if A(x) has a degree not greater than 2²⁰, the random combination D must also have a degree not greater than 2¹⁹.
When this process, part of the Fast Reed-Solomon Interactive Oracle Proof (FRI) protocol, is repeated iteratively — 20 times in this case — it ultimately reduces A(x) to a constant polynomial. This outcome provides a strong probabilistic guarantee that A(x) indeed has a degree not greater than 2²⁰, effectively proving the degree bound of the polynomial.
In Circle STARK, however, there is a significant structural variation compared to classical STARK protocols. Given a prime p, we can leverage a group of size p+1 that exhibits two-to-one properties analogous to those found in elliptic curves. Specifically, we utilize the set of points (x, y) satisfying the equation x² + y² = 1. For instance, consider the field defined by the Mersenne prime 2³¹ — 1. Within this field, the points (x, y) on the circle curve x² + y² = 1 form a group with well-defined addition and doubling operations. The addition of two points (x_1, y_1) and (x_2, y_2) is given by (x_1*x_2 — y_1*y_2, x_1*y_2 + x_2*y_1), while doubling a point (x, y) yields (2x² — 1, 2xy).
To construct the Circle FRI in the first round, we define two functions derived from a given function F(x, y). These functions are:
f_0(x) = (F(x,y)+F(x,-y))/2
f_1(x) = (F(x,y)-F(x,-y))/2y
Next, we form a random linear combination of f_0(x) and f_1(x) to obtain a one-dimensional function F(x) over a subset of the x-line:
F(x) = f_0(x) + rf_1(x)
where r is a randomly chosen scalar from the verifier.
In subsequent rounds, the mapping transforms as follows:
f_0(2x²-1) = (F(x)+F(-x))/2
f_1(2x²-1) = (F(x)-F(-x))/2x
This iterative process of redefining and combining functions ensures the preservation of the polynomial’s properties and reduces the problem dimensionally, similarly to classical STARK protocols but adapted to the circular structure.
Circle FFT
The classical Fast Fourier Transform (FFT) algorithm is a fundamental technique that efficiently converts a set of n evaluations of a polynomial with a degree not greater than n into the corresponding n coefficients of that polynomial. The classical FFT operates by recursively splitting the polynomial into two smaller polynomials, one representing the even-indexed coefficients and the other representing the odd-indexed coefficients. The FFT is then applied separately to these smaller polynomials, and their results are combined to reconstruct the full polynomial. This recursive approach significantly reduces the computational complexity, enabling rapid calculations that would otherwise be infeasible for large datasets.
When applied within the context of the FRI, the FFT takes a similar recursive path. However, instead of generating random linear combinations f_0 and f_1 at each step, the algorithm directly applies a half-sized FFT to both parts. The output of FFT(f_0) corresponds to the even coefficients, while FFT(f_1) corresponds to the odd coefficients, allowing for the polynomial’s reconstruction from its values.
In the context of Circle STARKs, the circle group also supports an FFT, but this variant operates over a different mathematical structure. Specifically, the objects manipulated by circle FFTs and circle FRI are not traditional polynomials; instead, they belong to what mathematicians refer to as a Riemann-Roch space. In this case, the Riemann-Roch space consists of polynomials considered modulo the circle equation x² + y² — 1 = 0. This means that any polynomial that includes a multiple of x² + y² — 1 is treated as equivalent to zero, effectively “reducing” the polynomial to a simpler form by substituting y² with 1 — x². Consequently, circle FFTs only allow for degree-1 powers of y; higher powers of y are replaced according to the circle relation.
A key implication of this structure is that the “coefficients” output by a circle FFT are not the usual monomials found in regular FRI (e.g., if regular FRI outputs [1,2,3,4], this represents P(x) = 4x³ + 3x² + 2x = 1). Instead, the coefficients in circle FFTs are expressed in a more complex basis specific to the circle structure. This basis might include terms such as
{1, y, x, xy, 2x² — 1, 2x²y — y, 2x³ — x, 2x³y — xy, 8x⁴ — 8x² + 1, …}.
The use of this non-standard basis reflects the underlying geometry of the circle, leading to a richer and more intricate set of coefficients that encode the polynomial’s behavior on the circle curve. This specialized FFT approach is crucial for efficiently handling computations within the circle group, enabling the practical application of Circle STARKs.
Other minor changes
Quotienting
In classical STARK protocols, proving that a polynomial P(x) equals a specific value y at a x-coordinate x typically involves constructing an auxiliary polynomial Q(x) defined as Q(x) =(𝑃−𝑦)/(𝑋−𝑥). The crux of the proof is to demonstrate that Q(x) is indeed a fixed polynomial, thereby confirming that the value of the P(x) at x is y.
In Circle STARKs, the methodology adapts to the circle group, where the structure is governed by the relation x² + y² = 1. Here, instead of proving the polynomial Q(x), the focus shifts to proving that a different quotient is a polynomial. Specifically, given a polynomial P(x, y), the goal is to prove that the quotient (P(x, y) — I(x, y))/L(x, y) is a fixed polynomial. In this context, I(x, y) is an interpolating polynomial that passes through two specific points on the circle, and L(x, y) is a line function that also passes through these two points on the circle.
Vanishing Polynomials
In classical STARKs, the vanishing polynomial is typically x^n — 1. This polynomial vanishes at all n-th roots of unity, which are the points where the polynomial evaluations are zero.
However, in Circle STARKs, the vanishing polynomial takes on a more complex form, reflecting the circular geometry of the problem space. The vanishing polynomials are defined recursively:
Z_1(x, y) =y,
Z_2(x, y)=x,
Z_{n+1}(x,y)=2Z_n(x,y)²-1.
The use of these vanishing polynomials ensures that the values of the polynomial are correct.
Reverse Bit Order
In STARK protocols, the evaluations of a polynomial are often arranged in a specific sequence known as reverse bit order. This ordering plays a critical role in the correctness of the FFT operations used within the protocol. For instance, consider a polynomial P(x) evaluated at various powers of a root of unity 𝜔, with the evaluations arranged in reverse bit order:
𝑃(1), 𝑃(𝜔^{𝑛/2}), 𝑃(𝜔^{𝑛/4}), 𝑃(𝜔^{3𝑛/4}), 𝑃(𝜔^{𝑛/8}), 𝑃(𝜔^{5𝑛/8}), 𝑃(𝜔^{3𝑛/8}), 𝑃(𝜔^{7𝑛/8}), 𝑃(𝜔^{𝑛/16})…
This arrangement is designed to facilitate the FFT’s recursive operations by aligning the data in a manner that reduces the number of operations needed to combine the even and odd parts of the polynomial efficiently.
In Circle STARKs, however, the folding structure introduces a different approach to organizing these evaluations. The process begins by leveraging the symmetry inherent in the circle group, where the first step involves grouping each point (x, y) with its mirror image (x, -y) on the circle. This pairing reflects the geometric symmetry of the circle.
In the second step, the structure takes advantage of further symmetries by grouping x with -x, effectively reflecting points across the origin. This step continues the process of folding the polynomial over the circle’s symmetrical axes.
In subsequent steps, the process becomes even more intricate. Points p and q are selected and grouped such that Q^i(p) = -Q^i(q), where Q^i(x) = 2x² — 1 represents a mapping applied i times. The result of this process is a systematic pairing of points that reflects the circle’s inherent symmetry at increasingly finer levels.
To adjust the reverse bit order for this unique folding structure, a subtle modification is required. Typically, reverse bit order involves simply reversing the order of the bits in the binary representation of an index. However, in Circle STARKs, this order must reflect the folding structure’s intricacies. Therefore, every bit in the binary representation of the index is reversed except for the last bit. The last bit is preserved because it carries special significance: it determines whether or not to flip the other bits. This subtle adjustment ensures that the ordering of the polynomial evaluations aligns with the folding operations, preserving the mathematical properties needed for the Circle STARK protocol’s correctness and efficiency.
Reference
- https://vitalik.eth.limo/general/2024/07/23/circlestarks.html
- https://shuklaayu.sh/blog/circle-starks/
- https://blog.lambdaclass.com/an-introduction-to-circle-starks/
- https://www.youtube.com/watch?v=NAhLYMysSdk
- https://eprint.iacr.org/2024/278
- https://github.com/starkware-libs/stwo
- https://medium.com/starkware/stwo-prover-the-next-gen-of-stark-scaling-is-here-f7429e764127