Shifted Witness Polynomials

Let's say we have a length-$n_\text{words}$ vector $w$, whose components $w[y]$ are 64-bit words.

Let's now fix some shift type $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$ and a shift amount $s \in \{0, \ldots , 63\}$. Let's say we want to shift each of $w$'s $n_\text{words}$ components by $s$ using $\text{op}$. This gives us a new $n_\text{words}$-word list. Let's give it a name: for each $y \in \{0, \ldots , n_\text{words} - 1\}$, we let

We will call these the shifted witness functions.

As Polynomials

What happens if we put both $w$ and $\textsf{shift}_{\text{op}}(w)(y, s)$ through multilinearization? How will the resulting multilinears relate to each other?

At this point, we assume that $n_\text{words} = 2^{\ell_\text{words}}$ is a power of 2. Let's review what multilinearization means, in this context. Going back to our original array $w$, we can identify $w$ with a $6 + \ell_\text{words}$-variate multilinear over $\mathbb{F}_2$:

The indeterminates $J_0, \ldots , J_5$ control the "bit within the word"; the indeterminates $Y_0, \ldots , Y_{\ell_\text{words} - 1}$ control the "word index". In other words, for each word index $y \in \mathcal{B}_{\ell_\text{words}}$ and each bit index $j \in \mathcal{B}_6$, $\widetilde{w}(j, y) = w[y]_j$ (i.e., the "$j$^th bit" of the latter).

Similarly, we can define the shifted witness polynomial

simply by multilinear-extending $\textsf{shift}_{\text{op}}(w)(y, s)$. Note that we again need to pick up 6 new variables—which we now call $I_0, \ldots , I_5$—that control the bit index within the word. Our defining property is that for each $i \in \mathcal{B}_6$, $y \in \mathcal{B}_{\ell_\text{words}}$ and $s \in \mathcal{B}_6$ in the cube, $\widetilde{\textsf{shift}}_{\text{op}}(w)(i, y, s) = \textsf{shift}_{\text{op}}(w)(y, s)_i = \text{op}(w[y], s)_i$ (we again take the "$i$^th bit").

How do we efficiently relate an evaluation claim on $\widetilde{\textsf{shift}}_{\text{op}}(w)(I, Y, S)$ to an evaluation claim on $\widetilde{w}(J, Y)$? The most naïve possible approach would read $w$'s entire table of values, shift them all, and compute a multilinear evaluation on $6 + \ell_\text{words} + 6$ variables. This is obviously unacceptable.

The Shift Indicators

We introduce shift indicators, and explain how they help us solve this problem. We again fix a shift type $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$.

For each such $\text{op}$, we define a corresponding function from $\mathcal{B}_6 \times \mathcal{B}_6 \times \mathcal{B}_6 \to \{0, 1\}$:

For each triple of inputs $i$, $j$ and $s$, it either is or isn't true that the $i$^th bit position of $\text{op}(v, s)$ is precisely the $j$^th bit position of $v$ (i.e., for each possible input $v$). The shift indicator picks up that fact.

With a bit of work we can unwind exactly what these mean. For each $i$, $j$ and $s$ in $\mathcal{B}_6$,

• $\widetilde{\textsf{shift-ind}}_{\mathsf{sll}}(i, j, s) = 1$ if and only if $\{j\} + \{s\} = \{i\}$.
• $\widetilde{\textsf{shift-ind}}_{\mathsf{srl}}(i, j, s) = 1$ if and only if $\{i\} + \{s\} = \{j\}$.
• $\widetilde{\textsf{shift-ind}}_{\mathsf{sra}}(i, j, s) = 1$ if and only if $\{i\} + \{s\} = \{j\}$ or both $\{j\} = 63$ and $\{i\} \geq 64 - \{s\}$ hold.

We will come back to these descriptions when we arithmetize the functions, in the next two pages.

Multilinear Shift Indicators

Now, we will write

for the multilinear extension of $\textsf{shift-ind}_\text{op}(i, j, s)$. This extension is a multilinear polynomial, with $\mathbb{F}_2$-coefficients, on $6 \times 3 = 18$ variables.

We now note the equality of multilinears:

To check this equality, it's enough to check it on the cube. We fix $i \in \mathcal{B}_6$, $y \in \mathcal{B}_{\ell_\text{words}}$ and $s \in \mathcal{B}_6$. Our goal is to show that for each such specialization,

This is basically an exercise. The sum $\sum_{j \in \mathcal{B}_6} \widetilde{\textsf{shift-ind}}_\text{op}(i, j, s) \cdot \widetilde{w}(j, y)$ has at most one nonzero summand. If, for some $j \in \mathcal{B}_6$, $\textsf{shift-ind}_\text{op}(i, j, s) = 1$, the sum will pick up exactly the $j$^th bit $\widetilde{w}(j, y)$, which itself equals $w[y]_j$. On the other hand, by definition of $\textsf{shift-ind}_\text{op}$, $w[y]_j = \text{op}(w[y], s)_i$, which itself equals $\textsf{shift}_\text{op}(w)(y, s)_i = \widetilde{\textsf{shift}}_\text{op}(\widetilde{w})(i, y, s)$, by definition of the latter things. This is basically an idea from [DP25, § 4.3].

This equality opens up the door to using the sumcheck to relate a claim on $\widetilde{\textsf{shift}}_{\text{op}}(w)(I, Y, S)$ to one on $\widetilde{w}(J, Y)$. Indeed, given an evaluation claim on the former, by running a 6-round sumcheck, the verifier can reduce it to two evaluation claims, on $\widetilde{\textsf{shift-ind}}_\text{op}$ and $\widetilde{w}$ respectively.

If the former, i.e. $\widetilde{\textsf{shift-ind}}_\text{op}$, is succinct, then we have solved our problem. Indeed, the verifier can evaluate that one himself, and then output the single, final evaluation claim on $\widetilde{w}$.

The rest of this site section will be devoted to arguing that the polynomials $\widetilde{\textsf{shift-ind}}_\text{op}(I, J, S)$ are succinct, for each $\text{op}$.