zk-STARKs: FRI protocol
Jumping right into the second part of your ZK-STARK series, we're focusing on the FRI protocol and its goal of proving the knowledge of a low-degree polynomial. This protocol is a crucial element in the ZK-STARK framework.
In the first post on the ZK-STARK series, we:
Defined the problem of proving the knowledge of the 12th number in the Lucas sequence.
Arithmetized the problem by building a trace and converting it to a polynomial.
Extended the domain of the polynomial by adding redundancy points.
Based on the extended domain, we introduced constraints which then formed a single composition polynomial.
Since the composition polynomial is another, more sophisticated representation of the original problem and its solution, if we are to prove that we know this polynomial, we are automatically proving that we know the 12th number of the Lucas sequence.
If you haven’t read the previous article, I am encouraging you to do so.
FRI theory
FRI stands for Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In more detail:
Fast: FRI has sublinear-time verification. This means that the verifier doesn't need to check the entire polynomial to be convinced that the prover doesn’t lie. Instead, the verifier can check a small portion of the function (randomly chosen) and still be confident about the overall correctness.
Reed-Solomon: refers to Reed-Solomon codes that use redundancy and polynomials to recover lost pieces of data. We can recover the polynomial of degree with only n+1 points. In the FRI context, the Reed-Solomon code means a polynomial.
Interactive Oracle Proof (IOP): In an IOP, the prover sends an oracle (a kind of "black-box" function) to the verifier, who can then query this oracle to decide whether to accept or reject the proof. The interaction can occur in multiple rounds, where in each round, the prover sends an oracle based on the verifier's previous queries.
Proximity: In the FRI protocol the prover doesn’t prove that he knows any polynomial which intersects a certain set of points. There may be more than one polynomial that meets the criteria. The prover should know the polynomial of the degree n, but in fact, knowing a polynomial of degree close to n is good enough. Proximity refers to this closeness in degree with the given polynomial.
If the prover doesn’t need to prove low-degreness of the polynomial entirely, but only approximately, the first questions that come to mind are: what is a low degree, how close is close enough, and why.
Low degree: in a STARK low degree depends on the degree of the composition polynomial and the length of the trace. In our case, the low degree is sixteen (the degree of the extended domain polynomial). For a more complex problem, it can be a few orders of magnitude more.
Closeness: for polynomials p and f, distance is defined as the number of points that both f and p do not match on. If the distance between two functions is small, the closeness is high, and vice versa. Small in this situation depends on the degree of both polynomials.
The concept of proximity is not new and has been explored before in probabilistically checkable proofs of proximity (CPPs). The CPPs however get inefficient and less sound when the number of points to check increases. FRI protocol addresses these issues. Let’s explore how.
Vitalik’s STARK
Before we go deeper into the construction of FRI, let’s start with a simple example of a STARK presented by Vitalik in his article on FRI. This will help us conceptually grasp what the whole thing is about. The part I’m referring to is available in the section “A First Look at Sublinearity” and can be summarized as follows:
The goal is to prove that a large set of points (say, 1 billion) all lie on a polynomial of a certain degree (e.g., less than 1,000,000) without having to check every single point.
To achieve this, Vitalik introduces the concept of a bivariate polynomial. This polynomial is constructed such that when evaluated with specific values of x and y, it matches the original polynomial f(x). Specifically, g(x,x1000) = f(x).
The prover evaluates g(x,y) over a large square. The diagonal of this square represents the values of g(x,y) that match the values of f(x).
Source: https://vitalik.eth.limo/general/2017/11/22/starks_part_2.html Instead of checking every point, the verifier selects a few rows and columns from this square. For each, he asks for a sample of points, ensuring that at least one point from each sample lies on the diagonal.
The verifier checks that the points match the original data (using Merkle branches) and correspond to a polynomial of the desired degree.
Conclusion: By checking these samples, the verifier gets a statistical proof that:
Most rows and columns are populated by points on the desired polynomial.
The diagonal line is mostly on the desired polynomial.
This sampling and verification process allows the verifier to be reasonably confident that most points on the diagonal correspond to the desired polynomial without having to check every single point. This is where the sublinearity comes in: the verifier can achieve this confidence with a computational effort that grows much slower than the size of the dataset.
In this example, the prover has to evaluate the polynomial g(x,y) on every single point, which is not very efficient. A better prover efficiency can be achieved with the application of modular math, which Vitalik presents in the subsequent section.
In short, instead of evaluating g(x,y) at every point in a large square, the prover evaluates it at points in a smaller grid and then uses modular arithmetic to extrapolate the values in the larger grid. This approach significantly reduces the prover’s computational complexity.
FRI practice
Here we are approaching the FRI protocol. In Vitalik’s examples, while the prover’s computational complexity was reduced, the verifier still had a significant amount of work to do. The verifier had to check a large number of points to ensure that they lie on the correct polynomial, which is computationally intensive.
To address this issue, STARKs introduce the concept of folding. The idea is to use the FRI protocol within itself to reduce the verifier's workload.
Instead of the verifier checking a large number of points directly, the prover generates proof that a smaller number of points lie on the correct polynomial. The verifier then only needs to check this smaller set of points and the STARK proof, significantly reducing their computational complexity.
This approach reduces the verifier's complexity from quadratic to logarithmic in terms of the size of the data. This is a substantial efficiency gain, making the protocol much more practical for large datasets.
To see how this plays out we will use the composition polynomial calculated based on the polynomial constraints from the previous article. The constraints are:
Recall that if the division on the right-hand side of the f polynomials leaves no remainder (i.e., the result is another polynomial), then the constraints are met. Let's represent the polynomials in the denominators on the right-hand with z.
The polynomial p(x), constructed within the trace's extended domain mod 97, is defined as follows:
Now, with the below piece of code, we can calculate the constraint polynomials. Here for the first two constraints:
pip install galois
import galois
# Define the finite field GF(97)
GF = galois.GF(97)
# Define the polynomial p(x) with the coefficients
coeffs = [90, 89, 73, 70, 78, 91, 75, 33, 25, 51, 41, 41, 69, 43, 72, 21]
p_x_galois = galois.Poly(coeffs, field=GF)
# Define the generator g and its powers for the constraints
g = 5
g4 = pow(g, 4, 97)
g5 = pow(g, 5, 97)
# Define the numerators for the constraints
numerator_f0 = p_x_galois - GF(7)
numerator_f1 = p_x_galois - GF(11)
# Define the denominators for the constraints
denominator_f0 = galois.Poly([1, -GF(g4)], field=GF)
denominator_f1 = galois.Poly([1, -GF(g5)], field=GF)
# Perform the polynomial division for f0(x), f1(x), f2(x), and f3(x)
quotient_f0, remainder_f0 = divmod(numerator_f0, denominator_f0)
quotient_f1, remainder_f1 = divmod(numerator_f1, denominator_f1)
# Print the results
print("Galois implementation:")
print(f"f0(x) quotient:", quotient_f0)
print(f"f0(x) remainder:", remainder_f0)
print(f"f1(x) quotient:", quotient_f1)
print(f"f1(x) remainder:", remainder_f1)
To finalize the process, let’s calculate the composition polynomial using the α values from the verifier. The composition polynomial is denoted as:
The alpha values are: α0 = 39, α1 = 93, α2 = 47, and α3 = 28. The resulting composition polynomial:
This polynomial c(x) represents the sum of the constraint polynomials f0, f1, f2, and f3, each multiplied by their respective α values. It also has been normalized to have degree 15, which allows us to have a more efficient folding mechanism that will come in handy when using the FRI protocol.
Now, after the commitment by the prover, we finally have arrived to the point when we can put the FRI protocol in action.
FRI querying
In the querying stage, the verifier's role is to check if the prover's polynomial is of a low degree and is related to the trace. Here's a breakdown of how it works:
Constraint verification
The verifier picks random points in a domain larger than subgroup G. This is done to preserve the zero-knowledge aspect.
At each point, the prover evaluates the trace polynomial and the constraint polynomials
By calculating:
\(z_i(x) = p(x) - g^i \cdot f(x)\)and finding them to be vanishing polynomials, the verifier confirms that the constraint polynomials are related to the trace polynomial.
To illustrate, consider the first constraint:
The verifier picks a random number, say 54, and compares if both sides of the below equation match. If yes, the verification is successful.
Let’s substitute. The left-hand side, calculated by the prover:
And the right-hand side, calculated by the verifier:
Since both sides are equal, the verification is successful, and the constraint holds. Note that the calculations are performed mod 97.
This process is repeated for other values and constraints. Importantly, the verifier only knows the right-hand side evaluations, preserving zero-knowledge. This step also ensures the prover cannot simply invent numbers, as the verifier's calculation must align.
Finally, with the constraints verified, the verifier confirms the polynomial's relation to the trace. Now is the time to confirm its low-degree nature.
Low-degree testing
Low-degree testing is vital for the soundness of the protocol. Without it, the prover could potentially use a high-degree polynomial that matches specific points on the composition polynomial c(x) to pass the verifier's checks. This is possible because a high-degree polynomial, due to its many oscillations, can be adjusted to pass through given points, unlike a low-degree polynomial.
The testing is performed with the so-called FRI operator. The FRI operator is instrumental in reducing the complexity of proving that a polynomial is of low degree. This is important because, in another way, the prover would have to send the entire polynomial or evaluations of the polynomial over some domain, which would be very costly.
Here's how the FRI operator works:
The operator first splits a given polynomial c(x) into even and odd parts, so:
\(c(x) = g_0(x^2) + xh_0(x^2)\)
In our example. The even part:
\(g_0(x^2) = 30x^7 + 74x^6 + 52x^5 + 88x^4 + 25x^3 + 37x^2 + 56x + 4\)
And the odd part:
\(h_0(x^2) = 56x^7 + 2x^6 + 32x^5 + 45x^4 + 47x^3 + 70x^2 + 63x + 44\)
The prover receives a random value α from the verifier.
A new polynomial c1(x) is created using a linear combination of g0(x) and h0(x), where α is used as a coefficient for the odd part. This reduces the polynomial's degree by half.
\(c_1(x)=g0(x)+αh0(x)\)This process is repeated with each iteration halving the degree of the polynomial. For instance, after the second iteration with α=72, the polynomial becomes c2(x), and so on.
After a logarithmic number of iterations, this process results in a constant or a very low-degree polynomial. In our case for α=69, the polynomial:
\(c_3(x) = 17x^3 + 29x^2 + 22x + 69\)After the third iteration and for α=75 we get:
\(c_4(x) = 58x + 56\)With each round, the prover commits to the newly formed polynomial using a Merkle Tree.
The verifier then checks if the FRI operator has been correctly applied by mirroring the process and aiming to arrive at the same constant. In our case, 50.
The verifier selects a point z (e.g. 109) from a larger domain, ensuring it’s not part of the subgroup G.
The prover evaluates the composition polynomial at z and −z, returning values c(z)=27 and c(−z)=−53.
With c(z) and c(−z), the verifier can find g0 and h0 by calculating:
\(c(z) = g_0(z^2) + zh_0(z^2); \text{ where } g_0(z^2) = 27\)\(c(-z) = g_0(z^2) - zh_0(z^2); \text{ where } h_0(z^2) = 53\)Using these values, the verifier computes the formula:
\(c_1(z^2) = g_0(z^2) + \alpha_0 h_0(z^2)\)and requests the prover to provide the corresponding Merkle path for c.
The verifier continues the process for the next iteration by querying:
\(c_1(-z^2) \text{ and solving for } g_1(z^n) \text{ and } h_1(z^n)\)The verifier can compute now:
\(c_2(z^n) = g_2(z^n) + \alpha_2 h_2(z^n)\)The verifier repeats this process for subsequent iterations, each time using a previously chosen scalar α and solving for the components of the polynomial.
The verifier then checks if the final value matches the constant provided by the prover in the commitment round. This confirmation validates the proof.
Since both parties arrived at the constant value of 50, the verifier is convinced that the polynomial c(x) is of a low degree.
The below code runs the perspective of the prover and the verifier. I encourage you to run the code to see what the process for both parties looks like at each step.
import galois
# Define the finite field GF(97)
GF = galois.GF(97)
# Define the initial polynomial p(x)
coeffs_p = [56, 30, 2, 74, 32, 52, 45, 88, 47, 25, 70, 37, 63, 56, 44, 4]
p = galois.Poly(coeffs_p[::-1], field=GF) # Coefficients are in reverse order for galois.Poly
# Define x as a polynomial
x = galois.Poly([1, 0], field=GF) # x
# The alpha values used in each iteration
alpha_values = [72, 69, 75, 83]
print("")
# Function to apply the FRI operator, using alpha values from the list
def apply_fri_operator_verbose(p, alpha_values, GF):
for alpha in alpha_values:
# Splitting p into even and odd coefficients
coeffs_even = [p.coeffs[i*2] if i*2 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)]
coeffs_odd = [p.coeffs[i*2 + 1] if i*2 + 1 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)]
# Creating even and odd polynomials
g = galois.Poly(coeffs_even, field=GF)
h = galois.Poly(coeffs_odd, field=GF)
print(f"Prover applying FRI Operator with alpha = {alpha}")
print(f"Even part (g) = {g}")
print(f"Odd part (h) = {h}")
# Apply the FRI operator
p = g + alpha * h
print(f"Resulting polynomial = {p}\n")
return p
# Apply the FRI operator with the list of alpha values
final_result = apply_fri_operator_verbose(p, alpha_values, GF)
print(f"Final Prover Result: {final_result}\n")
# Function to simulate the verifier's computation in each FRI iteration
def verifier_fri_computation_verbose(p, alpha_values, GF, z):
for alpha in alpha_values:
# Splitting p into even and odd coefficients
coeffs_even = [p.coeffs[i*2] if i*2 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)]
coeffs_odd = [p.coeffs[i*2 + 1] if i*2 + 1 < len(p.coeffs) else GF(0) for i in range((len(p.coeffs) + 1) // 2)]
# Creating even and odd polynomials
g = galois.Poly(coeffs_even, field=GF)
h = galois.Poly(coeffs_odd, field=GF)
# Apply the FRI operator
p_next = g + alpha * h
# Evaluate at z and -z (square z in each iteration)
z_squared = z**2 % GF.order
result_z = p_next(z_squared)
result_minus_z = p_next(-z_squared % GF.order)
print(f"Verifier iteration with alpha = {alpha}")
print(f"p(z) = {result_z}, p(-z) = {result_minus_z}")
print(f"g = {g}, h = {h}")
print(f"Next polynomial p_next = {p_next}\n")
p = p_next # Update polynomial for next iteration
z = z_squared # Update z for next iteration
return p(z) # Final result
# Random point z for verification (excluding the subgroup G)
z = 109
# Verifier's computation
verifier_result = verifier_fri_computation_verbose(p, alpha_values, GF, z)
print(f"Final Verifier Result: {verifier_result}")Decommitments
Let’s summarize where in the protocol the prover makes Merkle tree commitments and provides them to the verifier.
After the prover calculates p(x) that maps inputs G to the trace and creates the composition polynomial c(x), the prover commits to both polynomials and sends the roots to the verifier.
During the low-degree testing, the prover applies the FRI operator to reduce the polynomial’s degree. After each transformation, the prover commits to the polynomial and sends its root to the verifier. In our case, the prover sends commitments to the polynomials c1, c2, and c3.
Upon confirming that the Merklee roots provided by the prover are the same as the ones computed by the verifier the verification ends. Based on the constraints checks, low-degree testing, and decommitment processes the verifier can confirm if the claim made by the prover in the original statement is true.
Summary
We've made it! Now, let's take a moment to review the entire protocol, together with the parts we covered in the previous article:
Definition of the Problem
The prover and verifier agree on a computational integrity (CI) statement and the corresponding polynomial constraints. In our case, the CI statement is the Lucas sequence up to the 19th number.
Arithmetization
The prover constructs a polynomial p(x) that maps a subgroup G to the trace, which is a sequence of integers in the CI statement.
The prover extends the polynomial p(x) to a larger domain.
The prover combines the constraints with p(x) to create a constraint polynomials f(x).
The prover forms the composition polynomial p(x) from f(x).
The verifier queries the prover for specific values of p(x) and c(x), along with Merkle paths.
Low-Degree Testing (FRI protocol)
The prover folds polynomial c(x), reducing its degree.
The verifier queries the prover for specific folded polynomial values and Merkle paths at each stage of FRI.
Summary and Validation:
After the querying rounds, the verifier assesses the information provided by the prover. If the verifier's checks align with the prover's committed values and transformations, the CI statement is validated. This concludes the proof.
I must admit that my journey through KZG and FRI has been a rollercoaster. I had moments of doubt, but I'm proud to have made it this far!
From my perspective, FRI is more complex than KZG, particularly regarding (de)commitments, which aren't necessary for KZG. This added complexity, including computational aspects, is balanced by the elimination of the need for a trusted setup. Moreover, from what I've heard, FRI is more suitable for recursive proofs (so proofs of proofs), but I’m currently not experienced and knowledgeable enough to have any say on this.
In the next article about zero-knowledge proofs, I plan to better understand the concept of folding. This topic is currently generating significant buzz in the field, playing a crucial role in enhancing the efficiency of the proofs. Meanwhile, I want to express my gratitude for your time in reading this. Your attention means a great deal to me!
Sources
Starkware, STARK101
Aleksander Berentsen, Jeremias Lenzi, Remo Nyffenegger, A Walkthrough of a Simple zk-STARK
Vitalik Buterin, STARKs, Part II: Thank Goodness It's FRI-day