Posts in this series:
- The Case for zk-SNARKs
- The Case Against zk-SNARKs
- Alternatives to zk-SNARKs
In the final part of this series, I explore some competing technologies of zk-SNARKs, which thrive on the weaknesses of their most famous competitors.
Alternatives to zk-SNARKs
zk-STARKs
There are not many standard techniques that are efficient in some sense and non-interactive, and thus suitable for use in distributed ledgers. zk-SNARKs are one among this select group. Another high-profile type of solution is called a zk-STARK.
The acronym zk-STARK stands for
- zero-knowledge
- Scalable
- Transparent
- Argument of Knowledge
Not much changes on the surface, but the authors have decided to emphasize the Transparency aspect. There is perhaps not much of a difference between Scalable and Succinct, and in fact in more recent development of this technology, these constructions appear referenced as Transparent zk-SNARKs.
zk-STARKs bring big improvements to the table, and I highlight the following:
- They don’t require a Common Reference String, nor keys of any kind. As such, there is no Trusted Setup, which is the main point of contention with SNARKs.
- They require really weak cryptographic assumptions for their security, that have been well tested (the existence of collision-resistant hash functions).
- On top of it, these assumptions are not known to be broken by quantum computers, which means that at present zk-STARKs are Post-Quantum resistant, ie, they will continue to be secure even when Quantum computers of realistic sizes become available.
Of course there are drawbacks as well, or else we’d all be using zk-STARKs. The problem is their storage requirements. STARKs are doubly scalable, which means the proof verification is exponentially faster than the original computation’s time (think of the outsourced computation scenario) and the proof generation grows quasi-linearly with that time.
But the size of the proof they create is still too large, possibly 2 or 3 orders of magnitude more than those produced by zk-SNARKs. At present, this is a serious drawback for several applications, although 0x is already implementing zk-STARKs in Ethereum as a proof of concept.
zk-STARKs are still very recent, they’ve been around for 2 or 3 years at most, so this is early days and the technology has much to grow. Because of that, they are one of the hottest prospects for Zero-Knowledge non-interactive proof systems.
Sigma-Protocols
Sigma-Protocols are perhaps the oldest ZK proof system around. They have a fixed format with only 3 messages exchanged between Prover and Verifier, starting with the Prover sending.
Sigma-Protocols were created in the late 80s / early 90s and allow for the proving of a restricted, but large, family of statements. This includes pretty much any linear combination of “knowledge of discrete log proofs”, or any statement that can be characterized by a homomorphism between two groups, one for public instances, the other for secret witnesses, that is a one-way function.
Although they are, in origin, an interactive protocol, the verifier uses public-coin randomness, which means the Prover gets to see all the randomness used by the Verifier. This allows it to simulate that true randomness by using instead the output of a Hash Function, and thus remove the Verifier’s only message.
In comparison with zk-SNARKs, they have some very appealing properties similar to zk-STARKs. They:
- don’t require a Trusted Setup.
- use only a very simple and well tested cryptographic assumption, namely the hardness of the Discrete Log.
- are compartatively much easier to understand and implement, than both zk-SNARKs and zk-STARKs.
- can be extremely fast for proof generation and verification of simple statements.
The main problem of Sigma-Protocols is that they aren’t flexible enough. We can combine Sigma-Protocol proofs with AND and OR connectors, but each time you combine proofs you linearly increase the proof size, the proof generation time and the verification.
Sigma-Protocols do not scale at all, although you may be able to apply batching tricks to improve the performance, and so they are only usable with statements from a limited family and with a limited number of inner clauses.
Bulletproofs
Bulletproofs are another recent technique. Like zk-SNARKs, they are suited to encoding arithmetic circuits and so can in theory prove any NP statement.
They are not as scalable as zk-SNARKs or zk-STARKs, and so could be considered inferior choices to these in the case of big circuits, but they are particularly good for range proofs, that is, to prove a secret value lies within a certain range.
Besides this, they do offer some scalability and can be further optimized via aggregation of many similar proofs. These are their advantages:
- They don’t require a trusted setup
- Like Sigma-Protocols, they base their security only in the hardness of the Discrete Log. They:
- can be used to prove statements represented by generic circuits
- scale logarithmically with the number of statements, much better than Sigma-protocols.
- are particularly adequate to range proofs, and can aggregate several of these into a single proof, reducing the time for proof generation and verfiication
System Combinations
These are the main options available for Zero-Knowledge proofs, but you don’t have to restrict yourself to them. Since each system has its own advantages and disadvantagens, it is possible to combine them to handle a very complex statement with many different clauses.
You can combine Sigma-Protocols and zk-SNARKs in a single proof by making the discrete-log part of the proof in Sigma-Protocols and comitting to the input and output values of these, and proving in a zk-SNARK the operation of some circuit in the committed values via other types of operations.
You can also combine Sigma-Protocols and Bulletproofs in a similar way, using a technique the authors have dubbed Sigma-Bullets.
This is the end of this series, which I believe sums the best options for designing arbitrary Zero-Knowledge proof systems for custom statements. I hope you may have gained some ideas on how to decide which technology will works best for your particular requirements. It is worth spending some time ana save you from a miscalculated jump into a technology that is cool and trendy, but may be inadequate for your needs.
I hope you enjoyed this post, and wonder if it matches your experience. What other advantages / disadvantages do you think SNARKs have? Or what other technologies should I have talked about? Let me know your thoughts in the comments.
See you in the next post. Until then, happy coding and happy research.