FRI-based Commitments for Data Availability
The FRI scheme is renowned as a cornerstone of STARKs and can also serve as the basis for a polynomial commitment scheme using the DEEP-FRI method.
Part 3 of a Series on Polynomial Commitment Schemes for NomosDA. Read Part 1 here, Part 2 here, and Part 3 here.
FRI, short for Fast Reed-Solomon Interactive Oracle Proof of Proximity, is a scheme introduced in a 2017 paper for proving that a previously committed polynomial has a degree lower than some maximum. The FRI scheme is renowned as a cornerstone of STARKs and can also serve as the basis for a polynomial commitment scheme using the DEEP-FRI method. This FRI-based scheme was among the top candidates for NomosDA’s choice of PCS due to qualities including post-quantum security, a lack of trust assumptions, and a simple mathematical basis. As in our previous installments, we will describe how the scheme works, followed by an analysis based on our criteria from Part 1.
How FRI Works as a PCS
Committing to a Polynomial
In its basic form, the FRI protocol is used to prove that a given function is “close to” some polynomial with a specified maximum degree. This notion of closeness is determined by the fractional Hamming distance \(\delta\) between the function \(f\) and the bounded degree polynomial \(p\), which is defined as:
$$ \delta(f, p)=\frac{|\{x\in D : f(x)\neq p(x)\}|}{|D|} $$
That is, the size of the set of inputs \(x\) from the domain \(D\) (in our case, a multiplicative subgroup of a finite field) for which the evaluations of \(f\) and \(p\) are not equal, as a fraction of the total order of the domain. As we shall see, it is helpful to choose a subgroup \(D\) with an order \(|D|=n\) that is a power of \(2\). The degree bound of \(p\), which is much less than \(n\), is referred to as a “low degree”.
Reed-Solomon Codewords
In truth, the FRI protocol does not use \(p\) directly. Instead, it attempts to prove that \(f\) is close to a Reed-Solomon codeword. A Reed-Solomon code is an error-correcting code that consists of the evaluations of a polynomial \(p(x)\) over elements from some subgroup \(D\) of a finite field, and a Reed-Solomon codeword is the length \(2\cdot (deg(p)+1)=n\) sequence of elements resulting from one such evaluation, as below:
$$ \{p(\omega^i)\}|_{i=0}^{n-1} $$
\(deg(p)+1\) is referred to as the message length, and is less than the order of \(D\) by at least the rate \(\rho\) (for our purposes, \(\rho=\frac{1}{2}\)). Because any \(k\)-degree polynomial can be uniquely determined by \(k+1\) points satisfying the polynomial equation, the full codeword can be reconstructed with at least \(k+1\) elements from the codeword. Crucially for our purposes, this also means that this codeword can be used to represent \(p\) in the FRI protocol. For reasons that will become clear below, we will ensure that the degree of \(p\) is one less than a power of \(2\).
Since a Reed-Solomon codeword can be used to represent a polynomial with a low degree, committing to that polynomial is equivalent to committing to this codeword. This can be accomplished fairly simply by generating a Merkle tree of the elements in the codeword, with the polynomial commitment being the root of this tree.
Proving an Evaluation with DEEP-FRI
The FRI protocol typically proceeds with an interactive folding process, in which the prover and verifier interact to produce increasingly smaller codewords over smaller domains, finally yielding a single constant. The verifier then checks that the equivalency relations between each word and its reduced counterpart hold. If these round consistency checks pass, the verifier can be confident that the function committed to was close to a polynomial of low degree.
The DEEP-FRI (Domain Extension for Eliminating Pretenders) protocol modifies the above in order to produce the proof and verification stages of a polynomial commitment scheme. The basic insight underlying DEEP-FRI is that the evaluation quotient function
$$ h(x)=\frac{f(x)-v}{x-u} $$
is a polynomial if and only if the evaluation \(f(u)=v\) is true. Moreover, the degree of \(h\) will be one less than the degree of \(f\), provided that the evaluation holds. Therefore, running a low degree check for \(h\) is equivalent to proving that the above evaluation is correct. The rest of this article will concern itself with describing the modified DEEP-FRI protocol in its non-interactive form.
Folding
In the first protocol, known as the commit phase (not to be confused with the polynomial commitment Merkle root mentioned above), the prover will generate a proof for their evaluation \(f(u)=v\) by proving that the evaluation quotient \(h\) has a degree less than \(\rho\cdot|D|\) - that is, half the order of the domain.
As a polynomial function, \(h\) can be represented in the form \(\sum c_ix^i\) for every term \(i\). To reduce this function, the prover will first decompose it into its even and odd polynomial “parts”:
$$ h(x)=h_e(x^2)+x\cdot h_o(x^2) $$
where \(h_e\) is the polynomial with the even-numbered coefficients \(\sum c_{2i}x^{i}\) and \(h_o\) is the polynomial with the odd-numbered coefficients \(\sum c_{2i+1}x^{i}\). To ensure that the degrees of \(h_e\) and \(h_o\) are half that of \(h\), we use \(x^2\) as the input to these polynomial functions in this decomposition. Additionally, we multiply \(h_o(x^2)\) by \(x\) to correspond with the correct powers of the odd terms in \(h(x)\). Another, equivalent way to define these functions is:
$$ h_e(x)=\frac{h(x)+h(-x)}{2} \\ h_o(x)=\frac{h(x)-h(-x)}{2x} $$
Now, the prover will use the Fiat-Shamir heuristic to non-interactively obtain a random scalar \(\alpha\). This scalar is used to construct a reduced polynomial \(h'\) with half the degree of \(h\):
$$ h'(x)=h_e(x)+\alpha\cdot h_o(x) $$
The prover then proceeds to generate a new Reed-Solomon codeword for \(h'\). This codeword will be the result of the evaluation of \(h'\) over a smaller subgroup \(D'\) generated by \(\omega^2\). Thus, the new codeword is calculated to yield a list of \(\frac{n}{2}\) elements, corresponding to the order of \(D'\):
$$ \{h'(\omega^{2i})\}|_{i=0}^{\frac{n}{2}-1} $$
The folding process described above is repeated by the prover, reducing \(h'\) into \(h''\) and so on. Because we chose an initial polynomial with a degree one less than a power of \(2\), and likewise an initial subgroup with an order of some power of \(2\), the halving process in each round will always result in a simple, integer degree.
Once the prover reaches a reduced polynomial of degree \(0\), it sends this constant to the verifier along with the Merkle roots of the codewords generated in each round of reduction. This list, taken together, is the proof of the FRI scheme.
Verifying a DEEP-FRI Proof
The verification phase of DEEP-FRI is also known as the query phase. To verify the proof received from the prover, the verifier conducts round consistency checks to ensure that the folding was conducted correctly. Before beginning the checks, the verifier will select a random index \(i\), which will be used to generate the random elements used in each round’s consistency check.
For each round \(r\), the verifier will generate a pair of distinct elements \(s_0, s_1\) in the domain \(D_r\) that are square roots of an element \(s_2\) in the reduced domain \(D_r'=D_{r+1}\). This is accomplished by using the random index \(i\) and calculating
$$ s_0=\omega_r^i\\ s_1=-\omega_r^{i}=\omega^{i+|D_r|}\\ s_2=\omega_r^{2i}=\omega_{r+1} $$
where \(\omega_r\) is the generator of \(D_r\). At this point, the verifier will sample the elements from the codeword of \(h_r\) corresponding to \(s_0\) and \(s_1\) to produce two evaluation pairs: \((s_0, h_r(s_0))\) and \((s_1, h_r(s_1))\). Note that the prover must provide the Merkle paths corresponding to these values in order for the verifier to have access to them.
These two pairs are used to interpolate the unique degree one polynomial \(q\) satisfying these evaluations - that is, such that \(q(s_0)=h_r(s_0)\) and \(q(s_1)=h_r(s_1)\). If the prover acted honestly during the commit phase, the verifier should end up with the function below after performing Lagrange interpolation with the sampled evaluation pairs:
$$ q(x)=\frac{(1 + x \cdot \omega_r^{-i}) \cdot h_r(\omega_r^i) + (1 - x \cdot \omega_r^{-i}) \cdot h_r(-\omega_r^{i})}{2} \\ $$
This function can be regrouped to yield some familiar functions:
$$ q(x)=\frac{h_r(\omega_r^i) + x \cdot \omega_r^{-i}\cdot h_r(\omega_r^i) + h_r(-\omega_r^{i}) - x \cdot \omega_r^{-i}\cdot h_r(-\omega_r^{i})}{2} \\ =\frac{h_r(\omega_r^i)+h_r(-\omega_r^i)}{2} + x\frac{h_r(\omega_r^i)-h_r(-\omega_r^i)}{2\omega^i} $$
As it turns out, this is just a linear combination of \((h_r)_e(\omega_r^i)\) and \((h_r)o(\omega^i_r)\). Therefore, if the protocol was followed correctly, plugging in that round’s random scalar \(\alpha_r\) (regenerated by the verifier via Fiat-Shamir) will make \(q(\alpha_r)\) equivalent to \(h_{r+1}(\omega^{2i})\).
In short, the verifier uses their generated elements and corresponding evaluations \((s_0, h_r(s_0))\) and \((s_1, h_r(s_1))\) to generate a unique degree one polynomial \(q(x)\). If this polynomial’s evaluation using \(\alpha_r\) equals the evaluation \(h_{r+1}(\omega^{2i})\), then the verifier can be satisfied that the prover acted honestly during this round of folding. If this verification process is successful for every successive pair of codewords, the verifier can be reasonably satisfied that the proof is correct. For greater confidence, this test can be repeated with several random indices.
Batching
One important property of the FRI scheme is that several proofs can be batched together and verified in the same time as it takes to create and verify a proof for a single evaluation or low-degree claim. For \(m\) polynomials \(p_0(x), p_1(x), ..., p_{m-1}(x)\), the prover generates a random scalar \(\lambda\) using Fiat-Shamir and calculates the combination
$$ h(x)=\sum_{i=0}^{m-1} \lambda^i \cdot p_i(x) $$
The FRI protocol is then run on \(h\) instead of on each \(p_i\), with the verifier conducting an additional consistency check at every round of the query phase to ensure that the above relation between the codeword for \(h_r\) and the codewords for the \((p_i)_r\) polynomials hold. If this is done, a successful verification of the low degree status of \(h\) will be equivalent to verifying the low degree status of all the \(p_i\) polynomials.
Analysis
While FRI’s post-quantum security is its biggest selling point, its use of simple Merkle trees and no trusted setup make FRI-based commitments even more attractive for our purposes. That said, FRI’s performance is not the best, with both a verification time and proof size of \(\mathcal{O}(\log^2(n))\). FRI’s proof time of \(\mathcal{O}(n)\) is the same as the proof time of the KZG and IPA schemes. However, these performance issues can be reduced by batching several proofs together, or by employing some other optimisation techniques described in the literature.