FRI Polynomial Commitment Scheme

FRI Polynomial Commitment Scheme

The FRI (Fast Reed-Solomon Interactive Oracle) commitment scheme is a cryptographic protocol that plays a crucial role in various zero-knowledge proof systems. It's designed to efficiently prove the correctness of computations without revealing any underlying data. The FRI scheme is particularly important in the context of zk-STARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge), which are a type of non-interactive cryptographic proof that's scalable and doesn't require a trusted setup.

Problem addressed using FRI:

  1. Want P time linear in degree, not field size:

    • Let's say we use a Merkle tree for commitment to values in a field f. But this is very inefficient since if field f is big, then the number of leaves, and consequently the proof length grows significantly. In FRI, rather than P merkle-commiting to all (p-1) evaluations of q, P merkle-commits to evaluations of q(x) for \(x \in \Omega\) of \(F_p\).

    • \(\Omega\) has size \(\rho ^ {-1} k\) where \(\rho < 1/2\) constant and k is the degree of q.

    • Proof length will be about \(\lambda / log(\rho ^ {-1}). log^2(k)\) hash values where \(\lambda\) is the security parameter, aka. " \(\lambda\) bits of security ".

    • Let \(\omega \in F_p\), n is the smallest integer such that \(\omega ^ n = 1\), then \(\Omega = \{ 1, \omega, \omega ^2, \ldots, \omega ^ {n-1} \}\)

    • From group theory, \(\Omega\) has size n if and only if n divides p-1.

      • Hence, FRI based SNARKs work over fields like \(F_p\) with \(p = 2^{64} - 2^{32} + 1\) , p-1 is divisible by \(2^{32}\). Running FRI over the field can support any power of 2 value of n up to \(2^{32}\).
    • For eg. FRI commitment to univariate polynomial \(q(x)\) in \(F_{41}[X]\) when \(8 = \rho^{-1}.k\), where roots of unity = \(\{ 1, -1, 9, -9, 3, -3, 14, -14 \}\) becomes the root of the committed merkle tree.

To visualize roots of unity try this tool -> https://www.geogebra.org/m/sZFwAZfs

  1. V needs to know the committed vector at all evaluations over domain \(\Omega\) of some (k-1) degree polynomial.

    • V "inspects" a few entries of the vector to "get a sense" of whether its low-degree. This will add a Merkle authentication path ( log(n) hash values ) to the proof.

    • This is impractical. FRI's test will be interactive. We use a "folding phase" followed by a "query phase". The folding phase is log(k) rounds. The query phase is one round.


Folding Phase ( Interactive )

Step 1: Starting with a High-Degree Polynomial

  • The process begins with the prover having a high-degree polynomial. This polynomial is a representation of the computation or data they intend to prove something about.

Step 2: Interpolation and Evaluation

  • The polynomial is evaluated at various points. These points typically lie in a domain related to a specific subgroup of a finite field.

Step 3: The Folding Process

  • The prover reduces the degree of the polynomial. They select a subset of the evaluation points and merge the values of the polynomial at these points using a linear or affine transformation.

  • V picks up a random field element r, and r is used to "randomly combine" every two paired-up entries.

  • q(x) is split into "even and odd components" -> \(q(x) = q_e(X^2) + Xq_o(X^2)\)

  • The prescribed "folding" q is \(q_{fold}(Z) = q_e(Z) + rq_o(Z)\) where degree of \(q_{fold}\) is half of the degree of q.

Step 4: Recursive Application

  • What Happens: After folding, the polynomial's degree is lowered. The prover then commits to this new, reduced-degree polynomial. Folding is repeated until the degree falls to 0.

  • Why It Matters: This recursive process is essential for gradually simplifying the polynomial.

Step 5: End

  • The length of the folded vector after the degree has fallen to 0 is still \(\rho ^ {-1} >= 2\). Since the degree should be 0, P can specify the folder vector with a single field element.

( image credit: Justin Thaler lecture ( link in references ).

  • The calculation in the picture uses the fact that if x and -x are n'th roots of unity and z = \(x^2\). Then \(q_{fold}(z) = \frac{(r+x)}{2x} .q(x) + \frac{(r-x)}{-2x} .q(-x) \) ( derivation not covered in this post ).

  • FRI heavily uses the fact that the map \(x -> x^2\) is 2 to 1 on \(\Omega\), ensuring that the relevant domain halves in size with each fold.


Query Phase ( Interactive )

  • P may have "lied":

    • sending a vector that is not the prescribed folding of the previous vector

    • To "artificially" reduce the degree of the claimed folded vector.

  • The Query phase is where the verifier tries to detect inconsistencies.

  • V picks about \(\lambda / log ( \rho ^ {-1}) \) entries of each folded vector and confirming each is the prescribed linear combination of the relevant two entries of the previous vector.

  • Proof length ( and V time ): roughly \((\lambda / log(\rho ^ {-1})_. log(k)^2\) hash evaluations. Each of the folded vectors ( log(k) ) is queried at \(\lambda / log ( \rho ^ {-1})\)


  • For security analysis, refer the links in references. This article focuses on the working only.

  • There is a known attack where prover folders a polynomial s rather than q, where s agrees on a set T = \(\rho n\) elements of \(\Omega\).


Polynomial Commitment using FRI

  • Problems with FRI

    • P has only the Merkle-committed to evaluations of q over domain \(\Omega\), not the whole field.

    • V only knows that q is "not too far" from low-degree, not exactly low-degree.

  • Solution

    • We know \(q(X) - v = w(X)(X-r)\) is equivalent to \(q(r) = v\) ( refer here). w is a polynomial of degree at most d.

    • So to confirm \(q(r) = v\) V applies FRI's fold + query procedure to the functions \((q(X) - v)(X-r)^{-1}\) using degree bound d-1. Whenever the FRI verifier queries this function at \(\Omega\), evaluation can be obtained with one query to q at the same point.

    • V doesn't know that q is exactly a low degree, but to pass V's check, \(v\) has to equal \(h(r)\) where h is the degree d polynomial that is closest to q.

Each FRI verifies query brings <1 bit of security to the commitment scheme. FRI today is used as a weaker primitive tha a polynomial commitment ( list polynomial commitment scheme ), which suffices for SNARK security. P is bound to a "small set" of low-degree polynomials rather than to a single one.


Conclusion: The FRI commitment scheme represents a significant advancement in the field of cryptographic proofs, enabling more secure and efficient verification of computations in various applications, including blockchain technology and privacy-preserving computations.

Lastly, follow me on social media: Twitter, and LinkedIn for new updates in the cryptography space.


References:

  1. https://blog.lambdaclass.com/how-to-code-fri-from-scratch/

  2. Lecture by Justin Thaler Link

  3. https://chat.openai.com/

  4. https://eprint.iacr.org/2019/1020.pdf

  5. https://aszepieniec.github.io/stark-anatomy/fri.html