Jolt — our open-source, state-of-the-art zkVM — now supports zero knowledge, rendering it suitable for privacy applications. This advance does not require any SNARK recursion or “wrapping,” nor does it sacrifice transparency. And perhaps most surprisingly, proof size increased by only 3KB, with essentially no increase in prover time. This post explains how.
But first, a note on terminology: Most zkVMs are not actually zero knowledge — unless an expensive “wrapping” procedure is applied. (Most people have been using “zk” to refer to the property of succinctness, which refers to proofs that are short and fast to verify.) This wrapping typically involves recursively proving the verification of the zkVM proof inside another proof system that is ZK, which is both computationally costly and often requires giving up transparency (i.e., it introduces a trusted setup). As the community’s focus on privacy grows — requiring true zero knowledge, which is about privacy of the prover’s sensitive data — this misuse of terminology is becoming a real problem.
Jolt takes a different approach.
How we did it: NovaBlindFold
The technique we use is called NovaBlindFold. It grew out of the Nova and HyperNova folding schemes (see Section 7 of the HyperNova paper), and was recently implemented in Vega to obtain a ZK variant of Spartan. The core idea is simple and, in fact, dates back to the 1990s.
Why Jolt previously lacked zero knowledge
Jolt is not directly zero-knowledge for one specific reason: The sum-check-based prover’s messages leak data about the witness. Everything else about the proof system is already fine from a ZK perspective — it’s the sum-check prover messages, sent in the clear, that are the real culprit.
The blinding step
The fix is conceptually straightforward. Instead of sending the sum-check prover’s messages in the clear, the zk-Jolt prover sends hiding commitments to them. This transforms the non-ZK Jolt proof into a “blinded” proof π.
Importantly, π is actually shorter than the original Jolt proof. This is because the hiding commitments compress several field elements down to a single group element — so the blinded proof is more compact than the original sum-check messages it replaces.
The extension: (π, π’)
The blinding step creates a new problem: Because π is blinded, the verifier can no longer directly check the sum-check messages for validity. To address this, we extend π to a slightly longer proof (π, π’), where π’ proves that the values “inside” the blinded commitments would have passed the sum-check verifier’s checks.
Because π is shorter than the original unblinded proof, the “savings” in proof size almost fully offsets the “extra” data contributed by π’. The net result is a ZK proof that is only about 3 KB larger than the original non-ZK Jolt proof.
Designing π’: The old way vs. NovaBlindFold
The “old way” (first implemented in Hyrax in 2017) constructs π’ by running a sigma protocol for each multiplication performed by the sum-check verifier. This works, but it is neither particularly simple nor cheap.
NovaBlindFold provides a simpler and more efficient alternative. The idea is as follows:
- Take the sum-check verifier’s checks and express them as a constraint system.
- Randomly combine (i.e., fold) the witness — which is the solution to this constraint system corresponding to the actual proof — with another, independently sampled random solution to the same constraint system.
The folded solution is safe to reveal to the verifier because the random solution acts as a mask, destroying any information the real witness might have leaked (the same intuition behind why one-time pads achieve perfect secrecy).
To keep the proof as short as possible, we don’t reveal the folded solution in full, but instead apply Spartan to prove that the folded solution is a satisfying assignment. This ensures that π’ grows only logarithmically with the length of the folded solution rather than linearly. (Note: this application of Spartan does not have to be zero-knowledge, because the folded solution is not sensitive.)
***
Whether you want to use Jolt to scale blockchains with GPU provers, or to achieve privacy with proofs generated on a phone, Jolt now handles both — with no trusted setup and no recursion.
Huge thanks to the authors of Nova, HyperNova, and Vega for identifying such a clean and efficient technique for adding zero-knowledge to Jolt.
To learn more about Jolt, you can check out more here.
***
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.
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.
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.
