Understanding Zero-Knowledge Proofs: Part 1— Verifiable Computation with zk-SNARKs
In my view, one of the most consequential developments in cryptography as well as distributed computing in the past decade has been the development of practical schemes for zero-knowledge proofs that enable privacy-sensitive verifiable computation. I’m writing a series of articles about it, primarily to deepen my own understanding of this somewhat complex topic, and hoping that in the process that my summaries and the included links and pointers may be helpful to others as well.
Verifiable Computation (VC): Say you are sending some data to be computed at a remote location such as a cloud server, and it sends back results. How do you know that the results are from correctly executed computations? You could, of course, rerun the computation yourself to be sure, but that would be redundant. Is there another way? Turns out there is indeed a cryptographic approach, which works as follows.
Verifiable Computation using Cryptographic Proof and Verification: The scheme involves a prover and a verifier, and typically consists of three main steps or processes:
- Key Generation: this process takes the function to be computed, and generates an evaluation and a verification key
- Computation with Proof: this process performed at a prover node performs the desired computation F(u) on a given input u, and uses the evaluation key to generate a proof of correct computation.
- Verification: a Verifier then uses the proof from the prover, along with the verification key from the generation step, to verify that the computation was indeed done correctly.
Certain properties should hold for a verifiable computation scheme to be useful: correctness or completeness implies that assuming the keys were validly generated and the proof was correctly generated, the verifier will always accept the proof; security or soundness implies that no adversary can generate a proof that will be accepted if the correct computation is not performed; and efficiency requires that verification should be faster than doing the original computation (otherwise we didn’t need this elaborate scheme!).
Zero-Knowledge VC: There is an additional step that makes verifiable computation more powerful for use-cases that require confidentiality or privacy. Consider doing a computation that depends on two sets of inputs, say F(u,v), where u is information that is publicly known, and v is information that is private (known to the prover only). In this case, if the above steps are performed in such a way that v is known only to the prover that does the computation, and not to the verifier, it is said to be a zero-knowledge verifiable computation scheme.
zk-SNARK: Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) are a cryptographic implementation of the zero-knowledge verifiable computation principles described above. The key properties of zk-SNARKs are succinctness, meaning the proofs are short; non-interactivity, meaning the proof can be verified with a single message from the prover to the verifier; and zero-knowledge, ensuring no information about the private input is revealed during proof generation. By employing zk-SNARKs, one can achieve verifiable and trustworthy computations while preserving the privacy of sensitive information.
Many zk-SNARK schemes, or as they are more generally referred to — non-interactive zero knowledge (NIZK) proof schemes — have been developed, including Pinnochio (2013), Groth16 (2016), Sonic (2019), Marlin (2019), PLONK (2019), STARK (2019), Aurora (2019), Halo (2019). And from a practical perspective, a number of software libraries and tools such as CIRCOM, Arkworks, and ZoKrates, have been developed to simplify implementations of applications using them.
Applications: zk-SNARKs and zero-knowledge verifiable computation has a wide range of potential applications. These include building privacy-sensitive blockchain protocols (two prominent examples are ZCash and Mina) and enabling layer-2 scaling of computation on blockchains via zk-Rollups. But the applications go well beyond blockchains, for example to enabling verifiable machine learning model inference without having to release the weights to the user.
About this series: This article is intended to provide a gentle but broad overview of what zero-knowledge verifiable computation means and to point out that zk-SNARKs offer a practical way to achieve that. We see that this is an area that has been rapidly developing over the past few years, with many schemes being developed around 2019. In future articles of this series, I plan to get into some details of how zk-SNARKs work. We will begin with some basic math needed for cryptography, then look at elliptic curve cryptography in particular, followed by articles addressing key topics such as polynomial commitments, arithmetization schemes for computation such as R1CS and QAP, trusted setups and transparent alternatives, reviewing the different approaches, as well as some of the software libraries and tools available for developers today.
Next Article: Next, we will review some basic math needed for cryptography.
Further Reading
There are tons of articles and papers now that provide an introduction to zero-knowledge proofs and zk-SNARKs at different levels of abstraction. Below are several that I found useful.
- zkSNARKs in a Nutshell by Christian Reitwießner
- Why and how zk-SNARK works by Maksym Petkus
- zk-SNARKs: a gentle introduction by Anca Nitulescu
- zk-SNARKs under the hood by Vitalik Buterin
- An approximate introduction to how zk-SNARKs are possible by Vitalik Buterin
- Zero-Knowledge Proofs: A Technology Primer by Monoceros Ventures
- A review of zk-SNARKs by Thomas Chen et al.
- The missing explanation of zk-SNARKs by David Wong
- An introduction to the use of zk-SNARKs in blockchain by Alexandre Miranda Pinto
- Zero-Knowledge Proofs and its Application in Machine Learning by Yupeng Zhang
- https://zkp.science/ — a collection of pointers and resources
- A curated list: awesome ZKPs