Written by Rahul Dalal and Tamir Hemo.
We built VEIL, a compiler that adds zero-knowledge to hash-based proof systems with only ~3% overhead. This removes another dependency on elliptic curve cryptography, putting proof systems like SP1 on the path to full post-quantum security.
We're sharing how it works below.
What is VEIL
Modern proof systems like SP1 are designed for succinctness. Verifiers can quickly check complex computations against a short proof. This is valuable in settings where verification speed is critical, such as blockchains that require fast finality. But these systems are not natively zero-knowledge (ZK) and offer no privacy guarantees, ruling out use cases dealing with sensitive data, like content authenticity, private access control, or responsible vulnerability disclosure.
VEIL (Verifiable Encapsulation of Interactive proofs with Low overhead) is a compiler that adds zero-knowledge to hash-based proof systems. The resulting protocol reveals nothing about the witness while preserving soundness and succinctness.
We designed VEIL with these three properties in mind:
- Non-intrusive. VEIL adds zero-knowledge as a layer over the base protocol. It does not require designing and auditing custom cryptography for each conversion.
- Lightweight. Adding zero-knowledge comes at minimal cost: a 3% increase in prover time, a 22% increase in verifier time, and a 12% increase in proof size.
- Post-quantum. VEIL is entirely hash-based, so the resulting protocol is plausibly post-quantum as long as the base protocol is.
How VEIL Works
There are two established ways to add zero-knowledge to a succinct proof system. Both have significant constraints that have made adding zero-knowledge to production proof systems painful in practice.
- Wrap the whole thing in an outer ZK proof that the verifier would have accepted. This method is expensive and high-latency, as the outer system has to prove cryptographic hashing through an arithmetic circuit.
- Rewrite every piece of the proof system to be ZK from the ground up. This method is deeply intrusive and difficult to maintain. Every piece of the codebase becomes coupled to ZK logic, increasing the surface area for potential protocol mistakes.
VEIL takes a third path.
Hash-based multilinear proof systems share a structural pattern. The prover commits to the trace, then engages with the verifier in a purely algebraic interaction and reduces to multilinear evaluation claims checked against the original commitment.
The hashing only shows up in the commitment and the evaluation claim opening. Everything in between is field arithmetic. VEIL decouples them: it protects the hash-touching parts with cheap, targeted blinding and wraps the small algebraic interaction with a ZK system. The inner ZK proof never has to prove hashes.
The result is a wrapper approach in which the inner ZK system runs on a small algebraic statement instead of the full base verifier, adding only 3% in additional prover time.
A Post Quantum SP1
SP1 today depends on a Groth16 wrapper for zero-knowledge, inheriting Groth16's reliance on elliptic-curve cryptography, which is not post-quantum. As quantum timelines compress, removing elliptic-curve dependencies from production proof systems becomes a practical concern.
Once integrated into SP1, VEIL will replace the Groth16 wrapper with a hash-based one. Because hash-based cryptography is plausibly post-quantum, the resulting protocol inherits the post-quantum security of the base proof system rather than being bottlenecked by the security of the wrapper. SP1's path to full post-quantum security has other components beyond zero-knowledge, but VEIL closes the gap on the privacy side.
Conclusion
VEIL gives us a path to add zero-knowledge to hash-based proof systems without rebuilding them and without paying the cost of proving hashes in circuits.
The full technical details are in the VEIL paper. A prototype implementation, with examples of protocols converted to the VEIL format, is available in the SP1 repository.