Paper 2019/1482

Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof

Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song

Abstract

We present a new succinct zero knowledge argument scheme for layered arithmetic circuits without trusted setup. The prover time is $O(C+n\log n)$ and the proof size is $O(D\log C+{\log }^{2}n)$ for a $D$-depth circuit with $n$ inputs and $C$ gates. The verification time is also succinct, $O(D\log C+{\log }^{2}n)$, if the circuit is structured. Our scheme only uses lightweight cryptographic primitives such as collision-resistant hash functions and is plausibly post-quantum secure. We implement a zero knowledge argument system, Virgo, based on our new scheme and compare its performance to existing schemes. Experiments show that it only takes 53 seconds to generate a proof for a circuit computing a Merkle tree with 256 leaves, at least an order of magnitude faster than all other succinct zero knowledge argument schemes. The verification time is 50ms, and the proof size is 253KB, both competitive to existing systems. Underlying Virgo is a new transparent zero knowledge verifiable polynomial delegation scheme with logarithmic proof size and verification time. The scheme is in the interactive oracle proof model and may be of independent interest.

Note: Update email