Why it is said that “zk-SNARKs need a trusted setup” to work?

Question

What is the meaning of a "trusted setup" in this context? It is often said all around that zk-STARKs and Bulletproofs does not require a trusted setup. How do zk-STARKs and Bulletproofs manage to avoid the need for a trusted setup?

Answer 1

Zero-knowledge protocols act (very roughly) in three steps.

1. Setup
2. Prove
3. Verify

(1) needs to be carried out once, and after this setup phase is complete, (2) and (3) can usually be repeated indefinitely, using the output of the setup.

The difference between those "trusted setup" and "untrusted setup" protocols lies in step 1. In this first setup step, the prover and verifier agree on some common "public" parameters, which they will need to carry out their computations. "Agreeing upon parameters" usually means that another party imposes this set of parameters.

Let's take a very concrete example, the Schnorr protocol (which is not zero-knowledge, but that doesn't really matter):

1. Setup: prover and verifier agree on a field $\mathbb{F}_p$ and group $\mathbb{G}_q$ that they want to use. They also agree on a common base $G\in \mathbb{G}_q$ for their computations.
2. Prove knowledge of $x$ s.t. $xG=Y$. Choose a random $k\in \mathbb{F}_q$, send $K=kG$ to verifier, receive challenge $e$, reply with $s=k-xe$.
3. Verify $sG+eY=K$

To see that the Schnorr protocol does not have a trusted setup: all of the public parameters are picked randomly, they have no "secret relation" between them. There is "no trust" necessary in the parameters.

---

@Mathdropout already explained that zkSNARKs do not necessarily require trusted setup. It's not in the definition ("succinct argument of knowledge" does not read "with trusted setup"), but the most established instances of a SNARK seem to have had this property until recently.

To see how Bulletproofs (which is not a SNARK) does not require trusted setup, you can look at its public parameters. They look a lot like the public parameters of the Schnorr protocol: they have a field $\mathbb{F}_p$, a group $\mathbb{G}_q$, and a few sets of group generators $G, H, G_1, \dots, G_n, H_1, \dots, H_n \in \mathbb{G}_q$. There's no need for the generators to have a relation with each other; they can be randomly generated. For example, Dalek Bulletproofs uses a Keccak sponge to generate an "infinite" amount of random base points.

Answer 2

Roughly answering! In a zero knowledge proof, prover (P) wants to prove to verifier (V) that she knows witness (w) for a statement (s) without disclosing any information (zero information) about the witness.

But the above protocol is not non-interactive (and succinct). To make the above protocol non-interactive, we need a pre-processing setup (a.k.a CRS model). In other words, there should be some common parameters between prover and verifier thus they can talk to each other with the protocol and also we should convert the statement from circuit to a protocol-friendly version for proving, and it is better that we have some pre-calculations to make calculations of the above protocol efficient. There are two type of setup: trusted setup and transparent (public) setup. In a trusted setup, we have a trapdoor that we should keep it secret and if attacker got it, she can prove false statements. Trusted setup should be run once by a trusted third party. In a transparent setup, there is not any secret. Examples of zk-SNARK frameworks with trusted setup are Pinocchio and Zcash's zk-SNARK and examples of zk-SNARKs with transparent setup are DARK (as @Mathdropout answered) and Spartan, etc.

Also we have some models in cryptography. One model is random oracle model. In random oracle model, we use hash functions as random oracles. zk-SNARKs in random oracle models don't need trusted setup and are post-quantum secure, but they are inefficient. Examples of zk-SNARKs in ROM are STARK and Aurora, etc.

zk-SNARKs with trusted setup are more efficient than zk-SNARKs with transparent setup or zk-SNARKs in ROM. For example, you can see in the bellow table that Zcash's zk-SNARK has smallest proof size and verification time. Indeed, there are trade-offs: you give security (by trusting setup) and take efficiently.

Answer 3

It is not true that zk-Snarks need a trusted setup. It's just that all the zk-Snarks that depend on pairings (that I know of) hinge on a "trapdoor", the knowledge of which makes the scheme insecure. And before 2019, those were the only known zk-Snarks.

zk-Starks do not rely on pairings. Neither do bulletproofs. Bulletproofs are arguably not Snarks, since the verification time is not succinct.

The DARK scheme gives you a trustless zk-Snark (https://eprint.iacr.org/2019/1229). Recently, a gap was found in this paper but the cryptographers who found the gap were able to modify the scheme so that it is now secure and hinges on weaker cryptographic assumptions than before: https://eprint.iacr.org/2021/358.