SNARK Circuits and Trusted Setup

By O(1) Labs, the team behind Coda Protocol

The trapdoor in SNARKs

Let's recap the last section — SNARKs are uniquely powerful due to their:

• small proof sizes

• fast verification times

The last property particularly matters because when you run an intensive computation once, you want many parties to be able to verify it quickly. Hence, SNARKs become very useful when there is a one-to-many relationship between prover and verifiers — perfect for blockchain networks.

But, how are SNARKs imbued with their super powers? The dirty secret is that by design, zk-SNARKs embed a trapdoor in the system, through a trusted setup. However, it's not as bad as it sounds. As I'll explain shortly, any risks have been mitigated through techniques in both the implementation layer as well as the theory.

This whole time, we have been discussing SNARKs from the vantage point of the generated proof, and its properties. In order to gain an intuition about the setup phase, let's see how the proof system is constructed from a high-level.

SNARK Circuits and Preprocessing

When we have a computation that we want to create proofs for, there are a series of steps taken to reduce it down to what is called a "SNARK circuit":

Image c/o https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

For the purposes of this article, I won't go into the details of how this process works. The details around NP reduction are quite involved, and require dedicated articles of their own. I recommend Vitalik's post that covers reduction down to QAPs as a starter. Furthermore, NIZK research is exploring other avenues of reducing a computation beyond circuit specifications, so I would expect this to rapidly improve.

Rather, what I want you take away is that after this transformation, there is a baked circuit of the computation you started out with. You can think of this like an electronic circuit that quickly generates proofs for a specific computation.

However, creating the circuit is not enough, as the prover and verifier need some way to non-interactively agree on how to test the circuit. In order to do this, we'll have to generate some public set of randomness that all parties can sample. There are two options available to us: the common reference string (CRS) model and the random oracle model (ROM). The CRS model assumes that there is some trusted party that can generate a random string for us, albeit with structure that hopefully nobody knows. The ROM on the other hand doesn't involve any trusted party and generally a hash function is used in practice to generate a random string.

SNARKs use structured CRS, which gives them one unique advantage — within the structured reference, some circuit specific knowledge is hidden. By embedding some of the data about the computation within the shared string, we can preprocess the SNARK circuit so that verification is very efficient. This is how SNARKs are able to get small proof sizes and quick verification times.

The downside though, is that generating a CRS requires a trusted setup. The byproduct of the trusted setup is some "toxic waste" that would allow any party that got hold of it to break the soundness assumptions of the SNARK circuit. What this means in practice is that a malicious prover could generate false proofs, and convince an honest verifier. This is the trapdoor inherent in the system that could be exploited if the trusted setup was compromised.

Trusted setups are improving

Trusted setup received its name because the simplest way to generate the CRS is to have one trusted party do it. That same party would then be completely responsible for destroying the toxic waste, in order for the system to remain secure. Yet, we all know the famous adage, "trust but verify". The trusted setup if performed by one party, is critically flawed and centralized.

Lucky for us there have been several improvements to mitigate this risk:

• Multi-party computations (MPCs) — A single party trusted setup is clearly flawed, but what about a trusted setup with 100 or 1000 parties? In an MPC trusted setup ceremony, many parties participate in generating the CRS, each with their own shard of the toxic waste byproduct. In order to generate false proofs, every single party would have to collude to piece together their toxic waste, with the guarantee that if even one had destroyed their waste, the system would be 100% safe.

  MPC trusted setups have been performed several times now, with Zcash pioneering state of the art ceremonies, including the Powers of Tau ceremony in which almost 100 groups participated. While there remains some risk in the implementation, it is greatly mitigated from early days.

• Updatable setups — While MPCs improve implementation level security, an even better solution would be to build a better theoretical trust model. With updatable reference strings, this became a reality.

  With earlier setups, once they had concluded, the CRS generated would be locked into place. Thus, if any party had the toxic waste, they could deceive verifiers forever. However, with updatable setups, any party that has doubts about a proving system can continue to update the shared string. This even applies after the proof system is live — any one honest party can update the string.

  In addition, this method also allows for universality, meaning that proofs aren't just locked into an application-specific circuit. By removing application-specific context from the shared string, we can generate proofs for any application within the max bounds of the SNARK circuit.

  The downside of this is that proof sizes are slightly larger and performance suffers from both prover and verifier time. There are not yet standardized benchmarks on various SNARK performance as the field is moving quickly, but I will update this when there are.

For now, the gold standard is using proven SNARK constructions (namely Groth16), and using a robust MPC to ensure that the trapdoor can never be exploited by one entity. Many other projects besides Zcash are continuing to advance the practice, and the safety of SNARK setup only continues to improve.