ZK Learning Series Part 1 — Historical Principles and Industry 

by Jupiter Zheng, Research Director at HashKey Capital

 

Nowadays, there are more and more Zero-knowledge Proof projects (“ZKP”) in the blockchain industry, especially since the emergence of ZKP applications at the scaling and privacy protection levels, exposing us to a wide variety of ZKP projects. Due to the mathematical nature of ZKP, it’s become more difficult to understand ZK in-depth. Therefore, we plan to start sorting out some changes in ZKP theory and application level from scratch, and explore the impact on the crypto industry and its value with readers, and learn together from several reports, which forms the summary of our insights. This article is Part 1 of the series, which primarily introduces the development history, application and some basic principles of ZKP.

A. History of ZKP

The modern ZKP system was first conceived by Goldwasser, Micali and Rackoff in their paper The Knowledge Complexity of Interactive Proof Systems (i.e. GMR85), which was put forward in 1985 and published in 1989. This paper mainly explained how much knowledge is needed to be exchanged to prove a statement is correct after K rounds of interaction in an interactive system. If the exchanged knowledge can be zero, it classifies as a ZKP. It is assumed that the prover has unlimited resources, while the verifier has only limited resources. The problem with interactive systems is that the proof is not entirely provable mathematically, but probabilistically correct, albeit with a small probability (1/2^n).

Therefore, the interactive system is not perfect with only approximate completeness, while the non-interactive system (NP) system emerged on this basis has completeness and thus is the perfect choice for the ZKP system.

The ZKP system in the early years was not efficient and usable, so it has only existed at the theoretical level, and has only begun to flourish in the past 10 years. Following the emergence of cryptography in crypto, ZKP has been brought to the forefront and become a crucial direction. In particular, developing a general, non-interactive ZKP protocol with a limited proof size is a significant exploration direction.

Basically, ZKP aims to make a trade-off between the speed of proof, the speed of verification and the size of the proof volume. An ideal protocol is featured with rapid proof and verification and small proof volume. The volume of the former is determined by trusted set-ups.

The most significant breakthrough in ZKP was Groth’s paper Short Pairing-based Non-interactive Zero-Knowledge Arguments in 2010, which was regarded as the theoretical pioneer of the most important group of zk-SNARKs in ZKP.

The most important progress in ZKP’s application was the ZKP system used by Zcash in 2015, which achieved the protection of privacy related to transaction and amount. After that, the concepts of zk-SNARK and smart contract combined, and zk-SNARK itself developed into a very wide range of application scenarios. Among them, some important academic achievements include:

Pinocchio (PGHR13): Nearly Practical Verifiable Computation in 2013, which compresses the proof and verification time to the applicable range. This 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. This is currently the most widely used ZK basic algorithm.

Bulletproofs (BBBPWM17): Short Proofs for Confidential Transactions and More in 2017, which puts forward the Bulletproof algorithm, a very short non-interactive ZKP, which does not require trusted setups. It is applied to Monero after 6 months, which serves as a very fast combination of theory-to-application.

zk-STARKs (BBHR18): Scalable, transparent, and post-quantum secure computational integrity in 2018, which put forward a ZK-STARK algorithm protocol that does not require trusted setups. This is another eye-catching direction of ZK development. StarkWare, the most significant ZK project, was born based on this.

Other developments including PLONK, HALO2, etc. are also crucial, which improved some aspects of zk-SNARKs.

B. Overview of the Application of ZKP

The two most widespread applications of ZKP are privacy protection and scaling. Following the launch of privacy transactions and several well-known projects such as Zcash and Monero in the early days, privacy transactions have once again become a very important category, but the necessity of privacy transactions was not as prominent as the industry expected; thus, this type of representative projects have begun to gradually enter the second- and third-tier camps (not withdrawing from the historical stage). At the application level, the necessity of scaling has never been treated with importance. But with the transformation of Ethereum 2.0 (already renamed as the consensus layer) to a rollup-centric route in 2020, the ZK series has officially drawn the attention from the industry.

Privacy transactions: There are a number of projects that have implemented privacy transactions, including Zcash and Tornado that use SNARK, Monero that uses bulletproof, and Dash. Dash does not use ZKP in a strict sense, but a simple currency mixing system that can only hide the address but not the amount. We are not going to discuss this in detail here.

The transaction steps of Zcash are as follows:

• At the System Setup stage, the proof key (encrypted proof polynomial) and the verification key are generated with the help of KeyGen functions

