Shifting

A virtual polynomial that circularly rotates a committed one

As we've already seen, we can think of multilinears as lists. Often, it's convenient to specify a virtual polynomial on the list side of things, and then to later recapture that operation on the algebraic side.

Describing how shifting operates on lists is not hard. Roughly, if we start with a list $(t_i)_{i = 0}^{2^\ell - 1}$ , we want to circularly rotate that thing downwards by $o$ steps, let's say. So the resulting list will be $(t_{i - o \pmod{2^\ell}})_{i = 0}^{2^\ell - 1}$ .

Actually, it will be convenient to refine this a bit. We are going to introduce a further block size parameter $b \in \{0, \ldots , \ell\}$ . For such $b$ and for some offset parameter $o \in \{0, \ldots , 2^b - 1\}$ , the task will be to

chunk the list $(t_i)_{i = 0}^{2^\ell - 1}$ into size- $2^b$ blocks;
circularly rotate each invdividual block (!) downward by $o$ steps.

If our initial multilinear is $t$ , we will write $\texttt{shift}_{b, o}(t)$ for the above thing.

Shifting Algebraically

Now, this is a perfectly valid description of something to do with a list. The much-harder question is: will the verifier have a way of evaluating $\texttt{shift}_{b, o}(t)$ efficiently? That is, let's assume that the verifier has the ability to efficiently evaluate $t(r')$ for any given point $r' \in \mathcal{T}_\tau^\ell$ (for example, $t$ is simply committed). Can we devise a means by which the verifier might bootstrap $t$ -evaluation into $\texttt{shift}_{b, o}(t)$ -evaluation? That is, how might the verifier efficiently ascertain $\texttt{shift}_{b, o}(t)(r)$ , given the ability to evaluate the underlying polynomial $t$ ?

Note here that we are already using the duality between lists and multilinears. At first, when we defined $\texttt{shift}_{b, o}(t)$ , we did so as a list. Just above though, we're already understanding it as a multilinear polynomial. Indeed, how else would we make sense of evaluating it at a random $r \in \mathcal{T}_\tau^\ell$ (i.e., which isn't necessarily in the cube)?

So the first thing we need to do is write down an algebraic expression for $\texttt{shift}_{b, o}(t)$ . In principle, this isn't hard, since we already know its values on the cube (we can just take its MLE). The problem though, will be to do this in such a way that the verifier may evaluate it efficiently.

As a sanity check, we note that writing an algebraic expression for $\texttt{shift}_{b, o}(t)$ is not hard. Indeed, we can just take its MLE:

\begin{equation*}\texttt{shift}_{b, o}(t)(X_0, \ldots , X_{\ell - 1}) = \sum_{v \in \mathcal{B}_\ell} \texttt{shift}_{b, o}(t)(v) \cdot \widetilde{\texttt{eq}}(X_0, \ldots , X_{\ell - 1}, v_0, \ldots , v_{\ell - 1}).\end{equation*}

The problem is that this didn't help us at all. This expression doesn't exploit any algebraic structure, and is no more efficient to evaluate for the verifier than an arbitrary $\ell$ -variate multilinear is (i.e, the work involved here is on the order of $2^\ell$ ).

We will soon see how to do better.

The Shift Indicator

We'll begin with a slight detour (which is really not one at all!). As above, we fix a height parameter $\ell \geq 0$ , a block size parameter $b \in \{0, \ldots , \ell\}$ , and an offset $o \in \{0, \ldots , 2^b - 1\}$ . As usual, we are going to identify $\mathcal{B}_b$ with $\{0, \ldots , 2^b - 1\}$ by sending $v \mapsto \{v\} \coloneqq \sum_{i = 0}^{b - 1} 2^i \cdot v_i$ .

We're going to define the shift indicator function $\texttt{s-ind}_{b, o}$ , beginning as a function on $\mathcal{B}_b \times \mathcal{B}_b$ . For each pair $(x, y) \in \mathcal{B}_b \times \mathcal{B}_b$ , we are going to declare that $\texttt{s-ind}_{b, o}(x, y)$ equals 1 if and only if $\{y\} \stackrel{?}\equiv \{x\} + \{o\} \pmod{2^b}$ holds, and equals $0$ otherwise. That is, this thing returns 1 on those pairs of cube-points which differ by $o$ steps (with wraparound) in the lexicographic ordering of the cube $\mathcal{B}_b$ . This was just a function, but as usual, we can implicitly associate it with its MLE, a $2 \cdot \ell$ -variate multilinear (whose restriction to the cube $\mathcal{B}_b \times \mathcal{B}_b$ recovers $\texttt{s-ind}_{b, o}$ ).

