David Heath - Zero Knowledge for Everything and Everyone

Zero-Knowledge (ZK) Proofs are important cryptographic objects that allow an untrusted prover to demonstrate to an untrusted verifier the truth of some statement while revealing nothing additional. ZK can potentially be used for complex applications, such as allowing a company to securely conduct an external audit of its records or allowing a code bounty hunter to prove the existence of a software bug without directly showing the vulnerability. Unfortunately, complex ZK applications are difficult to build in practice; existing ZK protocols require statements to be encoded as circuits, and it is difficult to express complex statements as simple circuits. To bring complex ZK applications to practice, developers need a more expressive design language.

Rather than providing a new design language, we provide an infrastructure that allows existing languages to run in ZK. In this talk, David will present a ‘ZK machine’, a low-level simulated processor that executes arbitrary assembly code in ZK. David will describe the machine, focusing on the inherent challenges and our corresponding solutions. We will explain how we can take off-the-shelf ANSI C programs, compile them to our custom assembly language, and efficiently run this assembly in a ZK protocol. Our system is practical and efficient; for example, it can prove the existence of a CVE-reported bug in gzip in 6.3 seconds.

The talk will be suitable even for those without cryptographic background. This research was done in collaboration with David’s advisor, Professor Vlad Kolesnikov, as well as Professor David Devecsery and his student Yibin Yang.