Sanjam Garg

zkSNARKs are cryptographic primitives that allow a prover to generate a small certificate of the correctness of a potentially very expensive computation. Furthermore, these certificates are cheap to verify and hide secrets the prover may have used in performing the computation. Realizing efficiency zkSNARKs have been a topic of extensive research in recent years, but despite recent advances, the generation of zkSNARKs remains thousands of times slower than checking the relation directly for typical applications, with large memory usage — effectively limiting their broader deployment. This proposal aims to take on this challenge.

Optimizing zkSNARKs: Unlocking Potential for Low-Cost, Confidential Computation Verification

By: Niki Borghei

November 15, 2023

zkSNARKs, as cryptographic tools, enable the production of a concise certificate confirming the accuracy of a possibly resource-intensive computation. These certificates are cost-effective to authenticate and shield any confidential information used during the computation. Enhancing the efficiency of zkSNARKs has been the focal point of significant research efforts lately. Yet, despite progress, creating zkSNARKs still lags significantly behind directly verifying the relationship in typical scenarios, leading to substantial memory usage. Consequently, this hinders their widespread implementation. Dr. Sanjam Garg, Associate Professor of Computer Science at UC Berkeley, aims to change this.

Q: What is the problem you are trying to solve with your Bakar project?

A: Modern computing systems involve outsourcing computation on copious amounts of personal data to untrusted third-party machines. How does one guarantee the integrity of these computations? Our Bakar project will build practical cryptographic methods for offering privacy and integrity in such applications.

Q: How would you describe the science behind your solution to someone who is not a scientist?

A: The cryptographic primitive of succinct arguments allow a prover to generate a small certificate of the correctness of a potentially very expensive computation. Furthermore, these certificates are cheap to verify and hide secrets the prover may have used in performing the computation. This powerful primitive allows a user with a cellphone to verify the computation performed by a swarm of supercomputers.

Q: What led to your interest in this area of research?

A: Cryptographers have worked on zero-knowledge proofs for decades. Significant interest from industry over the last five years has led to major improvements and practical constructions. It is very exciting to see deep mathematical techniques making a difference in the context of real world applications.

Q: What led to your interest in entrepreneurship?

A: It is an amazing time where sophisticated cryptography is impacting the lives of billions for people, e.g. with messaging apps like Signal and cryptocurrencies. With my entrepreneurial efforts, I am hoping to contribute to this effort.

Q: How will you apply your Bakar Spark fund to this effort?

A: The Bakar Spark fund will support students and postdoctoral researchers in my group working on making succinct arguments faster.

Q: When do you expect to see the initial application of your project?

A: As a first application, we are currently working on bringing trust in machine learning applications. In particular, our succinct arguments will allow a model owner to prove that their trained models are fair, preserve privacy of training data, and so on.