Paper 2023/1555

Polynomial IOPs for Memory Consistency Checks in Zero-Knowledge Virtual Machines

Yuncong Zhang, Shanghai Jiao Tong University
Shi-Feng Sun, Shanghai Jiao Tong University
Ren Zhang, Cryptape Co. Ltd, Nervos
Dawu Gu, Shanghai Jiao Tong University
Abstract

Zero-Knowledge Virtual Machines (ZKVMs) have gained traction in recent years due to their potential applications in a variety of areas, particularly blockchain ecosystems. Despite tremendous progress on ZKVMs in the industry, no formal definitions or security proofs have been established in the literature. Due to this lack of formalization, existing protocols exhibit significant discrepancies in terms of problem definitions and performance metrics, making it difficult to analyze and compare these advancements, or to trust the security of the increasingly complex ZKVM implementations. In this work, we focus on random-access memory, an influential and expensive component of ZKVMs. Specifically, we investigate the state-of-the-art protocols for validating the correct functioning of memory, which we refer to as the \emph{memory consistency checks}. Isolating these checks from the rest of the system allows us to formalize their definition and security notion. Furthermore, we summarize the state-of-the-art constructions using the Polynomial IOP model and formally prove their security. Observing that the bottleneck of existing designs lies in sorting the entire memory trace, we break away from this paradigm and propose a novel memory consistency check, dubbed $\mathsf{Permem}$. $\mathsf{Permem}$ bypasses this bottleneck by introducing a technique called the address cycle method, which requires fewer building blocks and---after instantiating the building blocks with state-of-the-art constructions---fewer online polynomial oracles and evaluation queries. In addition, we propose $\mathsf{gcq}$, a new construction for the lookup argument---a key building block of the memory consistency check, which costs fewer online polynomial oracles than the state-of-the-art construction $\mathsf{cq}$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
Keywords
Proof SystemSNARKZKVMRandom Access Memory
Contact author(s)
shjdzhangyuncong @ sjtu edu cn
shifeng sun @ sjtu edu cn
ren @ nervos org
dwgu @ sjtu edu cn
History
2023-10-11: approved
2023-10-10: received
See all versions
Short URL
https://ia.cr/2023/1555
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1555,
      author = {Yuncong Zhang and Shi-Feng Sun and Ren Zhang and Dawu Gu},
      title = {Polynomial {IOPs} for Memory Consistency Checks in Zero-Knowledge Virtual Machines},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1555},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1555}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.