FRI is a key component in constructing cryptographic proof systems, specifically used in proof-of-computation systems like STARKs and Plonky2. The main purpose of the FRI protocol is to prove that a function corresponds to evaluations of a low-degree polynomial over a given domain. This is critical in STARKs because it allows for proving computational integrity efficiently and at scale.

FRI is used to confirm that a given set of evaluations correspond to a low-degree polynomial. This is achieved by using interactive techniques that incrementally reduce a high-degree polynomial to a constant, allowing the verifier to efficiently verify the claims without reconstructing the entire polynomial.

In STARKs, FRI is utilized as a low-degree test within the larger context of a zero-knowledge proof system. Plonky2, another proof system, also employs FRI to ensure low-degree constraints are met in their proof-of-computation processes.

FRI involves a process called "folding," which reduces the degree of a polynomial by combining coefficients through a random challenge (random folding). This is done to convince a verifier that the original function (which could be large and computationally expensive) is indeed a low-degree polynomial.

Here is the basic idea of folding:

• Split the polynomial into even and odd parts: $f_e(x)=a_0+a_2x+\dots$ and $f_o(x)=a_1+a_3x+\dots$ . Hence, we can represent the original polynomial as $f(x)=f_e(x^2)+xf_o(x^2)$
• Combine them with a random coefficient (challenge $\beta$)
• Create a new polynomial with half the degree: $f_1(y)=f_e(y^2)+\beta.yf_o(y^2)$
• Repeat this process recursively until you get a constant polynomial (degree zero).

Phases of FRI

FRI has several key phases:

• Commitment Phase: In this phase, the prover commits to the polynomial's evaluations by building a Merkle tree over a suitable domain. The Merkle root represents a cryptographic commitment, ensuring data integrity and enabling efficient verification.
• Decommitment Phase: Once the prover has committed to the polynomial, the next step is to demonstrate that the folding process was carried out correctly. This involves proving that certain evaluations belong to the Merkle tree and are derived from previous layers. This phase requires the prover to produce Merkle proofs for various values.
• Verification Phase: The verifier checks that the commitment was made correctly and the decommitment proof is valid. This involves verifying Merkle proofs, evaluating polynomial transformations through folding, and ensuring consistency with the final degree zero polynomial.

Detailed Explanation of the FRI Phases

• Layers and Commitment: The prover starts with a polynomial of a given degree, evaluates it over a domain, and commits to these evaluations via a Merkle tree. This initial commitment serves as the first FRI layer.
• Random Challenges and Folding: The prover then receives a random challenge (via the Fiat-Shamir transformation, simulating interaction), which is used to fold the polynomial and reduce its degree. This process continues through multiple rounds, creating additional layers, each with a Merkle tree commitment.
• Decommitment and Proof Generation: To verify that the folding was done correctly, the prover needs to provide Merkle proofs and evaluations for the chosen indices. The decommitment phase generates these proofs, demonstrating that the committed values in each layer are consistent with the previous ones.
• Verification and Querying: The verifier checks the proofs for each query (index) by verifying Merkle tree paths and the folding process to ensure that the final result aligns with a low-degree polynomial. The verifier also checks the final constant value against the committed data.

Security Considerations