DEEP FRI
Brief recap of FRI
In FRI, our starting point is an input function where is a finite field, is the evaluation domain. The FRI protocol is a two-phase protocol (the two phases are called COMMIT and QUERY) that convinces a verifier that is close to the Reed-Solomon code .
COMMIT phase:
For to :
The verifier picks uniformly random and sends it to the prover.
The prover sends a merkle proof of a function . (In the case of an honest prover, ).
The prover sends a value . (In the case of an honest prover, is the constant function with value = ).
QUERY phase: (executed by the Verifier)
Repeat times:
Pick uniformly at random.
For to :
Define by .
Query at and to compute and .
Query and if , then REJECT.
If , then REJECT.
ACCEPT
Properties
For where is an FFT-friendly domain (subgroup of size ), BBHR17 showed that FRI satisfies the following:
Prover time , proof length
Verifier time , query complexity
Round complexity =
Soundness: Rejection probability of -far words (which basically means it is a bit smaller but that is ignorable), for sufficiently small
A word is said to be -far from the code if its Hamming distance from every codeword in is at least )
is a positive constant that depends mainly on the code rate.
In other words: Probability of rejecting -far word is approximately .
Understanding the Soundness
The soundness of a proximity testing protocol can be described by a soundness function that takes as input a proximity parameter , and outputs the minimum rejection probability of the verifier, where this minimum is taken over all words that are -far from the code.
where is the rejection probability of the word .
In the case of FRI soundness for a single test, an upper bound is easy to establish but the more important part is establishing a lower bound. The initial analysis in BBHR18b showed a nearly matching lower bound for sufficiently small values of . In particular, the bound obtained there gives where .
For codes of , becomes non-positive so the FRI protocol becomes meaningless. Even when considering the ideal case of . This rather low soundness means that many tests must be applied in order to reach a target soundness error. For example, to achieve a target soundness error of , then how many tests do we need?
This shows that for 128-bit security, we need more than 300 queries. So to reduce this number, we need to have a better soundness lower bound.
Improvements in the soundness lower bound
Following the limitations of FRI, there were some works that improved upon the .
Original FRI paper [BBHR17]:
Worst-to-average case reduction [BKS18]:
Improved bound from Lemma 3.1 of [BGKS20]:
From the second result, we can see that when , which is a big improvement for the soundness of FRI. Building on top of that, Lemma 3.1 improved the number of tests required for bit security from to which is ~25% less.
In addition, Lemma 3.1 is shown to be tight under a special case:
is a binary field
precisely
Evaluation domain equals all of
Therefore, we needed something different to break this soundness barrier and the DEEP (Domain Extension for Eliminating Pretenders) method was introduced.
DEEP FRI
First, what do we mean by “pretenders”? Let's say a malicious prover has a very large degree polynomial that agrees on all of with a low-degree polynomial. Then how does the verifier differentiate between such pretenders and an actual low-degree polynomial? If we sample , we won't find any discrepancies. Therefore, we attempt to sample outside the evaluation domain using quotient functions.
Quotienting
If is indeed evaluations of low-degree polynomial on then verifier should be able to query on an arbitrary . Suppose the prover claims , then is divisible by so let's denote it as:
COMMIT phase:
For to :
The verifier picks uniformly random .
The prover sends .
The prover sends a merkle proof of a function . (In the case of an honest prover, .
The prover sends a value . (In the case of an honest prover, is the constant function with value = ).
QUERY phase: (executed by the Verifier)
Repeat times:
Pick uniformly at random.
For to :
Define by .
Query at and to compute and .
If , then REJECT.
If , then REJECT.
ACCEPT
Resulting soundness
As a result of applying the DEEP technique, the soundness claim was improved to:
Final Remarks
The special case for tightness of the lower bound in Lemma 3.1 is something we can ignore. If we assume that the length of the code is much smaller than the size of the field (which is the case for practical STARK implementations), this bound can be improved significantly. Investigating this further, the authors of BCIKS2023 figured that when working with RS code over a sufficiently large field—polynomially large in the code’s blocklength—and when , the average-case distance is almost the same as the worst-case distance. With this, they claim that FRI can achieve the same soundness as DEEP FRI without its added prover complexities. However, the out-of-domain sampling method introduced in this paper is still used widely to improve the soundness of the underlying protocol (for example STIR).
References:
BBHR17
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. 2018. Fast Reed-Solomon interactive oracle proofs of proximity. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Retrieved from https://eccc.weizmann.ac.il/report/2017/134
BBHR18b
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Retreived from https://drops.dagstuhl.de/storage/00lipics/lipics-vol107-icalp2018/LIPIcs.ICALP.2018.14/LIPIcs.ICALP.2018.14.pdf
BKS18
Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. 2018. Worst-case to average case reductions for the distance to a code. In Proceedings of the 33rd Computational Complexity Conference. 24:1–24:23. DOI:https://doi.org/10.4230/ LIPIcs.CCC.2018.24
BGKS20
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. 2020. DEEP-FRI: Sampling outside the box improves soundness. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (LIPIcs), Thomas Vidick (Ed.), Vol. 151. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 5:1–5:32. DOI:https://doi.org/10.4230/LIPIcs. ITCS.2020.5
BCIKS2023
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. 2023. Proximity Gaps for Reed–Solomon Codes. J. ACM 70, 5, Article 31 (October 2023), 57 pages. https://doi.org/10.1145/3614423
Written by Batzorig Zorigoo from A41
Last updated