Paper 2024/387

Ceno: Non-uniform, Segment and Parallel Zero-knowledge Virtual Machine

Tianyi Liu, University of Illinois Urbana-Champaign
Zhenfei Zhang, Scroll Foundation
Yuncong Zhang, Shanghai Jiao Tong University
Wenqing Hu, Missouri University of Science and Technology
Ye Zhang, Scroll Foundation
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 program execution proof 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 happen at two levels: opcode and basic block. Both designs try to minimize 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 for accommodating diverse 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zero-knowledge proofsGKR protocolzero-knowledge virtual machine
Contact author(s)
tianyi liu 08 @ gmail com
zhenfei @ scroll io
shjdzhangyuncong @ sjtu edu cn
huwen @ mst edu
ye @ scroll io
History
2024-04-28: last of 4 revisions
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 = {Tianyi Liu and Zhenfei Zhang and Yuncong Zhang and Wenqing Hu and Ye Zhang},
      title = {Ceno: Non-uniform, Segment and Parallel Zero-knowledge Virtual Machine},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/387},
      year = {2024},
      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.