Paper 2023/1115

Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM

Yibin Yang, Georgia Institute of Technology
David Heath, University of Illinois Urbana-Champaign

We optimize Zero Knowledge (ZK) proofs of statements expressed as RAM programs over arithmetic values. Our arithmetic-circuit-based read/write memory uses only 4 input gates and 6 multiplication gates per memory access. This is an almost 3× total gate improvement over prior state of the art (Delpech de Saint Guilhem et al., SCN’22). We implemented our memory in the context of ZK proofs based on vector oblivious linear evaluation (VOLE), and we further optimize based on techniques available in the VOLE setting. Our experiments show that (1) our total runtime improves over that of the prior best VOLE-ZK RAM (Franzese et al., CCS’21) by 2-20× and (2) on a typical hardware setup, we can achieve ≈ 600K RAM accesses per second. We also develop improved read-only memory and set ZK data structures. These are used internally in our read/write memory and improve over prior work.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security 2024
Zero KnowledgeZK RAM
Contact author(s)
yyang811 @ gatech edu
daheath @ illinois edu
2023-11-03: revised
2023-07-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yibin Yang and David Heath},
      title = {Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1115},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.