23

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

10

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

  • Thank you, could you please say what "orders of magnitude too big" mean? (in your third figure.) Thanks – Questioner Jan 4 at 10:36
  • 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 Apr 1 at 21:39
4

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).

  • 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 Mar 27 at 11:01
  • 2
    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 Mar 28 at 22:41
1

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

  • 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 Nov 3 '18 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 Nov 13 '18 at 20:35
  • The speed of SNARK verification is not dependent on the circuit size, unlike the other systems. – Daira Hopwood Apr 24 at 22:21

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.