DEEP FRI

Brief recap of FRI

In FRI, our starting point is an input function f(0):L(0)Ff^{(0)} : \mathcal{L}^{(0)} \rightarrow \mathbb{F} where F\mathbb{F} is a finite field, L(0)F\mathcal{L}^{(0)} \subset \mathbb{F} 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 f(0)f^{(0)} is close to the Reed-Solomon code RS[F,L(0),ρ]\mathsf{RS}[\mathbb{F}, \mathcal{L}^{(0)}, \rho].

COMMIT phase:

  1. For i=0i = 0 to r1r - 1:

    1. The verifier picks uniformly random βiF\beta_i \in \mathbb{F} and sends it to the prover.

    2. The prover sends a merkle proof of a function f(i+1):L(i+1)Ff^{(i+1)} : \mathcal{L}^{(i+1)} \rightarrow \mathbb{F}. (In the case of an honest prover, f(i+1)=feven(i)+βifodd(i)f^{(i+1)} = f^{(i)}_{\mathsf{even}} + \beta_if^{(i)}_{\mathsf{odd}}).

  2. The prover sends a value CFqC \in \mathbb{F}_q. (In the case of an honest prover, f(r)f^{(r)} is the constant function with value = CC).

QUERY phase: (executed by the Verifier)

  1. Repeat ll times:

    1. Pick x0L(0)x_0 \in \mathcal{L}^{(0)} uniformly at random.

    2. For i=0i = 0 to r1r - 1:

      1. Define xi+1L(i+1)x_{i+1} \in \mathcal{L}^{(i+1)} by xi+1=xi2x_{i+1} = x_i^2.

      2. Query f(i)f^{(i)} at xix_i and xi-x_i to compute feven(i)(xi+1)f^{(i)}_{\mathsf{even}}(x_{i+1}) and fodd(i)(xi+1)f^{(i)}_{\mathsf{odd}}(x_{i+1}).

      3. Query f(i+1)(xi+1)f^{(i+1)}(x_{i+1}) and if feven(i)(xi+1)+βifodd(i)(xi+1)f(i+1)(xi+1)f^{(i)}_{\mathsf{even}}(x_{i+1}) + \beta_i f^{(i)}_{\mathsf{odd}}(x_{i+1})\neq f^{(i+1)}(x_{i+1}), then REJECT.

  2. If f(r)(xr)Cf^{(r)}(x_r) \neq C, then REJECT.

  3. ACCEPT

Properties

For V=RS[F,D,ρ]V=\mathsf{RS}[\mathbb{F}, D, \rho] where DD is an FFT-friendly domain (subgroup of size n=2kn=2^k), BBHR17 showed that FRI satisfies the following:

  • Prover time 6n\leq 6n, proof length n3\leq \frac{n}{3}

  • Verifier time 21logn\leq 21 \log n, query complexity 2logn\leq 2 \log n

  • Round complexity = logn2\frac{\log n}{2}

  • Soundness: Rejection probability of δ\delta-far words δo(1)\approx\delta-o(1) (which basically means it is a bit smaller but that is ignorable), for sufficiently small δ<δ0\delta < \delta_0

    • A word ww is said to be δ\delta-far from the code C\mathcal{C} if its Hamming distance from every codeword in C\mathcal{C} is at least δn\delta n)

    • δ0\delta_0 is a positive constant that depends mainly on the code rate.

  • In other words: Probability of rejecting δ\delta-far word is approximately min(δ,δ0)\min(\delta, \delta_0).

Understanding the Soundness

The soundness of a proximity testing protocol can be described by a soundness function s()s(\cdot) that takes as input a proximity parameter δ\delta, and outputs the minimum rejection probability of the verifier, where this minimum is taken over all words that are δ\delta-far from the code.

s(δ)=min{w s.t Δ(w,C)δ:Prrej(w)}s(\delta)= \min\{\forall w \text{ s.t }\Delta(w, \mathcal{C})\geq \delta: \mathsf{Pr}_{rej}(w)\}

where Prrej(w)Pr_{rej}(w) is the rejection probability of the word ww.

min(δ0,δ)o(1)s(δ)δ\min(\delta_0, \delta) - o(1) \leq s(\delta)\leq \delta

In the case of FRI soundness for a single test, an upper bound s(δ)δs(\delta) \leq \delta 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 δ\delta. In particular, the bound obtained there gives s(δ)min{δ,δ0}o(1)s(\delta) \geq \min\{\delta,\delta_0\} - o(1) where δ013ρ4\delta_0 \approx \frac{1-3 \rho}{4}.

For codes of ho1/3ho \geq 1/3, δ0\delta_0 becomes non-positive so the FRI protocol becomes meaningless. Even when considering the ideal case of ho0δ01/4ho \rightarrow 0\Rightarrow \delta_0 \rightarrow 1/4. 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 2λ2^{-\lambda}, then how many tests do we need?

