Decoding STARK: How to Prove Computation Accuracy Without Revealing the Data

Posted on: November 9, 2024 | Reading time: 31 minutes | Word count: 6424 words | Author: Dang Duong Minh Nhat

The FRI protocol (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) is revolutionizing the way we verify polynomials. With the growing need for efficient zero-knowledge proofs, particularly in blockchain and cryptography, FRI provides a way to verify that a given polynomial is close to a low-degree polynomial without needing to inspect the entire function. By recursively folding the polynomial and committing to its evaluations, FRI ensures both security and efficiency. This protocol is central to the emerging world of STARKs (Scalable Transparent Arguments of Knowledge), offering a fast, scalable solution to a longstanding problem in cryptographic verification.

In this blog, we dive into the inner workings of the FRI protocol, breaking down the commitment and query phases, the crucial recursive folding steps, and the importance of Merkle commitments. We’ll also explore how FRI ensures consistency via collinearity checks and how the verifier’s role is critical to maintaining the integrity of the proof. If you’re interested in how cutting-edge cryptography is making blockchain transactions more secure and scalable, this post is a must-read.

Table of Contents

Unlocking the Power of STARK: A Revolutionary Protocol for Scalable and Transparent Proofs

In today’s world of decentralized systems, verifiable computations are essential. Blockchain, for example, relies on proofs to ensure that transactions and computations are valid without revealing sensitive data. But traditional approaches to proof systems can become inefficient as the complexity of the computations increases. This is where STARKs (Scalable Transparent Arguments of Knowledge) come into play — offering a powerful and efficient way to verify computations without relying on trusted setups or sacrificing privacy.

In this post, we’ll dive into the core of the STARK protocol, exploring how it enables the scalable, transparent, and secure verification of computations. We’ll break down the protocol step by step and explain it in simple terms, while also showcasing some key mathematical formulas that power this groundbreaking technology.

What Is the STARK Protocol?

At its core, STARK is a cryptographic proof system that allows a prover to convince a verifier that a computation was performed correctly without revealing any details about the computation itself. The verification process is fast, transparent, and scalable, making it perfect for use in blockchain applications, privacy-preserving technologies, and more.

STARKs rely on a combination of polynomial commitments, interactive proofs, and arithmetic circuits to prove the correctness of a computation’s execution trace. Let’s break down how this works.

Why Does This Work?

The beauty of the STARK protocol lies in its scalability and transparency. By using polynomials, the prover can commit to large, complex computations without revealing sensitive data. The use of random challenges (from the verifier) ensures that the prover cannot cheat by modifying the trace. Additionally, since the STARK protocol does not rely on a trusted setup (as is the case with some other proof systems like SNARKs), it is transparent, making it more secure and accessible.

Moreover, the efficiency of the protocol is achieved by reducing the size of the commitment to the trace through polynomial commitment schemes, ensuring that the verifier can check the proof in logarithmic time relative to the size of the computation.

Key Advantages of STARKs

  1. Scalability: STARKs scale with the size of the computation, enabling verification of computations that involve huge amounts of data (e.g., large blockchain transactions, machine learning models, etc.).
  2. Transparency: The protocol does not require a trusted setup, ensuring that the system remains secure without relying on any secret parameters.
  3. Security: By leveraging polynomial commitments and interactive proofs, STARKs provide strong cryptographic guarantees that the prover cannot alter the trace.
  4. Efficiency: The protocol is designed to minimize the computational and communication costs, making it feasible for use in resource-constrained environments.

Arithmetization of the Execution Trace: Turning Computations into Polynomials

Introduction to Arithmetization

In the world of cryptographic proof systems, one of the most critical concepts is how to represent a computation in a way that allows us to verify its correctness without knowing the exact details of the computation itself. This process is known as arithmetization, and it’s a cornerstone of many modern cryptographic protocols, such as STARKs (Scalable Transparent Arguments of Knowledge).

But how exactly do we take a computation—such as an algorithm or program—and turn it into something we can verify using polynomials? The answer lies in the execution trace, which is a matrix that describes the state of a computation at each time step. Arithmetization is the process of transforming this execution trace into a polynomial representation that can be easily checked for correctness.

Let’s dive into how the execution trace is structured and how this transformation to polynomials works in the context of STARKs.

What Is an Execution Trace?

At a high level, the execution trace is a way to represent the sequence of states that a system (like a computer program or a blockchain transaction) goes through during its execution. The trace is represented as a matrix $T$, where each row corresponds to a time step in the computation, and each column corresponds to a specific variable or register that the system manipulates.

Trace Matrix Representation

