I have become quite familiar with Bulletproofs the last few months. Bulletproofs is the name given to a zero-knowledge proof system for arithmetic circuits, by Benedikt Bünz et al. It is a specific protocol with specific properties.

When Bulletproofs are discussed, they are often contrasted with zk-SNARKs and zk-STARKs. See, for instance, this question on the Ethereum StackExchange, where they discuss properties of Bulletproofs and compare them among zk-SNARKS and zk-STARKs.

A zk-SNARK is a zero-knowledge succinct non-interactive argument of knowledge. A zk-STARK is a "scalable transparent argument of knowledge", according to Eli Ben-Sasson's "Scalable, transparent, and post-quantum secure computational integrity".

To me, it sounds like the comparison ends there: the papers I consulted until now refer to SNARKs and STARKs as a list of properties that a proof system should have, not as a specific instantiation of a proof system. Considering the aforementioned Ethereum.SE question, it seems like both zk-SNARKs and zk-STARKs are actual instances of proof systems, since they list specific complexities and timings. Papers about specific SNARK and STARK construction, e.g. the Ben-Sasson paper, all seem to refer to "previous S[TN]ARK contructions", making me wonder whether the Eth.SE comparison can be fair.

So my question(s) is/are:

  1. What is a zk-SNARK:
    • a specific proof system, and if so: which one?
    • a class of ZK proof systems, and if so: is this class specific enough to claim that proofs are "always 200 bytes"?
  2. The same for zk-STARK, with most probably the same answer.
  3. I feel that question 1. will come down to a class of proof systems, which makes me wonder why Bulletproofs wouldn't be a "zero-knowledge, succinct non-interactive argument of knowledge"; they are typically considered separate.
  1. A class. Parameters according to which it is standard to compare them, are: prover time, verifier time, proof size, requirement of trusted setup, cryptographic assumptions. For "succinctness", the standard definition requires that verification time is sub-linear and proofs are "small".

  2. STARK however, is a name of a specific zk-SNARKS protocol, see any Eli Ben Sasson talk on Youtube for the specific attributes.

  3. I reckon it's because verification time is linear.

|improve this answer|||||
  • $\begingroup$ If your definition of succinctness is right, then Bulletproofs are indeed no SNARK: verifier time is $\mathcal O (n)$, proof size is $\mathcal O ( \log n)$. $\endgroup$ – Ruben De Smet Sep 18 '19 at 11:53
  • 4
    $\begingroup$ I confirm that the standard definition of succinctness applies to both size and verification time, which is why Bulletproof is not considered a STARK or a SNARK. $\endgroup$ – Geoffroy Couteau Sep 18 '19 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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