Prover Implementation

We now explain the implementation of our shift reduction's prover. We covered a lot of ground in the previous page, where described the protocol's overall two-phase sumcheck structure.

Here, we describe more explicitly how the prover can precompute the various tables of values that it needs in order to carry out those sumchecks. The point is to exploit the sparsity of the constraint system, and to get something whose performance is close to the witness size.

There are actually a few ways to do this, which are essentially similar in spirit and have slightly different tradeoffs at the implementation level. We are going to describe one which is conceptually simple and gets close to what we do.

The First Phase

We now describe the prover's implementation of the first phase of the shift reduction. The prover's inputs are the challenges $r_{\widehat{i}}$, $r'_x$ sampled during the univariate skip, the witness $w$, and the constraint array $z$.

Computation of h polynomials

We recall the definitions of the polynomials $h_\text{op}(J, S)$. For each $j \in \mathcal{B}_6$ and $s \in \mathcal{B}_6$:

First, the prover should precompute $\left( \delta_D(r_{\widehat{i}}, \widehat{i}) \right)_{i \in \mathcal{B}_6}$. As we've already seen, the prover can do this efficiently using a technique related to Lagrange interpolation.

We recall now what the shift indicators mean. We note that for each $\text{op} \in \{\mathsf{sll}, \mathsf{srl}\}$, for each $j \in \mathcal{B}_6$ and each $s \in \mathcal{B}_6$, there is at most one $i \in \mathcal{B}_6$ for which $\widetilde{\textsf{shift-ind}}_\text{op}(i, j, s) = 1$. We can thus set $h_\text{op}(j, s)$ equal to $\delta_D(r_{\widehat{i}}, \widehat{i})$ for precisely the appropriate value of $i$.

The case $\text{op} = \mathsf{sra}$ is slightly more tricky. Here, the case $j = 63$ is exceptional. In that case, for each $s \in \mathcal{B}_6$, $\widetilde{\textsf{shift-ind}}_\text{op}(i, j, s) = 1$ for each $i \in \mathcal{B}_6$ for which $\{i\} \geq 64 - \{s\}$.

Putting everything together, we get the following algorithm. We write $\mathsf{delta}$ for the length-64 flattening of $\left( \delta_D(r_{\widehat{i}}, \widehat{i}) \right)_{i \in \mathcal{B}_6}$.

• allocate empty, $64 \times 64$, all-zero arrays $\mathsf{h}_{\mathsf{sll}}$, $\mathsf{h}_{\mathsf{sra}}$ and $\mathsf{h}_{\mathsf{sra}}$, containing $\mathbb{F}_{2^{128}}$-elements.
• for $j \in \{0, \ldots , 63\}$ do:
  • for $s \in \{0, \ldots , 63 - j\}$ do: set $\mathsf{h}_{\mathsf{sll}}[j][s] \coloneqq \mathsf{delta}[j + s]$
  • for $s \in \{0, \ldots , j\}$ do: set $\mathsf{h}_{\mathsf{srl}}[j][s] \coloneqq \mathsf{delta}[j - s]$.
  • for $s \in \{0, \ldots , j\}$ do: set $\mathsf{h}_{\mathsf{sra}}[j][s] \coloneqq \mathsf{delta}[j - s]$.
• for $s \in \{1, \ldots , 63\}$ do: update $\mathsf{h}_{\mathsf{sra}}[63][s] \mathrel{+}= \mathsf{h}_{\mathsf{sra}}[63][s - 1]$.
• return $\mathsf{h}_{\mathsf{sll}}$, $\mathsf{h}_{\mathsf{sra}}$ and $\mathsf{h}_{\mathsf{sra}}$.

In the last line of the algorithm above, we do a "running prefix sum" trick. This completes our description of the prover's computation of the polynomials $h_\text{op}(J, S)$.

Computation of g polynomials

We now turn to the polynomials $g_\text{op}(J, S)$, for $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$. We reproduce their definitions here. For each $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$, $j \in \mathcal{B}_6$ and $s \in \mathcal{B}_6$:

Our prover's first goal will be to compute the all of the values $\widetilde{Z}_{\text{cons}, \text{op}}(r'_x, y, s)$ used above. Now across all possible $y \in \mathcal{B}_{\ell_\text{words}}$, all three $\text{op}$, and all 64 $s \in \mathcal{B}_6$, these three quantities represent $n_\text{words} \cdot 3 \cdot 64$ values, which is 192 times as large as the witness, and so too much to compute and store naïvely. When we are assessing claims on multiple constraint arrays $z$ at once—as we are in practice—this problem becomes worse (linearly in the number of constraint arrays).

