Paper 2022/809

A 2.1 KHz Zero-Knowledge Processor with BubbleRAM

David Heath, Georgia Institute of Technology
Vladimir Kolesnikov, Georgia Institute of Technology

Zero-Knowledge (ZK) proofs (ZKP) are foundational in cryptography. Most recent ZK research focuses on non-interactive proofs (NIZK) of small statements, useful in blockchain scenarios. Another line, and our focus, instead targets proofs of large statements that are useful, e.g., in proving properties of programs in ZK. We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set and proves in ZK the correctness of the execution. Such an approach is well-suited for constructing ZK proofs of large statements as it efficiently supports complex programming constructs, such as loops and RAM access. We propose several novel ZK improvements that make our approach concretely efficient: (1) an efficient arithmetic representation with conversions to/from Boolean, (2) an efficient read-only memory that uses $2 \log n$ OTs per access, and (3) an efficient read-write memory, BubbleRAM, which uses $1/2 \log^2 n$ OTs per access. BubbleRAM beats linear scan for RAM of size > 3 elements! Prior ZK systems used generic ORAM costing orders of magnitude more. We cast our system as a garbling scheme that can be plugged into the ZK protocol of [Jawurek et al, CCS’13]. Put together, our system is concretely efficient: for a processor instantiated with 512KB of main memory, each processor cycle costs 24KB of communication. We implemented our approach in C++. On a 1Gbps LAN, our implementation realizes a 2.1KHz processor.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. CCS 2020
Zero Knowledge Garbled Circuits
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
2022-06-23: approved
2022-06-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Heath and Vladimir Kolesnikov},
      title = {A 2.1 KHz Zero-Knowledge Processor with BubbleRAM},
      howpublished = {Cryptology ePrint Archive, Paper 2022/809},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.