Introducing Twist and Shout: Next-generation memory checking for zkVMs and more

Jolt is our open source zkVM which offers unmatched speed and simplicity. A previous post introduced the main takeaways and ideas underlying Jolt’s design philosophy. Now, Srinath Setty and I have released a new paper unveiling Twist and Shout, two new memory-checking arguments that ensure a prover correctly handles every read and write to the VM’s memory. 

The key insight behind Twist and Shout is that the prover can quickly commit to very large, yet highly sparse vectors. Once this commitment is made, memory-checking simplifies into massive but straightforward constraint systems that the sum-check protocol can handle. Crucially, these constraint systems remain sparse, and the sum-check prover only pays for non-zero elements when producing a proof.

By integrating Twist and Shout, I expect Jolt to achieve roughly a 3x end-to-end prover speedup, plus shorter proofs — on top of a separate 2x boost from known prover optimizations that we are in the process of implementing. 

(These expectations are based on a precise accounting of the work the prover does throughout the SNARKs. For example, when comparing one elliptic-curve-based SNARK to another, you can count group and field operations done by the prover, and thereby tell how the SNARK will perform before implementing it. If one SNARK prover does X group operations and Y field multiplications, and another does 2X and 3Y, the first prover will be faster. For details, see the paper.)

In other words, Twist and Shout reinforce — and amplify — Jolt’s core design principles. Below, we highlight the core lessons of Twist and Shout and their implications for zkVM design and SNARKs more generally.

1. Validation of Jolt’s lookup-centric architecture

Jolt transforms every VM action into either:

1. Lookups into read-only memory, proven with the Lasso lookup argument, or
2. Reads and writes to registers and RAM, proven with the Spice memory-checking argument.

This approach yields a simple and modular architecture. Now, we can replace Lasso with Shout and Spice with Twist to achieve that 3x prover speedup.

2. The sum-check protocol is key to fast SNARK provers

Some in the SNARK community paint “elliptic curves vs. hashing” (i.e., “big fields vs. small fields”) as the primary dichotomy separating fast SNARKs from slow ones. They often characterize elliptic-curve-based SNARKs with 256-bit fields as extremely slow. But this framing ignores two issues:

1. Performance data directly contradicts this view. For instance, Jolt with elliptic curve commitments is currently the fastest RISC-V zkVM.
2. “Hashing vs. curves” is but a single dimension of a multi-dimensional space. The most performance-critical dimension is whether one employs multilinear polynomials and the sum-check protocol versus univariate polynomials and quotienting.

In practice, Jolt-with-Twist-and-Shout-and-elliptic-curves will be an order of magnitude faster than hashing-based SNARKs that rely on univariate polynomials. Jolt-with-Twist-and-Shout-over-binary-fields (with Binius or another hashing-based scheme) will be faster still, but that’s not because “hashing vs. curves” is the linchpin. Indeed:

1. Binius relies internally on the sum-check protocol to enable very fast commitments to small values like 0s and 1s.
2. Jolt-over-binary-fields, once implemented, will add code complexity, require more prover memory, and offer only modest speedups on most CPUs. Also, its largest performance improvements require hardware with more robust support for binary-field arithmetic than today’s CPUs. 

3. 256-bit or binary fields are best for SNARK performance

Despite their popularity, SNARKs over 31-bit or 64-bit fields (especially those using univariate polynomials in place of multilinear polynomials and the sum-check protocol) are slow.

Why 256-bit or binary fields, rather than 31-bit characteristic fields? Twist and Shout highlight just one reason among many:

• Committing to 0s is roughly 30 times faster in a binary field than in a 31-bit field.
• The difference is even larger for 256-bit fields. When using elliptic-curve commitments based on these fields, 0s do not affect the commitment at all and can simply be ignored.

Twist and Shout take advantage of such fast commitments to 0s, plus the sum-check protocol, which avoids paying for these 0s “outside of the commitment scheme.” The result is an extremely fast, straightforward family of memory-checking arguments.

4. “SNARK-friendly” VMs are not actually SNARK friendly

Jolt already showed that instruction sets designed for real CPUs can also be SNARK friendly. The same principles that make instructions efficient for hardware (like the output being a simple function of the bits of the input) also lend themselves to sum-check-based lookup arguments.

Now, Twist and Shout push this even further by introducing the first memory-checking arguments that get substantially faster when memory sizes are small or when memory accesses stay local. As SNARK design advances, the performance profile of zkVM provers will edge closer and closer to that of real CPUs. In the end, any VM advertised as “SNARK-friendly” today will likely turn out to be merely “friendly” to the current limitations of today’s SNARKs. On top of that, these SNARKs come with major downsides — like the inability to leverage existing tooling ecosystems.

5. This is about more than zkVMs

Twist and Shout are broadly useful in SNARK design as standalone primitives. For example, Shout implies a new SNARK for non-uniform circuits (which we call SpeedySpartan) that is an order of magnitude faster than Spartan itself. In SpeedySpartan, gate inputs are simply lookups into a “table of gate values,” and the prover’s main task is to commit to the witness; everything else reduces to field operations.

In addition, the technical underpinnings of Twist and Shout are new and powerful. Twist and Shout have the prover commit to very large but very sparse vectors, and only “pay” for the sparsity rather than the total size of those vectors. I expect this approach to catalyze new high-performance SNARK protocols across a broad spectrum of applications and contexts. 

***

Twist and Shout, integrated into Jolt, will provide a significant leap in both speed and simplicity. They validate our broader design choices and further emphasize that the sum-check protocol is central to building fast SNARKs. 

***

Justin Thaler is Research Partner at a16z and an Associate Professor in the Department of Computer Science at Georgetown University. His research interests include verifiable computing, complexity theory, and algorithms for massive data sets.

***

The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.

 This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investment-list/.

The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures/ for additional important information.