Consider the following matrix $T$, where each element $T_{i,j}$ represents the value of the $j$-th register at the $i$-th time step:

$$ T = \begin{pmatrix} T_{1,1} & T_{1,2} & \dots & T_{1,w} \\ T_{2,1} & T_{2,2} & \dots & T_{2,w} \\ \vdots & \vdots & \ddots & \vdots \\ T_{T,1} & T_{T,2} & \dots & T_{T,w} \\ \end{pmatrix} $$

  • Each row $i$ represents the state of the system at time step $i$.
  • Each column $j$ corresponds to the value of a specific register (or variable) across all time steps.

The matrix $T$ has $T$ rows (one for each time step) and $w$ columns (one for each register or variable). This structure gives a snapshot of the entire computation process from start to finish.

Why Do We Need to Arithmetize the Trace?

The goal of arithmetization is to transform the trace $T$ into polynomials that can be used to verify the correctness of the computation. The reason for doing this is that polynomials are easier to manipulate algebraically, and we can use them to prove properties about the computation without revealing the actual data in the trace.

But how do we convert the matrix $T$ into a polynomial?

Converting the Trace to Polynomials

To make this conversion, we take each column of the trace and turn it into a polynomial. This allows us to check the values at different time steps using polynomial evaluation, which is a powerful technique for verification.

Trace Evaluation Domain

We begin by selecting a trace evaluation domain, which is a set of points where we will evaluate the polynomials. These points are typically taken from a finite field $\mathbb{F}$, which is a set of numbers with specific properties that make polynomial evaluation efficient and secure.

In particular, we choose a generator $g$ of a multiplicative subgroup of $\mathbb{F}$, and we evaluate the polynomial at powers of $g$ to encode the trace. The generator $g$ is typically chosen such that $g^i$ corresponds to the time steps of the execution trace.

Constructing Polynomials for Each Register

Let’s take a single column of the trace, say the $j$-th column, which contains the values $T_{1, j}, T_{2, j}, \ldots, T_{T,j}$ for the register at each time step. The goal is to construct a polynomial $t_j(x)$ that encodes this data.

For each column $T_j$, we define a polynomial $t_j(x)$ such that:

$$ t_j(1) = T_{1,j}, \quad t_j(g) = T_{2,j}, \quad \dots, \quad t_j(g^{T-1}) = T_{T,j} $$

Here, $g$ is the generator of a multiplicative subgroup of the finite field $\mathbb{F}$, and $g^i$ represents the evaluation point corresponding to the $i$-th time step in the trace.

The Trace Evaluation Domain

To make sure that the polynomial $t_j(x)$ works for all time steps, we ensure that $g^i$ (where $i$ is a time step) is within the evaluation domain. The domain typically comes from a cyclic subgroup of size $N = 2^n$, such that $2^n \geq T$ and the set $\lbrace 1, g , g^2 , g^3 ,…, g^N \rbrace$ covers all the necessary evaluation points for the trace.

This setup guarantees that the polynomial $t_j(x)$ is well-defined and its evaluation at $g^i$ will match the trace values, ensuring that we’ve accurately captured the execution trace in polynomial form.

Constraint Systems in STARKs: How We Ensure Computation Validity

One of the main features of STARKs (Scalable Transparent Arguments of Knowledge) is their ability to verify the correctness of a computation without requiring the verifier to check every individual step. Instead, the verifier relies on a constraint system that enforces certain rules about the computation.

The constraints used in STARKs come in two types: boundary constraints and transition constraints. These constraints are imposed on the trace polynomials, which are the polynomials that represent the execution of a program. By ensuring that these polynomials satisfy the constraints, we can confirm that the computation was performed correctly, without needing to know the exact details of every individual operation.

Boundary Constraints: Setting Initial Conditions

Boundary constraints are used to specify certain values that must be true at the beginning or end of the computation. Think of these constraints as enforcing “fixed” values at specific points in the computation, like specifying the starting values of a Fibonacci sequence.

Example: Fibonacci Sequence

Consider the Fibonacci sequence, where the first two numbers are always 1. In our computation, we can impose boundary constraints on the first two time steps (i.e., when $i = 0$ and $i = 1$) of the trace. Specifically, we require that:

$$ T_{0, 1} = 1, T_{1, 1} = 1 $$

These are the boundary conditions that must hold for the trace to be valid. In terms of the polynomial representation of the trace, we can translate these conditions into the following:

  • The value of $t_1(1)$ (the polynomial evaluation at $x = 1$) must be $1$.
  • The value of $t_1(g)$ (the polynomial evaluation at $x = g$, where $g$ is a generator in the finite field) must also be $1$.

