Twist and Shout: Faster Memory Checking Arguments via One-Hot Addressing and Increments

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 prover costs relative to the Spice [SAGL18 (opens in new tab)] and Lasso [STW24 (opens in new tab)] memory-checking procedures used by prior Jolt versions, from tiny memories (e.g., 32 registers as in RISC-V), to memories that are so large they cannot be explicitly materialized (e.g., structured lookup tables of size  or larger, which arise in the Jolt zkVM). We integrate Twist and Shout into the Jolt zkVM and evaluate them end-to-end against this prior Spice/Lasso-based Jolt baseline. On representative RV32IM benchmarks, Twist and Shout speed up the Jolt prover by about  while reducing proof size by about .