Entering the era of lattice SNARKs – with a faster, post-quantum Jolt

Markos Georghiades, Justin Thaler, Andrew Tretyakov, and Michael Zhu
Share

Tags

Today we are releasing Lattice Jolt, a new version of our open source zkVM (zero knowledge virtual machine). The architecture is the same one that already made Jolt the fastest and simplest zkVM available. What changes with this new version is the cryptography underneath it, which now rests on lattices instead of elliptic curves. This one change does three things at once:

  • It makes Jolt post-quantum.
  • It makes the prover and verifier 2x-3x faster.
  • It gives Jolt the shortest proofs of any post-quantum zkVM: under 100 KB today, with a path to further reductions. Proofs get posted on-chain and sent over networks, so smaller proofs mean cheaper verification everywhere.

Those properties hold across the whole range of settings where zkVMs get used. The same prover that handles billions of CPU cycles on GPUs can also prove millions of cycles on a phone, and in both cases developers write ordinary programs rather than hand-crafted circuits requiring special expertise. That is what we mean when we call Jolt the “everything SNARK”.

But the bigger story is what Lattice Jolt means for SNARK design and adoption. Nearly every post-quantum SNARK in production today is hash-based. Lattice Jolt shows that lattice-based SNARKs can be both faster and more compact. Digital signatures are going through the same transition: Hash-based schemes are the conservative choice, but lattice-based ones are what the world is mostly deploying. We expect SNARKs to follow, and the second half of this post explains why.

Replacing elliptic curves with lattices

Jolt’s previous polynomial commitment scheme, Dory, was the one component of the system that depended on elliptic-curve cryptography. Lattice Jolt replaces Dory with Akita, a new polynomial commitment scheme based on the lattice assumption Module-SIS. Lattice Jolt targets a full 128 bits of security based on this standard, well-studied assumption.

This is the same family of assumptions — Module-SIS and its sibling Module-LWE — that the world’s digital infrastructure is now migrating to. These assumptions underlie not only the digital signature standard ML-DSA, but also the key-establishment standard ML-KEM, which is already the most widely deployed post-quantum primitive in the world.

Akita’s development and implementation was led by researchers and engineers at LayerZero, in collaboration with researchers at Carnegie Mellon University, the University of Southern California, and our engineering and research teams here at a16z crypto.

How Lattice Jolt is faster

Not only is Lattice Jolt post-quantum, it’s faster than the elliptic curve-based version it replaces.

The speedup primarily comes from a simple source. Elliptic curves forced Jolt to work over 256-bit fields; lattice cryptography achieves comparable security over 128-bit fields. The Jolt prover’s work is dominated by multiplying field elements (essentially, very large numbers) — so halving their size makes each multiplication several times faster.

Jolt with Dory was already fast: Our last performance update on Jolt reported about 700,000 RISC-V (RV64IMAC) cycles per second on a laptop, and optimizations since then have pushed curve-based Jolt past 1 million cycles per second.

Lattice Jolt proves over 2 million cycles per second on the same machine.

Much of the past six months went not only into developing Akita and integrating it into Jolt, but also into rewriting the Jolt codebase from scratch. Jolt already ran well on GPUs, but the rewrite makes GPU implementations far easier to build and optimize.

The first payoff is an Apple Metal implementation, which brings large speedups to Apple hardware. (Metal is Apple’s framework for running code on the GPUs built into its devices, including MacBooks and iPhones.) —

  • GPU-accelerated Lattice Jolt proves over 10 million RV64IMAC cycles per second on a MacBook.
  • CPU-only Lattice Jolt proves over 2 million cycles per second on the same machine.
  • Even curve-based Jolt now runs at about 4 million cycles per second on a MacBook with Metal.

In other words, in a single release, Jolt on a MacBook has gone from about 1 million cycles per second (curve-based, CPU-only) to over 10 million (lattice-based, with Metal).

To put those numbers in perspective: When we first wrote about SNARK prover overheads four years ago, proving a computation cost millions of times more than simply running it. Lattice Jolt brings that overhead down to roughly 10,000x. And this is still not the end; clear engineering and protocol optimizations remain on the table.

Proof size matters just as much as prover speed. At under 100 KB, Lattice Jolt proofs are already substantially smaller than those of other post-quantum zkVMs, whose proofs range from over 200 KB to roughly 600 KB or more.

The switch to lattices also improves Jolt’s already best-in-class memory usage, dropping the prover’s space usage from about 300 bytes per cycle to 200. This means you can prove millions of RISC-V cycles on a mobile phone.

A companion paper, coming shortly, adds zero knowledge to Lattice Jolt, a property required for privacy applications.

The case for lattices over hashing

For years, the SNARK community’s attention — and essentially all of its production deployments — have gone to hash-based SNARKs as the path to post-quantum security.

But there has also been a sustained line of work on lattice SNARKs and lattice commitments — spanning LaBRADOR, Greyhound, LatticeFold, SuperNeo, and Akita’s immediate predecessor, Hachi. Lattice Jolt builds on that research, bringing a lattice commitment layer into the architecture of a high-performance zkVM while showing that lattice-based SNARKs have unmatched speed and compactness.

