7
$\begingroup$

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.
Improve this question
$\endgroup$
2
  • $\begingroup$ ethereum.stackexchange.com/questions/59145/… $\endgroup$
    – liquan.eth
    Commented Dec 30, 2020 at 6:50
  • $\begingroup$ I feel like that question is mostly asking about performance (advantages vs disadvantages) rather than the theoretical foundations and definitions of the terminology. It is a very useful post in its own regard though! $\endgroup$
    – Ruben De Smet
    Commented Dec 30, 2020 at 20:15

2 Answers 2

Reset to default
6
$\begingroup$

  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
$\endgroup$
2
  • $\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
    Commented Sep 18, 2019 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
    Commented Sep 18, 2019 at 11:57
3
$\begingroup$

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"?

zk-SNARK (short for zero-knowledge succinct non-interactive argument of knowledge) is a class of non-interactive zero-knowledge proof system which basically satisfies the following properties:

  1. succinct proof: the proof size is short, usually only contains constant number of group elements.
  2. zero-knowledge: the proof does not reveal any private info about prover's secret (witness) to malicious verifier.
  3. knowledge of argument: malicious prover cannot prove a false statement for some NP relation to the verifier such that the verifier accepts it. Usually captured by that there exists an extractor that can extract the witness from the proof.
  4. completeness: If both prover and verifier are honest, verifier will accept the proof with probability 1.

The same for zk-STARK, with most probably the same answer. zk-STARKs is stronger because it is transparent, which means it does not need secret trusted setup. And also current zk-STARKs is constructed using quantum-resistant primitives so it is supposed to be post-quantum secure.

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.

Bulletproofs is not succinct so it is not zk-SNARKs

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think indeed the answer to my question lies in what is meant by succinct: the proof size is "short" and prover/verifier time is "fast". However, I find that neither you nor @Chipotle define those terms rigorously. Chipotle clearly says verifier time should be sublinear, you say the proof "usually" contains a constant number of group elements. I feel like both of you have more-or-less halve the answer. $\endgroup$
    – Ruben De Smet
    Commented May 29, 2020 at 7:31
  • $\begingroup$ @RubenDeSmet I think Chipotle and me were saying the same thing but from different perspectives, if the proof contains a constant number of group elements, it naturally lead to sublinear verification time (since verifying these group elements you need to check pairings), more specifically, the verification time can be O(logn) for some constructions. $\endgroup$
    – CryptoLover
    Commented May 30, 2020 at 0:38

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.