Exploring FRI Commitment Scheme

FRI is a protocol between a prover and a verifier that demonstrates a codeword belongs to a low-degree polynomial. In this protocol, the prover, who knows the entire codeword, Merkle commits to it. The verifier, who knows the Merkle roots, requests openings at randomly chosen leaves to verify the encoding’s correctness and establish the membership of these leaves in the committed Merkle tree.

Overview

FRI — Fast Reed-Solomon IOP of Proximity is a polynomial commitment scheme that enables building an efficient proof system in which a prover commits to a polynomial and demonstrates to a verifier that the polynomial has a bounded degree d, without the need to reveal the entire polynomial.

More specifically, the FRI protocol allows to check that a function h(X) is close to being a polynomial over a finite subset θ ⊆ 𝔽, of which degree of the polynomial lasts below a certain threshold d.

Important Concepts

1. Codeword A codeword represents the evaluations of a low-degree polynomial on a finite domain θ. Size of domain θ, n = |θ| = r^-1 * d = 2^t, where d is degree of the polynomial and r^-1 is blowup factor. Domain size n should be power of 2.

2. Folding Split a large claim w into two reduced claims w₁ and w₂ half of the original size. Then both w(1) and w(2) are merged into a new claim w^ which is half of the original size w but includes both w₁ and w₂. The merge requires randomness provided by the verifier.

• The reduction can be iteratively repeated until the final claim w(x) is of trivial size, and can be quickly verified.
• If w(x) is true, then the original claim w must be true.

3. Merkle Tree Merkle trees are special kind of binary tree which has leaf nodes which includes the data or hash of data. And all intermediate nodes and the root node is hash of the corresponding left and right child values. Merkle path (or merkle-proof) is set of elements (size = log(n), where n is tree size) from the tree which can be used to prove a leaf is part of the tree (in logarithmic time complexity) without checking the whole tree (time complexity: linear).

How does FRI work?

FRI protocol consists of two phases:

1. Commitment Phase: The prover commits to folded vectors and sends Merkle roots of those vectors to the verifier.

2. Query Phase: The verifier requests the opening of a random element xᵢ ⊆ θ and verifies that the folding has been done correctly.

Important : The verifier does not know the function h(X). He only gets openings at specific values and Merkle commitments.

Commitment Phase

Phase 0: Commit to Codewords Evaluation domain, θ = ( w^j ) for all j ∈ [0, n] is a n-th root of unity. Generate Merkle Tree using all the evaluations (codewords) of h(X) on domain θ, where h(X) is a low degree-d polynomial. Commit the merkle root to the verifier. Phase 1: Folding In this phase, the prover and the verifier engage with an interactive protocol to fold the original polynomial into a constant size polynomial of degree = 0.

We divide the polynomial h in two halves e and f such that, h(x) = ∑cₜxᵗ = e(x²) + x * o(x²) where e(x²) has all elements with even powers and x * o(x²) has all elements with odd powers.

Now we fold it by, h’(z) = e(z) + β * o(z) where z = x² and β is a random value from verifier Polynomial h’(z) has degree = d/2 now and due the properties of algebraic fields the domain size of h’(z) also reduces by half. Again we compute the all the evaluations of h’ in new domain, generate merkle tree from the evaluation vector and commit the merkle root to the verifier.

This steps of folding and committing to the folded evaluations vectors is repeated until log(d) steps where degree of the folded polynomial becomes d’ = floor(d/2^(log(d) + 1)) = floor(d/2d) = 0 This means the last folded polynomial is of degree 0 basically a constant value. The generalised folded equation after t-th fold, hₜ(x) = eₜ₋₁(x²) + β * oₜ₋₁(x²) We can show that, hₜ(x²) = (β + x)/2x * hₜ₋₁(x) + (β - x)/-2x * hₜ₋₁(-x). That means we can compute values of hₜ using the values of hₜ₋₁ in two points.

Query Phase

In query phase, the verifier checks if the prover has done the foldings correctly. To do so, the verifier picks a random index j and asks the prover to reveal the evaluation h(w^j).

For each query j,

1. Verifier sends j to the prover
2. The prover then computes,

• h(w^j) and h(-w^j) in top layer
• h₀(w^2j) and h₀(-w^2j) in folding layer 0
• h₁(w^4j) and h₁(-w^4j) in folding layer 1 …
• and so on until layer k = log(d)

3. Along with the evaluations the prover also sends the merkle path or authentication path of every value to the verifier.
4. From the merkle paths verifier checks if an evaluation is part of the corresponding merkle tree or not.
5. From the evaluations at each level the verifier checks if folding of the next level is done correctly or not.

Conclusion

FRI is a relatively new commitment scheme that is originally an interactive protocol but can be transformed into a non-interactive one using the Fiat-Shamir transformation. It boasts better prover time complexity, at nlog(n), compared to the n² complexity of the Groth16 zkSNARKs scheme. Although FRI has logarithmic proof size and verification time (log²(n)) compared to the constant proof size and verification time of Groth16. It is more preferable in scenarios where provers have limited computing resources.