• At the CPA stage, ECIES encryption method (Elliptic Curve Integrated Encryption Scheme) is used to generate public and private keys

• At the Minting Coins stage, the number of new coins is generated for commitment of public address and coins

• At the Pouring stage, a zk-SNARK proof is generated, which is added to the pour transaction ledger

• At the Verification stage, validators verify if Mint and Pour transaction volumes are correct

• At the Receiving stage, receivers receive coins. If the received coins are intended to be used, Pouring will be continued to form zk-SNARK verification, and steps 4–6 above are repeated to complete the transaction.

There are still limitations on the use of ZK by Zcash: since it is based on UTXO, some transaction information is only shielded, rather than totally covered up. It is also difficult to scale (combined with other applications) due to the separate network based on Bitcoin’s design. The actual usage rate of shielding (that is, privacy transactions) is less than 10%, implying that privacy transactions have not been successfully expanded.

Tornado is more widely used by using a single large mixing pool, and is based on tried-and-tested networks like Ethereum. Tornado is essentially a mixing pool using zk-SNARK, and the trusted setup is based on the Groth16 paper. Tornado Cash is featured as follows:

• Only deposited coins can be withdrawn

• No coins can be withdrawn twice

• The proof process and the coin’s Nullifier are bound, and hashes with the same proof but different Nullifiers will not allow withdrawals

• With 126-bit security, which will not be degraded due to composition

Vitalik Buterin has mentioned that, compared to scaling, privacy is relatively easy to achieve. If some scaling protocols can be established, privacy will basically not be an issue.

Scaling: The scaling of ZKs can be achieved on first-tier networks such as Mina, or on second-tier networks — that is, ZK-rollups. The original ideology of ZK-rollups might have first come from Vitalik’s post in 2018: “On-chain scaling to potentially ~500 tx/sec through mass tx validation”.

ZK-rollup has two roles, one is Sequencer, and the other is Aggregator. Sequencer is responsible for packaging transactions, while Aggregator is responsible for combining a large number of transactions and creating a rollup, and eventually forming a SNARK proof (or a ZKP based on other algorithms). This proof will be compared with the previous state of Layer1, and then updated on Ethereum’s Merkle Tree to compute the new state tree.

Pros and cons of ZK-rollup
Pros: low cost; unlike OP which can be attacked economically; no need to delay transactions; can protect privacy; can achieve finality quickly

Cons: large amount of computation required to form ZK proofs; security issues (SNARK requires a trusted setup); not resistant to quantum attacks (SNARK and STARK can); transaction order may be changed.

According to the method of data availability and proof, Starkware has a classic classification for L2 (Volition’s data availability layer can be selected on-chain and off-chain):

Nowadays, the most competitive ZK-rollup projects on the market are: Starkware’s Starknet, Matterlabs’s 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 version) and STARK, as well as EVM support (including compatibility or anything equivalent).

• Aztec has developed a generalized SNARK protocol — Plonk protocol; Aztec3 in operation may support EVM, but privacy takes precedence over EVM compatibility

• Starknet uses zk-STARK, a ZKP that does not require trusted setups, but currently does not support EVM and has its own compiler and language developer

• zkSync also uses Plonk, which supports EVM. zkSync 2.0 is EVM compatible and has its own zkEVM

• Scroll is an EVM-compatible ZK-rollup; its team is also a key contributor to the Ethereum Foundation zkEVM project

Brief discussion of EVM compatibility issues:
The compatibility between ZK system and EVM has been a headache, and general projects will normally make a compromise between the two. Those who emphasize ZK may make a virtual machine in their own system and have their own ZK language and compiler, but it will increase the learning difficulty for developers, and will become a black box since it is basically not open-source.

In general, 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 a rapid integration at the beginning, but the rapid iteration of technology in the past one to two years has raised the compatibility of EVM to a high level, and developers can achieve a certain degree of seamless migration (i.e. the Ethereum main chain to ZK-rollup). This is a very exciting development, which will affect the development ecology and competitive landscape of ZK. We will discuss this issue in detail in a later report.

C. Basic Principles of implementatoin of zk-SNARKs

Goldwasser, Micali, and Rackoff proposed that ZKPs should have three properties:

• Completeness: Every statement with reasonable witness can be verified by validators

• Soundness: Statements with unreasonable witnesses should not be verified by validators

• Zero-knowledgeness: Verification process is zero-knowledge

Therefore, in order to understand ZKP, we must start with zk-SNARK, because many current blockchain applications start with SNARK. Let’s take a look at zk-SNARKs.

