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:
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
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: