Paper 2022/810

Zero Knowledge for Everything and Everyone: Fast ZK Processor with Cached RAM for ANSI C Programs

David Heath, Georgia Institute of Technology
Yibin Yang, Georgia Institute of Technology
David Devecsery, Facebook (United States)
Vladimir Kolesnikov, Georgia Institute of Technology

We build a complete and efficient ZK toolchain that handles proof statements encoded as arbitrary ANSI C programs. Zero-Knowledge (ZK) proofs are foundational in cryptography. Recent ZK research has focused intensely on non-interactive proofs of small statements, useful in blockchain scenarios. We instead target large statements that are useful, e.g., in proving properties of programs. Recent work (Heath and Kolesnikov, CCS 2020 [HK20a]) designed a proof-of-concept ZK machine (ZKM). Their machine executes arbitrary programs over a minimal instruction set, authenticating in ZK the program execution. In this work, we significantly extend this research thrust, both in terms of efficiency and generality. Our contributions include: • A rich and performance-oriented architecture for representing arbitrary ZK proofs as programs. • A complete compiler toolchain providing full support for ANSI C95 programs. We ran off-the-shelf buggy versions of sed and gzip, proving in ZK that each program has a bug. To our knowledge, this is the first ZK system capable of executing standard Linux programs. • Improved ZK RAM. [HK20a] introduced an efficient ZK-specific RAM BubbleRAM that consumes $O(\log^2 n)$ communication per access. We extend BubbleRAM with multi-level caching, decreasing communication to $O(\log n)$ per access. This introduces the possibility of a cache miss, which we handle cheaply. Our experiments show that cache misses are rare; in isolation, i.e., ignoring other processor costs, BubbleCache improves communication over BubbleRAM by more than $8\times$. Using BubbleCache improves our processor’s total communication (including costs of cache misses) by $\approx 25-30$%. • Numerous low-level optimizations, resulting in a CPU that is both more expressive and $\approx 5.5\times$ faster than [HK20a]’s. • Attention to user experience. Our engineer-facing ZK instrumentation and extensions are minimal and easy to use. Put together, our system is efficient and general, and can run many standard Linux programs. The resultant machine runs at up to 11KHz on a 1Gbps LAN and supports MBs of RAM.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 2021 IEEE Symposium on Security and Privacy (SP)
Zero Knowledge Systems Architecture
Contact author(s)
heath davidanthony @ gatech edu
yyang811 @ gatech edu
ddevec @ fb com
kolesnikov @ gatech edu
2022-06-23: approved
2022-06-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Heath and Yibin Yang and David Devecsery and Vladimir Kolesnikov},
      title = {Zero Knowledge for Everything and Everyone: Fast ZK Processor with Cached RAM for ANSI C Programs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/810},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.