Virtual Polynomials

Polynomials algebraically derived from committed ones

Virtual polynomials play an essential role in Binius, account for the bulk of this subsection's complexity.

All prior, DEEP-ALI-based SNARKS involve tables (or AIR instances) whose columns are exclusively committed. Throughout Binius, we secure enormous gains by refraining, when possible, from committing to "derived columns". That is, many of the columns we want to put into our tables happen to depend—in simple, algebraic ways—upon other columns. Instead of committing to all of them—and then constraining post facto that the various columns relate to each other in the required way—we may instead commit only to the "independent" or "fundamental" polynomials, and then materialize the further ones as virtual derivates of the these original things.

As a simple example, let's take a linear combination. Given underlying multilinears $t_0$ and $t_1$ and scalars $\alpha_0$ and $\alpha_1$ , we might be interested in the linear combination $t^* \coloneqq \alpha_0 \cdot t_0 + \alpha_1 \cdot t_1$ , let's say. (That is, $t^*$ 's entries are given element-wise as a linear combination of $t_0$ 's and $t_1$ 's entries.)

The classical approach would first instruct the prover to commit separately to $t^*$ , and then constrain or zerocheck that $t^* = \alpha_0 \cdot t_0 + \alpha_1 \cdot t_1$ holds for each $v \in \mathcal{B}_\ell$ . Instead of doing that, we can instead let the verifier conjure up $t^*$ "virtually".

What does this mean? The verifier just keeps the polynomial $t^* \coloneqq \alpha_0 \cdot t_0 + \alpha_1 \cdot t_1$ in its head as a "virtual" or "formal" object. When it comes time to evaluate $t^*$ —at $r \in \mathcal{T}_\tau^\ell$ , let's say—the verifier can't evaluate $t^*$ directly. On the other hand, the verifier can "pretend" it has evaluation access to $t^*$ , by splicing in a simple, local evaluation subroutine. That is, it may instead ask the oracle for $s_0 \coloneqq t_0(r)$ and $s_1 \coloneqq t_1(r)$ ; then, locally, it can compute the linear combination $t^*(r) = \alpha_0 \cdot s_0 + \alpha_1 + s_1$ . This procedure is essentially "as good as" having direct query access to $t^*$ , so the parties can act as if $t^*$ were committed.

Sketch of Definition

Here, we explain the definition of virtual polynomials in simple terms. Roughly, a virtual polynomial is a bundle consisting of a specification of a polynomial (i.e., in terms of other polynomials, themselves either committed or virtual), together with an algorithm, possibly interactive, which lets the verifier efficiently learn the thing's value at any given point.

Indeed, a "virtual polynomial" is defined in functional terms: if the verifier has the ability to efficiently learn its value at any point—possibly by querying other things, interacting with the prover, and doing a succinct amount of local work in the process—then it's a virtual polynomial. If it "walks and quacks" like a polynomial, then it is one (albeit perhaps virtual).

The thorough reference for this site subsection is [DP23, §§ 4.1 and 4.3].

Multilinears and Lists

We've already seen that multilinear polynomials and lists of values are two sides of the same coin. These two worlds are equivalent to each other, and can be mathematically connected. Thus, when we talk about constructing multilinears, we can feel free to work on both sides of this divide. What often happens is that we will first talk about the desired construction in the language of lists; then, when it comes time to actually construct that thing, we will need to supply a mathematical construction in the language of multilinears.

Terminal Examples

We begin by sketching the two most basic "virtual" polynomials. These are "degenerate" examples—which barely deserve to be called virtual polynomials—but which are important nonetheless. Indeed, they will serve as our atomic building blocks when we get into more complex constructions.

Committed polynomials. These polynomials are not virtual at all, but actually committed to. We already agreed—i.e., by definition of a PIOP—that the verifier may evaluate these things "in a single instruction" by just asking the oracle. Thus, they paradoxically count as (trivial) virtual polynomials.
Transparent polynomials. A transparent polynomial is one which the verifier may simply evaluate itself locally, with no help (and efficiently!). These are also "virtual", but again in a trivial way, since they don't depend on any underlying, committed polynomials.

Nontrivial Examples

The most "interesting" virtual polynomials depend on underlying committed (or transparent) polynomials in nontrivial ways. Here, we sketch the most important examples, referring where applicable to dedicated subpages.

Linear combinations. As we've seen in the example above, for any list of underlying, $\ell$ -variate multilinears $t_0, \ldots , t_{\mu - 1}$ , and any list of scalars $\alpha_0, \ldots , \alpha_{\mu - 1}$ , we may virtually simulate access to the combination polynomial $\alpha_0 \cdot t_0 + \cdots + \alpha_{\mu - 1} \cdot t_{\mu - 1}$ . Indeed, to evaluate the combination at any point $r \in \mathcal{T}_\tau^\ell$ , the verifier may simply evaluate the individual things there, and then locally take the appropriate linear combination. Of course, we need to assume that the number $\mu$ of underlying multilinears is small enough that the verifier can take the combination himself.
Merging. Occasionally we need ways of combining various constituent polynomials into bigger ones. Here, beginning with $2^\alpha$ $\ell$ -variate polynomials $t_0, \ldots , t_{2^\alpha - 1}$ , we can virtually materialize the $\ell + \alpha$ -variate polynomial whose list of values on $\mathcal{B}_{\ell + \alpha}$ is the concatenation of the constituent polynomials $t_0, \ldots , t_{2^\alpha - 1}$ 's respective lists. (We can also interleave them.)
Shifting. Our arguably most critical virtual construction lets us shift polynomials to create new ones. That is, given an $\ell$ -variate multilinear $t$ , we can create a derived one whose evaluations on $\mathcal{B}_\ell$ are exactly those of $t$ , but circularly rotated by some arbitrary, user-defined number of steps. When the number of offset steps is just 1, this lets us tie each row to the row above it, in a very efficient way.
Tiling. Given an $\ell$ -variate multilinear $t(X_0, \ldots , X_{\ell - 1})$ and an expansion parameter $\alpha$ , we can create an $\ell + \alpha$ -variate multilinear whose values on $\mathcal{B}_{\ell + \alpha}$ are simply those of $t$ , but repeated or tiled $2^\alpha$ times. Actually, this is not hard to do: we simply need to "pretend" that $t$ is rather actually $\ell + \alpha$ -variate, and simply ignores its last $\alpha$ variables. (A simple variant of this idea also lets us interleave $t$ with itself $2^\alpha$ times; here, the interleaved polynomial should ignore its low variables.)
Zero-padding. A related idea lets us zero-pad an $\ell$ -variate multilinear $t(X_0, \ldots , X_{\ell - 1})$ . That is, we create an $\ell + \alpha$ -variate polynomial $t'(X_0, \ldots , X_{\ell + \alpha - 1})$ , which agrees identically with $t$ on some $2^\ell$ -sized subcube of $\mathcal{B}_{\ell + \alpha}$ , but which is identically 0 elsewhere. To do this, we can proceed as above, but multiply in a few extra indeterminates: that is, we set $t'(X_0, \ldots , X_{\ell + \alpha - 1}) \coloneqq t(X_0, \ldots , X_{\ell - 1}) \cdot X_\ell \cdot \cdots \cdot X_{\ell + \alpha - 1}$ . This thing is virtual: to evaluate it at $(r_0, \ldots , r_{\ell + \alpha - 1})$ , the verifier can query $s \coloneqq t(r_0, \ldots , r_{\ell - 1})$ , and then locally compute and return $s \cdot r_\ell \cdot \cdots \cdot r_{\ell + \alpha - 1}$ .