Original source: HashKey Capital
first level title
1. The History of Zero-Knowledge Proofs
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 interaction 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 (prover) has unlimited resources, while the verifier (verifer) has only limited resources. The problem with interactive systems is that the proof is not entirely mathematically provable, but probabilistically correct, although the probability is small (1/2^n).
Therefore, the interactive system is not perfect, but only approximately complete. The non-interactive system (NP) system born on this basis is complete, and it becomes the perfect choice for the zero-knowledge proof system.
The zero-knowledge proof system in the early years was lacking in efficiency and usability, so it has always remained at the theoretical level. It has not begun to flourish until the last 10 years. With cryptography becoming prominent in crypto, zero-knowledge proof has come to the forefront and has become A very important direction. In particular, developing a general-purpose, non-interactive, proof-size-limited zero-knowledge proof protocol is one of the most critical directions of exploration.
Basically, zero-knowledge proof is a trade-off between the speed of proof, the speed of verification, and the size of the proof volume. The ideal protocol is fast proof, fast verification, and small proof volume.
The most important breakthrough of 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 progress in the application of zero-knowledge proof is the zero-knowledge proof system used by Z-cash in 2015, which realized the protection of transaction and amount privacy. Later, it developed to the combination of zk-SNARK and smart contracts, and zk-SNARK entered the Wider application scenarios.
Some important academic achievements during this period include:
Pinocchio (PGHR13) in 2013: Pinocchio: Nearly Practical Verifiable Computation, which compresses proof and verification time to the applicable scope, is also the basic protocol used by Zcash.
Groth16: On the Size of Pairing-based Non-interactive Arguments in 2016, which simplifies the size of the proof and improves the verification efficiency, is currently the most widely used ZK basic algorithm.
Bulletproofs (BBBPWM17) Bulletproofs: Short Proofs for Confidential Transactions and More in 2017 proposed the Bulletproof algorithm, a very short non-interactive zero-knowledge proof that does not require trusted settings, and it will be applied to Monero after 6 months, which is very fast Linking theory to application.
In 2018, zk-STARKs (BBHR18) Scalable, transparent, and post-quantum secure computational integrity proposed a ZK-STARK algorithm protocol that does not require trusted settings. This is another eye-catching direction for ZK development. Based on this, StarkWare, the most important ZK project, was born.
first level title
2. Brief introduction to the application of zero-knowledge proof
The two most widely used applications of zero-knowledge proofs are privacy protection and capacity expansion. In the early days, with the launch of private transactions and several well-known projects such as Zcash and Monero, private transactions once became a very important category. However, because the necessity of private transactions was not as prominent as the industry hoped, this type of representative projects began to slow down. Slowly enter the camp of the second and third tiers (not quit the stage of history). At the application level, the need for capacity expansion has been raised to the limit. As Ethereum 2.0 (which has been renamed the consensus layer) transforms into a rollup-centric route in 2020, the ZK series has officially returned to the industry's attention and has become the focus.
Private transactions: There are many projects that have implemented private transactions, including Zcash using SNARK, Tornado, Monero using bulletproof, and Dash. Strictly speaking, Dash does not use ZKP, but a simple and crude currency mixing system, which can only hide the address but not the amount, which is skipped here.
image description
Source: Demystifying the Role of zk-SNARKs in Zcash
In the System setup phase, the proof key (encryption proof polynomial) and the verification key are generated, with the help of the KeyGen function
The ECIES encryption method (Elliptic Curve Integrated Encryption Scheme) in the CPA stage is used to generate public and private keys
In the MintingCoins phase, the number of new coins generated. Commitment of public addresses and coins
In the pouring phase, a zk-SNARK proof is generated, and the proof is added to the pour transaction book
In the Verification phase, the verifier verifies whether the transaction volume of Mint and Pour is correct
In the receiving phase, the receiver receives coins. If you want to use the received coins, continue to call Pouring to form zk-SNARK verification, repeat the above steps 4-6 to complete the transaction.
Zcash still has limitations in using zero-knowledge, that is, it is based on UTXO, so some transaction information is only shielded, not really covered up. Difficult to scale (combine with other applications) because of its separate network based on Bitcoin's design. The usage rate of shielding (that is, private transactions) is less than 10%, indicating that private transactions have not been successfully expanded. (from 2202)
The single large mixing pool used by Tornado is more general and based on a "proven" network like Ethereum. Torndao is essentially a currency mixing pool using zk-SNARK, and the trusted setting is based on the Groth 16 paper. Features that Tornado Cash can provide include:
Only deposited coins can be withdrawn
No coin can be withdrawn twice
The certification process is bound to the nullification notification (Nullifier) of the currency, and hashes with the same certification but different Nullifiers will not allow withdrawals
Security has 126-bit security and will not be degraded due to composition
Vitalik mentioned that compared with capacity expansion, privacy is relatively easy to achieve. 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 layer network, such as Mina, or it can be done on the second layer network, that is, zk-roll up. The idea of ZK roll up may first come from Vitalik’s post in 2018, On-chain scaling to potentially ~500 tx/sec through mass tx validation.
image description
Source: Polygon
Advantages and disadvantages of ZK rollup:
Advantages: low cost, unlike OP who will be attacked by the economy, does not need to delay transactions, can protect privacy, and quickly achieve finality
image description
Source: Ethereum research
image description
Source: Starkware
The most competitive ZKrollup 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 selection of SNARK (and its improved version) and STARK, as well as the support for EVM (including compatibility or equivalent).
Aztec has developed a generalized SNARK protocol-Plonk protocol. Aztec3 in operation may support EVM, but privacy is prior to EVM compatibility
Starnet uses zk-STARK, a zkp that does not require trusted settings, but currently does not support EVM, and has its own compiler and development language
zkSync also uses plonk and supports EVM. zkSync 2.0 is EVM compatible and has its own zkEVM
Scroll, an EVM-compatible ZK rollup, the team is also an important contributor to the zkEVM project of the Ethereum Foundation
Briefly discuss EVM compatibility issues:
first level title
3. The basic principle of ZK SNARK implementation
Goldwasser, Micali, and Rackoff proposed that zero-knowledge proofs have three properties:
Completeness: Every statement with a reasonable witness can be verified by the verifier
Soundness: Every statement that has only unreasonable witnesses should not be verified by the verifier
Zero-knowledgeness: The verification process is zero-knowledge
So in order to understand ZKP, we start with zk-SNARK, because many current blockchain applications start with SNARK. First of all, 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.
Zero Knowledge: The proof process is zero-knowledge and will not expose redundant information
Succinct: small validation size
Non-interactive: non-interactive process
ARguments: Calculations are reliable, that is, certifiers with limited computing power cannot forge proofs, and certifiers with unlimited computing power can forge proofs
of Knowledge: The prover cannot construct a parameter and proof without knowing valid information
For the prover, it is impossible to construct a set of parameters and proofs without knowing the evidence (Witness, such as the input of a hash function or a path to determine the Merkle-tree node). "
image description
Source： https://learnblockchain.cn/article/3220
The steps are:
1. Transform the problem into a circuit
2. Flatten the circuit into the form of R1CS.
3. Convert R1CS to QAP (Quadratic Arithmetic Programs) format
4. Establish trusted setup, generate random parameters, including PK (proving key), VK (verifying key)
5. Proof generation and verification of zk-SNARK
In the next article, we will start to study the principles and applications of zk-SNARK, use several cases to see the development of ZK-SNARK, and explore its relationship with zk-STARK.
Reference：
https://ethresear.ch/t/on-chain-scaling-to-potentially-500-tx-sec-through-mass-tx-validation/3477
https://blog.polygon.technology/zkverse-why-zero-knowledge-rollups-need-a-new-consensus-mechanism/
https://blog.decentriq.com/zk-snarks-primer-part-one/
IOS
Android