min rejection probability s(δ)1/4max acceptance probability after l queries (114)l\text{min rejection probability } s(\delta)\geq 1/4 \Rightarrow \text{max acceptance probability after }l \text{ queries } \leq(1-\frac{1}{4})^l
(114)l2λllog234λlλlog2342.4λ(1-\frac{1}{4})^l \leq 2^{-\lambda}\Rightarrow l\cdot log_2\frac{3}{4}\leq-\lambda\Rightarrow l \geq-\frac{\lambda}{\log_2{\frac{3}{4}}}\approx2.4\lambda

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 δ0\delta_0.

  1. Original FRI paper [BBHR17]:

δ013ρ4l2.4λ\delta_0 \approx \frac{1-3\rho}{4} \Rightarrow l \geq 2.4\lambda
  1. Worst-to-average case reduction [BKS18]:

δ01ρ4l4λlog1ρ\delta_0 \approx 1-\sqrt[4]{\rho}\Rightarrow l\geq\frac{4\lambda}{\log\frac{1}{\rho}}
  1. Improved bound from Lemma 3.1 of [BGKS20]:

δ01ρ3l3λlog1ρ\delta_0\approx 1-\sqrt[3]{\rho}\Rightarrow l\geq \frac{3\lambda}{\log\frac{1}{\rho}}

From the second result, we can see that when ho0ho \rightarrow 0, δ01\delta_0 \rightarrow 1 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 λ\lambda bit security from 4λlog1ρ\frac{4\lambda}{\log\frac{1}{\rho}} to 3λlog1ρ\frac{3\lambda}{\log\frac{1}{\rho}} which is ~25% less.

In addition, Lemma 3.1 is shown to be tight under a special case:

  1. F\mathbb{F} is a binary field

  2. ho=1/8ho = 1/8 precisely

  3. Evaluation domain DD equals all of F\mathbb{F}

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 L(0)\mathcal{L}^{(0)} with a low-degree polynomial. Then how does the verifier differentiate between such pretenders and an actual low-degree polynomial? If we sample x0L(0)x_0\in \mathcal{L}^{(0)}, we won't find any discrepancies. Therefore, we attempt to sample outside the evaluation domain using quotient functions.

Quotienting

If f(0)f^{(0)} is indeed evaluations of low-degree polynomial P(X)P(X) on DD then verifier should be able to query PP on an arbitrary zFz\in\mathbb{F}. Suppose the prover claims P(z)=aP(z)=a, then P(X)aP(X) - a is divisible by XzX-z so let's denote it as:

QUOTIENT(P,z,a)=P(X)aXz\mathsf{QUOTIENT}(P, z, a) = \frac{P(X) - a}{X-z}

COMMIT phase:

  1. For i=0i = 0 to r1r - 1:

    1. The verifier picks uniformly random βi,ziF\beta_i, z_i \in \mathbb{F}.

    2. The prover sends feven(i)(zi)+βifodd(i)(zi)=af^{(i)}_{even}(z_i) + \beta_i f^{(i)}_{odd}(z_i)=a.

    3. The prover sends a merkle proof of a function f(i+1):L(i+1)Ff^{(i+1)} : L^{(i+1)} \rightarrow \mathbb{F}. (In the case of an honest prover, f(i+1)(X)=QUOTIENT(feven(i)(X)+βifodd(i)(X),zi,a))f^{(i+1)}(X)=\mathsf{QUOTIENT}(f^{(i)}_{\mathsf{even}}(X) + \beta_i f^{(i)}_{\mathsf{odd}}(X), z_i, a)).

  2. The prover sends a value CFqC \in \mathbb{F}_q. (In the case of an honest prover, f(r)f^{(r)} is the constant function with value = CC).

QUERY phase: (executed by the Verifier)

  1. Repeat ll times:

    1. Pick x0L(0)x_0 \in \mathcal{L}^{(0)} uniformly at random.

    2. For i=0i = 0 to r1r - 1:

      1. Define xi+1L(i+1)x_{i+1} \in \mathcal{L}^{(i+1)} by xi+1=xi2x_{i+1} = x_i^2.

      2. Query f(i)f^{(i)} at xix_i and xi-x_i to compute fodd(i)(xi+1)f^{(i)}_{\mathsf{odd}}(x_{i+1}) and feven(i)(xi+1)f^{(i)}_{\mathsf{even}}(x_{i+1}).

      3. If (feven(i)(xi+1)+βifodd(i)(xi+1))a(xi+1zi)f(i+1)(xi+1)\frac{(f^{(i)}_{\mathsf{even}}(x_{i+1}) + \beta_i f^{(i)}_{\mathsf{odd}}(x_{i+1})) - a}{(x_{i+1} - z_i)}\neq f^{(i+1)}(x_{i+1}), then REJECT.

  2. If f(r)(xr)Cf^{(r)}(x_r) \neq C, then REJECT.

  3. ACCEPT

Resulting soundness

As a result of applying the DEEP technique, the soundness claim was improved to:

δ01ρl2λlog1ρ\delta_0 \approx 1-\sqrt{\rho}\Rightarrow l\geq \frac{2\lambda}{\log\frac{1}{\rho}}

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 nn is much smaller than the size of the field qq (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 δ(0,1ρ)\delta \in (0, 1 - \sqrt{\rho}), 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