Posts in this series:
- The Case for zk-SNARKs
- The Case Against zk-SNARKs
- Alternatives to zk-SNARKs
In this post, I start a new series about zk-SNARKs, and explore where they might not be the best choice for your use case. Despite their popularity, they’re not a one-size-fits-all solution, and developers should be aware of where they could be advantageously replaced by other technologies.
Note: this series was previously published as a single post. Due to its length, I decided to break it in three.
If you’ve been reading my blog for some time now, you’ll know that I am very interested in zk-SNARKs. I have written some posts on what they can do, how to construct them and what the algebra underlying them looks like.
I have implemented a specific type of SNARK (BCTV14) in a number of languages and platforms, for a very specific (and relatively simple) circuit. My posts reflect my experience, in that they are relevant only to QAP-based SNARKs, which use bilinear pairings. That still covers a lot of ground, as those are the ones we most often see in practice.
This series tries to help those using SNARKs for their work to critically assess if SNARKs are the right tool. It can be the case, as I found out, that there is such an imposing forest in front of you that you miss the lonely, small tree under which the treasure is buried. In fact, there are other ways to make Zero-Knowledge proofs that may be a better choice for your proof statement.
This first post goes over the strengths of zk-SNARKs, and why, in my view, they gained such popularity in the communities of several blockchains.
What Are zk-SNARKs
zk-SNARKs have exploded in recent years as the most promising technology to solve privacy in blockchain, and there are good reasons for their popularity. Before I begin, I recap what zk-SNARKs are and why they”re such a revolutionary technique for distributed ledgers.
The acronym zk-SNARK stands for
- zero-knowledge
- Succinct
- Non-interactive
- Argument of Knowledge
Strictly speaking, a zk-SNARK is a message with a specific structure that serves as a “proof” of some statement.
Any person with a verification key can check this “proof”. If the statement holds, a correct proof will convince a verifier. If the statement is false, no prover (see section below) can convince a verifier that statement is true.
Moreover, the proof also guarantees that the prover knows exactly why the statement is true. This is the difference between “proof” and “proof of knowledge”. The first only guarantees a statement is valid. The second guarantees the prover knows a witness to the validity of the statement.
Proof or Argument
There is a small technicality above, in that we use the word “argument” instead of proof. “Proof” does make the text easier to understand, and so I will keep using it in this blog, but keep in mind that there is a difference in the meaning of these two words.
In a real “proof”, the verifier can not be fooled by any malicious Prover, no matter how powerful.
An “argument”, instead, is weaker: the Verifier is only protected against a Prover that is computationally limited. In other words, one that runs in a relatively practical (ie efficient) amount of time.
Proofs of Knowledge
The difference between “Proof” and “Proof of Knowledge” may seem quite odd to you. What does this actually mean? I illustrate with an example.
In cryptography, we use prime numbers for lots and lots of things. This means we need efficient means to select a (often huge) prime number.
This implies that we must have a way to show a number is prime. The most efficient algorithms to detect primality today are all random, like for example the Fermat, Solovay-Strassen and Miller-Rabin tests.
When you run a single execution of these tests for a number n, you will always get True if n is prime. On the other hand, if the test returns False, you know n is composite. However, n may be composite and the test may still return True, giving you a false positive.
You can’t fully trust a True reply, but since false positives only happen with limited probability, you can run the test several times and accept n is prime if the test never returns False.
At the end of this process, though, you learn whether the number is composite, but none of its factors.
In other protocols, for example RSA, the prime factorization of a large number is effectively a private key, and can be seen as a proof of identity. You can prove your identity by showing you do know that private key (a prime factor), but of course, without revealing it to the verifier.
A simple primality-test is not enough: you need a proof of knowledge that n is not prime to assert you do know one of its factors. zk-SNARKs are useful because they provide this stronger kind of proof.
The Case for zk-SNARKs
Non-Interactivity
There is a decisive aspect of zk-SNARKs that makes them well-tailored for a blockchain application: non-interactiveness. The original Zero-Knowledge proofs were interactive, meaning that a Prover and a Verifier had to exchange messages for a number of rounds until the Verifier would be in a position to decide whether the proof was valid.
In some cases, it was possible to remove this interactiveness using a venerable trick called the Fiat-Shamir heuristic. But for many complex cases, this was not possible, until later techniques were devised.
zk-SNARKs are all non-interactive, which means the Prover only needs to send a single message to the Verifier. In other words, the Prover can produce its proof oblivious of the Verifier’s response and there is no need for the verifier to be online at the moment the proof is created.
Indeed, this proof can be stored, replicated and distributed to many different Verifiers. This is essential for a distributed ledger setting, where a block creator produces a proof that must be verified before the block is accepted.
The proof is generated by a block creator and given to all block validators, who Verifier the proof in their own time. Meanwhile, the block creator can start working on the next block.
Succinctness and Non-Zero-Knowledge SNARKs
Although zk-SNARKs were probably first touted in crypto-currencies as a solution to the lack of privacy of blockchains like Bitcoin of Ethereum, in fact they are also much admired for their succinctness.
For example, ZK Rollup uses SNARKs as a technology to improve the scalability of Ethereum transactions, without privacy concerns.
The important characteristic in this setting is Succinctness, the ability to produce a very short proof that several computations have been correctly executed.
A particular scenario where this is desirable is when a client wishes to outsource a computation to much more powerful service, and simply verify the final result has been correctly computed. There is no need for Zero-Knowledge here, as the client may know everything the remote service needs to perform the required computation.
In blockchain applications, such a scenario can occur with the computation being outsourced to an off-chain service, which produces a result and a Snark proof of its correctness. This can be quickly verified by the validators, and the result placed in the blockchain.
Because the transactions themselves do not need to be written, just the final state of their execution, we can reduce the storage demands of the chain by many times. Crucially, this is only possible because these proofs can be verified very fast, without any serious impact in the time it takes to generate new blocks.
SNARKs are succinct because the size of the proof they produce is fixed, and very small (some hundreds of bytes only), independently of the complexity of the proof statement.
This has two advantages: a small price to pay for storage and transfer of this proof, especially important in Ethereum, where you have to pay gas for both of these; and very efficient proof verification, that can be executed extremely fast (depending on the language of course, but in the order of tens of milliseconds).
Public Verifier
zk-SNARKs have public verifiers, which means a proof can be checked by many different parties. You do have to own a proper key, but aside from that, you’re free to go.
Since this can be given to any user in a real blockchain (like ZCash), it is not a real impediment to verification and is ideal for public blockchains.
This is in opposition to some proofs that are for a designated verifier only, that is, they can be verified by a single party.
Full Statement Generality
I have already listed a set of characteristics of zk-SNARKs that make them extremely well-suited for use in blockchains. But for me, the most important one is the theme of this paragraph: full statement generality.
Again, let me compare with the beginnings of Zero-Knowledge proofs in the 1980s. It was one of the earliest results in the literature of Zero-Knowledge that we can produce ZK proofs for every statement in NP. I will not detail today what this means (that will likely be the theme of a future post), but this came at an extreme cost.
In the beginning, proofs were very ad-hoc. Each time researchers learned how to solve a new problem in Zero-Knowledge, they would provide a new proof construction or rely on the general feasibility result. The latter went something like this:
- The statement for our ZK proof is in NP. It can therefore be reduced to an NP-Complete problem (ie SAT, or Graph Colouring).
- We create a translation of the instance and the witness of our statement into an instance and witness of a SAT problem.
- We make the proof for the transformed instance, and give it to the verifier
- The verifier verifies the proof, and the reduction of the original to the modified instance, and outputs the result.
The problem with this approach is not only that the proof for the NP-Complete problem can be quite inefficient and non-interactive, but also that the reduction comes with another hit in performance.
zk-SNARKs are great in this respect, because they give an automated, out-of-the-box way of making proofs for any NP statement. And although the efficiency of generating the proof is directly related to the circuit complexity of the statement, the size of the proof and the time it takes to verify are independent of it.
This makes zk-SNARKS a very appealing construction for proofs of arbitrary statements.
Community Support
Due to the high visibility SNARKs have enjoyed in the last couple of years, a vivid community has developed around these concepts, and so it is relatively easy (compared to the other techniques) to find tools, implementations and advice on how to do it.
These are, for the most part, young and experimental, and so nowhere near the level of development we are used to in mature technologies, but they’re still much better than what is available for the competition, so you may want to start here at least to gain the basic concepts.
This sums up the strong points of zk-SNARKs, and why you may decide to use them. The next posts of the series will tell you why you might not want to use them, and what alternatives you have. Enjoy.