Polynomial Representation of Boundary Constraints

The key here is that polynomials are smooth curves, so if a polynomial passes through a point, the polynomial minus that value must be divisible by $(x - \text{point})$. In our case:

  • The polynomial $t_1(x) - 1$ must be divisible by $(x - 1)$, because $t_1(1) = 1$.
  • Similarly, the polynomial $t_1(x) - 1$ must be divisible by $(x - g)$, because $t_1(g) = 1$.

Mathematically, we express these divisibility conditions as:

$$ Q_{BC,1}(x)=\frac{t_1(x)-1}{x-g} \text{ and } Q_{BC,0}(x)=\frac{t_1(x)-1}{x-1} $$

These polynomials $Q_{BC, 1}(x)$ and $Q_{BC, 0}(x)$ will vanish if the boundary constraints are satisfied, i.e., if the polynomial evaluations at $x = 1$ and $x = g$ are both $1$.

Optimizing Boundary Constraints

If we have multiple boundary constraints (say, $n$ of them), we end up with $n$ polynomials. This could quickly become cumbersome. However, we can interpolate the boundary constraints into a single polynomial $t_{BC}(x)$, which satisfies the following conditions:

$$ t_{BC}(1) = 1, t_{BC}(g) = 1 $$

Then, the boundary constraint polynomial becomes:

$$ Q_{BC}(x)=\frac{t_1(x)-t_{BC}(x)}{Z_{BC}(x)} $$

where $Z_{BC}(x)$ is a vanishing polynomial that “zeros out” at the boundary points $x = 1$ and $x = g$:

$$ Z_{BC}(x)=(x-1)(x-g) $$

This approach allows us to bundle all boundary constraints into one polynomial, simplifying the verification process.

Transition Constraints: Enforcing Computation Logic

Transition constraints are used to ensure that the computation adheres to the program’s rules at every step. These constraints link consecutive rows of the trace and ensure that the values change according to specific transition rules.

Example: Fibonacci Transition Rule

In the case of the Fibonacci sequence, the rule is simple: each number is the sum of the two previous numbers. This rule can be expressed as:

$$ T_{i+2,1} = T_{i+1,1} + T_{i,1} $$

For each $i$, this transition rule must hold. In terms of the polynomial representation of the trace, we impose this rule on the polynomials. Specifically, for each time step $i$, we require the following polynomial relation:

$$ t_1(g^2 x) - t_1(g x) - t_1(x) = 0 $$

This ensures that, at each step, the polynomial evaluations follow the Fibonacci rule. If the rule is violated at any point, the polynomial $Q_T(x)$ will not be zero, signaling an error.

Polynomial Representation of Transition Constraints

To enforce the transition rule across the entire trace, we introduce the transition polynomial $Z_T(x)$, which vanishes at all the points corresponding to the time steps in the trace:

$$ Z_T(x) = \prod_{i=0}^{T-2} (x - g^i) $$

Here, $T$ is the total number of time steps in the computation, and $g^i$ corresponds to each step in the execution trace.

The transition constraint for the Fibonacci sequence can then be expressed as:

$$ Q_T(x) = \frac{t_1(g^2 x) - t_1(g x) - t_1(x)}{Z_T(x)} $$

If the transition rule holds correctly across all steps, $Q_T(x)$ will be a valid polynomial. If the computation deviates from the expected transition rule at any step, $Q_T(x)$ will fail to be a polynomial, indicating an invalid computation.

Combining Boundary and Transition Constraints

Let’s break down how the combination works.

Random Linear Combination of Polynomials

We take the boundary constraint polynomial $Q_{BC}(x)$ and the transition constraint polynomial $Q_T(x)$, and we combine them using random coefficients $\alpha_{BC}$ and $\alpha_T$. The idea is to create a new polynomial $CP(x)$, which is a linear combination of the two existing polynomials:

$$ CP(x) = \alpha_{BC} Q_{BC}(x) + \alpha_T Q_T(x) $$

Here’s how it works:

  • $\alpha_{BC}$ and $\alpha_T$: These are random coefficients chosen by the verifier. These values are important because they prevent the prover from manipulating the constraints in a way that would make them false while still satisfying the combination.
  • $Q_{BC}(x)$: This is the polynomial representing the boundary constraints (i.e., the fixed values at the beginning or end of the trace).
  • $Q_T(x)$: This is the polynomial representing the transition constraints (i.e., the relations that link consecutive time steps in the trace).

Why Does This Work?