Now the key claim is that $\texttt{s-ind}_{b, o}$ is transparent: the verifier can locally evaluate it on any pair of points $r$ and $r'$ in just $O(b)$ work. This claim is not obvious at all, and in [DP23, § 4.3] we expend a good amount of work proving it.

Here, we sketch a transparent construction of $\texttt{s-ind}_{b, o}$ , which was suggested to us by Jacob Kirmayer (this approach is different from that pursued in [DP23, § 4.3], but achieves the same outcome). As usual, we fix parameters $b \geq 0$ and $o \in \{0, \ldots , 2^b - 1\}$ . For arbitrary $(x, y) \in \mathcal{B}_b \times \mathcal{B}_b$ , we want to express the desired relationship $\{y\} \stackrel{?}\equiv \{x\} + \{o\} \pmod{2^b}$ in terms of a smaller problem. We denote the most-significant substrings $x' \coloneqq (x_{b - 1}, \ldots , x_1)$ , $y' \coloneqq (y_{b - 1}, \ldots , y_1)$ , and $o' \coloneqq (o_{b - 1}, \ldots , o_1)$ . If $o$ is even, then our desired relationship holds if and only if the least-significant bits $x_0$ and $y_0$ agree and $\{y'\} \stackrel{?}\equiv \{x'\} + \{o'\} \pmod{2^{b - 1}}$ holds. If $o$ is odd, then the relationship can hold only if $x_0 \neq y_0$ . Moreover, if $x_0 = 0$ and $y_0 = 1$ , then the relationship will hold if and only if $\{y'\} \stackrel{?}\equiv \{x'\} + \{o'\} \pmod{2^{b - 1}}$ does; if $x_0 = 1$ and $y_0 = 0$ , then we need to instead reduce to $\{y'\} \stackrel{?}\equiv \{x'\} + \{o'\} + 1 \pmod{2^{b - 1}}$ . In both cases we are able to reduce to smaller instances of the problem (or two!). Namely,

