The FRI protocol is an interactive proof system designed to prove the low degree (degree constraint) of a polynomial. The Prover commits to a polynomial form, and the Verifier ensures that the polynomial is of low degree by sampling several points from it, performing multiple random linear combinations, and polynomial folding. This interactive proof system is particularly important in zero-knowledge proofs, as it allows the verification of the polynomial’s properties without revealing the polynomial itself.
FRI is based on Reed-Solomon encoding and polynomial evaluation, progressively reducing the degree of the polynomial through sampling and folding until its low-degree property is obvious. The folding operation (Polynomial Folding) in the process helps reduce the communication cost between the Prover and the Verifier, making it especially efficient in large-scale proof systems. Its communication complexity and number of interaction rounds (in interactive proof systems) have a logarithmic relationship with the polynomial’s degree, i.e., \( O(\log d) \), where \( d \) is the highest degree of the polynomial.
FRI consists of three algorithmic components: Commit, Folding, and Query, as defined below:
· Commit: Given a polynomial \( p(X)\) of degree \( d \), a predefined domain set \(\Omega = \{w_1, w_2, ..., w_n\}\) of size ( n = q^d ) \(where ( q > 2 )\), and a collision-resistant hash function \( H \), the following information is computed:
· 2. Folding: The problem is recursively halved, i.e., a polynomial of degree \( d \) is split into two polynomials of degree \( d/2 \), and a random linear combination is used to generate a new polynomial of degree \( d/2 \). This process is repeated until the polynomial is reduced to a constant or reaches the desired degree. The steps are as follows: For the \( i \)-th round of FRI folding (until reduced to a constant, i.e., \( i \) can go up to \( \log d \)):
· 3. Query: The Verifier initiates several random challenges to check the correctness of the Prover’s folding process (which can be viewed as re-executing the folding process). The Prover must submit the evaluation values corresponding to each random challenge, along with the Merkle paths for the evaluations. The Merkle paths are used to check that the evaluations indeed belong to the Merkle root. The interaction proceeds as follows (we consider only one round of verification here, as each round follows the same process):
It is important to note that calculating \( p_e(X) \) and \( p_o(X) \) only requires querying \( p(X) \) at \( X = t \) and \( X = -t \), because the following identities hold (the Prover must also submit the corresponding Merkle paths when responding):
\[p(X) = p_e(X) + Xp_o(X)\]
For \( p(X) \), extract the even terms \(p_{e}(X)=\frac{p(X)+p(-X)}{2}\), and the odd terms \(p_{o}(X)=\frac{p(X)-p(-X)}{2}\).
Let us illustrate the FRI commit phase with a concrete cubic polynomial. Suppose we have a cubic polynomial:
\[f(x) = 2x^3 + 3x^2 + x + 5\]
According to the FRI protocol, two rounds of interaction (since \(\log_4 = 2\)) are needed to reduce the polynomial’s degree.
First, the Prover decomposes the cubic polynomial \( f(x) \) into two quadratic polynomials:
\[f(x) = g_0 (x^2) + x h_0 (x^2)\]
Here, \( g_0 (x^2) \) and \( h_0 (x^2) \) are polynomials in \( x^2 \). Thus, we can rewrite \( f(x) \) as:
\[f(x) = (2x^2 + 5) + x(3 x + 1)\]
Therefore:
Next, the Verifier sends a random value \( a_0 \).
The Prover computes \( f_1(x) = g_0 (x) + a_0 h_0 (x) \) based on the received random value \( 0 \). Suppose \( 0 = 1 \), then:
\[f_{1}(x)=(2x^{2}+5)+1\cdot(3x+1)=2x^{2}+5+3x+1=2x^{2}+3x+6.\]
The Prover then decomposes this quadratic polynomial \( f_1(x) \) into two lower-degree polynomials:
\[f_{1}(x)=g_{1}(x^{2})+xh_{1}(x^{2}).\]
Thus:
After the Prover has decomposed \( f_1(x) \), the Verifier sends another random value \( a_1 \) for the next step.
The Prover computes \( f_2(x) = g_1 (x) + a_1 h_1 (x) \) based on the received random value \( a_1 \). Suppose \( a_1 = 1 \), then:
\[f_2(x) = (2x^2 + 6) + 1 · 3 = 2x^2 + 6 + 3 = 2x^2 + 9\]
Next, the Prover decomposes this quadratic polynomial \( f_2(x) \) into two first-degree polynomials:
\[f_2(x) = g_2 (x^2) + x h_2 (x^2)\]
Thus:
The Verifier sends a final random value \( a_2 \), and the Prover computes\(f_{3}(x)=g_{2}(x)+\alpha_{2}h_{2}(x)\). Since \( h_2 (x) = 0 \), we get:
\[f_3(x) = 2x^2 + 9\]
At this point, the Prover has obtained a constant polynomial \( f_3(x) = 9 \), indicating that the polynomial’s degree has been reduced to zero, and the proof process ends.
Although FRI itself is already quite efficient, there is still room for further optimization when dealing with complex constraints or larger-scale proofs. DEEP-FRI optimizes the polynomial folding and random linear combination strategies by introducing deep algebraic structures. This allows for improved proof efficiency without significantly increasing the communication cost.
At the same time, DEEP-FRI supports queries at points outside the domain, significantly enhancing the soundness of the original FRI protocol. The number of queries can also be reduced accordingly, which helps decrease the proof size.
This operation is commonly used in certain proofs or algorithms to adjust the form of a function, eliminate the value at a specific point \( z \), or simplify and reduce polynomials in their construction. The specific process is as follows:
Given a point \( z \in F_q \) and a value \( b \in F_q \)
First, define the polynomial \( Z(Y) = Y - z \). This is a simple linear polynomial with root \( z \).
Next, define a new function \( g: L \to F_q \) as follows:
\[g(y)=\frac{f(y)-b}{z(y)}=\frac{f(y)-b}{y-z}.\]
1. Input Parameters:
2. Output: A new function \( g_(y) \), which is the result of subtracting \( b \) from the original function \( f_(y) \), and then dividing by \( y - z \).
DEEP-FRI consists of three algorithmic components: Commit, Folding, and Query. Here we consider the interactive proof system. If we need to convert it to a non-interactive system, we replace each challenge value sent by the verifier using the Fiat-Shamir transformation. The interactive proof algorithm for DEEP-FRI is defined as follows:
Suppose we are given a polynomial of degree \( d \), \( p(X) \), and a predefined domain set \( \Omega = \{w_1, w_2, ..., w_n\} \), where \( n = qd \) (with \( q > 2 \)), and a collision-resistant hash function \( H \). The following steps are required during this phase:
The Folding phase recursively folds the query domain of the polynomial \(f^{(i)}(x)\) and generates a new polynomial, causing the degree of the polynomial to decrease in the next iteration. The process is as follows:
For the \( i \)-th round of folding (\( i < \log d \)):
1. Polynomial Query:
\[B_{Z^{(0)}}^{(1)}(x) = H_x[f^{(1)}]\]
2. Random Challenge and Polynomial Degree Reduction
The folding operation is as follows:
We have a function \( f^{(i+1)}: L^{(i+1)} \rightarrow F_q \), which is defined based on the quotient operation (QUOTIENT). When given \( y \) as input, the function \(F^{(i+1)}\) is defined as:
\[f^{(i+1)}(y)=\frac{H_{x^{(i)}}[f^{(i)}]-B_{Z^{(i)}}^{(1)}(x)}{y-z^{(i)}}.\]
Here are the details:
At the end of this step, if the folded polynomial is a constant \( C \) or has reached a predefined degree, the process ends.
The Query phase is primarily used to verify whether the final polynomial calculations are correct. The process is as follows:
1 .Repeat the query \( l \) times:
The verifier selects a random point \(s^{(0)}\) from the domain \( D \), and for each \( i \), defines the corresponding point \(S^{(i+1)}\), where \( S^{(i+1)} = q^{(1)}(S^{(i)}) \). The even term formula is:
\[f_{even}(X)=\frac{f(X)+f(-X)}{2}.\]
The odd term formula is:
\[f_{odd}(X)=\frac{f(X)+f(-X)}{2}.\]
· The prover provides the verifier with the values \(f^{(i+1)}(s^{(i+1)})\) and \(H_x{(i)}[f{(i)}]\) (evaluations of the polynomial \(f^{(i+1)}(X)\) at \(X=s^{(i+1)}\) and \(X=-s^{(i+1)}\) ), along with the corresponding Merkle path.
· The verifier checks if the corresponding values are in the Merkle tree and verifies the following equation:
\[H_{x}[f^{(i)}]=f^{(i+1)}(s^{(i+1)})\cdot(s^{(i+1)}-z^{(t)})+{B}_{Z^{(i)}}^{(i)}(x^{(i)}).\]
2. Final Result Verification: Check if the final polynomial calculation matches the pre-committed value \( C \). If not, reject; otherwise, accept.
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
The FRI protocol is an interactive proof system designed to prove the low degree (degree constraint) of a polynomial. The Prover commits to a polynomial form, and the Verifier ensures that the polynomial is of low degree by sampling several points from it, performing multiple random linear combinations, and polynomial folding. This interactive proof system is particularly important in zero-knowledge proofs, as it allows the verification of the polynomial’s properties without revealing the polynomial itself.
FRI is based on Reed-Solomon encoding and polynomial evaluation, progressively reducing the degree of the polynomial through sampling and folding until its low-degree property is obvious. The folding operation (Polynomial Folding) in the process helps reduce the communication cost between the Prover and the Verifier, making it especially efficient in large-scale proof systems. Its communication complexity and number of interaction rounds (in interactive proof systems) have a logarithmic relationship with the polynomial’s degree, i.e., \( O(\log d) \), where \( d \) is the highest degree of the polynomial.
FRI consists of three algorithmic components: Commit, Folding, and Query, as defined below:
· Commit: Given a polynomial \( p(X)\) of degree \( d \), a predefined domain set \(\Omega = \{w_1, w_2, ..., w_n\}\) of size ( n = q^d ) \(where ( q > 2 )\), and a collision-resistant hash function \( H \), the following information is computed:
· 2. Folding: The problem is recursively halved, i.e., a polynomial of degree \( d \) is split into two polynomials of degree \( d/2 \), and a random linear combination is used to generate a new polynomial of degree \( d/2 \). This process is repeated until the polynomial is reduced to a constant or reaches the desired degree. The steps are as follows: For the \( i \)-th round of FRI folding (until reduced to a constant, i.e., \( i \) can go up to \( \log d \)):
· 3. Query: The Verifier initiates several random challenges to check the correctness of the Prover’s folding process (which can be viewed as re-executing the folding process). The Prover must submit the evaluation values corresponding to each random challenge, along with the Merkle paths for the evaluations. The Merkle paths are used to check that the evaluations indeed belong to the Merkle root. The interaction proceeds as follows (we consider only one round of verification here, as each round follows the same process):
It is important to note that calculating \( p_e(X) \) and \( p_o(X) \) only requires querying \( p(X) \) at \( X = t \) and \( X = -t \), because the following identities hold (the Prover must also submit the corresponding Merkle paths when responding):
\[p(X) = p_e(X) + Xp_o(X)\]
For \( p(X) \), extract the even terms \(p_{e}(X)=\frac{p(X)+p(-X)}{2}\), and the odd terms \(p_{o}(X)=\frac{p(X)-p(-X)}{2}\).
Let us illustrate the FRI commit phase with a concrete cubic polynomial. Suppose we have a cubic polynomial:
\[f(x) = 2x^3 + 3x^2 + x + 5\]
According to the FRI protocol, two rounds of interaction (since \(\log_4 = 2\)) are needed to reduce the polynomial’s degree.
First, the Prover decomposes the cubic polynomial \( f(x) \) into two quadratic polynomials:
\[f(x) = g_0 (x^2) + x h_0 (x^2)\]
Here, \( g_0 (x^2) \) and \( h_0 (x^2) \) are polynomials in \( x^2 \). Thus, we can rewrite \( f(x) \) as:
\[f(x) = (2x^2 + 5) + x(3 x + 1)\]
Therefore:
Next, the Verifier sends a random value \( a_0 \).
The Prover computes \( f_1(x) = g_0 (x) + a_0 h_0 (x) \) based on the received random value \( 0 \). Suppose \( 0 = 1 \), then:
\[f_{1}(x)=(2x^{2}+5)+1\cdot(3x+1)=2x^{2}+5+3x+1=2x^{2}+3x+6.\]
The Prover then decomposes this quadratic polynomial \( f_1(x) \) into two lower-degree polynomials:
\[f_{1}(x)=g_{1}(x^{2})+xh_{1}(x^{2}).\]
Thus:
After the Prover has decomposed \( f_1(x) \), the Verifier sends another random value \( a_1 \) for the next step.
The Prover computes \( f_2(x) = g_1 (x) + a_1 h_1 (x) \) based on the received random value \( a_1 \). Suppose \( a_1 = 1 \), then:
\[f_2(x) = (2x^2 + 6) + 1 · 3 = 2x^2 + 6 + 3 = 2x^2 + 9\]
Next, the Prover decomposes this quadratic polynomial \( f_2(x) \) into two first-degree polynomials:
\[f_2(x) = g_2 (x^2) + x h_2 (x^2)\]
Thus:
The Verifier sends a final random value \( a_2 \), and the Prover computes\(f_{3}(x)=g_{2}(x)+\alpha_{2}h_{2}(x)\). Since \( h_2 (x) = 0 \), we get:
\[f_3(x) = 2x^2 + 9\]
At this point, the Prover has obtained a constant polynomial \( f_3(x) = 9 \), indicating that the polynomial’s degree has been reduced to zero, and the proof process ends.
Although FRI itself is already quite efficient, there is still room for further optimization when dealing with complex constraints or larger-scale proofs. DEEP-FRI optimizes the polynomial folding and random linear combination strategies by introducing deep algebraic structures. This allows for improved proof efficiency without significantly increasing the communication cost.
At the same time, DEEP-FRI supports queries at points outside the domain, significantly enhancing the soundness of the original FRI protocol. The number of queries can also be reduced accordingly, which helps decrease the proof size.
This operation is commonly used in certain proofs or algorithms to adjust the form of a function, eliminate the value at a specific point \( z \), or simplify and reduce polynomials in their construction. The specific process is as follows:
Given a point \( z \in F_q \) and a value \( b \in F_q \)
First, define the polynomial \( Z(Y) = Y - z \). This is a simple linear polynomial with root \( z \).
Next, define a new function \( g: L \to F_q \) as follows:
\[g(y)=\frac{f(y)-b}{z(y)}=\frac{f(y)-b}{y-z}.\]
1. Input Parameters:
2. Output: A new function \( g_(y) \), which is the result of subtracting \( b \) from the original function \( f_(y) \), and then dividing by \( y - z \).
DEEP-FRI consists of three algorithmic components: Commit, Folding, and Query. Here we consider the interactive proof system. If we need to convert it to a non-interactive system, we replace each challenge value sent by the verifier using the Fiat-Shamir transformation. The interactive proof algorithm for DEEP-FRI is defined as follows:
Suppose we are given a polynomial of degree \( d \), \( p(X) \), and a predefined domain set \( \Omega = \{w_1, w_2, ..., w_n\} \), where \( n = qd \) (with \( q > 2 \)), and a collision-resistant hash function \( H \). The following steps are required during this phase:
The Folding phase recursively folds the query domain of the polynomial \(f^{(i)}(x)\) and generates a new polynomial, causing the degree of the polynomial to decrease in the next iteration. The process is as follows:
For the \( i \)-th round of folding (\( i < \log d \)):
1. Polynomial Query:
\[B_{Z^{(0)}}^{(1)}(x) = H_x[f^{(1)}]\]
2. Random Challenge and Polynomial Degree Reduction
The folding operation is as follows:
We have a function \( f^{(i+1)}: L^{(i+1)} \rightarrow F_q \), which is defined based on the quotient operation (QUOTIENT). When given \( y \) as input, the function \(F^{(i+1)}\) is defined as:
\[f^{(i+1)}(y)=\frac{H_{x^{(i)}}[f^{(i)}]-B_{Z^{(i)}}^{(1)}(x)}{y-z^{(i)}}.\]
Here are the details:
At the end of this step, if the folded polynomial is a constant \( C \) or has reached a predefined degree, the process ends.
The Query phase is primarily used to verify whether the final polynomial calculations are correct. The process is as follows:
1 .Repeat the query \( l \) times:
The verifier selects a random point \(s^{(0)}\) from the domain \( D \), and for each \( i \), defines the corresponding point \(S^{(i+1)}\), where \( S^{(i+1)} = q^{(1)}(S^{(i)}) \). The even term formula is:
\[f_{even}(X)=\frac{f(X)+f(-X)}{2}.\]
The odd term formula is:
\[f_{odd}(X)=\frac{f(X)+f(-X)}{2}.\]
· The prover provides the verifier with the values \(f^{(i+1)}(s^{(i+1)})\) and \(H_x{(i)}[f{(i)}]\) (evaluations of the polynomial \(f^{(i+1)}(X)\) at \(X=s^{(i+1)}\) and \(X=-s^{(i+1)}\) ), along with the corresponding Merkle path.
· The verifier checks if the corresponding values are in the Merkle tree and verifies the following equation:
\[H_{x}[f^{(i)}]=f^{(i+1)}(s^{(i+1)})\cdot(s^{(i+1)}-z^{(t)})+{B}_{Z^{(i)}}^{(i)}(x^{(i)}).\]
2. Final Result Verification: Check if the final polynomial calculation matches the pre-committed value \( C \). If not, reject; otherwise, accept.
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
