Paper 2025/105

Twist and Shout: Faster memory checking arguments via one-hot addressing and increments

Abstract

Memory checking arguments enable an untrusted prover to prove that it is correctly processing reads and writes to memory. They are used widely in modern SNARKs, especially in zkVMs, where the prover proves the correct execution of a CPU including the correctness of memory operations. We describe a new approach for memory checking, called the method of one-hot addressing and increments. We instantiate this method via two families of protocols, called Twist and Shout. Twist supports read/write memories, while Shout targets read-only memories (also known as lookup arguments). Both have logarithmic verifier costs. Unlike prior works, these protocols do not invoke "grand product" or "grand sum" arguments. Twist and Shout reduce commitment costs in two Jolt settings: 32 RISC-V registers and structured lookup tables of size $2^64$. With curve-based commitments, Twist at $d=1$ has about 3.7x fewer nonzero committed values and 1.7x fewer field multiplications than Spice for 32 registers; Shout at $d=2$ has at least 8x fewer nonzero committed values and 3.4x fewer field multiplications than Lasso for structured tables. We integrate Twist and Shout into the Jolt zkVM. They speed up the Jolt prover 3x while reducing proof size by about 5x.

Note: This update includes several concrete optimizations as well as additional details and corrections regarding one-hot checking in small-characteristic fields.