Insider Brief
- A16z Crypto released Lattice Jolt, a post-quantum proof system that it says produces faster, smaller proofs while using less memory.
- Lattice Jolt processed more than 2 million RISC-V cycles a second on a laptop CPU and exceeded 10 million with Apple Metal GPU acceleration.
- The system replaces elliptic-curve cryptography with the lattice-based Akita commitment scheme and produces proofs smaller than 100 kilobytes.
A16z Crypto has released a lattice-based version of its Jolt proof system that it says can resist attacks from future quantum computers while producing proofs two to three times faster than the technology it replaces.
The open-source system, called Lattice Jolt, is a zero-knowledge virtual machine, or zkVM. These systems allow a computer to prove that it correctly ran a program without requiring another computer to repeat the entire calculation. They are used in blockchains, privacy tools and other applications where participants may not trust one another.
According to a blog post from a16z Crypto, the new version replaces the elliptic-curve cryptography previously used in one part of Jolt with cryptography based on mathematical lattices. Lattices are repeating arrangements of points in many dimensions. Certain problems involving these structures are believed to be difficult for both conventional and quantum computers to solve.
The change makes Jolt post-quantum and improves its speed, proof size and memory use, the organization said. On the same laptop used for earlier tests, Lattice Jolt proved more than 2 million processor cycles a second using only the central processing unit, compared with more than 1 million cycles for the earlier elliptic-curve version.
With graphics processing acceleration through Apple’s Metal framework, Lattice Jolt exceeded 10 million cycles a second on a MacBook, according to the post. Proofs were smaller than 100 kilobytes, which a16z Crypto described as the shortest produced by a post-quantum zkVM.
The results appear to have yet to be independently verified and it should be noted that comparisons among proof systems can depend on hardware, security settings and the type of calculation being proved.
Although best known as an investor, a16z Crypto also employs researchers and engineers who develop open-source infrastructure for blockchains and related cryptographic systems. The group’s portfolio companies and the wider cryptocurrency industry could benefit from faster, quantum-resistant proof technology.
Proving a Program Ran Correctly
A SNARK, short for succinct noninteractive argument of knowledge, is a compact cryptographic proof. It can show that a statement is true or that a calculation was performed correctly without revealing all the data behind it.
A zkVM expands that concept by allowing developers to prove the execution of ordinary programs rather than building a separate cryptographic circuit for every application. Jolt supports programs that use RISC-V, an open instruction set that defines the basic commands that a processor understands.
One computer, known as the prover, runs the program and generates a proof. Another computer, called the verifier, checks that proof. Verification should require less work than repeating the original calculation.
This model can help blockchains move computation away from an expensive shared network while allowing the network to verify the result. It can also support private identity checks, financial transactions and other applications in which a user must prove something without disclosing the underlying information.
Jolt’s design is intended to cover both large and small workloads. A GPU-based prover can process programs involving billions of processor cycles, while a phone can handle programs with millions of cycles, according to a16z Crypto. Developers can write conventional software instead of constructing specialized proof circuits by hand.
A16z Crypto calls Jolt an “everything SNARK,” which relates to its goal of creating a general-purpose proof system that performs well enough across many applications to reduce the need for custom cryptographic engineering.
Lattice Jolt is not yet a full zero-knowledge system, however. The current version provides succinct proofs of correct computation, while a forthcoming companion paper will add the zero-knowledge property needed to hide private information.
Replacing Elliptic Curves With Lattices
The original Jolt architecture depended on a polynomial commitment system called Dory. A polynomial commitment allows a prover to commit to mathematical data and later demonstrate that particular claims about that data are correct without revealing or retransmitting everything.
Dory used elliptic-curve cryptography, which is common in existing blockchains and security systems. Elliptic curves offer strong protection against conventional computers, but a more mature quantum computing system running Shor’s algorithm could one day break widely used versions of the technology.
Lattice Jolt replaces Dory with Akita, a polynomial commitment scheme built on a lattice problem known as Module-SIS. Akita was developed and implemented by researchers and engineers at LayerZero in collaboration with teams at Carnegie Mellon University, the University of Southern California and a16z Crypto.
Module-SIS belongs to the same broad family of mathematical problems used in emerging post-quantum standards. A related problem, Module-LWE, supports encryption and key-establishment systems intended to replace current public-key cryptography.
The National Institute of Standards and Technology — or NIST — has already standardized lattice-based systems for digital signatures and key establishment. ML-DSA is a digital-signature standard, while ML-KEM allows two parties to establish a shared secret over an open network. The expanding deployment of these systems gives lattice cryptography a more established foundation than many experimental approaches.
A16z Crypto said Lattice Jolt targets 128 bits of security. That means a conventional attacker would generally be expected to need an impractical amount of computational work, on the order of possible operations, to defeat the system through brute force.
Jolt was suited to the switch because both elliptic-curve and lattice commitments can efficiently handle sparse vectors, or lists in which most values are zero or small. Jolt relies on such data structures, allowing its developers to exchange Dory for Akita without redesigning the rest of the architecture.
Smaller Numbers Bring Faster Proofs
Much of Lattice Jolt’s speed gain comes from reducing the size of the numbers involved in its calculations.
The elliptic-curve version required Jolt to operate with 256-bit values to reach its intended level of security. Lattice cryptography provides comparable protection while allowing the system to work with 128-bit values, according to a16z Crypto.
Generating a proof requires large numbers of mathematical multiplications. Cutting the size of the values in half can make each multiplication several times faster, producing gains across the full proving process.
Earlier versions of Jolt processed about 700,000 RISC-V cycles a second on a laptop. Later software improvements raised the elliptic-curve version above 1 million cycles a second. Lattice Jolt now exceeds 2 million cycles a second using the same machine’s CPU.
Speed is important because generating cryptographic proofs adds substantial computing time and expense to an application. Faster proving can reduce infrastructure costs, process more blockchain transactions and make it practical for phones and other consumer devices to produce proofs without noticeable delays.
A broader rewrite of the Jolt code also made GPU acceleration easier to implement. On a MacBook using Apple Metal, the lattice version exceeded 10 million cycles a second. The rewritten elliptic-curve version reached about 4 million cycles a second when it also used Metal.
That comparison means the overall performance of Jolt on a MacBook increased from about 1 million cycles a second for the earlier CPU-only configuration to more than 10 million for the lattice system with GPU acceleration. Not all of that improvement came from the cryptographic change because the tests also incorporate new code and different use of the hardware.
Proving a calculation remains far more expensive than running it normally. A16z Crypto estimated that Jolt’s proving overhead has fallen to about 10,000 times the cost of ordinary execution. Four years earlier, proof generation could require millions of times more work than the underlying calculation.
Memory use also declined from about 300 bytes for every processor cycle being proved to approximately 200 bytes. Lower memory requirements could make client-side proving on phones and other consumer devices more practical.
Proof size matters because proofs may need to be transmitted over networks and posted to blockchains, where data storage can be expensive. Lattice Jolt’s proofs are under 100 kilobytes, compared with a range of more than 200 kilobytes to approximately 600 kilobytes or more for other post-quantum zkVMs cited by a16z Crypto.
Challenging the Hash-Based Approach
Most post-quantum SNARKs in production use hash functions rather than lattices as their cryptographic foundation. Hash-based systems have often been viewed as the conservative choice because conventional cryptographic hashes are well studied and depend on somewhat simple security assumptions.
A16z Crypto claims in the post that the distinction is less clear in deployed proof systems. Many hash-based SNARKs use algebraic hash functions such as Poseidon because they can be evaluated efficiently inside a proof. These specialized hashes contain more mathematical structure than conventional hashes and have undergone less analysis, according to the post.
Some hash-based systems have also relied on unproven estimates when setting their practical security levels, a16z Crypto said. Other designs target less than 128 bits of security because reaching the full level would impose significant performance costs.
The difference becomes more important as the amount of computation grows. A16z Crypto said the probability that a false proof could pass verification in some hash-based systems increases roughly with the size of the statement divided by the size of the mathematical field. As a result, proving a billion-step computation over a 128-bit field could reduce effective security by about 30 bits.
Lattice Jolt’s error probability grows much more slowly, according to the post. Its security loss depends on the logarithm of the computation’s size, allowing it to retain nearly the full 128-bit target while using a 128-bit field.
That does not establish lattices as the best foundation for every proof system. Hash-based cryptography remains an important area of research, and its simpler underlying ideas may be useful where performance and proof size are less important. A16z Crypto said it plans to build a hash-based version of Jolt alongside its elliptic-curve and lattice systems.
The organization expects that version to require more memory and produce larger proofs. Binary mathematical fields used by some leading hash-based designs are well suited to proving hash operations but do not closely match the arithmetic performed by ordinary CPUs, making standard multiplication harder to prove.
The broader goal is to give developers versions of Jolt based on three independent cryptographic foundations. Elliptic curves may remain useful where quantum resistance is not immediately required, while hashes and lattices offer different paths to post-quantum protection.
A16z Crypto expects lattices to emerge as the more widely deployed option, pointing to the adoption of lattice-based digital signatures and key-establishment systems. Whether SNARKs follow the same path will depend on further security analysis, implementation testing and use under production conditions.
For smaller applications, the organization’s immediate target is to let a phone generate a proof in about one second. Jolt is approaching that threshold, according to the post, but has not yet consistently crossed it. Further protocol and engineering improvements are planned.
