$\newcommand{\prover}{\mathcal{P}}$
$\newcommand{\verifier}{\mathcal{V}}$
$\newcommand{\tower}{\mathcal{T}}$

# Polynomial IOPs for Binary Tower Fields

Notes on section 4 of https://eprint.iacr.org/2023/1784.pdf

## Background and definitions

**Polynomial IOP (for binary towers):** An interactive protocol $(\prover,\verifier)$ where the prover and verifier use the following *multilinear polynomial oracle*:
- Fix a tower height $\tau$ and a binary tower $\tower_0 \subset \tower_1 \subset \cdots \subset \tower_\tau$
- Prover $\prover$ can $\texttt{submit}$ to the oracle a polynomial $t \in \tower_{\iota}[X_0, \ldots, X_{\ell-1}]^{\preceq 1}$.
- In response, the oracle sends a unique handle $[t]$ for the polynomial $t$ to both the prover $\prover$ and the verifier $\verifier$.
- The verifier $\verifier$ can send the oracle a $\texttt{query}$ for the handle $[t]$ at a point $r \in \tower_\tau^\ell$.
- In response, the oracle sends the evaluation $t(r_0, \ldots, r_{\ell-1})$.

**Polynomial predicate:** A *$\mu$-ary polynomial predicate* over $\tower_{\iota}$ is a boolean-valued function $\Phi_{\iota, \ell}: \tower_{\iota}[X_0, \ldots, X_{\ell-1}]^{\mu} \rightarrow \{0,1\}$.

We are interested in polynomial IOPs that allow the verifier $\verifier$ to evaluate a polynomial predicate on the polynomials that Prover $\prover$ has submitted to the oracle.

**Example predicates:**
- For $r \in \tower_{\tau}^{\ell}, s \in \tower_{\iota}$, let $\textsf{Query}(r,s)_{\iota, \ell}: t \mapsto t(r_0, \ldots, r_{\ell-1}) = s$
- For $e \in \tower_{\iota}$, let $\textsf{Sum}(e)_{\iota, \ell}: t \mapsto \sum_{v \in \mathcal{B}_\ell}t(v) = e$
- Let $\textsf{Zero}_{\iota, \ell}: t \mapsto \bigwedge_{v \in \mathcal{B}_\ell}t(v) = 0$
- Product, multiset, permutation, lookup

## Virtual polynomials and protocols

**Virtual polynomial:** Consists of
- A list $[t_0], \ldots, [t_{\mu-1}]$ of handles, each representing a polynomial over $\tower_{\iota}$.
- An arithmetic circuit with
- Leaves: $X_0, \ldots, X_\ell$ or constants in $\tower_{\iota}$.
- Gates: $+, \times$ and the polynomials $t_0, \ldots, t_{\mu-1}$

The polynomial computed by the circuit is written as $T$ and the virtual polynomial as $[T]$. Note that a handle $[t_i]$ is itself is a virtual polynomial.

**Remark:** The idea here is that if we have already committed to some polynomials $[t_0], \ldots, [t_{\mu-1}]$, our IOPs aren't limited to checking polynomial predicates over the committed polynomials. We can also construct IOPs for polynomial predicates involving the virtual polynomials. In this way we can get the benefits of having committed to these virtual polynomials without additional commitment costs.

Virtual polynomials can be *composed*. If some of the handles $[t_0], \ldots, [t_{\mu-1}]$ of a virtual polynomial $[T]$ were replaced with more virtual polynomials, the result can be "unrolled" into a proper virtual polynomial.

**Example:** (Composition) Given a $\mu$-variate *composition polynomial* $g\in \tower_{\iota}[X_0, \ldots, X_{\mu-1}]$, a simple example of a virtual polynomial consists of:
- A list of handles $[t_0], \ldots, [t_{\mu-1}]$ for polynomials over $\tower_{\iota}$
- An arithmetic circuit representing the composition$T := g(t_0(X_0, \ldots, X_{\ell-1}), \ldots, t_{\mu-1}(X_0, \ldots, X_{\ell-1}))$.

Lasso's "Spark Only Structure" (SOS) tables can be viewed as instances of the above composition virtual polynomial.

**Virtual polynomial protocol:** An interactive protocol $(\prover,\verifier)$ for a $\mu$-ary polynomial predicate $\Phi_{\iota, \ell}$ that gives the prover $\prover$ and verifier $\verifier$ a shared input list $([T_0], \ldots, [T_{\mu-1}])$ of $\ell$-variate virtual polynomials. The protocol is *secure* if the prover $\prover$ has negligible probability of making the verifier accept when the predicate $\Phi_{\iota, \ell} (T_0, \ldots, T_{\mu-1})$ is false.

