The current growth rate of zero-knowledge proof projects (ZKP) in the blockchain industry is astonishing, especially the rise of ZKP applications at the two levels of expansion and privacy protection, which has exposed us to a variety of zero-knowledge proof projects. Due to the extremely mathematical nature of ZKP, it is significantly more difficult for encryption enthusiasts to understand ZK in depth. Therefore, we also hope to sort out some changes in ZKP theory and application from the beginning, and explore the impact and value on the crypto industry with readers - learning together through several reports, which also serve as a summary of the thoughts of the HashKey Capital research team. This article is the first in the series, mainly introducing the development history, applications and some basic principles of ZKP.
The modern zero-knowledge proof system originated from the paper jointly published by Goldwasser, Micali and Rackoff: The Knowledge Complexity of Interactive Proof Systems (GMR85), which was proposed in 1985 and published in 1989. This paper mainly explains how much knowledge needs to be exchanged after K rounds of interactions in an interactive system to prove that a statement is correct. If the exchanged knowledge can be made zero, it is called a zero-knowledge proof. It is assumed that the prover has unlimited resources and the verifier only has limited resources. The problem with interactive systems is that the proof is not entirely mathematically provable, but correct in a probabilistic sense, although the probability is very small (1/2^n).
Therefore, the interactive system is not perfect and only has approximate completeness. The non-interactive system (NP) system born on this basis has completeness and becomes the perfect choice for the zero-knowledge proof system.
The early zero-knowledge proof systems were lacking in efficiency and usability, so they have always remained at the theoretical level. It was not until the last 10 years that they began to flourish. As cryptography became prominent in crypto, zero-knowledge proofs came to the forefront and became a crucial direction. In particular, developing a general, non-interactive, zero-knowledge proof protocol with limited proof size is one of the most critical exploration directions.
Basically, zero-knowledge proof is a trade-off between the speed of proof, the speed of verification and the size of the proof. The ideal protocol is fast proof, fast verification and small proof size.
The most important breakthrough in zero-knowledge proof is Groth’s 2010 paper Short Pairing-based Non-interactive Zero-Knowledge Arguments, which is also the theoretical pioneer of the most important group of zk-SNARKs in ZKP.
The most important development in the application of zero-knowledge proof is the zero-knowledge proof system used by Z-cash in 2015, which protected the privacy of transactions and amounts. Later, it developed into the combination of zk-SNARK and smart contracts, and zk-SNARK entered the Wider application scenarios.
Some important academic achievements during this period include:
Other developments including PLONK, Halo2, etc. are also extremely important progress and have also made some improvements to zk-SNARK.
The two most widespread applications of zero-knowledge proofs are privacy protection and capacity expansion. In the early days, with the launch of privacy transactions and several well-known projects such as Zcash and Monero, privacy transactions once became a very important category. However, because the necessity of privacy transactions was not as prominent as the industry hoped, this type of representative projects began to slow down. Slowly enter the second and third tier camps (not withdraw from the stage of history). At the application level, the need for expansion has increased to the point where Ethereum 2.0 (which has been renamed consensus layer) has transformed into a rollup-centric route in 2020. The ZK series has officially returned to the industry’s attention and become the focus.
Privacy transactions: There are many projects that have implemented privacy transactions, including Zcash using SNARK, Tornado, Monero using bulletproof, and Dash. Dash does not use ZKP in the strict sense, but a simple and crude currency mixing system that can only hide the address but not the amount. I will not mention it here.
The zk-SNARKs transaction steps applied by Zcash are as follows:
Source: Demystifying the Role of zk-SNARKs in Zcash
Zcash still has limitations in using zero-knowledge, that is, it is based on UTXO, so part of the transaction information is only shielded, not really covered up. Because it is a separate network based on Bitcoin’s design, it is difficult to expand (combine with other applications). The actual usage rate of shielding (that is, private transactions) is less than 10%, which shows that private transactions have not been successfully expanded. (from 2202)
The single large mixing pool used by Tornado is more versatile and based on a “tried and tested” network like Ethereum. Torndao is essentially a currency mixing pool using zk-SNARK, and the trust setting is based on the Groth 16 paper. Features available with Tornado Cash include:
Vitalik mentioned that compared with expansion, privacy is relatively easy to implement. If some expansion protocols can be established, privacy will basically not be a problem.
Expansion: The expansion of ZK can be done on the first-tier network, such as Mina, or on the second-tier network, that is, zk-roll up. The idea of ZK roll up may have originated from Vitalik’s post in 2018, On-chain scaling to potentially ~500 tx/sec through mass tx validation.
ZK-rollup has two types of roles, one is Sequencer, and the other is Aggregator. The Sequencer is responsible for packaging transactions, and the Aggregator is responsible for merging a large number of transactions and creating a rollup, and forming a SNARK proof (it can also be a zero-knowledge proof based on other algorithms). This proof will be compared with the previous state of Layer1, and then update Ethereum Merkle tree, calculate a new state tree.
Source: Polygon
Advantages and disadvantages of ZK rollup:
Source: Ethereum research
Based on data availability and proof methods, Starkware has a classic classification diagram for L2 (Volition’s data availability layer can be selected on-chain or off-chain):
Source: Starkware
The most competitive ZK rollup projects currently on the market include: Starkware’s StarkNet, Matterlabs’ zkSync and Aztec’s Aztec connect, Polygon’s Hermez and Miden, Loopring, Scroll, etc.
Basically the technical route lies in the choice of SNARK (and its improved versions) and STARK, as well as support for EVM (including compatibility or equivalence).
Briefly discuss EVM compatibility issues:
The compatibility between ZK system and EVM has always been a headache, and most projects will choose between the two. Those who emphasize ZK may build a virtual machine in their own system, and have their own ZK language and compiler, but this will make it more difficult for developers to learn, and because it is basically not open source, it will become a black box. Generally speaking, the industry currently has two options. One is to be fully compatible with Solidity’s opcodes, and the other is to design a new virtual machine that is ZK friendly and compatible with Solidity. The industry did not expect such quick integration at the beginning, but the rapid iteration of technology in the past year or two has brought EVM compatibility to a new level, and developers can achieve a certain degree of seamless migration (that is, the Ethereum main chain to ZK rollup) is an exciting development, which will affect ZK’s development ecology and competitive landscape. We will discuss this issue in detail in subsequent reports.
Goldwasser, Micali and Rackoff proposed that zero-knowledge proofs have three properties:
So in order to understand ZKP, we start with zk-SNARK, because many current blockchain applications start with SNARK. First, let’s take a look at zk-SNARK.
zk-SNARK means: Zero-knowledge proof (zh-SNARK) is zero-knowledge Succint Non-interactive ARguments of Knowledge.
The proof principle of Groth16’s zk-SNARK is as follows:
Source: https://learnblockchain.cn/article/3220
The steps are:
In the next article, we will start to study the principles and applications of zk-SNARK, review the development of ZK-SNARK through several cases, and explore its relationship with zk-STARK.
The current growth rate of zero-knowledge proof projects (ZKP) in the blockchain industry is astonishing, especially the rise of ZKP applications at the two levels of expansion and privacy protection, which has exposed us to a variety of zero-knowledge proof projects. Due to the extremely mathematical nature of ZKP, it is significantly more difficult for encryption enthusiasts to understand ZK in depth. Therefore, we also hope to sort out some changes in ZKP theory and application from the beginning, and explore the impact and value on the crypto industry with readers - learning together through several reports, which also serve as a summary of the thoughts of the HashKey Capital research team. This article is the first in the series, mainly introducing the development history, applications and some basic principles of ZKP.
The modern zero-knowledge proof system originated from the paper jointly published by Goldwasser, Micali and Rackoff: The Knowledge Complexity of Interactive Proof Systems (GMR85), which was proposed in 1985 and published in 1989. This paper mainly explains how much knowledge needs to be exchanged after K rounds of interactions in an interactive system to prove that a statement is correct. If the exchanged knowledge can be made zero, it is called a zero-knowledge proof. It is assumed that the prover has unlimited resources and the verifier only has limited resources. The problem with interactive systems is that the proof is not entirely mathematically provable, but correct in a probabilistic sense, although the probability is very small (1/2^n).
Therefore, the interactive system is not perfect and only has approximate completeness. The non-interactive system (NP) system born on this basis has completeness and becomes the perfect choice for the zero-knowledge proof system.
The early zero-knowledge proof systems were lacking in efficiency and usability, so they have always remained at the theoretical level. It was not until the last 10 years that they began to flourish. As cryptography became prominent in crypto, zero-knowledge proofs came to the forefront and became a crucial direction. In particular, developing a general, non-interactive, zero-knowledge proof protocol with limited proof size is one of the most critical exploration directions.
Basically, zero-knowledge proof is a trade-off between the speed of proof, the speed of verification and the size of the proof. The ideal protocol is fast proof, fast verification and small proof size.
The most important breakthrough in zero-knowledge proof is Groth’s 2010 paper Short Pairing-based Non-interactive Zero-Knowledge Arguments, which is also the theoretical pioneer of the most important group of zk-SNARKs in ZKP.
The most important development in the application of zero-knowledge proof is the zero-knowledge proof system used by Z-cash in 2015, which protected the privacy of transactions and amounts. Later, it developed into the combination of zk-SNARK and smart contracts, and zk-SNARK entered the Wider application scenarios.
Some important academic achievements during this period include:
Other developments including PLONK, Halo2, etc. are also extremely important progress and have also made some improvements to zk-SNARK.
The two most widespread applications of zero-knowledge proofs are privacy protection and capacity expansion. In the early days, with the launch of privacy transactions and several well-known projects such as Zcash and Monero, privacy transactions once became a very important category. However, because the necessity of privacy transactions was not as prominent as the industry hoped, this type of representative projects began to slow down. Slowly enter the second and third tier camps (not withdraw from the stage of history). At the application level, the need for expansion has increased to the point where Ethereum 2.0 (which has been renamed consensus layer) has transformed into a rollup-centric route in 2020. The ZK series has officially returned to the industry’s attention and become the focus.
Privacy transactions: There are many projects that have implemented privacy transactions, including Zcash using SNARK, Tornado, Monero using bulletproof, and Dash. Dash does not use ZKP in the strict sense, but a simple and crude currency mixing system that can only hide the address but not the amount. I will not mention it here.
The zk-SNARKs transaction steps applied by Zcash are as follows:
Source: Demystifying the Role of zk-SNARKs in Zcash
Zcash still has limitations in using zero-knowledge, that is, it is based on UTXO, so part of the transaction information is only shielded, not really covered up. Because it is a separate network based on Bitcoin’s design, it is difficult to expand (combine with other applications). The actual usage rate of shielding (that is, private transactions) is less than 10%, which shows that private transactions have not been successfully expanded. (from 2202)
The single large mixing pool used by Tornado is more versatile and based on a “tried and tested” network like Ethereum. Torndao is essentially a currency mixing pool using zk-SNARK, and the trust setting is based on the Groth 16 paper. Features available with Tornado Cash include:
Vitalik mentioned that compared with expansion, privacy is relatively easy to implement. If some expansion protocols can be established, privacy will basically not be a problem.
Expansion: The expansion of ZK can be done on the first-tier network, such as Mina, or on the second-tier network, that is, zk-roll up. The idea of ZK roll up may have originated from Vitalik’s post in 2018, On-chain scaling to potentially ~500 tx/sec through mass tx validation.
ZK-rollup has two types of roles, one is Sequencer, and the other is Aggregator. The Sequencer is responsible for packaging transactions, and the Aggregator is responsible for merging a large number of transactions and creating a rollup, and forming a SNARK proof (it can also be a zero-knowledge proof based on other algorithms). This proof will be compared with the previous state of Layer1, and then update Ethereum Merkle tree, calculate a new state tree.
Source: Polygon
Advantages and disadvantages of ZK rollup:
Source: Ethereum research
Based on data availability and proof methods, Starkware has a classic classification diagram for L2 (Volition’s data availability layer can be selected on-chain or off-chain):
Source: Starkware
The most competitive ZK rollup projects currently on the market include: Starkware’s StarkNet, Matterlabs’ zkSync and Aztec’s Aztec connect, Polygon’s Hermez and Miden, Loopring, Scroll, etc.
Basically the technical route lies in the choice of SNARK (and its improved versions) and STARK, as well as support for EVM (including compatibility or equivalence).
Briefly discuss EVM compatibility issues:
The compatibility between ZK system and EVM has always been a headache, and most projects will choose between the two. Those who emphasize ZK may build a virtual machine in their own system, and have their own ZK language and compiler, but this will make it more difficult for developers to learn, and because it is basically not open source, it will become a black box. Generally speaking, the industry currently has two options. One is to be fully compatible with Solidity’s opcodes, and the other is to design a new virtual machine that is ZK friendly and compatible with Solidity. The industry did not expect such quick integration at the beginning, but the rapid iteration of technology in the past year or two has brought EVM compatibility to a new level, and developers can achieve a certain degree of seamless migration (that is, the Ethereum main chain to ZK rollup) is an exciting development, which will affect ZK’s development ecology and competitive landscape. We will discuss this issue in detail in subsequent reports.
Goldwasser, Micali and Rackoff proposed that zero-knowledge proofs have three properties:
So in order to understand ZKP, we start with zk-SNARK, because many current blockchain applications start with SNARK. First, let’s take a look at zk-SNARK.
zk-SNARK means: Zero-knowledge proof (zh-SNARK) is zero-knowledge Succint Non-interactive ARguments of Knowledge.
The proof principle of Groth16’s zk-SNARK is as follows:
Source: https://learnblockchain.cn/article/3220
The steps are:
In the next article, we will start to study the principles and applications of zk-SNARK, review the development of ZK-SNARK through several cases, and explore its relationship with zk-STARK.