By taking a random linear combination of the two polynomials, we ensure that:

  • Both polynomials must be valid: If either $Q_{BC}(x)$ or $Q_T(x)$ is not a polynomial (i.e., if the constraints aren’t satisfied), then $CP(x)$ won’t be a polynomial either.
  • Randomization: The random coefficients $\alpha_{BC}$ and $\alpha_T$ ensure that the verifier’s challenge is not predictable by the prover. This randomness adds an extra layer of security to the proof, making it harder for the prover to manipulate the constraints.

Verifying $CP(x)$

If both $Q_{BC}(x)$ and $Q_T(x)$ are polynomials, then their linear combination $CP(x)$ will also be a polynomial. The verifier can now check if $CP(x)$ satisfies the following:

  • If $CP(x)$ is a valid polynomial, then the boundary and transition constraints have been correctly enforced across the trace.
  • If $CP(x)$ is not a polynomial, it means that one or both of the constraint polynomials were violated, signaling an invalid computation.

In this way, the verifier only needs to check the validity of a single polynomial $CP(x)$, rather than checking each constraint separately.

Vector Commitments: A Crucial Building Block of STARKs

One powerful form of commitment used in STARKs is the vector commitment. In simple terms, a vector commitment allows a prover to commit to an entire sequence (or vector) of values and later reveal specific elements of the vector without revealing the entire sequence. This process ensures both security (the prover cannot change the committed data) and efficiency (the verifier can check specific elements quickly).

What is a Vector Commitment?

A vector is simply an ordered collection of values, for example:

$$ Y = (p(d_1), p(d_2), \dots, p(d_M)) $$

In a vector commitment, the prover builds a commitment to the entire vector, sending it to the verifier. The commitment is designed in such a way that the verifier can later check if a particular element of the vector is valid, without needing to see the entire vector. To commit to a vector, we use a cryptographic structure called a Merkle tree.

Vector Commitments in STARKs

In STARKs, vector commitments play a key role in verifying the correctness of computations. These vectors often represent the evaluations of polynomials at specific points in a finite field.

Committing to Polynomial Evaluations

Let’s say the prover has a polynomial $p(x)$, and they want to commit to its evaluations at certain points in a domain $D = (d_1, \dots, d_M)$. This means the prover wants to commit to the vector:

$$ Y = (p(d_1), p(d_2), \dots, p(d_M)) $$

Here’s where vector commitments come in:

  1. The prover computes the evaluations $p(d_1), p(d_2), \dots, p(d_M)$, forming the vector $Y$.
  2. The prover builds a Merkle tree from the values $Y$, which are the polynomial evaluations at the points $d_1, \dots, d_M$.
  3. The prover commits to this tree by sending the Merkle root $[Y]$ to the verifier.

Verifying Polynomial Integrity

The verifier can later ask the prover to reveal the value of $p(d_i)$ for some index $i$. The prover will send the value $p(d_i)$ and the authentication path for this evaluation. The verifier then checks if this value corresponds to the commitment.

This process allows the verifier to check any specific polynomial evaluation without needing to evaluate the entire polynomial. This is especially useful in zero-knowledge proofs where the verifier needs to be convinced of the correctness of the polynomial without knowing its exact form or all of its evaluations.

The FRI Protocol: Revolutionizing Polynomial Proximity Proofs

In the realm of cryptographic proofs, especially within the context of zero-knowledge proofs and scalable verifiable computation, the FRI protocol (Fast Reed-Solomon Interactive Oracle Proof of Proximity) stands out as a pivotal innovation. The protocol provides a highly efficient way to verify that a given vector is close to the evaluations of a low-degree polynomial, all while maintaining the privacy and integrity of the underlying computation.

What is the FRI Protocol?

The FRI protocol is an interactive proof system designed to verify that a given vector of values is close to being the evaluations of a low-degree polynomial over a finite field. More formally, it is used to prove that a vector $V = (v_1, v_2, \ldots, v_M)$ is “close” (in terms of polynomial distance) to a polynomial of degree at most $N - 1$. This is particularly useful in the context of cryptographic protocols like STARKs, where such proximity proofs are key for ensuring correctness without revealing sensitive information.

The key idea behind the FRI protocol is that instead of directly verifying the full polynomial, it reduces the problem to verifying smaller proximity conditions that ensure the vector is close to a low-degree polynomial. This allows the protocol to be much more efficient and scalable compared to traditional methods of verifying polynomials directly.

Key Parameters in FRI

The FRI protocol is built around several key parameters, each of which plays an important role in the efficiency, security, and scalability of the proof.

