Original source:secondary title

overview

overview

When studying the working principle of the blockchain system, we need to understand various cryptography knowledge, such as secp 256 k 1 , which is a curve and asymmetric signature algorithm, which is used for signatures in the bitcoin and ethereum systems and verify the account. For example, sha 256 is a hash algorithm used to compress variable-length information into fixed-length codes. Such as base 58, which can convert the information encoding into a string represented by printable characters. For example, ECDH, which is a Diffie-Hellman key exchange algorithm, is used to securely exchange communication keys between P2P nodes.

ZKP was first proposed in 1985. However, it has not found a large-scale application scenario for a long time, so the development of technology is very slow. Until the birth of Bitcoin in 2009, people found that it was very suitable for solving the privacy and scalability problems in the blockchain. Since then, a lot of capital and talents have been invested in the development and engineering application of this technology. There are many implementations of ZKP, such as: Groth 16, PlonK, STARK, etc., and no real industry standard has emerged so far. This article will take stock of the technical characteristics of various ZKP implementations, hoping to bring help to your study, research and engineering development .

ZKP application field

secondary title

1. Privacy certificate

Tornado Cash is a coin mixer running on Ethereum. It uses ZKP to prove the nodes on the Merkle-Tree. Users can deposit a fixed amount of tokens into the fund pool, and then use the Proof generated by ZKP to prove that they have deposited funds. But there is no need to disclose the transaction information when you deposit.

secondary title

2. Computing Outsourcing

zksync 1.0 is a good example. It performs Ethereum token transfers and transactions off-chain, and then submits the results to nodes. By verifying the ZKP proof, the node can know whether it is calculated according to the method it claims.

secondary title

3. Data compression

Mina is another example. In many high-speed blockchain systems, the transaction data is very large. The system needs to keep all the blocks for the verification of the consensus protocol. Therefore, the system has extremely high requirements for hardware, and permanent storage means that blocks Chain nodes will need to continuously increase disk space and data indexing capabilities. At this time, ZKP can be used to compress the verification data. Mina compresses the ledger to 11 KB through recursive zero-knowledge proof, but it can still verify the correctness of the block.

first level title

The proof system is the underlying algorithm implementation of ZKP, which can be divided into two types: interactive and non-interactive:

secondary title

1. Interactive proof system

The interactive proof system consists of two parties, called the Prover (P for short) and the Verifier (V for short), where P knows a certain secret (such as the secret key of the public key cryptosystem or a square root of the quadratic residue x), P hopes to convince V that he does hold the secret. Interactive proof consists of several rounds. In each round, P and V may need to send messages to each other based on messages received from each other and a result calculated by themselves. A typical way is that V sends a query to P in each round, and P makes a response to V. After all rounds are executed, V decides whether to accept P's proof according to whether P can correctly answer the query sent by itself in each round.

2. Non-interactive proof system

In the above-mentioned interactive proof system, P and V do not interact, and the proof is generated by P directly to V, and V directly verifies the proof. This kind of proof system is called non-interactive proof system (NIZK).

The proof system we use in the blockchain is generally NIZK, the node in the blockchain is the verifier V, and the end user or the two-layer network (Layer 2) is the prover P.

The reference link [ 1 ] at the end of the article describes the NIZK schemes and characteristics that have been published publicly in the past ten years.

• Bulletproofs

  In practical engineering applications, we mainly focus on performance and versatility, so we make a more detailed classification and comparison of some common proof systems, see the reference link at the end of the article [2]:

  Features: Concise proof size, no need for trusted settings, but proof generation and verification take a long time.

• SNARKs (Succinct Non-interactive ARguments of Knowledge)

  Representative projects: Bulletproofs, Halo, Halo 2.

  Features: The size of the proof is concise, and the proof verification time is relatively short, but each circuit needs to be trusted.

• SNORKs (Succinct Non-interactive Oecumenical (Universal) aRguments of Knowledge)

  Representative project: Groth 16.

  Features: Compact proof-of-size, only one trusted setup is required for all circuits.

• STARKs (Succinct (Scalable) Transparent ARguments of Knowledge)

  Representative projects: Sonic, PlonK, Marlin, Plonky 2.

  Features: The proof is very large, does not require trusted settings, and has good scalability.

