It feels like magic when I was learning zk-proof. zkp not only has the mathematical beauty but also (as a powerful tool) allows us to build all kinds of zk-apps.
I am deeply attracted by zkp. I would like to briefly sort out the history and evolution of zk-proof in this thread, and find out the key points for in-depth exploration.
Innovation
There are two types of innovation, one is to improve efficiency and make things can do better. The second is disruptive innovation, which can achieve what was completely impossible before, and this type of innovation will open a new door for everyone.
The practical zk-proving system is evolving into a disruptive innovation after bitcoin (distributed ledger) and ethereum (distributed computer).
Function
The word zkp has been abused. In fact, it has two functions. The first is proof of knowledge, the second is zero knowledge.
So the first function (proof of knowledge) can be used directly to prove that something is true, without necessarily requiring zero knowledge to protect privacy, everything depends on your goal and trade-off.
The zk-snark we use in the rollup not only needs to use the proof of knowledge function to prove the transactions are valid, but also use the zero knowledge function to protect input witness in the circuit (to prevent leaked and forgery proof).
Interactive proof
The earliest zk-proof is interactive proof, such as the example of F(x) = 0, Alice and Bob both know the function, Alice also knows x and does not want to reveal the actual value of x.
We can prove it by an interactive protocol. Bob asks some relevant questions to determine whether Alice knows x (by Q&A way). Through multiple interactions, the accuracy rate can rise to more than 99%.
Interactive protocol
Non-interactive proof
But the interactive protocol is too complicated. At this time, a non-interactive proof algorithm appears.
The prover (who proves that something is true) only needs to generate a proof, and then throw the proof to all the verifiers (who verify that the proof is valid) to verify. No need to frequently interact with each verifier, which allows zkp to be widely used.
a16z has an excellent article on this history, and an interesting statement in it, in a 2011 paper called “From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again” proposed zk-snark.
The paper mentions a zk-snark use case “a third-party efficiently running computations on a large set of data without needing to download or compile the dataset”.
For example, when using a cloud platform to train a machine learning model, you have to rerun the data to judge whether the model is valid, but using zk-snark, you only need to verify the proof of the model is valid.
Although the paper does not mention the privacy and scaling of blockchain, it still can be seen that it is very close. In 2013, zcash used zk-snark to build the first privacy blockchain, zkp was officially applied to Blockchain.
Groth16
One of the earliest zk-snark proof scheme is Groth16 proposed in 2016, both zcash and filecoin are used, among which filecoin is mainly to prove itself stored file content is valid.
Groth16 is based on pairing-friendly elliptic curves, the proof size very small (only three sets of elements), and the verification very fast.
The trade-off is it needs to perform a trusted setup for different circuits. The snarkjs library of iden3 also use the Groth16 protocol (you can use it, and you need to perform many setups for the circuits).
Sonic
So one direction in this field is to build a universal setup, such as Sonic proposed in 2019.
Sonic is a universal-setup proof scheme, it only needs one setup, and all other circuits share this setup. But Sonic’s proof is large, and the cost of verification is relatively high. Overall, the performance is not very good.
Plonk
Also in 2019, there appeared Plonk and Merlin based on Sonic, these two proof scheme is also general-purpose and greatly reduces the proof generation time and verification time.
Later, based on Plonk + lookup table, Plonkup was published in 2020, and UltraPlonk was invented based on Plookup + customs gate.
So understanding Plonkish (Plonk system) is very important, the new proof systems are based on the previous proof system, and Plonk is a key part of this process. “Plonkish” comes from this tweet.
Halo2
Halo2 is also based on UltraPlonk (Scroll is using). Halo2 uses a lot of Plonkish functions and replaces the KZG polynomial commitment with Inner-Product Argument, which has weaker security assumptions than Plonk.
Because of recursive proof, zkEVM can improve the time and efficiency of generating block proof, and finally be applied to the production environment. I’m looking forward to seeing layer1’s EVM also becomes zk-friendly.
Halo2, like zkEVM, is also an open-source project that encourages community participation and contribution. And Halo2 is the most powerful proof scheme I have seen so far, so Plonkish and Halo2 will be the focus of my study.
Comparison
This article has a comparison of the efficiency of different proof systems.
Comparison
Alessandro Chiesa’s speech at ZKSummit also divided all proof schemes into three categories.
Evolution of zk-proofs
It feels like magic when I was learning zk-proof. zkp not only has the mathematical beauty but also (as a powerful tool) allows us to build all kinds of zk-apps.
I am deeply attracted by zkp. I would like to briefly sort out the history and evolution of zk-proof in this thread, and find out the key points for in-depth exploration.
Innovation
There are two types of innovation, one is to improve efficiency and make things can do better. The second is disruptive innovation, which can achieve what was completely impossible before, and this type of innovation will open a new door for everyone.
The practical zk-proving system is evolving into a disruptive innovation after bitcoin (distributed ledger) and ethereum (distributed computer).
Function
The word zkp has been abused. In fact, it has two functions. The first is proof of knowledge, the second is zero knowledge.
So the first function (proof of knowledge) can be used directly to prove that something is true, without necessarily requiring zero knowledge to protect privacy, everything depends on your goal and trade-off.
The zk-snark we use in the rollup not only needs to use the proof of knowledge function to prove the transactions are valid, but also use the zero knowledge function to protect input witness in the circuit (to prevent leaked and forgery proof).
Interactive proof
The earliest zk-proof is interactive proof, such as the example of F(x) = 0, Alice and Bob both know the function, Alice also knows x and does not want to reveal the actual value of x.
We can prove it by an interactive protocol. Bob asks some relevant questions to determine whether Alice knows x (by Q&A way). Through multiple interactions, the accuracy rate can rise to more than 99%.
Non-interactive proof
But the interactive protocol is too complicated. At this time, a non-interactive proof algorithm appears.
The prover (who proves that something is true) only needs to generate a proof, and then throw the proof to all the verifiers (who verify that the proof is valid) to verify. No need to frequently interact with each verifier, which allows zkp to be widely used.
a16z has an excellent article on this history, and an interesting statement in it, in a 2011 paper called “From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again” proposed zk-snark.
The paper mentions a zk-snark use case “a third-party efficiently running computations on a large set of data without needing to download or compile the dataset”.
For example, when using a cloud platform to train a machine learning model, you have to rerun the data to judge whether the model is valid, but using zk-snark, you only need to verify the proof of the model is valid.
Although the paper does not mention the privacy and scaling of blockchain, it still can be seen that it is very close. In 2013, zcash used zk-snark to build the first privacy blockchain, zkp was officially applied to Blockchain.
Groth16
One of the earliest zk-snark proof scheme is Groth16 proposed in 2016, both zcash and filecoin are used, among which filecoin is mainly to prove itself stored file content is valid.
Groth16 is based on pairing-friendly elliptic curves, the proof size very small (only three sets of elements), and the verification very fast.
The trade-off is it needs to perform a trusted setup for different circuits. The snarkjs library of iden3 also use the Groth16 protocol (you can use it, and you need to perform many setups for the circuits).
Sonic
So one direction in this field is to build a universal setup, such as Sonic proposed in 2019.
Sonic is a universal-setup proof scheme, it only needs one setup, and all other circuits share this setup. But Sonic’s proof is large, and the cost of verification is relatively high. Overall, the performance is not very good.
Plonk
Also in 2019, there appeared Plonk and Merlin based on Sonic, these two proof scheme is also general-purpose and greatly reduces the proof generation time and verification time.
Later, based on Plonk + lookup table, Plonkup was published in 2020, and UltraPlonk was invented based on Plookup + customs gate.
So understanding Plonkish (Plonk system) is very important, the new proof systems are based on the previous proof system, and Plonk is a key part of this process. “Plonkish” comes from this tweet.
Halo2
Halo2 is also based on UltraPlonk (Scroll is using). Halo2 uses a lot of Plonkish functions and replaces the KZG polynomial commitment with Inner-Product Argument, which has weaker security assumptions than Plonk.
Halo2 does not need setup, and implements a very powerful recursive proof function.
Because of recursive proof, zkEVM can improve the time and efficiency of generating block proof, and finally be applied to the production environment. I’m looking forward to seeing layer1’s EVM also becomes zk-friendly.
Halo2, like zkEVM, is also an open-source project that encourages community participation and contribution. And Halo2 is the most powerful proof scheme I have seen so far, so Plonkish and Halo2 will be the focus of my study.
Comparison
This article has a comparison of the efficiency of different proof systems.
Alessandro Chiesa’s speech at ZKSummit also divided all proof schemes into three categories.
Speech video.
Summary
zkp, like bitcoin and ethereum, is the beginning of many great innovations.
Whether it is the principle behind it or the latest proof system, it is worth researching and learning.