STARK (Scalable Transparent Argument of Knowledge) is a kind of proof system introduced in 2018 by Eli Ben-Sasson and his colleagues, offering better scalability and transparency than traditional SNARK systems. STARK operates by transforming complex computations into arithmetic circuits, which are then represented as polynomial evaluation problems. To conceal intermediate results during computation, polynomial commitments are employed while allowing the verifier to sample and check these results. By applying low-degree extensions, intricate computations are reduced to verifying low-degree polynomials, before the efficient interactive proof protocol, FRI, is used to check if a polynomial has a low-degree. This technology has broad applications in enabling privacy preservation and verifiable computations.
A notable advancement in STARK protocol design is the shift from employing large finite fields to smaller ones, enhancing the protocol's efficiency and practicality. By operating within smaller finite fields, arithmetic operations are streamlined, leading to faster proof generation and verification times. These smaller fields align more closely with the architecture of modern processors, allowing for optimized performance and reduced computational overhead, therefore making STARKs a more viable option for real-world applications, such as scaling blockchain systems and enabling privacy-preserving computations.
Algorithmically, the complexity of multiplication grows quadratically with the number of bits involved. Consequently, reducing field size from 64 bits to 32 bits theoretically promises a fourfold performance boost. Nevertheless, the architecture of modern processors, equipped with vectorized 32-bit instructions, can amplify these gains. By capitalizing on these hardware optimizations, practical implementations often surpass the predicted speedup, demonstrating that the transition to smaller fields yields significant performance benefits in real-world scenarios. Mersenne primes are primes of the form \(2^{n}-1\). The modular reduction operation in Mersenne primes is compute-friendly:
\[ k \equiv k \pmod{2^{n}} + \left\lfloor \frac{k}{2^{n}} \right\rfloor \pmod{2^{n}-1} \]
which in pseudo-code can be written as:
\[ k = (k\ \&\ p) + (k \gg n) \]
Therefore, researchers have identified the Mersenne prime \(2^{31}-1\) as a particularly efficient choice for arithmetic operations within STARK protocols when executed on standard 32-bit CPU and GPU architectures. This prime number's alignment with the native word size of these processors enables optimized performance for fundamental arithmetic operations. Recognizing this advantage, efforts have been dedicated to integrating Mersenne prime \(2^{31}-1\) into STARK protocol design, aiming to improve the overall efficiency and speed of proof generation and verification while leveraging the computational capabilities of modern hardware.
A field is considered smooth when its order minus one can be factored into a large power of two and a small odd co-factor. Formally, this is expressed as
\[ p-1 = 2^{m} \cdot c \]
where p is the field order, \(m\) is a sufficiently large integer, and \(c\) is an odd number. The smoothness property is crucial for the efficient operation of traditional STARK protocols, which rely on algorithms like Fast Fourier Transform (FFT) and the FRI verifier. Unfortunately, Mersenne primes, which are of the form \(2^{n}-1\), inherently lack this smoothness property. As a result, standard STARK constructions cannot be directly applied to fields defined by Mersenne primes. To overcome this limitation, a more sophisticated protocol known as Circle STARK has been developed. By incorporating additional algebraic structures, Circle STARKs are capable of handling non-smooth fields whose prime order is such that \(p=3\pmod{4}\), thereby expanding the range of prime numbers suitable for STARK-based applications.
We use STARKs to generate a proof that attests to the integrity of a computation and a verifier can verify it very fast. The steps to generate a STARK proof consist of the following 9 steps.
1.Representation of Computation: Express the computation as a system of polynomial equations over a finite field \(F\):
2.Obtaining the Execution Trace: Compute the execution trace \(T\), a matrix of field elements in \(F\), as the result of executing the program.
3. Interpolation of Trace Columns: For each column \( T_{j} \) of the execution trace \( T \), interpolate a univariate polynomial \( f_{j}(x) \in F[x] \) such that \( f_{j}(i) = T_{j}[i] \) for all \( i \in D \), where \( D \) is a smooth domain.
4.Evaluation and Merkle Tree Construction: Evaluate each interpolated polynomial \(f_{j}(x)\) at points in a larger, disjoint domain \(D_{0}\) to obtain a set of evaluations \(e_{j} = \{f_{j}(x)\ |\ x \in D_{0}\}. Construct a Merkle tree \(M_{j}\) from the elements of \(e_{j}\).
5.Constraint Enforcement: For each constraint \(P_{i}(x)\) in the AIR, construct a polynomial \(Q_{i}(x) = P_{i}(f_{1}(x), f_{2}(x), \dots, f_{n}(x))\).
6.Division and Constraint Verification: For each \(Q_{i}(x)\), compute \(R_{i}(x) = Q_{i}(x) / Z_{D}(x)\), where \(Z_{D}(x)\) is the vanishing polynomial of the domain \(D\). The constraint \(P_{i}(x)\) is satisfied if and only if \(R_{i}(x)\) is a polynomial.
7.Random Linear Combination: Given a set of polynomials \( \{R_{1}(x), R_{2}(x), \dots, R_{m}(x)\} \), the verifier selects random challenge values \(r_{1}, r_{2}, \dots, r_{m} \in F\) and computes the linear combination \(R(x) = \sum r_{i} \cdot R_{i}(x)\).
8.Evaluation and Merkle Tree Construction: Evaluate the polynomial \(R(x)\) at points in \(D_{0}\) to obtain a set of evaluations \(e_{R} = \{R(x)\ |\ x \in D_{0}\}. Construct a Merkle tree \(M_{R}\) from the elements of \(e_{R}\).
9.Degree Bound Verification: Apply the FRI protocol to the set of evaluations \(e_{R}\) to verify that the corresponding polynomial has degree at most \(n\), where \(n\) is the expected degree of \(R(x)\).
Given evaluations of a polynomial \(A(x)\) over a finite field \(F\), prove that the degree of \(A(x)\) is less than or equal to \(d = 2^{n}\).
Polynomial Splitting:
Random Linear Combination:
Iterative Reduction:
Degree Bound Verification:
If the degree of \(A(x)\) is indeed less than or equal to \(d\), the process outlined above will always produce a constant polynomial at the end of the iterations. Conversely, if the degree of \(A(x)\) is greater than \(d\), there is a high probability that the random linear combinations introduced in each iteration will expose a degree mismatch at some point, leading to a rejection of the proof. Besides, the security of the FRI protocol relies on the hardness of distinguishing a low-degree polynomial from a random function. The use of random challenges in each iteration strengthens the protocol's security by making it computationally infeasible for a malicious prover to construct a fraudulent proof.
Let \(F_{p}\) be a finite field of prime order \(p\). Define the circle group \(G\) as:
\[ G = \{(x, y) \in F_{p}^{2} \mid x^{2} + y^{2} = 1\} \]
The group operation \(+\) on \(G\) is defined as:
\[ (x_{1}, y_{1}) + (x_{2}, y_{2}) = (x_{1} \cdot x_{2} - y_{1} \cdot y_{2}, x_{1} \cdot y_{2} + x_{2} \cdot y_{1}) \]
The doubling operation on \(G\) is defined as:
\[ 2 \cdot (x, y) = (2 \cdot x^{2} - 1, 2 \cdot x \cdot y) \]
Circle FRI Protocol: Given a function \(F: G \rightarrow F_{p}\), we define the following:
\[ f_{0}: F_{p} \rightarrow F_{p} \text{, such that } f_{0}(x) = \frac{F(x, y) + F(x, -y)}{2} \]
\[ f_{1}: F_{p} \rightarrow F_{p} \text{, such that } f_{1}(x) = \frac{F(x, y) - F(x, -y)}{2 \cdot y} \]
A random linear combination is formed as:
\[ F'(x) = f_{0}(x) + r \cdot f_{1}(x) \]
For the next iteration, we define:
\[ f'_{0}(x) = \frac{F'(x^{2}) + F'( -x^{2})}{2} \]
\[ f'_{1}(x) = \frac{F'(x^{2}) - F'( -x^{2})}{2 \cdot x^{2}} \]
The process continues recursively, reducing the domain size at each step.
Key Differences from Classical STARK:
Additional Considerations:
The Fast Fourier Transform (FFT) is an efficient algorithm to compute the Discrete Fourier Transform (DFT). It exploits the symmetry properties of the DFT matrix to reduce the computational complexity from \(O(N^{2})\) to \(O(N\log{N})\). While there are many FFT algorithms, the most common is the Cooley-Tukey algorithm, which recursively divides the DFT into smaller DFTs until the problem size becomes trivial.
More formally, given a sequence of \(N\) complex numbers \(\{x_{0}, x_{1}, \dots, x_{N-1}\}\), where \(N\) is a power of \(2\), the FFT proceeds as follows:
Decomposition:
Recursive DFT:
Combination:
The time complexity of the Cooley-Tukey algorithm can be expressed as a recurrence relation: \(T(N) = 2 \cdot T(N/2) + O(N)\). Solving this recurrence relation yields \(T(N) = O(N \log{N})\).
FFT significantly accelerates polynomial multiplication and interpolation operations. By transforming polynomials from the coefficient representation to the value representation, FFT reduces the complexity of multiplication from a quadratic to a linear operation. This is achieved by evaluating the polynomials at specific points, performing element-wise multiplication on the resulting values, and then applying the inverse FFT to recover the coefficients of the product polynomial. Similarly, interpolation, the process of finding a polynomial that passes through a given set of points, can be efficiently computed using the FFT by converting the problem into a polynomial multiplication.
Let \(F_{p}\) be a finite field of prime order \(p\). The circle group \(G_{p}\) is defined as the set of points \((x, y)\) in \(F_{p}^{2}\) satisfying the equation \(x^{2} + y^{2} = 1\). The group operation on \(G_{p}\), denoted by \(\cdot\), is defined as:
\[ (x_{0}, y_{0}) \cdot (x_{1}, y_{1}) = (x_{0} \cdot x_{1} - y_{0} \cdot y_{1}, x_{0} \cdot y_{1} + x_{1} \cdot y_{0}) \]For certain prime fields, such as \(F_{2^{31}-1}\), the circle group \(G_{p}\) has a large order, specifically \(2^{31}\) elements. A generator \((g_{x}, g_{y}) \in G_{p}\) can be found such that every element in \(G_{p}\) can be expressed as a power of \((g_{x}, g_{y})\) under the group operation.
The FFT can be adapted to the circle group, resulting in a "Circle FFT". However, the underlying mathematical objects are different from the classical FFT. Instead of operating on polynomials over a finite field, the Circle FFT operates on functions defined over the circle group, which belong to a Riemann-Roch space. This space consists of functions that can be represented as polynomials modulo the ideal generated by the circle equation \(x^{2} + y^{2} - 1\).
Let \(G_{p}\) be the circle group defined over a finite field \(F_{p}\). For an \(n\)-point Circle FFT, we define a basis of polynomials \(\{b_{k}(x, y)\}\) for \(k = 0, \dots, n-1\), where \(n = 2^{m}\) for some positive integer \(m\). The basis polynomials are constructed recursively using a binary representation of the index \(k\):
\[ k = \sum_{i=0}^{m-1} j_{i} \cdot 2^{i}\text{, where }j_{i} \in \{0, 1\} \] \[ b_{k}(x, y) = y^{j_{0}} \cdot v_{1}(x)^{j_{1}} \cdot v_{2}(x)^{j_{2}} \dots v_{m-1}(x)^{j_{m-1}} \]where \( v_{0}(x) = 1 \), \( v_{i}(x) = 2 \cdot x^{2} - 1 \) for \( i > 0 \).
A polynomial \(p(x, y)\) over \(G_{p}\) can be expressed as a linear combination of the basis polynomials:
\[ p(x, y) = \sum_{k=0}^{n-1} c_{k} \cdot b_{k}(x, y) \]where \( c_{k} \in F_{p} \) are the coefficients. The Circle FFT evaluates \( p(x, y) \) at a set of \( n \) points in \( G_{p} \).
The Circle FFT employs a divide-and-conquer approach similar to the classical FFT. At each stage, a polynomial \(p(x, y)\) is split into two functions:
\[ f_{0}(x) = \frac{p(x, y) + p(x, -y)}{2} \] \[ f_{1}(x) = \frac{p(x, y) - p(x, -y)}{2y} \]The functions \(f_{0}(x)\) and \(f_{1}(x)\) are then evaluated at the square roots of the evaluation points of the previous stage. This process continues recursively until the base case of a 2-point FFT is reached.
In classical STARKs, the vanishing polynomial is defined as:
\[ Z_{n}(x) = x^{n} - 1 \]The roots of \(Z_{n}(x)\) are the \(n\)-th roots of unity, which form a cyclic group under multiplication. These roots of unity are typically used as evaluation points for polynomials in the STARK protocol.
In Circle STARKs, the vanishing polynomials are defined recursively:
\[ v_{1}(x) = x \] \[ v_{i}(x) = 2 \cdot v_{i-1}(x)^{2} - 1 \]These vanishing polynomials are specifically designed to align with the structure of the circle group. The roots of these polynomials are related to the points on the circle group, and they play a crucial role in the constraint satisfaction checks within the Circle STARK protocol.
The vanishing polynomials in both classical and Circle STARKs are essential for enforcing constraints and verifying the correctness of computations within their respective protocols.
Circle STARKs have demonstrated exceptional performance by capitalizing on the computational efficiency of finite fields defined by Mersenne primes. While these fields lack the smoothness property required by traditional STARKs, Circle STARKs effectively circumvent this limitation by operating within the structure of a circle group. Despite the inherent differences between the two approaches, Circle STARKs maintain a strong resemblance to their classical counterparts, with most complexities abstracted away from developers. Combined with optimized lookup mechanisms like LogUp and GKR, Circle STARKs have the potential to significantly enhance the performance of general-purpose zero-knowledge virtual machines.
References:
The rich text element allows you to create and format headings, paragraphs, blockquotes, images, and video all in one place instead of having to add and format them individually. Just double-click and easily create content.
A rich text element can be used with static or dynamic content. For static content, just drop it into any page and begin editing. For dynamic content, add a rich text field to any collection and then connect a rich text element to that field in the settings panel. Voila!
Headings, paragraphs, blockquotes, figures, images, and figure captions can all be styled after a class is added to the rich text element using the "When inside of" nested selector system.
STARK (Scalable Transparent Argument of Knowledge) is a kind of proof system introduced in 2018 by Eli Ben-Sasson and his colleagues, offering better scalability and transparency than traditional SNARK systems. STARK operates by transforming complex computations into arithmetic circuits, which are then represented as polynomial evaluation problems. To conceal intermediate results during computation, polynomial commitments are employed while allowing the verifier to sample and check these results. By applying low-degree extensions, intricate computations are reduced to verifying low-degree polynomials, before the efficient interactive proof protocol, FRI, is used to check if a polynomial has a low-degree. This technology has broad applications in enabling privacy preservation and verifiable computations.
A notable advancement in STARK protocol design is the shift from employing large finite fields to smaller ones, enhancing the protocol's efficiency and practicality. By operating within smaller finite fields, arithmetic operations are streamlined, leading to faster proof generation and verification times. These smaller fields align more closely with the architecture of modern processors, allowing for optimized performance and reduced computational overhead, therefore making STARKs a more viable option for real-world applications, such as scaling blockchain systems and enabling privacy-preserving computations.
Algorithmically, the complexity of multiplication grows quadratically with the number of bits involved. Consequently, reducing field size from 64 bits to 32 bits theoretically promises a fourfold performance boost. Nevertheless, the architecture of modern processors, equipped with vectorized 32-bit instructions, can amplify these gains. By capitalizing on these hardware optimizations, practical implementations often surpass the predicted speedup, demonstrating that the transition to smaller fields yields significant performance benefits in real-world scenarios. Mersenne primes are primes of the form \(2^{n}-1\). The modular reduction operation in Mersenne primes is compute-friendly:
\[ k \equiv k \pmod{2^{n}} + \left\lfloor \frac{k}{2^{n}} \right\rfloor \pmod{2^{n}-1} \]
which in pseudo-code can be written as:
\[ k = (k\ \&\ p) + (k \gg n) \]
Therefore, researchers have identified the Mersenne prime \(2^{31}-1\) as a particularly efficient choice for arithmetic operations within STARK protocols when executed on standard 32-bit CPU and GPU architectures. This prime number's alignment with the native word size of these processors enables optimized performance for fundamental arithmetic operations. Recognizing this advantage, efforts have been dedicated to integrating Mersenne prime \(2^{31}-1\) into STARK protocol design, aiming to improve the overall efficiency and speed of proof generation and verification while leveraging the computational capabilities of modern hardware.
A field is considered smooth when its order minus one can be factored into a large power of two and a small odd co-factor. Formally, this is expressed as
\[ p-1 = 2^{m} \cdot c \]
where p is the field order, \(m\) is a sufficiently large integer, and \(c\) is an odd number. The smoothness property is crucial for the efficient operation of traditional STARK protocols, which rely on algorithms like Fast Fourier Transform (FFT) and the FRI verifier. Unfortunately, Mersenne primes, which are of the form \(2^{n}-1\), inherently lack this smoothness property. As a result, standard STARK constructions cannot be directly applied to fields defined by Mersenne primes. To overcome this limitation, a more sophisticated protocol known as Circle STARK has been developed. By incorporating additional algebraic structures, Circle STARKs are capable of handling non-smooth fields whose prime order is such that \(p=3\pmod{4}\), thereby expanding the range of prime numbers suitable for STARK-based applications.
We use STARKs to generate a proof that attests to the integrity of a computation and a verifier can verify it very fast. The steps to generate a STARK proof consist of the following 9 steps.
1.Representation of Computation: Express the computation as a system of polynomial equations over a finite field \(F\):
2.Obtaining the Execution Trace: Compute the execution trace \(T\), a matrix of field elements in \(F\), as the result of executing the program.
3. Interpolation of Trace Columns: For each column \( T_{j} \) of the execution trace \( T \), interpolate a univariate polynomial \( f_{j}(x) \in F[x] \) such that \( f_{j}(i) = T_{j}[i] \) for all \( i \in D \), where \( D \) is a smooth domain.
4.Evaluation and Merkle Tree Construction: Evaluate each interpolated polynomial \(f_{j}(x)\) at points in a larger, disjoint domain \(D_{0}\) to obtain a set of evaluations \(e_{j} = \{f_{j}(x)\ |\ x \in D_{0}\}. Construct a Merkle tree \(M_{j}\) from the elements of \(e_{j}\).
5.Constraint Enforcement: For each constraint \(P_{i}(x)\) in the AIR, construct a polynomial \(Q_{i}(x) = P_{i}(f_{1}(x), f_{2}(x), \dots, f_{n}(x))\).
6.Division and Constraint Verification: For each \(Q_{i}(x)\), compute \(R_{i}(x) = Q_{i}(x) / Z_{D}(x)\), where \(Z_{D}(x)\) is the vanishing polynomial of the domain \(D\). The constraint \(P_{i}(x)\) is satisfied if and only if \(R_{i}(x)\) is a polynomial.
7.Random Linear Combination: Given a set of polynomials \( \{R_{1}(x), R_{2}(x), \dots, R_{m}(x)\} \), the verifier selects random challenge values \(r_{1}, r_{2}, \dots, r_{m} \in F\) and computes the linear combination \(R(x) = \sum r_{i} \cdot R_{i}(x)\).
8.Evaluation and Merkle Tree Construction: Evaluate the polynomial \(R(x)\) at points in \(D_{0}\) to obtain a set of evaluations \(e_{R} = \{R(x)\ |\ x \in D_{0}\}. Construct a Merkle tree \(M_{R}\) from the elements of \(e_{R}\).
9.Degree Bound Verification: Apply the FRI protocol to the set of evaluations \(e_{R}\) to verify that the corresponding polynomial has degree at most \(n\), where \(n\) is the expected degree of \(R(x)\).
Given evaluations of a polynomial \(A(x)\) over a finite field \(F\), prove that the degree of \(A(x)\) is less than or equal to \(d = 2^{n}\).
Polynomial Splitting:
Random Linear Combination:
Iterative Reduction:
Degree Bound Verification:
If the degree of \(A(x)\) is indeed less than or equal to \(d\), the process outlined above will always produce a constant polynomial at the end of the iterations. Conversely, if the degree of \(A(x)\) is greater than \(d\), there is a high probability that the random linear combinations introduced in each iteration will expose a degree mismatch at some point, leading to a rejection of the proof. Besides, the security of the FRI protocol relies on the hardness of distinguishing a low-degree polynomial from a random function. The use of random challenges in each iteration strengthens the protocol's security by making it computationally infeasible for a malicious prover to construct a fraudulent proof.
Let \(F_{p}\) be a finite field of prime order \(p\). Define the circle group \(G\) as:
\[ G = \{(x, y) \in F_{p}^{2} \mid x^{2} + y^{2} = 1\} \]
The group operation \(+\) on \(G\) is defined as:
\[ (x_{1}, y_{1}) + (x_{2}, y_{2}) = (x_{1} \cdot x_{2} - y_{1} \cdot y_{2}, x_{1} \cdot y_{2} + x_{2} \cdot y_{1}) \]
The doubling operation on \(G\) is defined as:
\[ 2 \cdot (x, y) = (2 \cdot x^{2} - 1, 2 \cdot x \cdot y) \]
Circle FRI Protocol: Given a function \(F: G \rightarrow F_{p}\), we define the following:
\[ f_{0}: F_{p} \rightarrow F_{p} \text{, such that } f_{0}(x) = \frac{F(x, y) + F(x, -y)}{2} \]
\[ f_{1}: F_{p} \rightarrow F_{p} \text{, such that } f_{1}(x) = \frac{F(x, y) - F(x, -y)}{2 \cdot y} \]
A random linear combination is formed as:
\[ F'(x) = f_{0}(x) + r \cdot f_{1}(x) \]
For the next iteration, we define:
\[ f'_{0}(x) = \frac{F'(x^{2}) + F'( -x^{2})}{2} \]
\[ f'_{1}(x) = \frac{F'(x^{2}) - F'( -x^{2})}{2 \cdot x^{2}} \]
The process continues recursively, reducing the domain size at each step.
Key Differences from Classical STARK:
Additional Considerations:
The Fast Fourier Transform (FFT) is an efficient algorithm to compute the Discrete Fourier Transform (DFT). It exploits the symmetry properties of the DFT matrix to reduce the computational complexity from \(O(N^{2})\) to \(O(N\log{N})\). While there are many FFT algorithms, the most common is the Cooley-Tukey algorithm, which recursively divides the DFT into smaller DFTs until the problem size becomes trivial.
More formally, given a sequence of \(N\) complex numbers \(\{x_{0}, x_{1}, \dots, x_{N-1}\}\), where \(N\) is a power of \(2\), the FFT proceeds as follows:
Decomposition:
Recursive DFT:
Combination:
The time complexity of the Cooley-Tukey algorithm can be expressed as a recurrence relation: \(T(N) = 2 \cdot T(N/2) + O(N)\). Solving this recurrence relation yields \(T(N) = O(N \log{N})\).
FFT significantly accelerates polynomial multiplication and interpolation operations. By transforming polynomials from the coefficient representation to the value representation, FFT reduces the complexity of multiplication from a quadratic to a linear operation. This is achieved by evaluating the polynomials at specific points, performing element-wise multiplication on the resulting values, and then applying the inverse FFT to recover the coefficients of the product polynomial. Similarly, interpolation, the process of finding a polynomial that passes through a given set of points, can be efficiently computed using the FFT by converting the problem into a polynomial multiplication.
Let \(F_{p}\) be a finite field of prime order \(p\). The circle group \(G_{p}\) is defined as the set of points \((x, y)\) in \(F_{p}^{2}\) satisfying the equation \(x^{2} + y^{2} = 1\). The group operation on \(G_{p}\), denoted by \(\cdot\), is defined as:
\[ (x_{0}, y_{0}) \cdot (x_{1}, y_{1}) = (x_{0} \cdot x_{1} - y_{0} \cdot y_{1}, x_{0} \cdot y_{1} + x_{1} \cdot y_{0}) \]For certain prime fields, such as \(F_{2^{31}-1}\), the circle group \(G_{p}\) has a large order, specifically \(2^{31}\) elements. A generator \((g_{x}, g_{y}) \in G_{p}\) can be found such that every element in \(G_{p}\) can be expressed as a power of \((g_{x}, g_{y})\) under the group operation.
The FFT can be adapted to the circle group, resulting in a "Circle FFT". However, the underlying mathematical objects are different from the classical FFT. Instead of operating on polynomials over a finite field, the Circle FFT operates on functions defined over the circle group, which belong to a Riemann-Roch space. This space consists of functions that can be represented as polynomials modulo the ideal generated by the circle equation \(x^{2} + y^{2} - 1\).
Let \(G_{p}\) be the circle group defined over a finite field \(F_{p}\). For an \(n\)-point Circle FFT, we define a basis of polynomials \(\{b_{k}(x, y)\}\) for \(k = 0, \dots, n-1\), where \(n = 2^{m}\) for some positive integer \(m\). The basis polynomials are constructed recursively using a binary representation of the index \(k\):
\[ k = \sum_{i=0}^{m-1} j_{i} \cdot 2^{i}\text{, where }j_{i} \in \{0, 1\} \] \[ b_{k}(x, y) = y^{j_{0}} \cdot v_{1}(x)^{j_{1}} \cdot v_{2}(x)^{j_{2}} \dots v_{m-1}(x)^{j_{m-1}} \]where \( v_{0}(x) = 1 \), \( v_{i}(x) = 2 \cdot x^{2} - 1 \) for \( i > 0 \).
A polynomial \(p(x, y)\) over \(G_{p}\) can be expressed as a linear combination of the basis polynomials:
\[ p(x, y) = \sum_{k=0}^{n-1} c_{k} \cdot b_{k}(x, y) \]where \( c_{k} \in F_{p} \) are the coefficients. The Circle FFT evaluates \( p(x, y) \) at a set of \( n \) points in \( G_{p} \).
The Circle FFT employs a divide-and-conquer approach similar to the classical FFT. At each stage, a polynomial \(p(x, y)\) is split into two functions:
\[ f_{0}(x) = \frac{p(x, y) + p(x, -y)}{2} \] \[ f_{1}(x) = \frac{p(x, y) - p(x, -y)}{2y} \]The functions \(f_{0}(x)\) and \(f_{1}(x)\) are then evaluated at the square roots of the evaluation points of the previous stage. This process continues recursively until the base case of a 2-point FFT is reached.
In classical STARKs, the vanishing polynomial is defined as:
\[ Z_{n}(x) = x^{n} - 1 \]The roots of \(Z_{n}(x)\) are the \(n\)-th roots of unity, which form a cyclic group under multiplication. These roots of unity are typically used as evaluation points for polynomials in the STARK protocol.
In Circle STARKs, the vanishing polynomials are defined recursively:
\[ v_{1}(x) = x \] \[ v_{i}(x) = 2 \cdot v_{i-1}(x)^{2} - 1 \]These vanishing polynomials are specifically designed to align with the structure of the circle group. The roots of these polynomials are related to the points on the circle group, and they play a crucial role in the constraint satisfaction checks within the Circle STARK protocol.
The vanishing polynomials in both classical and Circle STARKs are essential for enforcing constraints and verifying the correctness of computations within their respective protocols.
Circle STARKs have demonstrated exceptional performance by capitalizing on the computational efficiency of finite fields defined by Mersenne primes. While these fields lack the smoothness property required by traditional STARKs, Circle STARKs effectively circumvent this limitation by operating within the structure of a circle group. Despite the inherent differences between the two approaches, Circle STARKs maintain a strong resemblance to their classical counterparts, with most complexities abstracted away from developers. Combined with optimized lookup mechanisms like LogUp and GKR, Circle STARKs have the potential to significantly enhance the performance of general-purpose zero-knowledge virtual machines.
References:
