A 2.1 KHz Zero-Knowledge Processor with BubbleRAM

David Heath, Vladimir Kolesnikov

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. Critically, 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 $2log n$ OTs per access, and (3) an efficient read-write memory, øurram, which uses $\frac1 2 log^2 n$ OTs per access. øurram 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 $512$KB of main memory, each processor cycle costs $24$KB of communication. We implemented our approach in \textttC++. On a 1Gbps LAN our implementation realizes a $2.1$KHz processor.

Original languageEnglish (US)
Title of host publicationCCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Number of pages20
ISBN (Electronic)9781450370899
StatePublished - Oct 30 2020
Externally publishedYes
Event27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020 - Virtual, Online, United States
Duration: Nov 9 2020Nov 13 2020

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Conference27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020
Country/TerritoryUnited States
CityVirtual, Online


  • garbling scheme
  • verifiable garbled circuits
  • zero knowledge

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'A 2.1 KHz Zero-Knowledge Processor with BubbleRAM'. Together they form a unique fingerprint.

Cite this