zk-SNARK stands for: Zero-knowledge Succinct Non-interactive ARguments of Knowledge; Zero Knowledge: The proof process has zero knowledge and will not expose redundant information; Succinct: Validation is small; Non-interactive: non-interactive process; ARguments: The computation is sound; that is, the prover with limited computing power cannot forge the proof, and the prover with unlimited computing power can forge the proof; of Knowledge: The prover cannot construct a parameter and proof without knowing valid information.

It is impossible for the prover to construct a set of parameters and proofs without knowing the proof (Witness, such as an input to a hash function or a path that determines a Merkle-tree node).”

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

The steps are:
1. Convert the questions into a circuit

2. Compile the circuit into the form of R1CS.

3. Convert R1CS to QAP (Quadratic Arithmetic Programs) format

4. Set up a trusted setup, 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 principle, development and application of zk-SNARK, explore the development of zk-SNARK through several cases, and the relationship with zk-STARK etc.

References:

• https://ethresear.ch/t/on-chain-scaling-to-potentially-500-tx-sec-through-mass-tx-validation/3477
  
• https://blog.decentriq.com/zk-snarks-primer-part-one/
• https://vitalik.ca/general/2021/01/26/snarks.html
• https://z.cash/technology/zksnarks/

About HashKey Capital
HashKey Capital, HashKey Group’s venture capital arm, is an institutional asset manager investing exclusively in blockchain technology, digital assets and crypto-financial infrastructures. It provides accredited investors and professional investors with secure access and diversified exposure to digital assets. HashKey Capital combines the agility and independent risk-taking traditionally found in the best venture firms, while offering differentiated access to the network of relationships found in one of the largest industrial and financial conglomerates in the world.
capital.hashkey.com | ir@hashkey.com

Notes and Disclaimer
Views, information and opinions expressed in this material are those of the individuals involved and do not necessarily represent that of the HashKey Group (including any of its affiliates). While we make every effort to ensure that the information we are sharing is accurate, we welcome any comments, suggestions, or correction of errors.

This material should not be considered as an offer or solicitation to sell, buy or subscribe to any financial instruments or product, securities or any derivative instrument, or any other rights pertaining thereto. We are not acting as a financial adviser, consultant or fiduciary to you with respect to any information provided in this material. We do not express any opinion or recommendation whatsoever as to any strategies, products or any other information presented in the materials.

Any decision made by a party after accessing to this material shall be on the basis of its own research and not be influenced or based on any view expressed in this material or otherwise. This material does not address all risks. This material does not constitute investment advice or a recommendation and has been prepared without regard to individual financial circumstances, objectives or particular needs of you. You should seek their own financial, tax, legal, regulatory and other advice regarding the appropriateness or otherwise of investing in any investments and/or pursuing any investment strategies. The HashKey Group does not express any opinion as to the present or future value or price of any instruments referred to in this material.

By accessing this material, you acknowledge that the HashKey Group makes no warranty, guarantee, or representation as to the accuracy or sufficiency of the information featured in this material. The information, opinions, and recommendations presented in this material are for general information only and any reliance on the information provided in this material is done at your own risk. This material should not be considered professional advice. Moreover, the HashKey Group makes no warranty that this material, or the medium that makes it available, is free of viruses, worms, or other elements or codes that manifest contaminating or destructive properties.

By accessing this material, you acknowledge that the entire contents and design of this material, are the property of the HashKey Group, or used by the HashKey Group with permission, and are protected under applicable copyright and trademark laws. Except as otherwise provided herein, users of this material may save and use information contained in this material only for personal or other non-commercial, educational purposes. No other use, including, without limitation, reproduction, retransmission or editing, of this material may be made without the prior written permission of the HashKey Group.

Unless specifically stated otherwise, the HashKey Group does not endorse, approve, recommend, or certify any information, product, process, service, or organisation presented or mentioned in this material, and information from this material should not be referenced in any way to imply such approval or endorsement. The third party materials or content of any third party site referenced in this material do not necessarily reflect the opinions, standards or policies of the HashKey Group. The HashKey Group assumes no responsibility or liability for the accuracy or completeness of the content contained in third party materials or on third party sites referenced in this material or the compliance with applicable laws of such materials and/or links referenced herein.

The HashKey Group expressly disclaims any and all liability or responsibility for any direct, indirect, incidental, special, consequential or other damages arising out of any individual’s use of, reference to, reliance on, or inability to use, this material or the information presented in this material.