International Association
for Cryptologic Research

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