Jolt: An update

In April, the a16z crypto research and engineering teams released an initial implementation of Jolt, a state-of-the-art zkVM. Since then, the Jolt team and open source contributors have made several improvements to Jolt’s performance and usability. 

The upshot for performance is that Jolt’s verifier costs have come way down: from proof sizes that were well into the MBs in April, to about 200 KBs today. Further reductions down to 25 KBs are possible. 

Jolt’s reduced verifier costs will pay further dividends in the coming months, unlocking efficient folding schemes to control prover space. Integrating folding into Jolt will yield three major features all at once. Folding will 

1. keep the prover’s space to just a few GB, 
2. achieve zero-knowledge, and 
3. yield on-chain proofs. 

Separately, the Jolt prover is poised to speed up by roughly a factor of up to 3. This improvement will come from incorporating recently-identified optimizations to the sum-check protocol, and better leveraging of the highly uniform nature of the constraint system arising in Jolt.

A short video overview of the Jolt roadmap and vision is here. Details of the improvements completed since April are below.

Rust standard library support

On release, Jolt only supported guest programs written in “no-std” Rust. Engineering partner Noah Citron integrated support for the Rust standard library, enabling developers to use many more existing Rust crates off-the-shelf. 

RISC-V “M” extension

With help from open source contributors Mihir Wadekar and Ethan Lee, we added support for the RISC-V “M” extension for integer multiplication and division. This significantly improved Jolt’s performance on guest programs using many multiplications or divisions, which previously would be compiled to lengthy instruction sequences. 

Support for new commitment schemes

The initial implementation of Jolt used Hyrax as its polynomial commitment scheme, though the Jolt architecture is compatible with any multilinear commitment scheme. While Hyrax provided good prover performance, its proofs were relatively large. Open source contributors Pat Stiles and Ethan Lee integrated the Zeromorph and HyperKZG polynomial commitment schemes, respectively, both of which significantly reduce proof sizes with only a modest prover slowdown. 

Smaller opening proofs

We implemented a sum-check-based protocol (originally implemented in Nova) to reduce multiple opening proofs to one. This reduces proof size and, for some polynomial commitment schemes, reduces prover time as well. 

“Quarks” grand products

Open source contributor alpeh_v implemented the grand product argument described in the Quarks paper as an alternative to Jolt’s existing implementation of Thaler ‘13 grand products. Compared to Thaler ‘13, the Quarks grand product argument yields smaller proofs at the cost of prover time. 

Progress towards on-chain verification

Alpeh_v and Matteo Mer also made significant progress toward a Solidity implementation of the Jolt verifier. Once completed, this will allow Jolt proofs to be verified on any EVM blockchain. 

AVX-512 library for field arithmetic

We worked with Dag Arne Osvik to release an AVX-512 library for 256-bit Montgomery arithmetic. This can be used to accelerate field arithmetic in Jolt, Groth16, and other elliptic curve-based SNARKs on hardware that supports the extension. A full integration of this library into Jolt will come in the future.

Ongoing formal verification efforts

Led by Quang Dao and Carl Kwan, interns in our summer research program, formal verification efforts have taken on four tasks so far:

1. Building and validating a formal model of RISC-V in ACL2
2. Verifying that the “evaluation table decompositions” in Jolt are all correct (i.e., verifying the way we break each primitive instruction into lookups into “subtables” and collate the results into the instruction’s output) 
3. Confirming that the “R1CS constraints and lookups” in Jolt together in fact capture correct RISC-V semantics
4. Formalizing in Lean the completeness and soundness of the Jolt polynomial IOP, starting with two of its key components: Lasso and Spartan

The first two tasks are complete, the third is nearly so, and the fourth is in progress. These efforts have already led to the identification of minor bugs and optimizations in the Jolt implementation. 

Coming soon

Our work is far from finished. We are working with several teams and individual contributors to advance Jolt, and we have several exciting improvements underway, including:

• Various sum-check prover optimizations 
• Further reduction in proof size and verifier costs
• GPU integration
• Continuations via folding (i.e., integration of Jolt with Nova). 

Integration of the Binius commitment scheme and a switch from 256-bit prime-order fields to binary fields are further out.

If you’d like to contribute or learn more about Jolt’s roadmap, reach out to @moodlezoup. 

***

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.

Michael Zhu is a research engineer for a16z crypto, writing open-source code in collaboration with the research team and helping portfolio companies on all things smart contract-related. Prior to joining a16z crypto, Michael led protocol development at 0x Labs, architecting smart contracts to facilitate peer-to-peer trading on multiple blockchains. Before that, he was a student at Stanford University, where he received BS and MS degrees in Computer Science.

***

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

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.