The STARKs paper states

Third, and most important, ZK-PCPs are transparent (or “public randomness” ), which means that the randomness used by the verifier is public; in particular, setting up a ZK-PCP requires no external trusted setup phase

as one of its main advantages over SNARKs. This statement is not fully clear to me. Which properties rely on this "common random string"? Does the verifier only "trust" a received proof if he/she trusts that the public random string was chosen uniformly at random? If not, why can't the prover simply pick a random string itself and send it along with the proof if the setup does not need to be trusted? This way there would be no setup at all.


1 Answer 1


That is a very good question. First, observe that in general, using a common random string (or any other form of trusted setup) is necessary to get any provable security guarantee, as soon as you want your proof system to handle statements outside of BPP. Indeed, it is known that non-interactive zero-knowledge proofs without any trusted setup can only exist for languages in BPP.

So, it is necessarily the case that "something" relies on the common reference string being sampled at random, in a trusted way. That "something" can be either soundness, zero-knowledge, or both (since those are the two security properties we care about). With most existing proof systems, the crs is actually needed for both:

  • if the prover picks the string himself, he can break the soundness of the proof (i.e., prove incorrect statements)
  • if the verifier picks the string himself, he can break the zero-knowledge property of the proof.

Whether this issue can be mitigated has been studied under the name of subversion resistance. This is a line of work which attemps to build NIZKs/SNARGs that maintain some security guarantees even if the common reference string is adversarially subverted. It was initiated in this paper. Essentialle, it shows that achieving zero-knowledge and preserving soundness under subversion at the same time is impossible - however, the other way around is possible. Several follow-ups (1, 2) have built various subversion-resistant SNARGs.

The transparent setup of STARKs avoid this issue essentially by relying on the Fiat-Shamir transform; in the random oracle model, it is in fact possible to have NIZKs without setup for arbitrary languages, so that's just what they do (succinctly). Of course, in the end, their non-interactive argument has no provable security guarantee in the plain model, but only heuristic security guarantees given by the analysis in the ROM.

So to conclude:

  • Standard SNARGs: you need to perform a trusted setup or find a globally verifiable source of randomness which is hard to manipulate (e.g. the result of the last 100 loteries, or randomness extracted from black spots on the sun, or whatever you like - to be honest, any nothing-up-my-sleeve number should work in practice, so you can just take the digits of Pi). But in exchange for that, they can be proven secure under some (non-standard) assumption, in the standard model.
  • STARKs: no trusted setup, you have a provably secure construction, but only in an idealized model with a random oracle. This gives you something heuristically secure, but with no formal security argument, when you replace the random oracle with a true hash function. However, it removes the burden of finding a source of globally verifiable randomness.
  • $\begingroup$ Thanks for the elaborate answer! I just got very confused by the "transparent setup" statement in their paper, since I have never seen it in any other paper and I don't really understand why they didn't simply say that they don't require a setup instead of calling it transparent. Thanks anyways! $\endgroup$
    – Cryptonaut
    Mar 19, 2019 at 18:40
  • $\begingroup$ When no one satisfies a given property, no one gives it a name - but when you claim to be the first to achieve it, you name it, it makes it easier to clearly state your improvement :) $\endgroup$ Mar 19, 2019 at 18:55
  • $\begingroup$ I mean without knowing the details it sounds like it's either just a public-coin zero-knowledge argument or a sigma protocol? That we already had before and these things have names :) $\endgroup$
    – Cryptonaut
    Mar 19, 2019 at 20:38
  • $\begingroup$ yep, that's what it is, but succinct, concretely efficient, and post quantum. That, we did not have. $\endgroup$ Mar 19, 2019 at 21:15
  • $\begingroup$ fair enough. Thanks a lot for the clarification! $\endgroup$
    – Cryptonaut
    Mar 19, 2019 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.