FRI Polynomial Commitment With Code Walkthrough

Polynomial commitment schemes are widely used in blockchain infrastructures, forming the backbones of zero knowledge and validity proving which in recent years has accelerated in terms of adoption. KZG is a popular commitment scheme based on elliptic curve pairing (see my other post explaining it), however there are growing concerns on the hardness of the discrete logarithm problem due to the rise of quantum computing. In this article, we would walk through another polynomial commitment scheme, namely Fast Reed-Solomon IOP of Proximity (FRI), which is hash-based and thus quantum resistant.

Supposing you have a large polynomial with tens of thousands of coefficients. To check that a point belongs on the polynomial, the naive way is for the verifier to have access to the entire polynomial coefficients and evaluate that the point indeed lies on the said polynomial. This is not practical for verifier which is resource constrained. Similar to the usual polynomial commitment schemes, in FRI the prover will commit the polynomial, which allows the verifier to use the much smaller commitment to verify the evaluation points on the polynomial.

Commitment Phase

During the commitment phase, the core concept of FRI is to fold the original polynomial repeatedly until a desired size. The folding process takes the polynomial and separate it into its odd and even components. For example, a polynomial of f(x) = 1 + 2x + 3x² + 4x³ + 5x⁴ + 6x⁵ + 7x⁶ + 8x⁷ will be separated into its odd component f_odd(x) = 2x + 4x³ + 6x⁵ + 8x⁷ and its even component f_even(x) = 1 + 3x² + 5x⁴ + 7x⁶. The resulting polynomial is then f(x) = f_even(x²) + x* ​f_odd(x²). The odd and even polynomials are then mixed together with a randomness r to form the next polynomial. The randomness is provided by the verifier in an interactive protocol, but usually obtained through the fiat shamir transformation for non-interactivity.

Splitting the mixing the polynomial using the example above. The resulting polynomial for the next round is f_1(x).

As you can see with the example above, the resulting polynomial now only has degree 3, and the size of the polynomial has been reduced by half from its original polynomial. We repeat the process of splitting and mixing until achieving a final polynomial with the desired size.

During each round of folding the polynomial, the polynomial is converted from the coefficient form to the evaluation form with a constant blowup factor. For example, if the blowup factor is 4, a polynomial with 8 coefficients will be evaluated at 32 points. The evaluations points will be the root of unity points, which are w⁰, w¹, w² and so on. These evaluation points are then arranged as the leaves of a merkle tree, where the corresponding merkle root is the commitment for that particular round.

Query Phase

Now that the prover has produced the commitments, the verifier is able to query the commitment and verify that the prover indeed commit them honestly. The verifier will query a single evaluation point from the roots of unity points that are used to generate the commitment. The prover then provide the evaluations at that point and also its negative counterpart. For example, if the verifier queries point g, the prover will provide evaluations of f(g) and f(-g) for the original polynomial. Recall that during the commitment phase, the provider commits a merkle root at each round. Thus, the prover will also provide the corresponding merkle path to the root based on the evaluation point provided by the verifier. The prover repeats this process for each round, where the evalution point is squared each round. For example, if the verifier queries point g, the prover provide evaluations of f(g) and f(-g) for the first round, f(g²) and f(-g²) for the second round and so on.

The verifier will end up with a proof for each round that consists of the positive and negative evalution points, and the corresponding merkle paths to the commitment.

Verify Phase

With these proofs, the verifier can now verify that the polynomial is committed correctly. For each round of polynomial, the verifier verifies two things — (i) the evaluation points provided are indeed in the committed merkle tree and (ii) the evaluation points have the correct relationship with the evaluations points of the previous round, as shown in the formula below.

Relationship of evaluation points with the previous round. Detailed explanation of this relationship is well described here.

The intuition is that the folding done by the prover can be checked locally simply by using random evaluation points.

We have now completed an end-to-end FRI protocol. The verifier does not need to carry out the heavy computation of a polynomial evaluation (especially when the polynomial is very large), and can delegate the evaluation work to a prover, yet still being able to verify that it is done correctly by comparing the proofs against the commitments.

Feel free to check out the full implementation or leave any questions that you have!