Domain and Parameters

  • Evaluation Domain Size: The domain size $M = 2^m$ is the total number of points at which the vector is evaluated. The protocol works over a finite field $\mathbb{F}$, and the domain $D = (d_1, \dots, d_M)$ consists of evaluations of a polynomial at specific points in this field.
  • Polynomial Degree: The degree of the polynomial being tested is $N - 1$, where $N = 2^n$, with $n < m$. This means that $N$ is smaller than $M$, which is an important factor in ensuring the protocol’s efficiency. The relationship between these parameters is crucial to the overall security and efficiency of the FRI protocol.

The Domain $D$

The domain $D = (d_1, \dots, d_M)$ is defined as follows:

$$ d_i = h \omega^i \text{ for } i = 0, 1, 2, \ldots, M - 1 $$

where $h \in \mathbb{F}$ is a scalar, and $\omega$ is a primitive $M$-th root of unity in the field $\mathbb{F}$. This structure is important for ensuring that the polynomial evaluations are evenly distributed and that the symmetry properties required for the protocol hold.

One key property of this domain is that it satisfies:

$$ -d_i \in D \text{ for all } i $$

This symmetry is necessary for the FRI protocol’s correctness, as it allows certain algebraic manipulations to hold during the verification steps.

The Blowup Factor $\beta$

A key concept in the FRI protocol is the blowup factor, denoted as $\beta$. This factor plays a crucial role in the relationship between the evaluation domain $M$ and the degree of the polynomial $N - 1$.

The blowup factor is defined as:

$$ \beta = \frac{M}{N} = 2^{m-n} $$

Here, $M = 2^m$ is the size of the domain, and $N = 2^n$ is the size of the polynomial’s degree. Since $m > n$, this blowup factor grows exponentially, but it is controlled by the relationship between $m$ and $n$.

Why is $\beta$ Important?

The blowup factor $\beta$ has two main implications:

  1. Security: The larger $\beta$ is, the more “spread out” the polynomial evaluations are, making it harder for a dishonest prover to deceive the verifier. A larger $\beta$ increases the probability that the prover will be caught cheating. This makes the protocol more secure.
  2. Verification Efficiency: The blowup factor also influences the number of verification steps the verifier needs to perform. A larger $\beta$ means that the protocol will require more rounds of verification to ensure correctness, as the verifier is checking a larger number of points. Thus, there is a trade-off between security and efficiency.

Degree Adjustment in Polynomial Constraints: The Secret to Efficient STARKs

In STARKs, the prover needs to convince the verifier that the execution trace of a computation is correct. To do this, the prover encodes the execution trace as a set of polynomials and applies constraints to ensure that the trace follows the rules of the computation. However, these polynomials can sometimes have a high degree, which would make the verification process computationally expensive.

Degree adjustment is a technique used to ensure that the degree of the constraint polynomials remains sufficiently low, making the verification process efficient and scalable. In essence, degree adjustment allows the system to control the growth of the polynomial degrees and ensures that the final constraints are well-suited for efficient verification, even in large-scale systems.

How Does Degree Adjustment Work?

Let’s take a closer look at how degree adjustment is mathematically implemented and why it is necessary. Suppose we have a constraint polynomial $C_j(x)$ that enforces certain conditions on the execution trace. The degree of this constraint polynomial is denoted as $D_j$, and the goal is to ensure that the degree of the final constraint is low—specifically, less than a chosen threshold $D$.

To achieve this, the prover applies the degree adjustment technique, which modifies the polynomial $C_j(x)$ using the following formula:

$$ C_j(x) \cdot (\alpha_j x^{D - D_j - 1} + \beta_j) $$

Where:

  • $C_j(x)$ is the original constraint polynomial.
  • $D_j$ is the degree of $C_j(x)$.
  • $D$ is the smallest power of 2 greater than or equal to the maximum degree of any constraint polynomial (i.e., the desired degree threshold).
  • $\alpha_j$ and $\beta_j$ are random field elements chosen by the verifier, adding an element of randomness to the process. This randomness ensures that the adjustments do not introduce any predictable patterns that could be exploited by a malicious prover.

Why Adjust the Degree?

The main reason for degree adjustment is to control the degree of the constraint polynomials. If the degree of the polynomials is too high, the verification process becomes computationally expensive and inefficient. By adjusting the degree to a lower, fixed value $D$, we ensure that the constraints remain manageable while still enforcing the required conditions on the execution trace.

In addition, this technique allows us to compress the constraints in a way that doesn’t sacrifice soundness (the ability to catch false claims) or completeness (the ability to prove true claims).

Composition of Constraints

Once the degree of each individual constraint is adjusted, the next step is to combine these constraints into a single composition polynomial. The composition polynomial represents the overall set of constraints that the execution trace must satisfy, and it is used to verify the correctness of the trace.

