A Beginner's Guide to Zero-Knowledge Proofs: Development History, Applications, and Basic Principles

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.

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

1. Pinocchio (PGHR13) in 2013: Pinocchio: Nearly Practical Verifiable Computation, which compresses the proof and verification time to the applicable scope, is also the basic protocol used by Zcash.
2. Groth16 in 2016: On the Size of Pairing-based Non-interactive Arguments, which simplifies the size of the proof and improves the verification efficiency, is currently the most widely used ZK basic algorithm.
3. 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 a trusted setup. It will be applied to Monero 6 months later and is very fast. The combination of theory and application.
4. 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 of ZK development at present, and it is also based on Based on this, StarkWare, the most important ZK project, was born.

Other developments including PLONK, Halo2, etc. are also extremely important progress and have also made some improvements to zk-SNARK.

2. Brief description of the application of zero-knowledge proof

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

1. The System setup phase generates the proof key (encryption proof polynomial) and verification key, using the KeyGen function
2. CPA phase ECIES encryption method (Elliptic Curve Integrated Encryption Scheme) is used to generate public and private keys
3. Minting Coins stage, the number of new coins generated. Public address and coin commitment
4. In the Pouring stage, a zk-SNARK certificate is generated and added to the pour transaction ledger.
5. In the Verification phase, the verifier verifies whether the transaction volumes of Mint and Pour are correct.
6. In the Receiving stage, 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 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:

1. Only the deposited coins can be withdrawn.
2. No coins can be withdrawn twice
3. The proof process is bound to the currency’s nullification notification (Nullifier). The hash of the same proof but different Nullifier will not allow the withdrawal of coins.
4. The security is 126-bit and will not be degraded due to composition.

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:

1. Advantages: low cost, unlike the OP who will be economically attacked, no need to delay transactions, privacy can be protected, and finality can be achieved quickly
2. Disadvantages: Forming ZK proof requires a large amount of calculation, security issues (SNARK requires a trusted setting), not resistant to quantum attacks (SNARK, STARK can), transaction order may be changed

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).

1. Aztec has developed a generalized SNARK protocol-Plonk protocol. The running Aztec3 may support EVM, but privacy takes precedence over EVM compatibility.
2. 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.
3. zkSync also uses plonk and supports EVM. zkSync 2.0 is EVM compatible and has its own zkEVM
4. Scroll, an EVM-compatible ZK rollup, the team is also an important contributor to the Ethereum Foundation’s zkEVM project

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.

3. Basic principles of ZK SNARK implementation

Goldwasser, Micali and Rackoff proposed that zero-knowledge proofs have three properties:

1. Completeness: Every statement with reasonable witnesses can be verified by the verifier
2. Soundness: Every claim with only unreasonable witnesses should not be verified by the verifier
3. Zero-knowledge: 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, 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.

1. Zero Knowledge: The proof process is zero knowledge and does not expose redundant information.
2. Succinct: Small verification size
3. Non-interactive: non-interactive process
4. ARguments: The calculation is reliable, that is, the prover with limited computing power cannot forge the proof, and the prover with unlimited computing power can forge the proof.
5. of Knowledge: The prover cannot construct a parameter and proof without knowing valid information
6. It is impossible for the prover to construct a set of parameters and proof without knowing the witness (such as the input of a hash function or a path to determine a Merkle-tree node).

The proof principle of Groth16’s zk-SNARK is as follows:

Source: https://learnblockchain.cn/article/3220

The steps are:

1. Convert 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 a trusted setup and generate random parameters, including PK (proving key) and 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, review the development of ZK-SNARK through several cases, and explore its relationship with zk-STARK.

Disclaimer：

1. This article is reprinted from [HashKey Capital]. All copyrights belong to the original author [HashKey Capital]. If there are objections to this reprint, please contact the Gate Learn team, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute any investment advice.
3. Translations of the article into other languages are done by the Gate Learn team. Unless mentioned, copying, distributing, or plagiarizing the translated articles is prohibited.