Zero knowledge for everything and everyone: Fast ZK processor with cached ORAM for ANSI C programs

David Heath, Yibin Yang, David Devecsery, Vladimir Kolesnikov

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

Abstract

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 an efficient 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 the Linux programs 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 oblivious RAM (ORAM). [HK20a] introduced an efficient ZK-specific ORAM BubbleRAM that consumes O(log2 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×. Using BubbleCache improves our processor's total communication (including costs of cache misses) by ≈ 25-30%.• Numerous low-level optimizations, resulting in a CPU that is both more expressive and ≈ 5.5× 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2021 IEEE Symposium on Security and Privacy, SP 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1538-1556
Number of pages19
ISBN (Electronic)9781728189345
DOIs
StatePublished - May 2021
Externally publishedYes
Event42nd IEEE Symposium on Security and Privacy, SP 2021 - Virtual, San Francisco, United States
Duration: May 24 2021May 27 2021

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
Volume2021-May
ISSN (Print)1081-6011

Conference

Conference42nd IEEE Symposium on Security and Privacy, SP 2021
Country/TerritoryUnited States
CityVirtual, San Francisco
Period5/24/215/27/21

Keywords

  • Systems Architecture
  • Zero Knowledge

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Zero knowledge for everything and everyone: Fast ZK processor with cached ORAM for ANSI C programs'. Together they form a unique fingerprint.

Cite this