The composition polynomial is constructed by taking a random linear combination of all the adjusted constraints. Mathematically, this is done as follows:

$$ CP(x) = \sum_{j=1}^{k} C_j(x) \cdot (\alpha_j x^{D - D_j - 1} + \beta_j) $$

Where:

  • $k$ is the total number of constraints.
  • Each constraint $C_j(x)$ is adjusted by the term $(\alpha_j x^{D - D_j - 1} + \beta_j)$.

Why Use a Composition Polynomial?

The composition polynomial serves as a way to combine multiple constraints into a single object that can be more easily verified. This process of combining the constraints allows the verifier to check that the execution trace adheres to all the required conditions using a single polynomial evaluation.

The degree of the composition polynomial is crucial to the efficiency of the entire proof. If the degree of the composition polynomial is too high, it would lead to inefficient verification. However, since each individual constraint is adjusted to have a low degree, the composition polynomial itself will also have a manageable degree, ensuring that the verification process remains efficient even for large-scale computations.

Committing to the Trace: The Heart of STARK Integrity

In the world of Scalable Transparent Arguments of Knowledge (STARKs), one of the most crucial aspects of the protocol is ensuring the integrity and correctness of the computation trace. The trace, a series of states that represent the evolution of a computation, must be committed in such a way that allows a verifier to confidently check the validity of the proof, without requiring them to re-run the entire computation.

At the core of this process is the concept of commitment: the act of binding a prover to a specific computation trace, without the possibility of later changing the trace. To do this efficiently, STARKs use a combination of polynomial commitments and Merkle trees.

The Polynomial Commitment Process

The key idea is to transform the execution trace into a series of polynomials. Each column $T_j$ of the trace matrix $T$ represents a sequence of values for a given register across all time steps. By interpolating these values, we can construct polynomials that encode the trace’s validity.

Step 1: Interpolation of Columns

For each column $T_j$ of the trace matrix, we will create a polynomial $t_j(x)$ that interpolates the values of that column over a known domain. This domain is usually chosen as a cyclic group, $D_S = \lbrace 1, g , g^2 , g^3 ,…, g^N \rbrace$, where $g$ is a generator of the multiplicative group, and $N$ is a power of 2 large enough to cover the number of time steps in the trace.

To define the polynomial $t_j(x)$, we enforce the condition that it matches the values of the column at each time step:

$$ t_j(g^i) = T_{i,j}, \quad \text{for all} , i $$

Thus, for each column $T_j$, the polynomial $t_j(x)$ has degree $T - 1$ and is uniquely defined by its values at the points $g^0, g^1 , g^2 , g^3 ,…, g^{T - 1}$. This interpolation ensures that the polynomial $t_j(x)$ captures the behavior of the corresponding register across all time steps.

Step 2: Commitment to Polynomials

Once the polynomials $t_j(x)$ are constructed, the next step is to commit to them. In STARKs, commitment means that the prover creates a cryptographic commitment to these polynomials, binding them to the trace while ensuring they cannot be altered later.

This is done by evaluating each polynomial $t_j(x)$ over a larger, extended domain known as the Low-Degree Extension (LDE) domain, denoted $D_{LED}$. This domain is typically chosen to be larger than the original evaluation domain $D_S$, and its purpose is to extend the polynomial’s evaluation points to make the commitment more secure.

For each polynomial $t_j(x)$, the prover computes the following:

$$ [t_j] := \text{Commit}(t_j(D_{LED})) $$

This means that the prover evaluates $t_j(x)$ at all the points in the LDE domain $D_{LED}$ and then constructs a Merkle tree from these evaluations. A Merkle tree is a binary hash tree that allows for efficient verification of individual polynomial evaluations.

  • The root of the Merkle tree becomes the commitment $[t_j]$, which the prover sends to the verifier.

Unveiling the FRI Protocol: How to Verify Polynomials Efficiently

The FRI protocol allows the prover to demonstrate that their polynomial, say the composition polynomial $CP(x)$, is close to a low-degree polynomial. The essence of the FRI protocol is to recursively fold the polynomial, reducing its degree at each step, until we are left with a polynomial that is easy to verify.

The beauty of FRI lies in its ability to dramatically reduce the complexity of checking large-degree polynomials while maintaining rigorous security guarantees. By following a sequence of folding steps, the prover and verifier can efficiently assess whether the polynomial behaves like a low-degree polynomial.

The FRI protocol is structured into two phases: the commitment phase and the query phase.

  1. In the commitment phase, the prover constructs and commits to the polynomial evaluations over progressively smaller domains.
  2. In the query phase, the verifier checks whether the committed polynomial is indeed close to a low-degree polynomial by querying random points. The verifier’s role here is to check the consistency of the polynomial across the different levels of folding.

