Tradeoff space, and other NIZKs (STARKs and Bulletproofs)

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

The Hunting of the SNARK

We've discussed zero-knowledge proofs from a high level, and SNARKs in particular for their additional properties of succinctness and non-interactivity. But SNARKs are just one type of Non-interactive Zero-Knowledge (NIZK) proof system, which happen to have succinct proofs.

Other types of NIZK's include Bulletproofs and STARKs, which we will cover shortly. In addition, there are many variants, or "constructions" of SNARKs that optimize for certain parameters over others. Hence, it is worthwhile to first discuss this tradeoff space that all NIZKs operate in. Then we can look at the different constructions using this framework.

There are 4 main parameters on which zero-knowledge proof systems optimize for:

1. prover time: the time it takes to compute or generate a proof

2. proof size: how big the proof is

3. verifier time: the time it takes to verify a proof

4. setup transparency: how the proof system is pre-processed

Let's dig in a bit deeper. The first three parameters make intuitive sense:

1. We want faster prover times — In order to be able to provide a proof about a computational result, we need to generate it ourselves, and then broadcast it across a network to verifying parties. Thus, it is naturally more advantageous that the time it takes to make this proof is as low as possible. This is because we're already running the underlying computation, and we don't want too much additional overhead when computing the proof.

   Goal: nearly linear prover time, relative to the computation

2. We want smaller proof sizes — It also makes sense that we want the proof size to be as small as possible, since a verifying party may want to store the proof for later reference.

   Goal: proofs in the order of hundreds of bytes

3. We want faster verifier times — And of course, we also want to minimize verifying time, since verifying parties are receiving the proof in lieu of running a computation themselves. Thus, it should be very quick for them to check the proof (much faster than running the computation itself).

   Goal: logarithmic verifier time, on the order of milliseconds

The last parameter, setup transparency, is a bit trickier to understand and will require a bit more context, so let's table it for now. Let's take a look first at how different proof systems make tradeoffs between these three parameters.

How different proof systems stack up

Earlier I mentioned other NIZKs including STARKs and Bulletproofs. These proof differ in several ways, including the fundamental cryptographic assumptions upon which they are built. But for the scope of this article, we will only look at the brass tacks — how performant they are in each of these categories.

(Image c/o Elena Nadolinski)

From the image above, we can get a quick sense of how the proof systems compare to one another. This is by no means a static image, as there is a flurry of research going on in ZKP land to improve all proof systems. But, it serves as a helpful image to gain some intuition about why the hype has focused on SNARKs over the others.

Immediately, we can see that STARKs have the best prover time, but pay the cost in terms of larger proof sizes. Bulletproofs are a bit better in terms of proof size, but unfortunately have linearly scaling verifier times.

SNARKs have the smallest proof sizes and great verification times, but prover times could be improved. Out of the three, SNARKs stack up the strongest, given these parameters. But there is one little catch about SNARKs — the little subtext about trusted setup.

This brings us back to the 4th parameter that we conveniently ignored in the previous section — the transparency of the setup process. All proof systems require a setup, but Bulletproofs and STARKs are transparent, which means that no trusted setup is required. SNARKs on the other hand, do need a trusted setup, which is often seen as a sort of kryptonite to their super powers.

There are a lot of articles already spreading FUD around trusted setup, so that won't be my goal here. What I'd rather like to impress upon you is why a trusted setup is needed in the first place, and how the downsides are being addressed.