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

Abstract

This talk introduces our work that is published in Asiacrypt 2023. This work is about zero-knowledge virtual machines (ZKVM). ZKVM has become increasingly popular recently because of its potential applications in various areas, particularly its ability to enhance the privacy and scalability of blockchain systems. In this work, we focus on an influential and expensive component of ZKVMs---memory consistency checks (MCC). We formalize the state-of-the-art constructions of MCC in the PIOP model and prove their security. Observing that the bottleneck of existing designs, we propose a novel memory consistency check, dubbed Permem. Compared to the existing MCC protocols, Permem not only has improved efficiency, but also supports the memory address space as large as the entire finite field, significantly boosting the memory sizes of ZKVMs.

Read the full paper.

Authors

Yuncong Zhang, ShiFeng Sun, Ren Zhang, Dawu Gu

Published in

Asiacrypt 2023

Tags

Proof System, SNARK, ZKVM, Random Access Memory

---

More papers from the authors:

• VOProof: Efficient zkSNARKs from Vector Oracle Compilers

• NC-Max: Breaking the Security-Performance Tradeoff in Nakamoto Consensus

• When is Slower Block Propagation More Profitable for Large Miners?

• Lay Down the Common Metrics: Evaluating Proof-of-Work Consensus Protocols' Security

• Authenticated and Auditable Data Sharing via Smart Contract

• Analysing and Improving Shard Allocation Protocols for Sharded Blockchains