Title: Efficient Zero-Knowledge Proofs for High-Level Programs: How to Build ZK CPUs

Date: Thursday, May 2nd, 2024 

Time: 11:00 am - 12:30 pm EST 

Location: Coda C0915 Atlantic

Zoom: https://gatech.zoom.us/j/99220911209 

Yibin Yang

Computer Science PhD Student

School of Cybersecurity and Privacy                                         

Georgia Institute of Technology

Committee: 

Dr. Vladimir Kolesnikov (advisor) – School of Cybersecurity and Privacy, Georgia Institute of Technology, USA

Dr. Alexandra Boldyreva – School of Cybersecurity and Privacy, Georgia Institute of Technology, USA

Dr. Carmit Hazay – Faculty of Engineering, Bar-Ilan University, Israel

Dr. Joseph Jaeger – School of Cybersecurity and Privacy, Georgia Institute of Technology, USA

Dr. Taesoo Kim – School of Cybersecurity and Privacy, Georgia Institute of Technology, USA

Abstract:

Zero-Knowledge (ZK) Proofs (ZKPs) allow a prover P to convince a verifier V that a given statement is true without revealing anything beyond this fact. Proposed by Goldwasser, Micali, and Rackoff in 1985, ZK has now become one of the most active areas in cryptography. This is mainly because ZKPs naturally enable fruitful privacy-preserving applications, including cryptographic signature schemes, private blockchain, private programming analysis, privacy-preserving ML and many more.

Existing ZKP schemes usually express their statements as circuits or constraint systems. This is sufficient for theoretical exploration, since any NP statement can be expressed as a circuit with polynomial overhead.  However, it does not efficiently capture modern programs, which are developed, e.g., using high-level programming languages such as C/C++/Assembly. 

There are two basic sources of inefficiency in representing high-level ZK programs as circuits (or constraint systems): (1) ZK branching – a circuit is always evaluated in its entirety, while programs crucially rely on paying only for the execution path, and (2) ZK RAM – a high-level program can access (read or write) a large main memory, i.e., via an LOAD/STORE instruction, while circuits must scan entire memory for each access.

In this proposal, I will begin by explaining the undesirable overhead caused by these technical challenges, and discussing the difficulties to resolve them. Next, I will provide a walkthrough of my relevant completed research projects (published on 1x IEEE S&P, 1x IEEE EuroS&P, 2x ACM CCS, 1x USENIX Security, and 1 under submission). Each project focuses on improving either ZK branching or ZK RAM, or both, ultimately enabling efficient ZKPs over high-level programs. Our most advanced ZKP scheme, Tight ZK CPU (under submission), incurs only a “tight” constant-factor blowup compared to non-cryptographic execution. The proposal will conclude with a presentation and discussion of the additional problems in this field, which are expected to be resolved by the time of my thesis defense.