Twist and Shout

🚧 These docs are under construction 🚧

👷If you are urgently interested in this specific page, open a Github issue and we'll try to expedite it.👷

One-hot polynomials

Shout

Prefix-suffix Shout

Twist

"Local" vs "alternative" algorithm

wv virtualization

In the Twist and Shout paper (Figure 9), the read and write checking sumchecks of Twist are presented as follows:

Observe that the write checking sumcheck is presented as a way to confirm that an evaluation of $\widetilde{\text{Inc}}:{\mathbb{F}}^{\log K}\times {\mathbb{F}}^{\log T}\to \mathbb{F}$ is correct.

Under this formulation, both $\widetilde{\text{Inc}}$ and the $\widetilde{\text{wv}}:{\mathbb{F}}^{\log T}\to \mathbb{F}$ polynomial are committed.

With a slight tweak, we can avoid committing to $\text{wv}$. First, we will modify $\widetilde{\text{Inc}}$ to be a polynomial over just the cycle variables, i.e. $\widetilde{\text{Inc}}:{\mathbb{F}}^{\log T}\to \mathbb{F}$. Intuitively, the $j$th coefficient of $\widetilde{\text{Inc}}$ is the delta for the memory cell accessed at cycle $j$ (agnostic to which cell was accessed).

Second, we will reformulate the write checking sumcheck to more closely match the read checking sumcheck:

$$\widetilde{\text{wv}}(r^{\prime })=\sum _{k=(k_1,\dots ,k_d)\in {\left(\{0,1{\}}^{\log (K)/d}\right)}^d,j\in \{0,1{\}}^{\log (T)}}\widetilde{\text{eq}}(r,k)\cdot \widetilde{\text{eq}}(r^{\prime },j)\cdot \left(\left(\prod _{i=1}^d{\widetilde{\text{wa}}}_i(k_i,j)\right)\cdot \left(\widetilde{\text{Val}}(k,j)+\widetilde{\text{Inc}}(j)\right)\right)$$

Intuitively, the write value at cycle $j$ is equal to whatever was already in that register ($\widetilde{\text{Val}}(k,j)$), plus the increment ($\widetilde{\text{Inc}}$).

We also need to tweak the $\widetilde{\text{Val}}$-evaluation sumcheck to accommodate the modification $\widetilde{\text{Inc}}$. As presented in the paper:

After modifying $\widetilde{\text{Inc}}$ to be a polynomial over just the cycle variables:

$$\widetilde{\text{Val}}(r_{\text{address}},r_{\text{cycle}})=\sum _{j^{\prime }\in \{0,1{\}}^{\log T}}\widetilde{\text{Inc}}(j^{\prime })\cdot \widetilde{\text{wa}}(r_{\text{address}},j^{\prime })\cdot \widetilde{\text{LT}}(j^{\prime },r_{\text{cycle}})$$