Comparison of Different zk-SNARKs
Zero-knowledge proof technique has been proven as a strong tool in protecting privacy in many different kinds of blockchain networks (e.g., ZCash, Algorand, Hyperledger). This article is intended to introduce recent development of zero-knowledge proof systems and give a complete comparison among those important published works until the end of 2019. In this article I’m trying to give a (brief?) comparison of different zk-SNARKs and will focus several recent works about it. I agree there is a long line of research about zk-SNARKs so any comments are welcome. This article only represents my own view.
I concluded about the recent development of zero-knowledge proof systems and have compared them from the following theoretical dimensions:
- Prover time complexity
- Verifier time complexity
- Common Reference String Size
- Proof size
- Whether it is post-quantum secure ?
- Does it support a universal common reference string ?
- Does it have trusted setup?
- Does it support updatable common reference string?
- What cryptography assumptions are they based on?
Time complexity and size are easy to understand and both can be represented in big-O asymptotic complexity. In case the reader doesn’t know some other properties about zero-knowledge proofs, I introduce them below:
- Common Reference String: the term common reference string is from a model called common reference string model (a.k.a CRS model) in which both prover and verifier have access to the same string CRS taken from some existing distribution. The common reference string is usually generated in the trusted setup phase and It is usually used in NON-INTERACTIVE zero-knowledge proofs.
- Universal Common Reference String: A common reference string is universal means that it allows a single setup to support all circuits of some bounded size. The universal common reference string (universal CRS) is also often called universal structure reference string (universal SRS).
- Updatable CRS/SRS: An updatable common reference string allows an open and dynamic set of participants can contribute secret randomness to it indefinitely. Although this is still a trusted setup in some sense, it increases confidence in the security of the parameters as only one previous contributor must have destroyed their secret randomness in order for the SRS to be secure.
Since the appearance of zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) and its application in Bitcoin, there are many follow-up works that were intended to improve it. There are basically two important lines of research about these zero-knowledge proofs.
The first line of research is starting from Groth 16 → GKM+18 → Sonic 19 → PLONK 19/MARLIN 19. In this line of research the authors mainly focus on getting rid of trusted setup while maintaining an efficient proof system.
The second line is starting from Ligero 17 → Aurora 18 → Fractal 19. These works are focused on post-quantum security so they are using many post-quantum secure building blocks. For example, hash function and Reed-Solomon code.
There are other milestones. For example, zk-STARKs, which gets rid of the trusted setup and is post-quantum secure. However, it is not very efficient both in theory and in practice.
In this article we mainly discuss and compare those proof systems in the first line of research.
The first most attractive proving system is a (pre-processing) succinct non-interactive argument of knowledge, or zk-SNARK for short, which has a small constant proof size and constant-time verification costs even for arbitrarily large relations. One next milestone is Groth 16, which is a zk-SNARK that contains only 3 group elements in the proof. Groth 16 is the most efficient one in proof size even many other follow-up works appear til now. However, it does not solve the trusted setup problem. In fact, Groth 16 still needs a trusted setup. For people who want to know why having a trusted setup is bad, I encourage the reader to this post by QEDit: Diving into the zk-SNARKs Setup Phase
One additional imperfection of Groth 16 is that it is actually a proving system with circuit-specific common reference string. That means the proof system can only support a fixed circuit in the setup phase for the prover. That means, when the proof system is used in other different applications, we must re-run the setup phase with different parameters.
Inspired by the trusted setup problem and circuit-specific problem, Groth et al. introduced the notion called universal and updatable structure reference string (or universal and updatable SRS). It allows a single setup to support all circuits of some bounded size. Moreover, the common reference string is updatable, meaning an open and dynamic set of participants can contribute secret randomness to it indefinitely. Although this is still a trusted setup in some sense, it increases confidence in the security of the parameters as only one previous contributor must have destroyed their secret randomness in order for the SRS to be secure.
For example, the common reference string is universal allows the same parameters can be used for any application using this zk-SNARK. Thus we can imagine including the global parameters in an open-source implementation, or one could use the same parameters for all smart contracts in Ethereum.
The common reference string is updatable means that any user, at any time, can update the parameters, including after the system goes live. After a single honest user has participated, no party can prove fraudulent data. This property means that a distrustful user could update the parameters themselves and have personal confidence in the parameters from that point forward.
However, while the construction due to Groth et al. does have constant-size proofs and constant-time verification, it requires an SRS that is quadratic with respect to the number of multiplication gates in the supported arithmetic circuits. Moreover, updating the SRS requires a quadratic number of group exponentiations, and verifying the updates requires a linear number of elliptic curve pairings. Finally, while the prover and verifier need only a linear size, circuit-specific string for a given fixed relation (rather than
the whole SRS), deriving this from the SRS requires an expensive Gaussian elimination process. In a concrete setting such as Zcash, which has a circuit with 2¹⁷ multiplication gates, the SRS would be
on the order of terabytes and is thus prohibitively expensive. Also, this is just a theoretical work and there was no implementation of GKM+18. This all leads to the appearance of Sonic below.
Sonic is mostly developed intending to solve the SRS scaling problem. Sonic’s structured reference string is linear in size with respect to the size of supported circuits, as opposed to the GKM+18, which scales quadratically. The structured reference string in Sonic also does not need to be specialized or pre-processed for a given circuit. This makes a large, distributed and never-ending setup process a practical reality.
Sonic uses a smaller set of global parameters. As a result, storing, updating, and verifying Sonic’s parameters could be achieved on a personal laptop. On the other hand, GKM+18’s public parameters are expensive to store, update, and verify, to the extent that it would require a distributed set of computers to carry out these tasks. Also, to use GKM+18’s zk-SNARK with a specific application, some party has to run an expensive (but untrusted) derivation process on the global parameters to obtain application-specific parameters. Sonic does not require any derivation process.
Sonic has two modes of operation, the “helper” mode, and the “unhelped” mode. The helper mode is simpler and more efficient but assumes the presence of untrusted third parties that aggregate a number of proofs together. The unhelped mode assumes neither batching or aggregation, however, is more expensive (estimated proof sizes over 256-bit groups is 1kb). For each proof, the Sonic verifier requires knowledge of the evaluation of a (sparse) polynomial for known polynomial. Computing this polynomial for themselves requires an undesirable level of work for the verifier, but a reasonable level of work for the prover or helper.
Since Sonic only provides its implementation under its helper mode, we only focus such mode in this article. The helper commits to a batch of proofs. They then calculate the verifiers’ polynomials and provide a short, easy to verify proof of the correct calculation. In the blockchain setting, they could be run by the miners. The miner who adds a block would be required to provide the help for all proofs in the block, and all other parties in the network could quickly verify the validity of this help. Given m proofs, the helper runs in time proportional to m provers. The helpers’ proof sizes are small. Verifying the help requires a one-off calculation of the polynomial s(X,Y) at known points z,y and then a small computation per proof (this computation is independent of the size of the application).
Marlin is a consecutive work that focus on reducing the gap between zk-SNARK with universal and updatable SRS and zk-SNARK with circuit-specific CRS. Actually, Marlin and another concurrent work PLONK (https://eprint.iacr.org/2019/953.pdf) both have the same goal about this. Since PLONK does not have any proper implementation I only focus on discussing Marlin. From theoretical point of view, Marlin does not improve too much than Sonic but in practice it claims 10X faster in prover running time than Sonic.
The improvements of Marlin are mostly in concrete parameters but from asymptotic complexity perspective it is almost the same as Sonic. The authors also give a comparison in practice between Marlin and Groth 16, and no surprise Marlin is slower.
SuperSonic claims they get rid of the trusted setup by constructing a new polynomial commitment. The technique is kind of new and there is no open-source code yet. I’m also working on research about it. Stay tuned!