Paper 2025/105

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

Srinath Setty, Microsoft Research
Justin Thaler, Georgetown University, a16z crypto research
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 or larger, which arise in Lasso and the Jolt zkVM). Detailed cost analysis shows that Twist and Shout are well over 10x cheaper for the prover than state-of-the-art memory-checking procedures configured to have logarithmic proof length. Prior memory-checking procedures can also be configured to have larger proofs. Even then, we estimate that Twist and Shout are at least 2--4x faster for the prover in key applications. Finally, using Shout, we provide two fast-prover SNARKs for non-uniform constraint systems, both of which achieve minimal commitment costs (the prover commits only to the witness): (1) SpeedySpartan applies to Plonkish constraints, substantially improving the previous state-of-the-art protocol, BabySpartan; and (2)Spartan++ applies to CCS (a generalization of Plonkish and R1CS), improving prover times over the previous state-of-the-art protocol, Spartan, by 6x.

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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.