Abstract
In this paper, we explore a novel Zero-knowledge Virtual Machine (zkVM) framework leveraging succinct, non-interactive zero-knowledge proofs for verifiable computation over any code. Our approach divides the proof of program execution into two stages. In the first stage, the process breaks down program execution into segments, identifying and grouping identical sections. These segments are then proved through data-parallel circuits that allow for varying amounts of duplication. In the subsequent stage, the verifier examines these segment proofs, reconstructing the program's control and data flow based on the segments' duplication number and the original program. The second stage can be further attested by a uniform recursive proof. We propose two specific designs of this concept, where segmentation and parallelization occur at two levels: opcode and basic block. Both designs try to minimize the control flow that affects the circuit size and support dynamic copy numbers, ensuring that computational costs directly correlate with the actual code executed (i.e., you only pay as much as you use). In our second design, in particular, by proposing an innovative data-flow reconstruction technique in the second stage, we can drastically cut down on the stack operations even compared to the original program execution. Note that the two designs are complementary rather than mutually exclusive. Integrating both approaches in the same zkVM could unlock more significant potential to accommodate various program patterns. We present an asymmetric GKR scheme to implement our designs, pairing a non-uniform prover and a uniform verifier to generate proofs for dynamic-length data-parallel circuits. The use of a GKR prover also significantly reduces the size of the commitment. GKR allows us to commit only the circuit's input and output, whereas in Plonkish-based solutions, the prover needs to commit to all the witnesses.
Recommended Citation
T. Liu et al., "Ceno: Non-uniform, Segment and Parallel Zero-Knowledge Virtual Machine," Journal of Cryptology, vol. 38, no. 2, article no. 17, Springer, Jun 2025.
The definitive version is available at https://doi.org/10.1007/s00145-024-09533-2
Department(s)
Mathematics and Statistics
Keywords and Phrases
GKR Protocol; SNARK; Stack-base Virtual Machine; Zero-knowledge Virtual Machine
International Standard Serial Number (ISSN)
1432-1378; 0933-2790
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2025 Springer, All rights reserved.
Publication Date
01 Jun 2025
Comments
Shanghai Jiao Tong University, Grant 711999