Paper 2025/105
Twist and Shout: Faster memory checking arguments via one-hot addressing and increments
Abstract
A memory checking argument enables a prover to prove to a verifier 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, which we call the method of one-hot addressing and increments. We instantiate this method via two different families of protocols, called Twist and Shout. Twist supports read/write memories, while Shout targets read-only memories (also known as lookup arguments). Both Shout and Twist have logarithmic verifier costs. Unlike prior works, these protocols do not invoke "grand product" or "grand sum" arguments.
Twist and Shout significantly improve the prover costs of prior works across the full range of realistic memory sizes, 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
Note: Fixed an error in the description of the "local" proving algorithm for Twist (Section 8.2.2) and associated cost accounting. Fixed an error in Section 6.3 on a proving algorithm for Booleanity-checking--this slightly increases an additive O(d K^{1/d}) term in prover time for that algorithm to O(K^{1/d} log(K)). Additional typo corrections.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- SNARKsmemory-checking argumentssum-check protocolzkVMs
- Contact author(s)
-
srinath @ microsoft com
justin r thaler @ gmail com - History
- 2025-02-27: last of 7 revisions
- 2025-01-22: received
- See all versions
- Short URL
- https://ia.cr/2025/105
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/105, author = {Srinath Setty and Justin Thaler}, title = {Twist and Shout: Faster memory checking arguments via one-hot addressing and increments}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/105}, year = {2025}, url = {https://eprint.iacr.org/2025/105} }