Paper 2024/456

Tight ZK CPU: Batched ZK Branching with Cost Proportional to Evaluated Instruction

Yibin Yang, Georgia Institute of Technology
David Heath, University of Illinois Urbana-Champaign
Carmit Hazay, Bar-Ilan University
Vladimir Kolesnikov, Georgia Institute of Technology
Muthuramakrishnan Venkitasubramaniam, Ligero Inc.

We explore Zero-Knowledge proofs (ZKP) of statements expressed as programs written in high-level languages, e.g., C or assembly. At the core of executing such programs in ZK is the repeated evaluation of a CPU step, achieved by branching over the CPU’s instruction set. This approach is general and covers traversal-execution of a program’s control flow graph (CFG): here CPU instructions are straight-line program fragments (of various sizes) associated with the CFG nodes. This highlights the usefulness of ZK CPUs with a large number of instructions of varying sizes. We formalize and design an efficient tight ZK CPU, where the cost (both computation and communication, for each party) of each step depends only on the instruction taken. This qualitatively improves over state-of-the-art, where cost scales with the size of the largest CPU instruction (largest CFG node). Our technique is formalized in the standard commit-and-prove paradigm, so our results are compatible with a variety of (interactive and non-interactive) general-purpose ZK. We implemented an interactive tight arithmetic (over $\mathbb{F}_{2^{61}-1}$) ZK CPU based on Vector Oblivious Linear Evaluation (VOLE) and compared it to the state-of-the-art non-tight VOLE-based ZK CPU Batchman (Yang et al. CCS’23). In our experiments, under the same hardware configuration, we achieve comparable performance when instructions are of the same size and a $5$-$18×$ improvement when instructions are of varied size. Our VOLE-based ZK CPU can execute $100$K (resp. $450$K) multiplication gates per second in a WAN-like (resp. LAN-like) setting. It requires ≤ $102$ Bytes per multiplication gate. Our basic building block, ZK Unbalanced Read-Only Memory (ZK UROM), may be of an independent interest.

Available format(s)
Cryptographic protocols
Publication info
Zero KnowledgeZK for DisjunctionsEmulating CPU in ZK
Contact author(s)
yyang811 @ gatech edu
daheath @ illinois edu
Carmit Hazay @ biu ac il
kolesnikov @ gatech edu
muthu @ ligero-inc com
2024-03-22: approved
2024-03-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yibin Yang and David Heath and Carmit Hazay and Vladimir Kolesnikov and Muthuramakrishnan Venkitasubramaniam},
      title = {Tight ZK CPU: Batched ZK Branching with Cost Proportional to Evaluated Instruction},
      howpublished = {Cryptology ePrint Archive, Paper 2024/456},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.