# Evolution of zk-proof

###### tags: `thread`

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

## Disruptive innovation

There are two types of innovation, one is to improve efficiency and make things can do better; The second is [disruptive innovation](https://en.wikipedia.org/wiki/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)

## What is ZKP

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)

## The history

The earliest zk-proof is interactive proof, such as the example of F(x) = 0, Alice and Bob both know 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%


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](https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/) 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"

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 that 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

## Evolution of proving systems

### Groth16

The earliest zk-snark proof scheme is [Groth16](https://eprint.iacr.org/2016/260) proposed in 2016, both zcash and filecoin are used, among which filecoin is mainly to prove itself [stored file content is valid](https://research.protocol.ai/sites/snarks/)

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](https://github.com/iden3/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](https://eprint.iacr.org/2019/099) 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

### Plonkish

Also in 2019, there appeared the [Plonk](https://eprint.iacr.org/2019/953) and [Merlin](https://eprint.iacr.org/2019/1047) 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](https://eprint.iacr.org/2020/315) 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

### Halo2

Halo2 is also based on UltraPlonk

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](https://eprint.iacr.org/2019/1021) 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

### Comparisons

This [article](https://medium.com/coinmonks/comparing-general-purpose-zk-snarks-51ce124c60bd) has a comparison of the efficiency of different proof systems


Alessandro Chiesa's [speech](https://www.youtube.com/watch?v=-EkUn4iD8Z8) at ZKSummit also divided all proof schemes into three categories



## Conclusions

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

[Thread](https://twitter.com/LuozhuZhang/status/1530984087061929984?s=20&t=hf32T6kwnUQiTjAV1MfiLA)