43

zk-SNARKs, Zk-STARKs and BulletProofs are three major zero knowledge proofs to provide privacy for the blockchain technology.

If we can compare them,

(1) Bulletproofs and Zk-STARKs require no trusted setup.

Unlike zk-SNARKs that requires a trusted setup that creates an uncomfortable situation for it.

(2) Zcash using zk-SNARKs can hide amount address along with sender and recipient.

It is not yet clear to me if it is possible to hide sender and recipient by Bulletproofs and Zk-STARKs.

(3) Apparently, Zk-STARKs is faster than zk-SNARKs is faster than Bulletproofs.

(4) Bulletproofs is shorter than zk-SNARKs and Zk-STARKs.

In general, what are the main differences (advantages and disadvantages) between these 3 main zero knowledge proofs techniques ?

Note: The references are used for the above comparisons:

https://crypto.stanford.edu/bulletproofs/

https://blockonomi.com/bullet-proofs/

https://nulltx.com/mit-review-acclaims-zk-snarks-but-zk-starks-may-steal-the-show/

Note 1: The following article compares SNARKs with STARKs: https://medium.com/coinmonks/zk-starks-create-verifiable-trust-even-against-quantum-computers-dd9c6a2bb13d

Note 2: I compared zk-SNARKs vs. Zk-STARKs vs. BulletProofs in following figure. Any comment on this comparison is appreciated:

enter image description here

Improve this question

4 Answers 4

Reset to default
28

A few of your points are valid (e.g. SNARKs and STARKS are both faster than Bulletproofs) but there are also some mistakes:

  1. STARKs are only faster than SNARKs at the prover level (1.6s vs 2.3s), while for verifiers the protocol is slightly slower (16ms vs 10ms).
  2. If by shorter you mean size in bytes, Bulletproofs are only smaller than STARKs (1,300B vs 45,000B), while they are significantly larger than SNARKs (1,300B vs 288B)

What are the main differences (advantages and disadvantages)?

According to the awesome ZKP repo:

awesomeZKP

According to Elena Nadilinski's slides from Devcon4:

leanthebean

According to Zooko Wilcox's (Zcash) keynote from Devcon4:

zooko

According to Eli-Ben Sasson's (STARKware) keynote at the Technion Summer School (do note that this last picture measures a subset-sum solver, probably more complex than the computations done in the comparison above):

eliben

Improve this answer
2
  • Thank you, could you please say what "orders of magnitude too big" mean? (in your third figure.) Thanks
    – Questioner
    Commented Jan 4, 2019 at 10:36
  • 1
    Orders of magnitude are, roughly, the powers of 10 in a number. You can easily see compare these when you represent numbers in Scientific notation. For example: ``` 27 = 2.7 * 10^1 98 = 9.8 * 10^1 342 = 3.42 * 10^2 50000 = 5 * 10^4 ``` The first two numbers, although one is almost 4 times as large as the other, are in the same order of magnitude: they're both between 10 and 100. The others, though, are larger. 50000 is 3 orders of magnitude above 27, because its exponent in scientific notation is 4, and 27's is 1.
    – Alex Pinto
    Commented Apr 1, 2019 at 21:39
12

Starks are almost better than Snarks all around: they require weaker crypto assumptions, don't require a trusted setup and are post-quantum resistant. But they have a major drawback, as in the proof is huge.

For certain applications, like the one I have to work, that is simply not feasible. We had to choose between a Snark proof in the order of hundreds of bytes and a STARK proof in the hundreds of kilobytes. That single factor was a killer for us.

The time to verify is also remarkably larger in Starks than Snarks. In the former, it grows in time O(poly log n), whereas for Snarks it is linear in the input size, which is just a small constant, especially in complex circuits. Remember that n here is the number of gates.

For example, take a circuit that proves you know the pre-image of a certain hash value. The input will be the size of that input, which is 32 bytes if you're using SHA256. For this function, though, the number of gates will be in the tens of thousands, and you can see how the verification time for the SNARK is negligible in comparison.

The numbers in the tables above are very misleading. They don't tell you what sort of circuit you have, and how large n is. Depending on how complex your circuit is, they may vary wildly. I prefer to use asymptotic notation, and there is a good table for that in this paper (page 3).

Improve this answer
3
  • Thank you, but in the STARKs paper, it is mentioned: "for medium- and large-scale sequential computations our ZK-STARK verifier time is better than other solutions" (Page 12) (Link to the paper: eprint.iacr.org/2018/046.pdf). Does it mean that they claim STARKs verify time on average is shorter than SNARKs? Thanks
    – Questioner
    Commented Mar 27, 2019 at 11:01
  • 3
    Hi, thank you for the question. The answer is I don't know. From what I read, the authors of the paper have selected a very specific circuit type (the DPM benchmark). Also I think they are a bit dishonest in how they measure the verification time, as they add the one-time setup to it. There is no reason to do this, the verification and the setup are independent processes. If you see the graph, they have also included a line for libSnark without the setup and is significantly under the ZKStark line.
    – Alex Pinto
    Commented Mar 28, 2019 at 22:41
  • 1
    Asymptotic notation reflects growth of computation when input size increases, and may not always reflect cost in reality. In many cases, STARK can outcompete SNARK in verification time bcoz it uses simple field arithmetic while the latter uses expensive elliptic curve pairings on extension fields.
    – sinoTrinity
    Commented Jul 19, 2022 at 17:29
1

AFAIK Bulletproofs are shorter but to verify them takes way longer then Starks thus making it non scalable for blockchain tx obscuring.

Improve this answer
3
  • Thank you, Yes, but how about STarks ? when they are faster than both of SNarks and Bulletproofs and at the same time they do not need a trusted setup . And also what the advantage of this fact that Bulletproofs are shorter than STarks ? Thanks
    – Questioner
    Commented Nov 3, 2018 at 14:08
  • According to comment here (bitcoin.stackexchange.com/q/79423/41513) the size and speed in sNarks and Bulletproofs are dependent on the complexity and simplicity of the statement, but I am not sure about sTarks if its size and speed is independent on the complexity of the statement. Thanks
    – Questioner
    Commented Nov 13, 2018 at 20:35
  • 2
    The speed of SNARK verification is not dependent on the circuit size, unlike the other systems.
    – Daira-Emma Hopwood
    Commented Apr 24, 2019 at 22:21
0

Some Screenshots I have taken from various sources that differentiate between these three. These may help:

enter image description here enter image description here

enter image description here

Improve this answer
1
  • Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Commented Oct 2, 2023 at 11:02

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.