The above classification is not absolute. For example, the Halo/Halo 2 project, they also borrowed a lot of ideas from Plonk in their design. In addition, SNORKs are usually classified into SNARKs because they all require trusted settings.

3. Performance comparison

(See the reference link at the end of the article [3])

first level title

circuit programming

• The circuit is the business logic implementation of the ZKP system, and the development of ZKP applications requires circuit programming. Why is the ZKP logic code called a "circuit"? There are mainly the following reasons:

• The code of the ZKP proof will be converted into a series of expressions R 1 CS with simple constraints, and then converted into a huge polynomial QAP using Lagrange interpolation method, which is finally constrained in the form of gate circuits.

• Similar to a hardware circuit, all branches of code will be executed together.

We don't need to use cryptography to implement ZKP applications from scratch. There are many development libraries that have implemented these underlying proof systems. We only need to focus on the implementation of business logic. Of course, each library has a different level of abstraction, some need to learn the expressions describing the circuit, and some can be easily implemented only by defining the code according to the process.

secondary title

• libsnark

1. Commonly used development libraries

The general proof system, basic circuit library and application examples are implemented in C++ language.

Proof system: BBFR 15, BCCT 12, BCCT 13, BCGT V1 3, BCIOP 13, BCT V1 4 a, BCT V1 4 b, CT V1 5, DFGK 14, Groth 16, GM 17, GGPR 13, PGHR 13.

• gnark

Link: https://github.com/scipr-lab/libsnark.

A proof system implemented in Go, providing a high-level API to design circuits.

Proof system: Groth 16, PlonK.

• bellman

Link: https://github.com/consensys/gnark.

A proof system implemented in Rust that provides a circuit interface, infrastructure, and some basic circuit implementations, such as boolean and numerical abstractions.

Proof system: Groth 16.

• snarkjs

Link: https://github.com/zkcrypto/bellman.

A proof system implemented in Javascript and WASM that can be used to trust setup, generate proofs, and verify proofs. snarkjs uses iden 3's own circom compiler to compile the circuits defined by the DSL.

Proof system: Groth 16, PlonK.

• ethsnarks

Link: https://github.com/iden3/snarkjs.

Implemented in Python, proofs can be generated in the user's browser, using Ethereum smart contracts as validators. At present, the project development is not active, and it may be a better choice to use Circom in the same scenario.

Proof system: Groth 16.

• bulletproofs

Link: https://github.com/HarryR/ethsnarks.

A proof system implemented in Rust with single and aggregate range proofs, strongly typed multi-party computations, and a programmable constraint system API for proving arbitrary statements is in development.

Proof system: bulletproofs.

• halo 2 

Link: https://github.com/dalek-cryptography/bulletproofs.

A proof system based on a Rust implementation, maintained by the ZCash team. Halo 2 is specific to PLONKish, allowing very direct control over how circuits are represented in arithmetic operations, making it ideal for writing highly optimized circuits.

Link: https://github.com/zcash/halo 2.

secondary title

2. Development process

Taking gnark as an example, a typical workflow is as follows:

1) Use code to describe the problem to be solved.

2) Compile into R 1 CS constraint system.

3) Make credible settings on R 1 CS to get Proving key and Verify key.

5) The verifier uses the Verify key to verify the Proof.

special language for circuit programming

secondary title

• Cairo

1. Based on the Ethereum platform

Cairo is a programming language for writing provable programs, in which one party can prove to another that a certain computation was performed correctly. Cairo and similar proof systems can be used to provide scalability to blockchains. StarkNet uses the Cairo programming language for its infrastructure and for writing StarkNet contracts.

Proof system: STARK.

• Zokrates

Link: https://www.cairo-lang.org/docs/.

ZoKrates uses DSL to describe circuits and provides some commonly used circuit libraries, which can help you use verifiable calculations in DApps, from standardizing your programs in high-level languages ​​to generating calculation proofs, and then verifying these proofs in Solidity.

Proof system: GM 17, Groth 16, Marlin.

• Circom

Link: https://zokrates.github.io/.

The Circom language uses DSL to describe circuits, and can cooperate with snarkjs to generate proofs in user browsers, using Ethereum smart contracts as verifiers.

Proof system: Groth 16, PlonK.

• Noir

Link: https://iden 3.io/circom.

Aztec's Rust-based privacy programming language uses a DSL to describe circuits, allowing safe and seamless construction of privacy-preserving zero-knowledge circuits.

