Paper 2024/387

Parallel Zero-knowledge Virtual Machine

Wenqing Hu, Missouri University of Science and Technology
Tianyi Liu, University of Illinois Urbana-Champaign
Ye Zhang, Scroll Foundation
Yuncong Zhang, Shanghai Jiao Tong University
Zhenfei Zhang, Scroll Foundation
Abstract

Zero-knowledge virtual machine (zkVM) is a novel applica- tion of succinct and non-interactive zero-knowledge proof protocols that allows for verifiable computation over arbitrary codes. In this paper, we present a new paradigm to build such a zkVM via data parallel circuits. Our parallelization happens at the opcode and the basic block level. Such a design allows us to eliminate almost all of the circuit overhead for opcodes, including the control flow and the data flow which can be substantial in a zero-knowledge circuit. The size of our circuit is dynamic and optimal in the sense that it only costs the sum of all individual op- codes that are executed in the program, (i.e., you only pay as much as you use); while in all previous designs, the circuit is of a constant size, de- termined by the product of a) the upper limit of the number of opcodes, and b) the size of a super opcode circuit that is capable of handling every type of opcode. Further, we present an asymmetric GKR prover that is tailored to the data parallelism in our zkVM design, accompanied by various optimized constraint gadgets. The use of GKR prover also leads to significant re- ductions in the number of witnesses that are to be committed: GKR allows us to commit only the input and output of the circuits, whereas in previous Plonkish-based solutions, the prover needs to commit to all the witnesses

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zero-knowledge proofsGKR protocolzero-knowledge virtual machine
Contact author(s)
huwen @ mst edu
tianyi28 @ illinois edu
ye @ scroll io
shjdzhangyuncong @ sjtu edu cn
zhenfei @ scroll io
History
2024-03-04: approved
2024-03-02: received
See all versions
Short URL
https://ia.cr/2024/387
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/387,
      author = {Wenqing Hu and Tianyi Liu and Ye Zhang and Yuncong Zhang and Zhenfei Zhang},
      title = {Parallel Zero-knowledge Virtual Machine},
      howpublished = {Cryptology ePrint Archive, Paper 2024/387},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/387}},
      url = {https://eprint.iacr.org/2024/387}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.