\begin{equation*}\texttt{s-ind}_{b, o}(x, y) = \widetilde{\texttt{eq}}(x_0, y_0) \cdot \texttt{s-ind}_{b - 1, o'}(x', y')\end{equation*}

if $o$ is even, and

\begin{equation*}\texttt{s-ind}_{b, o}(x, y) = (1 - x_0) \cdot y_0 \cdot \texttt{s-ind}_{b - 1, o'}(x', y') + x_0 \cdot (1 - y_0) \cdot \texttt{s-ind}_{b - 1, o' + 1}(x', y')\end{equation*}

if $o$ is odd.

It remains to show that this recursion can be solved efficiently using dynamic programming. In fact, it's not too hard—though a bit tricky—to show that, for each intermediate level $k \in \{0, \ldots , b - 1\}$ , at most two shift indicators $o$ need to be computed and memoized; in fact, these are none other than $o_k \coloneqq o \gg b - k$ and $o_k + 1 \pmod{2^k}$ .

The Shift Polynomial

Assuming this fact for now, we get a new way of writing $\texttt{shift}_{b, o}(t)$ . Indeed, $\texttt{shift}_{b, o}(t)(X_0, \ldots , X_{\ell - 1})$ equals:

\begin{equation*}\sum_{v \in \mathcal{B}_b} t(v_0, \ldots , v_{b - 1}, X_b, \ldots , X_{\ell - 1}) \cdot \texttt{s-ind}_{b, o}(v_0, \ldots , v_{b - 1}, X_0, \ldots , X_{b - 1}).\end{equation*}

What is the intuition of this? First of all, this thing is evidently multilinear, provided that we believe that $\texttt{s-ind}_{b, o}$ is multilinear. Thus we need to argue that its restriction to the cube $\mathcal{B}_\ell$ equals exactly $\texttt{shift}_{b, o}(t)$ . To see this, we pick a cube element $w \in \mathcal{B}_\ell$ and study the value of the above expression, with $(X_0, \ldots , X_{\ell - 1})$ specialized to $(w_0, \ldots , w_{\ell - 1})$ . As the outer sum index $v \in \mathcal{B}_b$ varies, the multiplier $\texttt{s-ind}_{b, o}(v, w)$ will be nonzero precisely when $\{w\} \stackrel{?}\equiv \{v\} + \{o\} \pmod{2^b}$ holds (here, we implicitly truncate $v$ and $w$ by only considering their lowest $b$ bits). Thus, the sum above will pick out "exactly one" value of $t$ . Which? The value of $\texttt{shift}_{b, o}(t)(w)$ will be $t(v^*_0, \ldots , v^*_{b - 1}, w_b, \ldots , w_{\ell - 1})$ , where the bitstring $(v^*_0, \ldots , v^*_{b - 1})$ is chosen to be the $o$ -step lexicographic predecessor of $(w_0, \ldots , w_{b - 1})$ . This is exactly what we wanted.

Efficient Evaluation

What about the problem we started with—namely, for the verifier to learn $\texttt{shift}_{b, o}(t)(r)$ efficiently? The key is that if we take the above expression—but specialize $(X_0, \ldots , X_{\ell - 1})$ to $(r_0, \ldots , r_{\ell - 1})$ —then we wend up with the expression:

\begin{equation*}\texttt{shift}_{b, o}(t)(r) = \sum_{v \in \mathcal{B}_b} t(v_0, \ldots , v_{b - 1}, r_b, \ldots , r_{\ell - 1}) \cdot \texttt{s-ind}_{b, o}(v_0, \ldots , v_{b - 1}, r_0, \ldots , r_{b - 1}).\end{equation*}

This is exactly the thing we can sumcheck: indeed, it's enough to sumcheck the $b$ -variate polynomial $\texttt{shift}_{b, o}(t, r)(Y_0, \ldots , Y_{b - 1})$ defined by:

\begin{equation*}t(Y_0, \ldots , Y_{b - 1}, r_b, \ldots , r_{\ell - 1}) \cdot \texttt{s-ind}_{b, o}(Y_0, \ldots , Y_{b - 1}, r_0, \ldots , r_{b - 1}).\end{equation*}

This polynomial's sum over the cube will be nothing other than our desired evaluation $\texttt{shift}_{b, o}(t)(r)$ . At the very end of the sumcheck, the verifier will be reduced to evaluating two things: $t(r'_0, \ldots , r'_{b - 1}, r_b, \ldots , r_{\ell - 1})$ , on the one hand, and $\texttt{s-ind}_{b, o}(r'_0, \ldots , r'_{b - 1}, r_0, \ldots , r_{b - 1})$ , on the other (here, the point $r' \in \mathcal{T}_\tau^b$ will be sampled during the sumcheck). The first thing the verifier can just query. As for the second, we already agreed above that $\texttt{s-ind}_{b, o}$ is transparent! Thus the verifier can just efficiently evaluate it itself.

This completes the description of $\texttt{shift}_{b, o}(t)$ as a virtual polynomial—i.e., as a thing that the verifier can efficiently evaluate at any point $r \in \mathcal{T}_\tau^\ell$ .

Then What?

What do we get out of this construction? In short, shifting lets us link distinct rows of our tables. Occasionally, it happens that we want to "spread" a computation across multiple rows. When we do this, we often want to "link" the end of one row with the beginning of the next. In fact, this sort of looks like how classical AIR works.

Of course, we will not always want to do this, and our use of M3 vastly reduces the frequency that we want to use this kind of thing. On the other hand, it can be useful to have.

Copy Constraints

We note that shifting achieves a goal analogous to that achieved by copy constraints, which appear in PLONKish schemes. In those schemes, copy constraints allow the verifier to require that various arbitrary pairs of elements of the prover's trace table be equal to each other. In particular, these pairs can control cells in completely arbitrary locations (in a completely unstructured way—the linked cells don't need to be near each other, for example). In fact, just this sort of copy constraint is achieved by the protocol [DP23, Prot. 4.22].

Because copy constraints are unstructured, they are very powerful; on the other hand, this power comes at an efficiency cost. Copy-constraint protocols like [DP23, Prot. 4.22] require instance-dependent transparent preprocessing; moreover, at runtime, they reduce to expensive multiset-checks. On the other hand, in many cases, this power is not needed: we only end up needing to link cells in very structured and predictable ways (e.g., linking the end of each row to the beginning of the following row).

Our shift construction, then, achieves the effective outcome of copy constraints, but at a far-lower efficiency cost. Indeed, the cost is just a single $\ell$ -round sumcheck (or even fewer rounds, if the shifting is blockwise!).