Paper 2022/1010

Orion: Zero Knowledge Proof with Linear Prover Time

Abstract

Zero-knowledge proof is a powerful cryptographic primitive that has found various applications in the real world. However, existing schemes with succinct proof size suffer from a high overhead on the proof generation time that is super-linear in the size of the statement represented as an arithmetic circuit, limiting their efficiency and scalability in practice. In this paper, we present Orion, a new zero-knowledge argument system that achieves $O(N)$ prover time of field operations and hash functions and $O(\log^2 N)$ proof size. Orion is concretely efficient and our implementation shows that the prover time is 3.09s and the proof size is 1.5MB for a circuit with $2^{20}$ multiplication gates. The prover time is the fastest among all existing succinct proof systems, and the proof size is an order of magnitude smaller than a recent scheme proposed in Golovnev et al. 2021. In particular, we develop two new techniques leading to the efficiency improvement. (1) We propose a new algorithm to test whether a random bipartite graph is a lossless expander graph or not based on the small set expansion problem. It allows us to sample lossless expanders with an overwhelming probability. The technique improves the efficiency and/or security of all existing zero-knowledge argument schemes with a linear prover time. (2) We develop an efficient proof composition scheme, code switching, to reduce the proof size from square root to polylogarithmic in the size of the computation. The scheme is built on the encoding circuit of a linear code and shows that the witness of a second zero-knowledge argument is the same as the message in the linear code. The proof composition only introduces a small overhead on the prover time.

Note: We fix three mistakes in the previous version of the paper. (1) There was a mistake in the proof of the expander testing algorithm based on the densets sub-graph algorithm. In particular, in Case 2 of Theorem 2 in the original version, the density $\frac{|E'|+c}{|V'|+1}>\frac{|E'|}{|V'|}$ only holds when $c>\frac{|E'|}{|V'|}$, or $|V'|>|E'|$, which was not the case for lossless expanders. In this version, we propose a different algorithm based on the small set expansion problem to identify lossles expander graphs with a negligible soundness error in Section 3. (2) While achieving zero-knowledge, we masked the protocol by a random message instead of a random vector of length $n$, which was not zero-knowledge. We provide a new protocol with proof of soundness and zero-knowledge using the techniques in [BCG+17] properly. (3) In the old Protocol 4, we used a SNARK as a building block, which was not sound. It needs to be replaced by a commit-and-prove SNARK. We thank Quang Dao, Xifan Yu, Weijie Wang, and Charalampos Papamanthou for pointing out the mistake in the densest subgraph algorithm, we thank Jonathan Bootle for pointing out the problem in the zero-knowledge variant, and Binyi Chen and Benedikt Bünz for pointing out the problem and giving a solution using CP-SNARK.