**Example:** (Query) There is always a virtual polynomial protocol for the predicate $\textsf{Query}(r,s)_{\iota, \ell}$ on the input $[T]$. The verifier $\verifier$ can query each of the handles at point $r$ and evaluate the virtual polynomial directly. However, there could exist more efficient protocols depending on the specific virtual polynomial $T$. We will see an example of this in the shifting construction.

**Remark:** A common pattern in polynomial IOPs goes: The Prover and Verifier agree to some polynomial derived from committed polynomials (i.e. a virtual polynomial) and then run a known sub-protocol on it. The idea behind the virtual polynomial framework is to explicitly abstract out these two "primitives" out of polynomial IOPs:
- *Constructing* virtual polynomials
- *Composing* virtual polynomial protocols

A virtual polynomial protocol can be thought of as a sub-protocol within a polynomial IOP. Since virtual polynomials can be composed, so can virtual polynomial protocols.

## Prior virtual polynomial protocols

### Sumcheck

The sumcheck protocol is a polynomial IOP for the predicate $\textsf{Sum}(e)_{\iota, \ell}: t \mapsto \sum_{v \in \mathcal{B}_\ell}t(v) = e$. But internally, all the Verifier needs from its polynomial handle $[t]$ is to query the polynomial $t$ at a random point. Since the verifier can just as well query virtual polynomials, the sumcheck protocol can be viewed more generally as a virtual polynomial protocol.

### Zerocheck