This should not be surprising. As mentioned, the same pattern has already played out for digital signatures.

Cryptographers have built signatures from many assumptions. Hash-based signatures are often viewed as the most conservative: their security assumptions are simple and old. But the world is moving primarily toward lattice-based signatures because they are shorter and faster —

  • ML-DSA signatures are on the order of a few kilobytes.
  • The NIST-standardized hash-based alternative, SLH-DSA, is several times larger.
  • For encryption and key exchange, the case is even clearer: No hash-based option exists (provably so), and post-quantum deployment is overwhelmingly lattice-based. ML-KEM — the primary key-establishment standard NIST finalized in 2024 — is already deployed by default in major browsers, messaging apps, and a large share of TLS connections on the web.

The analogy between SNARKs and signatures isn’t superficial. A digital signature is essentially a proof of knowledge of a secret key, tied to an authorized message. SNARKs extend this paradigm from one narrow statement to arbitrary computation. So it would be surprising if the long-term cryptographic landscape for SNARKs looked completely different from the landscape for signatures and encryption.

There is also a misconception worth clearing up here: Hash-based SNARKs are often described as the conservative post-quantum choice because they are “just based on hashes”. That is true only if the underlying hash function is non-algebraic.

Today, most hash-based SNARK deployments rely on SNARK-friendly algebraic hash constructions like Poseidon to make it cheap to prove that a hash was evaluated correctly, which is especially important for recursion (note here recursion means proving you hold a valid SNARK proof). Those constructions are far more structured than standard hash functions, and their cryptanalysis is much less mature.

In short, we do not have confidence in the security of algebraic hash functions. Despite this, they are used pervasively in production SNARK systems today. (Though, in a sign of progress, the Ethereum Foundation recently announced that it is moving away from them.)

Algebraic hashes are not the only hidden assumption in deployed hash-based SNARKs: Many have historically set concrete security levels using conjectured proximity-gap bounds rather than fully proven ones. Some of the strongest have turned out to be false.

Even hash-based SNARKs that avoid the above conjectures often target fewer than 128 bits of security, because a full 128 bits comes with significant performance overheads. Why? Hash-based SNARKs can’t reach 128 bits of security over a 128-bit field, owing to soundness error that scales like n/|F|, where n is roughly the size of the statement being proved and |F| is the field size. So over a 128-bit field, proving a billion-step statement loses about 30 bits of security, dropping under 100 bits. Instead, Lattice Jolt’s soundness error scales like log(n)/|F| — keeping nearly the full 128 bits of security over the same field (the small log(n) loss can be restored with standard techniques).

Ironically, some systems marketed as the “conservative” post-quantum choice in fact rely on algebraic hash functions, conjectural proximity-gap bounds, and a sub-128-bit target security level all at once. So while hash-based SNARKs are an important direction, they are not automatically the low-risk option that many believe them to be.

One Jolt, three foundations: curves, lattices, and hashes

Our view has always been that Jolt should not be tied to one cryptographic foundation. We should have mature, performant SNARKs based on curves, hashes, and lattices. Different assumptions and performance profiles will be appropriate for different settings.

But if digital signatures are any guide, lattice-based SNARKs will become the most deployed post-quantum option.

Jolt is unusually well positioned for this transition. The original Jolt design exploited properties of elliptic curves that are especially useful for commitments, including fast commitments to sparse vectors. Lattice commitments have the same property: Committing to a vector is cheap when most of its entries are zero or small, and Jolt commits almost exclusively to such vectors. This property made it possible to swap out Dory for Akita while leaving the rest of Jolt intact.

We will build a hash-based version of Jolt. But a hash-based version — compared to curve-based and lattice-based Jolt — will have worse space efficiency, bigger proofs, and a variety of complications. This is because the most promising hash-based SNARKs work over binary fields, number systems that are convenient for proving hash evaluations but mismatched with how CPUs do arithmetic. That mismatch makes proving ordinary CPU multiplications expensive. Even so, the ecosystem should have zkVMs under every major assumption family, just as it has for digital signatures.

The everything SNARK

Lattice Jolt is everything builders need from a zkVM at once: post-quantum, transparent, fast, compact, and space-efficient. It brings the lattice-SNARK line of work, from LaBRADOR to Hachi, into a production zkVM without giving up anything that made Jolt fast in the first place.

Our goal is to not only release the most performant zkVM as open source for anyone to use, but to largely eliminate the need to hand-tune SNARKs for particular applications. This doesn’t require Jolt to be as fast as hand-tuned provers — an impossible goal analogous to demanding a CPU match a purpose-built ASIC at every task. It only requires Jolt to be fast enough for an acceptable user experience.

For the “small” statements relevant to client-side proving (where hand-optimized circuits dominate today), the key bar to clear is generating proofs on a phone in under a second or so. Jolt is on the edge of achieving this already, with plenty more speedups in the pipeline.

The era of lattice SNARKs is upon us.

 

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/investments/.

Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. 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.