FRI Polynomial Commitment Scheme

· Cryptography & Blockchain

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