On the other hand, very few of these combinations will actually have nonzero values, because of sparsity. Our goal is to compute and store only the ones that we need. We will compute and store $\widetilde{Z}_{\text{cons}, \text{op}}(r'_x, y, s)$ only for those triples $(y, \text{op}, s)$ for which that value is nonzero.

To do this, we will create a kind of dictionary datastructure. We will keep a list, indexed by $y \in \{0, \ldots , n_\text{words} - 1\}$, called $\textsf{index}$. For each $y \in \{0, \ldots , n_\text{words} - 1\}$, $\textsf{index}[y]$ will itself be a dictionary, whose keys will be triples $(\text{op}, s)$, and whose values will be $\mathbb{F}_{2^{128}}$-elements. For each $y$, the keys of $\textsf{index}[y]$ will be precisely those triples $(\text{op}, s)$ for which the column $\widetilde{Z}_{\text{cons}, \text{op}}(X, y, s)$ is not identically zero; for each such key, the value $\textsf{index}[y][(\text{op}, s)]$ will be $\widetilde{Z}_{\text{cons}, \text{op}}(r'_x, y, s)$. (In the case of many constraint arrays, the keys of $\textsf{index}[y]$ will be not pairs but triples, containing also an index into the list of constraint arrays.)

The following algorithm populates this datastructure:

• precompute $\mathsf{tensor} \coloneqq \left( \widetilde{\texttt{eq}}(r'_x, x) \right)_{x \in \mathcal{B}_{\ell_\text{and}}}$, the tensor expansion of $r'_x$.
• let $\textsf{index}$ be a length-$n_\text{words}$ array, whose elements are dictionaries, initialized to empty.
• for each $x \in \{0, \ldots , n_\text{cons} - 1\}$ do:
  • load the $x$^th list $L^z_x$ from the constraint system.
  • for each $(y, \text{op}, s) \in L^z_x$ do:
    • update $\mathsf{index}[y][(\text{op}, s)] \mathrel{+}= \mathsf{tensor}[x]$.
• return $\mathsf{index}$.

For each $y$, we understand the dictionary $\textsf{index}[y]$ as a defaultdict, in the sense that if the key $(\text{op}, s)$ is not yet present in $\textsf{index}[y]$, the operation $\mathsf{index}[y][(\text{op}, s)] \mathrel{+}= \mathsf{tensor}[x]$ will implicitly create the key—with value 0—before executing.

With these in hand, we're ready to compute the polynomials $g_\text{op}(J, S)$. To compute these, we run the following algorithm:

• for each $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$, initialize $\mathsf{g}_\text{op}$ to be an empty, $2^6 \times 2^6$ array of field elements.
• for each $y \in \{0, \ldots , n_\text{words} - 1\}$ do:
  • for each key–value pair $\left( (\text{op}, s), \textsf{value} \right)$ in $\textsf{index}[y]$ do:
    • for each $j \in \{0, \ldots , 63\}$ do:
      • if $w[y]_j \stackrel{?}= 1$ do:
        • $\mathsf{g}_\text{op}[j][s] \mathrel{+}= \textsf{value}$.
• return $\mathsf{g}_\text{op}$ for all three $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$.

We claim that for each $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$, the resulting array $\mathsf{g}_\text{op}$ contains precisely the table of values of $g_\text{op}(J, S)$ on $\mathcal{B}_6 \times \mathcal{B}_6$. This completes our description of the first phase.

The Second Phase

As we've seen, to prepare for the second phase of the shift reduction, the prover needs to prepare the tables of values of two different $\ell_\text{words}$-variate multilinears:

and

The first is just a standard partial specialization. The prover just needs to tensor-expand the 6-dimensional challenge $r_j$, and then, for each $y \in \{0, \ldots , n_\text{words} - 1\}$, take the subset sum $\sum_{j = 0}^{63} w[y]_j \cdot \widetilde{\texttt{eq}}(r_j, j)$.

For the second, we can again use our $\mathsf{index}$. We claim that the following algorithm computes the required table of values:

• initialize $\mathsf{Z}$, an all-zero, length-$n_\text{words}$ array of $\mathbb{F}_{2^{128}}$-elements.
• compute in advance the tensor-expansion $\left( \widetilde{\texttt{eq}}(r_s, s) \right)_{s \in \mathcal{B}_6}$.
• for $y \in \{0, \ldots , n_\text{words} - 1\}$ do:
  • for each key–value pair $\left( (\text{op}, s), \textsf{value} \right)$ in $\textsf{index}[y]$ do:
    • update $\mathsf{Z}[y] \mathrel{+}= h_\text{op}(r_j, r_s) \cdot \mathsf{value} \cdot \widetilde{\texttt{eq}}(r_s, s)$.
• return $\mathsf{Z}$.

This completes the precomputation; $\mathsf{Z}$ yields the table of values of the second multilinear in $Y$ above. The prover can at this point proceed with the second phase of the sumcheck.

Constraint Matrices

We touch on one final topic, which is how the verifier can evaluate $\widetilde{Z}_{\text{cons}, \text{op}}(r'_x, r_y, r_s)$, for all three $\text{op}$, himself. As we saw earlier, this is the last unexplained thing that the verifier needs to do at the very end.

The correctness of the following algorithm essentially follows from the standard properties of multilinear evaluation. The point is to do everything in a way that exploits sparsity.

• for each $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$, initialize a single scalar $\mathsf{m}_\text{op}$, starting at 0.
• precompute the tensor expansions $\left( \widetilde{\texttt{eq}}(r'_x, x) \right)_{x \in \mathcal{B}_{\ell_\text{and}}}$, $\left( \widetilde{\texttt{eq}}(r_y, y) \right)_{y \in \mathcal{B}_{\ell_\text{words}}}$ and $\left( \widetilde{\texttt{eq}}(r_s, s) \right)_{s \in \mathcal{B}_6}$.
• for each $x \in \{0, \ldots , n_\text{cons} - 1\}$ do:
  • load the $x$^th list $L^z_x$ from the constraint system.
  • for each $(y, \text{op}, s) \in L^z_x$ do:
    • update $\mathsf{m}_\text{op} \mathrel{+}= \widetilde{\texttt{eq}}(r'_x, x) \cdot \widetilde{\texttt{eq}}(r_y, y) \cdot \widetilde{\texttt{eq}}(r_s, s)$.
• return $\mathsf{m}_\text{op}$ for all $\text{op} \in \{\mathsf{sll}, \mathsf{srl}, \mathsf{sra}\}$.

This completes our treatment of the shift reduction.