Proof system: PlonK.

• zkEVM

Link: https://noir-lang.org/index.html.

Currently, zkSync, Polygon, Scroll, Starkware and other teams are working on the realization of zkEVM, and have made significant progress.

secondary title

• zkApp (Mina)

2. Based on the public chain platform

zkApps are Mina Protocol's smart contracts powered by zero-knowledge proofs. zkApps can perform arbitrarily complex computations off-chain while only charging a fixed fee to send the generated zero-knowledge proofs to the chain to verify this computation, unlike other blockchains that run computations on-chain and use variable gas fees Contrary model. zkApps are written in Typescript.

Proof system: PlonK.

• LEO (Aleo)

Link: https://docs.minaprotocol.com/zkapps.

Leo is a functional, statically typed programming language purpose-built for writing private applications. Designed for developers, it can be built intuitively on top of the Aleo blockchain, providing the foundation for a private, decentralized ecosystem.

Link: https://leo-lang.org/.

first level title

ZKP common security issues

• In the past few years, the SlowMist security team has conducted circuit and application security audits for many well-known ZKP products, including ZKSwap, Zkdex, Zksafe, etc., and found a number of medium and high-risk vulnerabilities. Application has a deeper understanding. The common security problems found by the SlowMist security team in the ZKP application audit are:

Trust parameter risk
In order to use zk-SNARKs, a common set of parameters is required, called the Common Reference String (CRS). But the creation of these parameters also produces some private parameters, and if a party obtains these private parameters, they can forge proofs.

In addition, the process of generating the CRS needs to be audited to ensure that there are no random number backdoors, or that private parameters are not intentionally preserved. Using zk-SNORKs also requires ensuring that the Structured Reference String (SRS) is trusted.

• The security risks in the trusted configuration stage can be solved by using secure multi-party computing (MPC). The characteristic of MPC is that as long as any participant can participate honestly, the final calculation result obtained through this multi-party computing system is credible.

static code security

• This part is mainly due to security issues caused by non-standard coding, such as: unchecked parameters, unprocessed return values, numerical overflow, unchecked boundaries, etc. If the language for writing circuits is C/C++, there will also be a risk of memory overflow .

Supply Chain Attack Risk

• The supply chain risk mainly comes from the use of vulnerable code bases, such as: old version warehouses. Usually, ZKP applications also need to be used in conjunction with the client or the Web front end, and this part is also vulnerable to hackers in various ways.

logical error

• Logic errors are the most likely errors in circuit implementation. It is necessary to check whether the circuit design meets the requirements in combination with the requirements document.

double spend attack

• Wrong design may lead to double-spending attacks. For example, some ZKP libraries have scalability risks. Attackers can use known Proofs to generate different Proofs. If the design is improper, it will lead to double-spending attacks.

prove forgery

• Effective proof is the primary problem to be solved by ZKP, ensuring completeness and reliability, that is, "false cannot be true, true cannot be false", so if a circuit can create a false proof, it is usually due to a loophole in the underlying library, usually we It is recommended that the project party use a public audited ZKP library and use a stable release version.

side channel attack

• If the circuit is not designed properly, different private information may have different computing characteristics, and the attacker may guess the private input data through the public input or proof.

circuit constraint failure

• Inappropriate circuit expressions may result in unconstrained variables.

special value attack

• Some special input values ​​may bypass the system's validation logic, such as: 0, null, etc.

Privacy input guessing

• For applications such as Tornado Cash, if the input information can be guessed, it will lead to serious privacy leakage problems. At this time, strict auditing of the input data is required to ensure that it cannot be guessed.

Some projects may have special administrator privileges, once the privileges are illegally used, project funds and user assets will be stolen.

• Smart Contract Risk

Smart Contract Risk

first level title

Summarize

Summarize

Finally, thanks to Safeheron, a leading one-stop digital asset self-custody service provider, for its professional technical advice.

Reference link:

[ 1 ]. https://en.wikipedia.org/wiki/Zero-knowledge_proof

[ 2 ]. https://github.com/matter-labs/awesome-zero-knowledge-proofs

[ 3 ].https://docs.google.com/presentation/d/1gfB6WZMvM9mmDKofFibIgsyYShdf0RV_Y8TLz3k1Ls0/edit