FRI Binius - HackMD

# FRI Binius A PCS for multilinear polynomials over small fields with polylogarithmic verifier and zero embedding overhead. "FRI-Binius = Sum-Check + FRI + Packing" ## References FRI Binius (Diamond & Posen 2024): https://eprint.iacr.org/2024/504 Binius: (Diamond & Posen 2023) https://eprint.iacr.org/2023/1784 Novel Polynomial Basis (Lin, Chung, Han 2014): https://arxiv.org/abs/1404.3458 BaseFold (Zeilberger, Chen, Fisch 2023) https://eprint.iacr.org/2023/1705 ## Outline - Reed Solomon Review - FRI Review - Non-packing version ("multilinear FRI-like PCS") - Packing version ## Reed-Solomon Code - Message: polynomial $P$ of degree $<k$ - Codeword: evaluations of $P$ on some domain $D$ of size $n > k$. - Minimum Distance: $n-k+1$ (two distinct polynomials of degree $k-1$ agree on at most $k-1$ points) - Efficient Encoding: If $n$ a power of 2 and $D$ consists of the $n$th roots of unity, then the encoding map is FFT, which we can compute in $O(n \log n)$ ## FRI Review - Prover has a polynomial $P(X) \in K[X]^{<2^\ell}$ of degree less than $2^\ell$. - Prover computes RS encoding w.r.t. domain $D^0$ the set of $2^{\ell + R}$ roots of unity - Call this codeword $f^0: D^0 \to K$. If Prover was honest, then $f^0(x) = P(x)$ for all $x \in D^0$ - $P$ denotes an actual polynomial held by an honest prover - $f$ denotes a purported codeword sent to a verifier - FRI is a protocol for proving that $f^0$ is close to a codeword - By the minimum distance property of RS encoding, being close enough to a codeword implies a unique decoding - Can be used to construct a PCS ### Commit phase: - $\ell$ rounds of interaction - Each round maps domain $D^i$ to $D^{i+1}$ of half the size - Function $f^i$ over $D^i$ is mapped to function $f^{i+1}$ over $D^{i+1}$ - If prover is honest, each function $f^i$ is a codeword, i.e. is evaluations of a polynomial $P^i$ - Each round halves the degree of $P^i$ - So after $\ell$ rounds, original $P^0 = P$ has been reduced to a constant In each round: - Prover holds $P^i(X)$ from previous round ($P^0 = P$) - Prover decomposes $$P^i(X) = P^i_E(X^2) + X \cdot P^i_O(X^2)$$ - Verifier sends random $r_i$ - Prover "folds" $P^i$ using $r_i$ to get $P^{i+1}(X) = P^i_E(X) + r_i P^i_O(X)$ - Prover sends codeword $f^{i+1}: D^{i+1}\to K$. Here $D^{i+1} = \{ x^2 | x \in D^i\}$ and $f^{i+1}$ is the evaluations of $P^{i+1}$ on this domain In last round, prover has a constant polynomial $P^\ell = c$ and sends this value to verifier. ### Sampling phase: - The commit phase is only meaningful if the codewords $f^i, f^{i+1}$ are related to each other. - If the prover was honest, his polynomials are related by $$P^{i+1}(x^2) = \frac{P^i(x) + P^i(-x)}{2} + r_i\frac{P^i(x) - P^i(-x)}{2x}$$ So Verifier can check the consistency of codewords $f^i$ across rounds by - Choosing some initial $x_0 \in D^0$ - Letting $x_{i+1} = x_i^2$ - Checking $f^{i+1}(x_{i+1}) = \frac{f^i(x_i) + f^i(-x_i)}{2} + r_i\frac{f^i(x_i) - f^i(-x_i)}{2x_i}$ - Final claim: $c = \frac{f^{\ell-1}(x_{\ell-1}) + f^{\ell-1}(-x_{\ell-1})}{2} + r_{\ell-1}\frac{f^{\ell-1}(x_{\ell-1}) - f^{\ell-1}(-x_{\ell-1})}{2x_{\ell-1}}$ ## Abstract FRI FRI can be generalized. For example, we used $X \mapsto X^2$ to reduce $\deg P^i$ by half, but we could have used $X \mapsto X^a$ to reduce it by a factor of $a$. We could even have used a different reduction map at each step. The abstract description of FRI that will be used by FRI Binius is - $f^i$ is the RS encoding of $P^i$ over a domain $D^i \subset K$ - The domains are related by maps $q_i: K\to K$. - $D^{i+1} = q_i(D^i)$ - $q_i$ is $a_i:1$, i.e. every point of $D^{i+1}$ has $a_i$ preimages in $D^i$ - All preimages of points in $D^{i+1}$ lie in $D^i$ (i.e. none lie in $K \setminus D^i$) - The codewords $f^i, f^{i+1}$ are related by some "folding" operation that takes a challenge $r_i$ from verifier and reduces their size by the factor $a_i$ - For $x \in D^{i+1}$, we can efficiently compute $f^{i+1}(x)$ from the values of $f^i$ on $q_i^{-1}(x) \subset D^i$ Under these conditions, some number of rounds of interaction will reduce the prover's polynomial's degree to 0, at which point they can send the verifier the constant value. *Question*: How does this final constant value relate to the original polynomial and the verifier's challenge scalars $r_i$? ## BaseFold BaseFold observes that the reduction maps $q_i$ can be carefully chosen so that the final constant is the evaluation of a multilinear polynomial at $\vec r = (r_0, \ldots r_{\ell-1})$. More precisely, if $P(X) = \sum_{i=0}^{2^\ell-1} a_i X^i$ then the constant we reduce $P$ down to over $\ell$ rounds will be $a_0 + a_1 r_0 + a_2 r_1 + a_3 r_1 r_0 + \ldots + a_{2^\ell-1} r_0 \cdot r_1 \cdot ... r_{\ell-1}$ This is the evaluation $t(r_0, \ldots r_{\ell-1})$ where $t$ is the MLP with coefficients $a_i$. ## PCS for Multilinear Polynomials "Sum-check + FRI" This is a prequel to FRI Binius that does not yet use the packing technique. So this is only appropriate when you're committing to polynomials over a field $K$ that's big enough to use the RS encoding. Say $t \in K[X_0, \ldots X_{\ell-1}]^{<1}$ is a multilinear polynomial in $\ell$ variables. It's determined by $2^\ell$ values, and we generally use its values $\{ t(v) | v \in B_\ell \}$ on the $\ell$-dimensional Boolean hypercube. Use those same values as the coefficients of a *univariate* polynomial $$P(X) = \sum_{i=0}^{2^\ell-1} t([i]) X_i(X)$$ where $t([i])$ means $t$ evaluated at $[i] \in B_\ell$ whose coordinates are the binary representation of $i$. Note that we do *not* use the monomial basis $\{1, X, X^2, \ldots X^{2^\ell-1}\}$ to define $P(X)$. We are using a basis $\{X_0(X), \ldots X_{2^\ell-1}(X)\}$ referred to as the "novel polynomial basis" that has special properties. The reason for doing so is that it will be cheap to compute the RS encoding of $P$. (More precisely: the RS encoding of $P$ amounts to evaluating $P$ on some domain $D^0$. These evaluations are the coefficients of $P$ in the Lagrange basis corresponding to $D^0$. The "novel polynomial basis" is defined such that changing to Lagrange basis is just an NTT. This is a relative of the FFT and can be computed in $O(n \log n)$ time.) So far we have - $t \in K[X_0, \ldots X_{\ell-1}]^{<1}$ the MLP we want to commit to - $P \in K[X]^{< 2^\ell}$ a univariate polynomial whose coefficients in this novel polynomial basis are the same as $t$'s coefficients in its ML Lagrange basis - $f^0: D^0 \to K$, the RS encoding of $P$ on a domain $D^0$ of size $2^{\ell + R}$. BaseFold showed that we could use FRI with carefully chosen reduction maps $q_i$ and we would end up folding $P$ down to a constant polynomial $P^\ell$ whose value is $t(r_0, \ldots r_{\ell-1})$. This is useful, but it is not yet a PCS. Note that the evaluation point $(r_0, \ldots r_{\ell-1})$ was not supplied in advance, but rather produced one coordinate at a time in each FRI round. We need to prove $t(r_0, \ldots r_{\ell-1}) = s$ for $(r_0, \ldots r_{\ell-1})$ chosen *prior to* the FRI protocol. So DP combine FRI with a sum-check protocol. Recall that we can prove $t(r_0, \ldots r_{\ell-1}) = s$ by defining $$h(X_0, \ldots X_{\ell-1}) = t(X_0, \ldots, X_{\ell-1}) \tilde{eq}(X_0, \ldots X_{\ell-1}, r_0, \ldots r_{\ell-1})$$ and showing that $s = \sum_{v \in B_\ell} h(v)$. Sum-check on $h$ and FRI on $P$ both use $\ell$ rounds of interaction. FRI binius does these rounds simultaneously using shared challenges $r_i'$ The sum-check protocol reduces the claim $s = \sum_{v \in B_\ell} h(v)$ to the claim $$s_\ell = h(r_0',\ldots r_{\ell-1}') = t(r_0',\ldots r_{\ell-1}') \tilde{eq}(r_0',\ldots r_{\ell-1}', r_0,\ldots r_{\ell-1})$$ (where $s_\ell$ is produced over the course of the protocol). The FRI protocol reduces the polynomial $P$ to the constant $c = t(r_0',\ldots r_{\ell-1}')$. So together these reduce the claim $t(r_0, \ldots r_{\ell-1}) = s$ to $$s_\ell = c \cdot \tilde{eq}(r_0',\ldots r_{\ell-1}', r_0,\ldots r_{\ell-1})$$ (Note that the verifier still needs to perform the FRI sample phase that enforces the consistency of the codewords $f^i, f^{i+1}$ throughout the FRI protocol.) ## FRI Binius Now suppose we wish to commit to $t \in \mathcal{T}_\iota [X_0, \ldots X_{\ell-1}]$ for some small $\iota$. Recall that $\mathcal{T}_\iota$ has $2^{2^\iota}$ elements. For example, $\iota = 3$ corresponds to committing to a vector of bytes, and in this case $| \mathcal{T}_3 | = 256$. Therefore a RS encoding over $\mathcal{T}_3$ must have its codeword size $2^{\ell + R} \le 256$. This limits the size of messages we can encode. To get around this, DP introduced a "packing" construction in Binius, where they choose some $\kappa >0$ such that $\mathcal{T}_{\iota+\kappa}$ is big enough to use RS encoding. They group their list of $\mathcal{T}_\iota$ elements into chunks of size $2^\kappa$ and consider each chunk as an element of $\mathcal{T}_{\iota+\kappa}$. The special algebraic properties of the tower of binary fields $\mathcal{T}_0 \subset \mathcal{T}_1 \subset \ldots$ mean that this packing is just a concatenation of bit representations. The original $t \in \mathcal{T}_\iota[X_0,\ldots X_{\ell-1}]$ was determined by $2^\ell$ elements of $\mathcal{T}_\iota$. After packing we have $2^{\ell-\kappa}$ elements of $\mathcal{T}_{\iota + \kappa}$. These represent a polynomial $\hat t \in \mathcal{T}_{\iota+\kappa}[X_0, \ldots X_{\ell-\kappa-1}]$. That is, we now only have $\ell-\kappa$ variables. As above, we'll use coefficients of $\hat t$ to define a univariate polynomial $P(X)$. Its degree will now be $<2^{\ell-\kappa}$. This means we now only need $\ell - \kappa$ FRI rounds to reduce it to a constant. OTOH, we wish to evaluate the original $t \in \mathcal{T}_\iota [X_0, \ldots X_{\ell-1}]$ at some $(r_0, \ldots r_{\ell-1}) \in \mathcal{T}_\tau^\ell$. (Think of $\tau$ as large.) This would require an $\ell$-round sum-check protocol applied to $$h(X_0, \ldots X_{\ell-1}) = t(X_0, \ldots, X_{\ell-1}) \tilde{eq}(X_0, \ldots X_{\ell-1}, r_0, \ldots r_{\ell-1})$$ Since we only have $\ell-\kappa$ FRI rounds, we do a *partial* sum-check on $h$. That is, rather than reducing the $\sum_{v \in B_\ell} h(v)$ claim down to $s_\ell = h(r_0', \ldots r_{\ell-1}')$, we reduce it only down to $$s_{\ell-\kappa} = \sum_{v \in B_\kappa} h(v, r_0', \ldots r_{\ell-\kappa-1}')$$ That is, there are still $\kappa$ variable left to sum over. These FRI rounds have reduced $P$ down to the constant $c = \hat t(r_0',\ldots r_{\ell-\kappa-1}')$ This constant is valued in the *tower algebra* $A_{\iota, \kappa, \tau}$. That means it can be viewed as $2^\kappa$ elements of $\mathcal{T}_\tau$. We write $c = \{c_u \}_{u \in B_\kappa}$  It turns out that $c_u$ is related to our original polynomial $t$ by $c_u = t(u_0, \ldots u_{\kappa-1}, r_0', \ldots r_{\ell-\kappa-1}')$. These are precisely the evaluations of $t$ needed to compute $\sum_{v \in B_\kappa} h(v, r_0', \ldots r_{\ell-\kappa-1}')$