The Procedure

Here, we get to the "grand finale" of this site. Our setup is a list of polynomials $t_0, \ldots , t_{n - 1}$, respectively of sizes $\ell_0, \ldots , \ell_{n - 1}$, all defined over $\mathcal{T}_\tau$, and jointly committed to in just the way prescribed by our batch commitment procedure. That is, we've actually committed to just a single, massive, piecewise polynomial $t^*(X_0, \ldots , X_{\ell^* - 1})$, which takes the values that the individual polynomials $t_0, \ldots , t_{n - 1}$ respectively do on various subcubes of $\mathcal{B}_{\ell^*}$ (and zero-fills the remaining vertices).

We now fix a list of sum claims, each of the form

Here, the $A_j(X_0, \ldots , X_{\ell_j - 1})$ are further transparent polynomials that arise during the ring-switching reduction. We don't need to worry what these polynomials even are for the purposes of this page; we merely need the fact that they're transparent (i.e., efficiently evaluable by the verifier at any given point).

Our goal in this page will be to jointly evaluate all of these sum claims. Our algorithm will essentially run FRI, our front-loaded sumcheck, and our piecewise evaluation procedure together, in an interleaved way, and using just one stream of random challenges for all three algorithms.

Some Preliminaries

We now record our evaluation protocol. We drop a slightly simplified variant in which a certain oracle skipping optimization is omitted. (We refer to [DP24, § 6.2] for a description of this optimization.)

We write $f^{(0)} : S^{(0)} \to \mathcal{T}_\tau$ for the result of the prover's initial commitment. Here, $S^{(0)} \subset \mathcal{T}_\tau$ is a Reed–Solomon domain of size $2^{\ell^* + \mathcal{R}}$. We moreover fix the usual sequence of further FRI domains $S^{(0)}, \ldots , S^{(\ell^*)}$, as well as the 2-to-1 folding maps $q^{(i)} : S^{(i)} \to S^{(i + 1)}$. Using these, we get a FRI folding procedure, which, given a word $f^{(i)} : S^{(i)} \to \mathcal{T}_\tau$ and a folding challenge $r_i \in \mathcal{T}_\tau$, produces a folded word $f^{(i + 1)} \coloneqq \mathsf{fold}(f^{(i)}, r_i)$, a map $f^{(i + 1)} : S^{(i + 1)} \to \mathcal{T}_\tau$.

We moreover use a notational device which we've already used in the previous two pages. We assume as usual that the polynomials $t_0, \ldots , t_{n - 1}$ are arranged in sorted order, so that $\ell_0 \geq \cdots \geq \ell_{n - 1}$ holds. Moreover, for each $j \in \{0, \ldots , \ell^*\}$, we are going to write $j_i \in \{0, \ldots , n\}$ for the minimal $j \in \{0, \ldots , n\}$ for which $\ell_j \leq i$ holds. We note that $j_{\ell^*} = 0$ necessarily holds; moreover, $j_0 = n$ will too, provided we assume that each $\ell_j$ is positive—which we do now. Finally, the elements $j_0 \geq \cdots \geq j_{\ell^*}$ will be nonincreasing.

The Steps

Here is our algorithm. Again, to reiterate, we are trying to batch-process a list of sum claims of the form

where the $t_j(X_0, \ldots , X_{\ell_j - 1})$ are batch-committed and the $A_j(X_0, \ldots , X_{\ell_j - 1})$ are transparent. The verifier initializes claim datastructures $T_0, \ldots , T_{n - 1}$, each featuring $.\text{claim}$ and $.\text{next}$ fields. The verifier initializes $T_j.\text{next} \coloneqq j + 1$ for each $j \in \{0, \ldots , n - 1\}$.

Here we go:

• The verifier samples a batching challenge $\alpha \gets \mathcal{T}_\tau$ and sends it to the prover. As in the front-loaded sumcheck, the verifier computes the batched sum claim:

• For each round $j \in \{0, \ldots , \ell^* - 1\}$, the prover and verifier proceed as:
  • The prover computes the round polynomial $$\begin{equation*}g_i(X) = \sum_{j = 0}^{j_i - 1} \alpha^j \cdot \sum_{v \in \mathcal{B}_{\ell_j - i - 1}} C_j(r_0, \ldots , r_{i - 1}, X, v_0, \ldots , v_{\ell_j - i - 2}),\end{equation*}$$ and sends it to the verifier. Here, the upper limit $j_i \in \{0, \ldots , n\}$ is as we've already explained.
  • The verifier checks whether $s^*_i \stackrel{?}= g_i(0) + g_i(1)$ holds.
  • The verifier samples $r_i \gets \mathcal{T}_\tau$ and sends it to the prover. The verifier moreover computes the updated sum claim: $$\begin{equation*}s^*_{i + 1} \coloneqq g_i(r_i).\end{equation*}$$
  • The prover computes $f^{(i + 1)} \coloneqq \mathsf{fold}(f^{(i)}, r_i)$, and commits $f^{(i + 1)}$ to the string oracle (unless we're in the last round $i = \ell^* - 1$, in which case the prover just sends the constant value $c \coloneqq f^{(\ell)}(0)$).
  • For each $j \in \{j_{i + 1}, \ldots , j_i - 1\}$ (these are exactly the $j \in \{0, \ldots , n - 1\}$ for which which $\ell_j = i + 1$ holds), the prover nondeterministically sends the "now-ready" claimed evaluation $$\begin{equation*}b_{j, \ell_j} = t_j(r_0, \ldots , r_i).\end{equation*}$$
  • Again for each $j \in \{j_{i + 1}, \ldots , j_i - 1\}$, the verifier does the following things:
    • It mutates $$\begin{equation*}s^*_{i + 1} \mathrel{-}= \alpha^j \cdot b_{j, \ell_j} \cdot A_j(r_0, \ldots , r_i).\end{equation*}$$ The quantity $A_j(r_0, \ldots , r_i)$ it just computes directly, which it can, since it's transparent.
    • It moreover marks: $$\begin{equation*}T_j.\text{claim} \coloneqq b_{j, \ell_j}.\end{equation*}$$
  • Now, the verifier kicks off a "smoothing" step for lower-dimensional subcubes. It initializes $k \coloneqq j_i$, and then runs the following loop. While $k < n$:
    • The verifier sets $c_0 \coloneqq T_k.\text{claim}$.
    • If $T_k.\text{next} < n$, then the verifier sets $c_1 \coloneqq T_k.\text{next}.\text{claim}$ and overwrites $T_k.\text{next} = T_k.\text{next}.\text{next}$. Otherwise, the verifier sets $c_1 \coloneqq 0$.
    • In any case, the verifier overwrites $T_k.\text{claim} = (1 - r_i) \cdot c_0 + r_i \cdot c_1$, and also updates $k = T_k.\text{next}$.
• At the very end, the verifier requires $s^*_{\ell^*} \stackrel{?}= 0$.
• The verifier moreover requires $c \stackrel{?}= T_0.\text{claim}$, where $c$ is the final constant FRI value.
• The verifier kicks off FRI querying.

Security Claim

The claim is that if the verifier accepts all of its checks above, then (except with low probability) all of the individual sum claims $s_{j, 0} \stackrel{?}= \sum_{v \in \mathcal{B}_{\ell_j}} t_j(v) \cdot A_j(v)$ were valid. The security proof is not simple, but it combines essentially the respective security proofs of FRI, front-loaded sumcheck, and piecewise evaluation. A rigorous treatment of a simpler case–in which just one polynomial is being committed—can be found in [DP24, § 3.3].