Twist and Shout via logup*

Georg Wiese (Powdr Labs), 2025

Adapts Twist and Shout to work with hash-based commitment schemes, using the pushforward machinery from logup*.

Motivation: Twist and Shout rely on efficient commitments to sparse polynomials, which is natural for elliptic-curve-based schemes but expensive for hash-based schemes. Logup* provides a way around this.

One-hot matrix commitment scheme

Logup* implicitly contains a commitment scheme for matrices with one-hot rows $M\in {\mathbb{F}}^{n\times m}$. Instead of committing to the full matrix, commit to its dense encoding $M_{\text{dense}}\in {\mathbb{F}}^n$ (the column index of the 1 in each row).

To evaluate $\tilde{M}(r_{\text{row}},r_{\text{col}})$:

1. The prover commits to $P:={M_{\text{dense}}}_{\ast }{\mathsf{eq}}_{r_{\text{row}}}\in {\mathbb{F}}_{\text{ext}}^m$.
2. Prover proves well-formedness via GKR, as in Logup*.
3. The key identity is $\tilde{M}(r_{\text{row}},r_{\text{col}})=\tilde{P}(r_{\text{col}})$.

Derivation of (3):

$$\begin{array}{rl}\tilde{P}(r_{\text{col}})& =⟨P,{\mathsf{eq}}_{r_{\text{col}}}⟩\\ & =\sum _{j=0}^{m-1}P[j]\cdot \widetilde{\mathsf{eq}}(\text{bits}(j),r_{\text{col}})\\ & =\sum _{j=0}^{m-1}\left(\sum _{i\mid M_{\text{dense}}[i]=j}\widetilde{\mathsf{eq}}(\text{bits}(i),r_{\text{row}})\right)\cdot \widetilde{\mathsf{eq}}(\text{bits}(j),r_{\text{col}})\\ & =\sum _{(i,j)\mid M[i,j]=1}\widetilde{\mathsf{eq}}(\text{bits}(i)\Vert \text{bits}(j),r_{\text{row}}\Vert r_{\text{col}})\\ & =\tilde{M}(r_{\text{row}},r_{\text{col}})\end{array}$$

The third step expands the pushforward definition, the fourth uses the product structure of $\widetilde{\mathsf{eq}}$, and the last step is the definition of the multilinear extension of a matrix with one-hot rows (only $n$ nonzero terms).

Batching

Naively, opening $d$ one-hot matrices requires $d$ pushforward commitments. Batching reduces this to one. Given $d$ dense encodings $M_{\text{dense}}^{(1)},\dots ,M_{\text{dense}}^{(d)}\in {\mathbb{F}}^n$ of one-hot matrices $M^{(i)}\in \{0,1{\}}^{n\times m}$:

1. Concatenate: $M_{\text{dense}}^{(\ast )}:=M_{\text{dense}}^{(1)}\Vert \cdots \Vert M_{\text{dense}}^{(d)}\in {\mathbb{F}}^{n\cdot d}$.
   • This does not require new commitments: $\widetilde{M_{\text{dense}}^{(\ast )}}(x)={\sum }_{i=1}^d\widetilde{eq}(\text{bits}(i),x)\cdot \widetilde{M_{\text{dense}}^{(i)}}$.
2. Use ${\tilde{M}}^{(i)}(x_{\text{row}},x_{\text{col}})={\tilde{M}}^{(\ast )}(x_{\text{row}},\text{bits}(i),x_{\text{col}})$ to translate $d$ claims to ${\tilde{M}}^{(i)}$ to claims about ${\tilde{M}}^{(\ast )}$.
3. Reduce $d$ claims to one via Reducing Multiple Evaluations to One.
4. Open via a single pushforward $P:={M_{\text{dense}}^{(\ast )}}_{\ast }{\mathsf{eq}}_{r_{\text{row}}}\in {\mathbb{F}}_{\text{ext}}^m$.

Twist and Shout via logup*

Shout via logup*

Directly applies the one-hot commitment scheme with batching. With decomposition parameter $d$ (as in original Shout):

• Given $d$ dense address vectors ${\mathsf{ra}}_{\text{dense}}^{(i)}\in {\mathbb{F}}^T$
• Given memory content $\mathsf{Val}\in {\mathbb{F}}^K$
• Commit to one batched pushforward $P:={{\mathsf{ra}}_{\text{dense}}^{(\ast )}}_{\ast }{\mathsf{eq}}_{r_{\text{row}}}\in {\mathbb{F}}_{\text{ext}}^{\sqrt[d]{K}}$

For $d=1$, this is equivalent to using logup* directly. For large memories, $d>1$ reduces the pushforward cost from $K$ to $\sqrt[d]{K}$ extension field elements.

Twist via logup*

Same idea applied to the read/write case:

• Given $d$ read address vectors ${\mathsf{ra}}_{\text{dense}}^{(i)}\in {\mathbb{F}}^T$
• Given $d$ write address vectors ${\mathsf{wa}}_{\text{dense}}^{(i)}\in {\mathbb{F}}^T$
• Given Increment vector ${\mathsf{Inc}}_{\text{val}}\in {\mathbb{F}}^T$ (dense; position determined by write address)
• One batched pushforward $P\in {\mathbb{F}}_{\text{ext}}^{\sqrt[d]{K}}$ (shared across all $2d$ address matrices)