The Commitment Phase in the FRI Protocol: Recursive Folding and Merkle Commitments

The commitment phase of the FRI protocol involves a sequence of steps where the prover progressively reduces the degree of the composition polynomial $CP(x)$ using recursive transformations. The goal is to make the polynomial’s degree smaller at each step until it eventually becomes a constant polynomial. At each step, the prover commits to the polynomial by evaluating it over smaller domains and using Merkle trees to ensure consistency and integrity.

Let’s break down this phase step by step.

Initial Step: Halving the Polynomial Degree

The process starts with the original polynomial $CP(x)$. The first operation splits the polynomial into two parts:

  • The even-degree part $g(x^2)$, which combines $CP(x)$ and $CP(-x)$.
  • The odd-degree part $h(x^2)$, which involves subtracting $CP(-x)$ from $CP(x)$.

These operations are mathematically expressed as:

$$ g(x^2) = \frac{CP(x) + CP(-x)}{2} $$

$$ x \cdot h(x^2) = \frac{CP(x) - CP(-x)}{2} $$

Thus, the original polynomial $CP(x)$ can be written as:

$$ CP(x) = g(x^2) + x \cdot h(x^2) $$

This step reduces the degree of the polynomial by half. Notice that $g(x^2)$ and $h(x^2)$ are now defined over a new domain $D_1$, which is a subset of the original domain $D$, having half its size. This new domain can be represented as:

$$ D_1 = \lbrace h^2, h^2 \omega^2, \dots, h^2 \omega^m \rbrace $$

Here, $\omega$ is a primitive root of unity, and $h$ is a base element of the domain.

Random Linear Combination: Reducing the Degree Further

At this point, the verifier chooses a random coefficient $\alpha_0$, and the prover constructs a new polynomial:

$$ P_1(x^2) = g(x^2) + \alpha_0 h(x^2) $$

This new polynomial $P_1(x^2)$ is now evaluated over the new domain $D_1$, and the prover commits to these evaluations by constructing a Merkle tree. The root of the Merkle tree, denoted $[P_1]$, is sent to the verifier as the commitment for this stage.

The Merkle root acts as a cryptographic proof that the prover has indeed committed to the values of the polynomial $P_1(x)$ over the domain $D_1$, without revealing the polynomial itself.

Recursive Halving: Repeating the Process

The recursive halving process continues as follows: for each subsequent step $k$, the polynomial is halved again. The polynomial at step $k$, denoted $P_k(y^2)$, is derived from the previous polynomial $P_{k - 1}(y)$ using the formula:

$$ P_k(y^2) = \frac{P_{k-1}(y) + P_{k-1}(-y)}{2} + \alpha_{k-1} \left( \frac{P_{k-1}(y) - P_{k-1}(-y)}{2} \right) $$

This equation represents the splitting of $P_{k - 1}(y)$ into two parts and introducing a random linear combination via the coefficient $\alpha_{k - 1}$.

At each step $k$, the domain $D_k$ is updated to:

$$ D_k = \lbrace h^{2^{k-1}}, (h\omega)^{2^{k-1}}, \dots, (\omega^l h)^{2^{k-1}} \rbrace $$

This updated domain $D_k$ has half the size of the previous domain $D_{k - 1}$, and the polynomial $P_k(x)$ is evaluated over this smaller domain.

Again, the prover constructs a Merkle tree from the polynomial evaluations and sends the root of this tree as the commitment to the verifier.

Final Layer: Constant Polynomial

The recursive halving continues until the degree of the polynomial becomes zero. At this final step $n$, the polynomial is reduced to a constant value $c$, such that:

$$ P_n(x) = c $$

The prover sends this constant value $c$ to the verifier, which serves as the final commitment in the chain.

The Query Phase in the FRI Protocol: Ensuring Consistency Through Collinearity Checks

In the Query Phase, the verifier selects a random point $q$ from the domain $D_k$(the current folding layer). The goal of the phase is to ensure that the polynomial $P_k(x)$, which has been progressively reduced through recursive folding, is consistent at each stage. Specifically, the verifier checks whether the values at $q$ and $-q$ (the negation of $q$) in the polynomial correspond to the expected values at the next folding layer.

