SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge

Abstract:

Theoretical results in cryptography provide various techniques for outsourcing computation with strong integrity and confidentiality guarantees. Yet, these techniques continue to suffer from high overheads in the general case.

In this work, we significantly reduce the aforementioned costs via a combination of new theoretical and engineering techniques. Concretely, we present a new system for proving the correctness of high-level program executions. Proofs in our system are non-interactive, short (less than 300 bytes), and can be verified publicly in milliseconds. Moreover, our proofs are zero-knowledge proofs of knowledge.

Our work raises additional intriguing mathematical questions, whose solutions could push outsourced computation even further.

Joint work with Eli Ben-Sasson, Daniel Genkin, Eran Tromer, and Madars Virza.