Content

1. The FRI Principle

1.1 Overview of the Principle

Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI) is an interactive protocol used to check if the degree of a committed polynomial is less than a specific value \( d \). The general idea is as follows: Given two polynomials \( p \) and \( q \) with degree \( d \), for any random challenge \( a \), the polynomial \( p + a q \) is of degree \( d \) (thus its encoded value is also close to a degree \( d \) polynomial).

Specifically, the FRI protocol is divided into three phases: Commit, Folding, and Query.

• Commit: A set of size \( n \) is chosen. For a degree \( d \) polynomial \( p \), each element of the set is used to compute and store the result as a leaf node. A Merkle tree is then constructed, and the Merkle root is used as the final commitment.
• Folding: The degree of the polynomial \( p \) is continually reduced by half, i.e., the degree is reduced from \( d \) to \( d/2 \), until the polynomial’s degree reaches 0 (i.e., a constant) or a predefined degree.
• Query: The verifier sends a random challenge to validate the correctness of the prover’s folding. The prover must provide not only the corresponding values at specific points but also the corresponding Merkle path to demonstrate that the point is indeed part of the Merkle tree.

The main advantages of FRI are: 

• Fast proof generation, as it only uses collision-resistant hash functions. 
• Post-quantum security and independence from trusted setup, as it only relies on encoding and collision-resistant hash functions.

The main drawbacks of FRI are:

• Verification time is polylogarithmic, which is slower compared to other protocols like Marlin and Plonk.
• The proof size is large, as it includes evaluations for all challenges and the corresponding Merkle paths (which are \( \log n \)).

1.2 Implementation Process

Next, we describe the three phases of the FRI protocol: Commit, Folding, and Query. It is important to note that the FRI protocol outlined here is the interactive version, meaning that the verifier sends random challenges to the prover. To convert it to a non-interactive version, the Fiat-Shamir transformation is used to replace random challenges with queries to a random oracle.

Commit: Given a degree \( d \) polynomial \( p(X) \), a predefined set \( \{w_1, w_2, \dots, w_n\} \) of size \( n \) (where \( n = qd, q > 2 \)) and a collision-resistant hash function \( H \), the following steps are performed:

• Compute each \( p(w_i) \), and use each \( p(w_i) \) as a leaf node in a Merkle tree.
• Construct the Merkle tree using the collision-resistant hash function \( H \).
• The verifier uses the Merkle root as the commitment, and the prover stores the entire Merkle tree.

Folding: The problem size is halved using a binary method, i.e., the degree \( d \) polynomial is converted into two degree \( d/2 \) polynomials, and a Random Linear Combination (RLC) is used to generate a new degree \( d/2 \) polynomial, until the polynomial is reduced to a constant or reaches the predefined degree. The steps are as follows: For the \( i \)-th round of FRI folding (until the polynomial is compressed to a constant, i.e., \( i \) is at most \( \log d \)):

• Calculate the new domain \(Ω : w_j \mapsto w_j^2 \), ensuring that the polynomial retains this property in the subsequent domains.
• The verifier sends a random challenge \( x \).
• The prover computes the compressed polynomial \( p_{\text{fold}}(X) = p_e(X) + x p_o(X) \), where \( p_e(X) \) represents the even terms of \( p(X) \) and \( p_o(X) \) represents the odd terms of \( p(X) \).  The even terms are computed as:  \[ p_e(X) = \frac{p(X) + p(-X)}{2} \]  The odd terms are computed as:  \[ p_o(X) = \frac{p(X) - p(-X)}{2} \]
• The prover computes \( p_{\text{fold}}(X) \) in \( i \), constructs the Merkle tree, and uses the Merkle root \( \text{root}_i \) as the commitment for the \( i \)-th round. When the polynomial reaches a specific degree or a constant, the folding process ends.

Query: The verifier issues several random challenges to verify the correctness of the prover’s folding process (which can be viewed as re-executing the folding process). The prover must submit the evaluations for each challenge, along with the corresponding Merkle paths, to verify that the evaluations are correct and part of the Merkle root. The detailed interaction logic is as follows (this process is repeated for multiple rounds, though only one round is considered here as the verification method is the same for each round):

• A value \( t \) is selected from the set Ω.
• The prover returns the corresponding \( p_{(t)}\) and the associated Merkle path.

For \( i = 1 \ldots \log d \)

1. Calculate \( t = t^2 \) as the point for the next round.
2. The prover returns the corresponding \( p_{\text{fold}}(t) \) and the Merkle path.
3. Verify that \( p_{\text{fold}}(t) = p_e(t) + t p_o(t) \)

To compute \( p_e(X) \) and \( p_o(X) \), only the values of \( p(X) \) at \( X = t \) and \( X = -t \) are needed, as the following equation holds (the prover must submit the corresponding Merkle paths when responding):

\[ p(X) = p_e(X) + X p_o(X)\]

For \( p(X) \), the even terms are extracted as \( p_e(X) = \frac{p(X) + p(-X)}{2} \), and the odd terms are extracted as \( p_o(X) = \frac{p(X) - p(-X)}{2} \). The rest of the terms can be simplified and expanded.

1.3 Performance Trade-offs

FRI involves trade-offs between proof size, proving time, and verification time, primarily determined by the size of the set Ω, where \( n = qd \).

• If \( q \) is increased, the number of points that the prover must prove increases, thereby increasing the prover’s proving time. As a result, the Merkle path also becomes longer, increasing the overall proof size. However, the verification time for the user decreases.
• If \( q \) is decreased, the number of points the prover must prove decreases, reducing the prover’s proving time. Consequently, the Merkle path becomes shorter, and the overall proof size decreases. However, the verification time for the user increases.

To reduce proof size (i.e., the length of the Merkle path), Plonky2 typically submits a Merkle cap rather than the Merkle root, which consists of the node values of the subtrees of the Merkle root.

2. Applied to Polynomial Commitment

Like KZG polynomial commitments, FRI can also be applied to polynomial commitments. Given a polynomial \( p(X) \) and a point \( t \), such that \( p(t) = y \), we can define:

\[h(X) = \frac{p(X) - y}{X - t}\]

In polynomial commitments, commitments to both \( h(X) \) and \( p(X) \) are made simultaneously, and specific points are opened to check that \( h(X) \) and \( p(X) \) have degrees at most \( d-1 \) and \( d \), respectively. Through random challenges, we verify:

\[h(X) (X - t)= p(X) - y\]

If the equality holds, the verification is successful.

‍Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions, you can contact the ZKM team on discord: discord.com/zkm