The following zerocheck protocol from HyperPlonk decides the predicate $\textsf{Zero}_{\iota, \ell}: T \mapsto \bigwedge_{v \in \mathcal{B}_\ell}T(v) = 0$.
- Verifier $\verifier$ samples a random $r \leftarrow \tower_\ell^{\tau}$ and sends $r$ to the prover $\prover$.
- $\verifier$ and $\prover$ run the sumcheck protocol with claimed sum $0$ on the virtual polynomial $[T'] := T(v) \cdot \widetilde{\texttt{eq}}(r_0, \ldots, r_{\ell-1}, v_0, \ldots, v_{\ell-1})$.

where $\widetilde{\texttt{eq}}$ is an *equality indicator polynomial*.

*Completeness:* If the polynomial $T(v)=0$ for all points of $\mathcal{B}_{\ell}$, then the sum $$\sum_{v \in \mathcal{B}_\ell}T'(v)$$ $$= \sum_{v \in \mathcal{B}_\ell} T(v) \cdot \widetilde{\texttt{eq}}(r,v)$$ $$ = 0 $$

*Soundness:* Recall the expression for $T$'s multilinear extension: $$\widetilde{T}(X_0, \ldots, X_{\ell-1}) = \sum_{v \in \mathcal{B}_\ell} T(v) \cdot \widetilde{\texttt{eq}}(X_0, \ldots, X_{\ell-1}, v_0, \ldots, v_{\ell-1})$$
The sumcheck protocol invoked above checks exactly this expression at the point $r$. In other words, it computes $\widetilde{T}(r)$.

If $T(v)$ is nonzero for a $v \in \mathcal{B}_{\ell}$, then its multilinear extension $\widetilde{T}$ is not identically zero. Therefore with high probability ($1- \frac{\ell}{|\tower_\tau|}$), for our challenge point $r$ we have $\widetilde{T}(r) \neq 0$.

### Other plonk-ish virtual polynomial protocols

The protocols given by HyperPlonk for the other predicates product, multiset, permutation follow this structure:
- From the input virtual polynomials $([T_0], \ldots, [T_{\mu-1}])$, Prover and verifier construct and agree on one or more additional virtual polynomials.
- Prover and verifier run a known virtual polynomial protocol on the newly constructed virtual polynomials

## New virtual polynomial constructions

We haven't used the binary tower setting yet. Diamond and Posen give some new virtual polynomial constructions that specifically apply to binary towers. The most interesting one constructs the *shift* of a polynomial as a virtual polynomial.

Bit-shifting is a common operation in hash functions. A naive approach to get the bit-shift of a committed polynomial $t$ in a SNARK would be to commit to a second shifted polynomial $t'$ and then add constraints asserting that $t'$ is indeed the bit-shift of $t$. Instead, with Binius's (efficient) construction for *virtual* shift polynomials, our SNARK only needs to commit to $t$. Values of the shifted polynomial $t'$ can be materialized as needed.

### The shifting construction

For $v = (v_0, \ldots, v_{\ell-1})$ in $\mathcal{B}_{\ell}$, let $\{v\}$ denote the (mod ${2^\ell}$)-integer $\sum_{i=0}^{\ell-1} 2^i \cdot v_i$. Let $\{ \}^{-1}$ denote the inverse, so that $\{\{v\}\}^{-1} = v$.

We will think of functions $t: \mathcal{B}_{\ell} \rightarrow \tower_\iota$ as vectors of $\tower_\iota$ elements in lexicographic order. That is, $t \in \tower_\iota^{\mathcal{B}_\ell}$.

To simplify the construction, let's consider the case where $\iota = 0$, so we are working with polynomials over $\tower_\iota = \tower_0$, (bits). We will also fix the *block size parameter* $b \in \{0,\ldots,\ell\}$ mentioned in the paper to be $\ell$.

For each *shift offset* $o \in \mathcal{B}_{\ell}$, define the *shift mapping* $s_{o}: \mathcal{B}_{\ell} \rightarrow \mathcal{B}_{\ell}$ as:
$$ s_{o}(v) = \{\{v\} - \{o\} \mod 2^\ell\}^{-1}$$

Define the *shift operator* $\texttt{shift}_{o}: \tower_\iota^{\mathcal{B}_\ell} \rightarrow \tower_\iota^{\mathcal{B}_\ell}$ by mapping the vector $t \in \tower_\iota^{\mathcal{B}_\ell}$ to the shifted-by-$o$ vector $t(s_o(v))$.

**Example:** Let $\ell=2$ and let $t = (0,1,1,1)$. Then:
- $\texttt{shift}_{01}(t) = (1,0,1,1)$
- $\texttt{shift}_{10}(t) = (1,1,0,1)$

Our goal is to take a *polynomial* $t$, and produce a *virtual polynomial* that agrees with the operator $\texttt{shift}_{o}(t)$ on inputs from the Boolean hypercube $\mathcal{B}_{\ell}$. In other words, our goal is to construct the multilinear extension polynomial $\widetilde{\texttt{shift}}_{o}(t)$.

#### Small shift indicators:
We will build $\widetilde{\texttt{shift}}_{o}(t)$ using the following $o$-step *shift indicator* functions $\texttt{s-ind}_o: \mathcal{B}_{\ell} \times \mathcal{B}_{\ell} \rightarrow \{0,1\}$, which are defined as:

$$\texttt{s-ind}_o(x,y) = \begin{cases}
1 & \textrm{if } \{y\} \equiv \{x\} + \{o\} \mod{2^\ell} \\
0 & \textrm{otherwise}
\end{cases}$$

The multilinear extensions $\widetilde{\texttt{s-ind}}_o(x,y)$ of these shift indicator functions have a small arithmetic circuit construction of size $O(\ell)$. We won't go into the details of this construction. We will assume we have these small circuits for $\widetilde{\texttt{s-ind}}_o(x,y)$ in hand.

#### Shift circuit:
For each function $t \in \tower_\iota^{\mathcal{B}_\ell}$ and point $v \in \mathcal{B}_\ell$ we can write:
$$\texttt{shift}_{o}(t)(v) = \sum\limits_{u \in \mathcal{B}_{\ell}} t(u_0, \ldots, u_{\ell-1}) \cdot \texttt{s-ind}_o(u_0, \ldots, u_{\ell-1},v_0, \ldots, v_{\ell-1}). $$Hence, its multilinear extension can be written as: $$\widetilde{\texttt{shift}}_{o}(t)(X_0, \ldots, X_{\ell-1}) = \sum\limits_{u \in \mathcal{B}_{\ell}} \tilde{t}(u_0, \ldots, u_{\ell-1}) \cdot \widetilde{\texttt{s-ind}}_o(u_0, \ldots, u_{\ell-1},X_0, \ldots, X_{\ell-1}).$$ This function is clearly multilinear, and it agrees pointwise with $\texttt{shift}_{o}(t)$ over $\mathcal{B}_{\ell}$.

Since there are $|\mathcal{B}_\ell| = 2^\ell$ terms in this sum and $\widetilde{\texttt{s-ind}}_o$ has $O(\ell)$ size circuits, the size of the whole arithmetic circuit for this virtual polynomial is $O(2^{\ell})$

#### Efficient querying:
The above virtual polynomial construction features a sum over points of $\mathcal{B}_{\ell}$. Hence, the verifier $\verifier$ can query values of the shifted virtual polynomial $\widetilde{\texttt{shift}}_{o}(t)$ by simply invoking a sumcheck protocol!