The prover’s job in this phase is to respond with the following:

  1. Evaluations at $q$ and $-q$: The prover sends the values of the polynomial $P_k(q)$, $P_k(-q)$ and $P_{k + 1}(q^2)$.
  2. Merkle Paths: For each evaluation, the prover also provides the Merkle proof (or authentication path), which allows the verifier to check that these values are consistent with the Merkle commitment to the polynomial evaluations from the previous phase.
  3. Consistency Check: Finally, the prover demonstrates that the values $P_k(q)$ and $P_k(-q)$ are consistent with the polynomial at the next layer, $P_{k + 1}(q^2)$.

Verifying Consistency: The Collinearity Check

Once the prover sends the required information, the verifier must check the consistency of the polynomial evaluations. The consistency is verified through a collinearity check, which essentially ensures that the values at each layer of folding align correctly with the expected values at the next layer.

The verifier receives three pieces of information at each step:

  • $P_k(q)$, the value of the polynomial at $q$
  • $P_k(-q)$, the value of the polynomial at $-q$
  • $P_{k + 1}(q^2)$ the expected value of the next polynomial at $q^2$

The Collinearity Check: What Does It Mean?

Let’s dig a little deeper into the collinearity check. Essentially, this check is about ensuring that the three points $A = (q, P_k(q))$, $B = (-q, P_k(-q))$ and $C = (\alpha_k, P_{k+1}(q^2))$ lie on a straight line. To understand why this must be true, we can perform an elementary Lagrange interpolation between points $A$ and $B$ to find the equation of the line passing through them.

We start with the standard form of Lagrange interpolation for two points:

$$ y = \sum_i y_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} $$

For our case, the interpolation for $A = (q, P_k(q))$ and $B = (-q, P_k(-q))$ is:

$$ y = P_k(q) \cdot \frac{x - (-q)}{q - (-q)} + P_k(-q) \cdot \frac{x - q}{-q - q} $$

Simplifying this expression:

$$ y = \frac{P_k(q) + P_k(-q)}{2} + x \cdot \frac{P_k(q) - P_k(-q)}{2q} $$

Now, we set $x = \alpha_k$, which gives us the y-coordinate of point $C$:

$$ y = \frac{P_k(q) + P_k(-q)}{2} + \alpha_k \cdot \frac{P_k(q) - P_k(-q)}{2q} $$

This is exactly the y-coordinate of $C$, $P_{k + 1}(q^2)$, so we can conclude that the points $A$, $B$, and $C$ lie on a straight line. This is why the collinearity check is so important: it provides a simple and efficient way to verify the consistency of the prover’s claims at each layer of folding.

Final Check at the Last Layer: Verifying the Constant

In the final layer of the folding process, the polynomial reduces to a constant value $c$. To verify this, the verifier checks the consistency of the polynomial evaluations at the previous layer, $P_{n - 1}$, at the points $\omega_j^{2^{n-1}}$ and $-\omega_j^{2^{n-1}}$, using the following formula:

$$ c’ = \frac{P_{n-1}(\omega_j^{2^{n-1}}) + P_{n-1}(-\omega_j^{2^{n-1}})}{2} + \alpha_{n-1} \left( \frac{P_{n-1}(\omega_j^{2^{n-1}}) - P_{n-1}(-\omega_j^{2^{n-1}})}{2} \right) $$

If this computed value $c’$ matches the constant $c$ that the prover has committed to, the verifier can be confident that the polynomial was correctly reduced to a constant value and that the folding process has been executed properly.

References

  1. Anatomy of a STARK. Aszepieniec. Retrieved from https://aszepieniec.github.io/stark-anatomy/
  2. LambdaClass. (2023, March 01). LambdaWorks or how we decided to create our zkSNARKs library and a STARK prover. Retrieved from https://blog.lambdaclass.com/lambdaworks-or-how-we-decided-to-created-our-zksnarks-library-and-a-stark-prover/
  3. STARKs protocol. LambdaClass. Retrieved from https://github.com/lambdaclass/lambdaworks/tree/main/docs/src/starks
  4. StarkWare Team. (2023, July). ethSTARK Documentation. Retrieved from https://eprint.iacr.org/2021/582.pdf
  5. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. Retrieved from https://drops.dagstuhl.de/storage/00lipics/lipics-vol107-icalp2018/LIPIcs.ICALP.2018.14/LIPIcs.ICALP.2018.14.pdf
  6. Stefano De Angelis. (2024, October 22). Practical notes on the FRI low degree test. Retrieved from https://hackmd.io/@deanstef/SJTT3MDhC

Connect with Me

Connect with me on Facebook, LinkedIn, via email at dangduongminhnhat2003@gmail.com, GitHub, or by phone at +84829258815.

FRI Protocol  Polynomials  Zero-Knowledge Proofs  STARKs  Blockchain  Cryptography  MerkleTrees  Interactive Oracle Proofs