From Zero to Hero in Zero Knowledge Proofs [Part 8]
This is the eighth part of the series that takes you from absolute ground zero in ZKPs to a fairly advanced level. We will start from the absolute basics and then move onward and upward. Subscribe to get regular updates!
In the previous post, we talked about the building blocks of zk-SNARKs and the Generator G algorithm that produces some public keys. We talked about how the steps taken in the Generator G algorithm are also referred to as the Trusted Setup. Let’s dive into those details now.
Trusted setup ceremony
A trusted setup ceremony is a procedure that is done once to generate a piece of data that must then be used every time some cryptographic protocol is run.
zk-SNARK requires a one-off trusted setup ceremony to produce proving and verification keys. These keys are kept public so that they can be used by various parties to generate and verify proofs.
For each new program C, a new trusted setup ceremony must be done since it is dependent on the program C. Recap from the previous lesson, Generator G takes a secret lambda and the program C as the input to create the pk and the vk.
(pk,vk)=G(lambda,C)
Therefore, the trusted setup is not generic and needs to be done individually for each new program.
Toxic waste
A secret parameter called lambda is required for the trusted setup. This parameter is called Toxic Waste and sometimes makes it tricky to use zk-SNARK in real-world applications.
The reason for this is that anyone who knows this parameter can generate fake proofs. Specifically, given any program C and public input x, a person who knows lambda can generate a fakeProof such that:
V(vk,x,fakeProof)=true
evaluates to true without knowledge of the secret witness w.
Therefore, it is imperative that the knowledge of lambda needs to be erased as soon as the proving and verification keys are generated, otherwise, the system can be cheated and therefore cannot be trusted.
Bringing trust to the trusted setup
The obvious way to construct SNARK public parameters is just to have someone generate a public/private keypair, similar to an ECDSA keypair, and then destroy the private key. However, how do you trust this one party that they have actually destroyed the private secret material?
To cater to this, multi-party computation is used.
Multi-Party Computation is a cryptographic protocol that distributes a computation across multiple parties where each party uses a secret to perform the computation and no individual party can see the other parties secret data.
For a trusted setup ceremony, n parties participate in a ceremony to generate the required cryptographic material i.e. the pk and the vk. Each of the parties brings their own secret data to the ceremony.
The expectation from each party is that after the ceremony, they need to get rid of their secret. The trust assumption is that even if one of the n parties is honest, the resulting output will be secure.
N parties bring together their secret lambdas to the ceremony to generate proving and verification keys
For the trusted setup ceremony to fail, all N parties need to be malicious and make their secret public. However, even if one of the parties decides to destroy their secret, overall the trusted setup would be successful and the generation of fake proofs would not be possible.
That was all for today. In the next blog posts, we will go through an example zk-SNARK program and how the SNARK proofs are generated.
Hey there, thanks for reading this far. If you liked this article, don’t forget to follow and leave a clap.
I am building Plurality Network, the user context layer on web3. Join our discord to get alpha!
Follow me here, on LinkedIn, on X, or on Farcaster to get the latest blockchain technical content in simple, bite-sized reads.
