1. FRI Protocol Overview

1.1 Introduction

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.

1.2 Principles of FRI

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 $\mathrm{\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:

1. Compute $p(w_i)$ for each $i$, and use each $p(w_i)$ as a leaf node in a Merkle tree.
2. Construct the Merkle tree using the hash function $H$.
3. The Verifier uses the Merkle root as the commitment, and the Prover keeps the entire Merkle tree.

· 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$):

1. Compute the new domain ${\mathrm{\Omega }}_i:w_j\to w_j^2$ to ensure the polynomial retains the same property in subsequent domains.
2. The Verifier sends a random challenge $x$.
3. The Prover computes the folded 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.
4. Evaluate $p_{\text{fold}}(X)$ over the domain ${\mathrm{\Omega }}_i$, and use the results as leaf nodes in a Merkle tree, with the Merkle root ${\text{root}}_i$ serving as the commitment for the $i$-th round. Folding ends when the polynomial is reduced to a specific degree or a constant.

· 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):

1. Select a value $t$ from the set $\mathrm{\Omega }$.
2. The Prover responds with the corresponding $p(t)$ and its Merkle path;
   For $i=1$ to $\log d$:
3. >Compute $t=t^2$ as the next point to open;
4. he Prover responds with $p_{\text{fold}}(t)$ and the corresponding Merkle path;
5. Verify that $p_{\text{fold}}(t)=p_e(t)+t{p}_o(t)$.

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)+X{p}_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}$.

1.3 Instances of FRI

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.

1.3.1 Prover Decomposes the Polynomial

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(3x+1)$$

Therefore:

• $g_0(x^2)=2x^2+5$
• $h_0(x^2)=3x+1$

1.3.2 Verifier Sends a Random Value $a_0$

Next, the Verifier sends a random value $a_0$.

1.3.3 Prover Submits and Continues Decomposing

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)+x{h}_1(x^2).$$

Thus:

• $g_1(x^2)=2x^2+6$
• $h_1(x^2)=3$

1.3.4 Verifier Sends Random Value $a_1$

After the Prover has decomposed $f_1(x)$, the Verifier sends another random value $a_1$ for the next step.

1.3.5 Prover Submits and Continues Decomposing

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:

• $g_2(x^2)=2x^2+9$
• $h_2(x^2)=0$ (since there is no $x$-term)

1.3.6 Verifier Sends Random Value $a_2$

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$$

1.3.7 Constant (Polynomial) Submission

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.

2. DEEP-FRI Principles

2.1 Advantages

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.

2.2 Quotient Operation

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 set $L\subseteq F_q$, where this set is a subset of the finite field $F_q$.
• Given a function $f:L\to F_q$ that maps each element of the set $L$ to an element of $F_q$.

Given a point $z\in F_q$ and a value $b\in F_q$

2.2.1 Definition

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:

• $f_y$: The value of the original function at $y$.
• $b$: The given constant.
• $z$: The given point.

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$.

2.3 DEEP-FRI Process

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:

2.3.1 Commit

Suppose we are given a polynomial of degree $d$, $p(X)$, and a predefined domain set $\mathrm{\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:

1. Compute $p(w_i)$ for each $i$: Each $p(w_i)$ is used as a leaf node in a Merkle tree.
2. Construct the Merkle tree using hash function $H$: Use $H$ to build the Merkle tree.
3. Verifier checks the Merkle root: The verifier uses the Merkle root as the commitment, and the prover retains the entire Merkle tree.

2.3.2 Folding

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:

1. Both parties compute the next domain $L^{(i+1)}$.
2. In each round $i$, the verifier selects a random point $Z^{(i)}$ , which, with high probability, is not in the domain $L^{(i)}$.
3. The prover responds with a low-degree polynomial $f^{(i)}(x)$, following the given rules, to produce a new polynomial ${\mathcal{B}}_{Z^{(0)}}^{(1)}(x)$ satisfying the equation:

$$B_{Z^{(0)}}^{(1)}(x)=H_x[f^{(1)}]$$

2. Random Challenge and Polynomial Degree Reduction

1. The verifier sends a random challenge $x^{(i)}$.
2. The prover folds according to the rules and computes the evaluation of the folded polynomial over the domain $L^{(i+1)}$. All evaluation values are used as leaf nodes, constructing a Merkle tree and generating the corresponding Merkle root.

The folding operation is as follows:

We have a function $f^{(i+1)}:L^{(i+1)}\to 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:

1. $H_{x^{(i)}}[f^{(i)}]$: This is the new function value obtained after some transformation of $f_i$. The folding process here should follow the same folding strategy as FRI.
2. $z^{(i)}$: This is the given point $z$, which corresponds to the earlier quotient formula $Z(Y)=Y-z$. Here, $y-z^{(i)}$ is used in the denominator for the quotient operation.
3. $B_{Z^{(i)}}^{(i)}(x)$: This is another function or value related to $z_i$ and $x$, potentially a compensation term or target value.

At the end of this step, if the folded polynomial is a constant $C$ or has reached a predefined degree, the process ends.

2.3.3 Query

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