This speaker series is made possible by an anonymous charitable donation in memory of cypherpunks and privacy advocates Len Sassaman, Hugh Daniel, Hal Finney, and Caspar Bowden.
View the list of past and upcoming speakers
Zero-Knowledge Proofs Beyond Circuits and Constraints — How to Efficiently Build a “ZK CPU”
Yibin Yang, Georgia Institute of Technology
[Download (MP4)] [View on Youtube]
March 15, 2024 2:00pm, in DC 1302 and Zoom
Abstract
With recent advances in efficient Zero-Knowledge Proofs (ZKP) schemes, ZKP has become one of the most active areas in cryptography that enables fruitful real-world applications. However, generic ZK schemes usually express the statements as circuits or constraint systems. The complicated front-end compiling problem brings efficiency overhead and a technical barrier for a broad deployment of ZKP.
In this talk, I will focus on our recent progress in emulating “Central Processing Unit (CPU)” inside ZKP. The talk will be divided into two parts. In the first half of the talk, I will present our recent work (ACM CCS ’23, joint with David Heath, Carmit Hazay, Vladimir Kolesnikov and Muthuramakrishnan Venkitasubramaniam) on proving batched ZK disjunctive statements. Namely, the prover wishes to repeatedly prove to the verifier that she knows the inputs that can satisfy 1-out-of-B circuits. This models the execution of CPU steps. In the second half of the talk, I will present our other recent work (USENIX Security ’24, joint with David Heath) on enabling ACCESS gates in the circuit. Namely, the prover and the verifier want to access a large read-write memory. This models the RAM machinery. Together, these two works enable an efficient full-fledged “ZK CPU”.
Bio
Yibin Yang (He/Him/His) is a PhD candidate from Georgia Institute of Technology, USA, advised by Professor Vladimir Kolesnikov. Yibin's research is centered around cryptography, with a particular focus on Zero-Knowledge Proofs (ZKP) and Multi-Party Computation (MPC). Recently, he has been focusing on enabling generic ZK/MPC systems to support the RAM model of computation – namely, parties can perform ZKP/MPC while directly using high-level programming languages such as C/C++/assembly to express the computation task. He also heavily gets involved in the fair MPC, arithmetic garblings, and Blockchain layer-2 programmability.
