Code Talks: Application of Zero-Knowledge Proof Technology in the Blockchain Industry

Published in

ppio

10 min readNov 29, 2019

November’s Code Talk event showcased a talk about the different types of zero-knowledge proofs and how they can be applied to improve a project.

PPIO Code Talks is an open platform for high-quality presentations and discussions on blockchain technology with the aim of engaging the community and spreading ideas. The following is an adaptation of a presentation given on November 26 by Dr. Guo Xionghui of Loopring, covering the application of zero-knowledge proof technology in the blockchain industry.

One of the most important application directions of blockchain technology is that data put on the chain is open, transparent, and cannot be tampered with. Despite the security of such a system, there is still an issue. Not all data on the chain should be made public, in fact, some data should be kept private. But how does one guarantee that sensitive information like company contracts remain private?

The following article will be divided into four parts. The first is a simple summary of zero-knowledge proof technology. It has previously been covered in a previous post on ZK Rollup technology, but for those who missed that article or want a refresher, the first section will be essential. The following sections will cover three major application directions of zero-knowledge proof technology in the blockchain industry. One is a private transaction, the other is a storage proof, and the last one is a decentralized currency transaction.

Summary of Zero-Knowledge Proof Technology

I want to prove that I know that the input of a function is x and the output of this function is equal to y. However, I can’t tell you how much x is. This concept is called zero-knowledge. At the same time, I want you to believe that I know that x can calculate y. This addition concept is what is known as a zero-knowledge proof.

A zero-knowledge proof is a system that has several traits. Trait one appears if I give an honest proof. This proof can’t be falsified and must be one that anyone can verify — it is true. Another trait appears if I give a false proof. It can’t pass the proof verification system — therefore you know that it’s false. Those are two of its characteristics, a third characteristic is that it does not disclose any knowledge

1.1 Alibaba and the Forty Thieves

As taken from a previous Code Talks: Alibaba was caught by robbers. In order to save his life, he needed to prove to the robbers that he had the password to open a stone door, while at the same time, he could not tell the robbers the password. He came up with a solution: the robbers would give enough space so they couldn’t hear the password to open the door but close enough to fire an arrow if Alibaba tried to escape. From this distance, Alibaba showed the robbers the opening and closing of the stone door.

This whole process of the zero-knowledge proof is that the prover must convince the verifier that an assertion (Alibaba knows how to open the stone gate) is correct without providing any useful information to that verifier (the password of the stone gate).

1.2 Zero-Knowledge Proof Framework Structure

Generally speaking, a zero-knowledge proof framework can be divided into four steps:

First, we need to abstract the problem. Generally speaking, we will express the abstract problem as an arithmetic circuit, or understand it as a program that operates together. We can call it a circuit generating circuit. With this circuit expression, we are constructing a constraint system. There are actually several constraint systems now, but the most commonly used is R1CS, a constraint system. With this constraint system, we turn this problem into a polynomial satisfaction problem, called the QAP problem.

As far as you can imagine such a process, we first convert a specific calculation problem into a polynomial problem that can be satisfied. In the end, we will construct the algorithm of a zero-knowledge proof to construct a generated proof. In this step, there are various technical means of zero-knowledge proof. A famous example is ZK Snark, which is one of many zero-knowledge proofs.

1.2 Circuit Calculations

I want to calculate this function x ^ 3 + X + 5 which is the equation the circuit is expressing. With this circuit, I will use a constraint system to express the circuit.

After the circuit is expressed, a constraint system is generated, and then the constraint system is reduced to a QAP problem. After the QAP problem is obtained, the final proof is given by using various algorithms and systems of a zero-knowledge proof. This is the whole framework system for zero-knowledge proof.

2. ZCash Privacy Transactions

2.1 ZCash Transfer

ZCash privacy transaction is one-way a zero-knowledge proof can be applied. Its application is very simple. Sometimes when transferring money, we can’t disclose who is transferring and who is receiving, nor can we disclose the amount.

This is the problem that zCash seeks to solve. It’s called a private transfer. There are three things to hide at the same time: the amount, the receiver, and the sender. To do this, we can rely on zero-knowledge proof technology.

2.2 Note

The first step is to express the transfer as a check. We call it a note. Then we need to make a zero-knowledge proof of the note. We will also generate one that can be used by a consumer. It is important to remember that as long as we spend a certain amount of money and then generate another incoming note at the same time, the other person will get the sum of money.

As long as zero-knowledge proof is used to prove that the whole transfer results in one party sending money, the other receiving money and that the final balance reflects that, everything is fine. Anyone can get the encrypted message, and without knowing what it is, the proof can be verified. As long as proof is right, you can know that the transfer is right, even if no one knows how much has been transferred to who or from who.

2.3 Merkel Tree

Using the payment transfer listed in the previous section, we can refer to a Merkel tree. Let’s say we have to prove that I have an invoice that I can also use. This invoice will have an important data structure.

If you are familiar with blockchain technology, then you will also know, or at least have heard about Merkel trees. In fact, the Merkel tree is a hash tree. At the bottom of the tree is a hash tree, and then two more hashes are used to calculate a root hash. This is the whole Merkel tree.

With a Merkel tree we can prove that I have an invoice. I know that once a path reaches the end then the final root hash can be calculated. At the same time, the root hash can be recorded on the blockchain and can’t be tampered with. So this guarantees that I must know something before the transfer can take place.

3. FileCoin Storage Proof

Popular data storage project IPFS employs two techniques that use zero-knowledge proof.

We can first look at how IPFS not only stores raw data but also processed data.

3.1 Data Storage Method

Data must be divided into a 256-megabyte sector. The sector is 32 bytes, and then a series of transformations are performed for each of those 32 bytes. Afterward these transformations are processed, then data is stored on the hard disk. The core problem that needs to be solved is how do you prove that the file, or piece, I saved for you is the key piece.

3.2 Data Storage Proof of Replication

Proof of Replication is an ‘interactive proof system in which a prover defends a publicly verifiable claim that it is dedicating unique resources to storing one or more retrievable replicas of a data file’.

Its algorithm is to construct a Merck number for each layer of such data, and then record the root of the grinding tree of each layer of Merck number on the blockchain so that it can’t be tampered with. The Merck tree represents all the data to be stored, then I must prove that I have passed such a process to help you to have this part of the data.

3.3 Proof-of-Spacetime (PoSt)

Think of this proof as if you are coming to someone every other day of the week and asking: how are things you are saving for me? Are they still there?

If you’re saving a file for me, it’s called the proof-of-spacetime. The proof is very simple. In fact, if you didn’t record the root hash of the Merkel tree on the chain before, I will randomly sample a piece of data. Then you will need to provide Merkel evidence that you can calculate the final root hash. As long as you can provide this evidence, I know that you continue to store this data.

4. Loopring Protocol 3.0

We are working on the third version of the Loopring protocol. Our project was initiated in 2017. What we wanted at the time was to offer decentralized coin transactions on Ethereum. Then we made two versions — 1.0 and 2.0. However, the speed was too slow. On Ethereum, we could only do a maximum of 2–3 transactions per second, which is difficult to use for a commercial project. In attempting to solve this problem, we started to explore zero-knowledge proof.

4.1 ZK Rollup

The design of Loopring Protocol 3.0 relies on ZK Roll Up. Referring to the image below, if you look at the node, it denotes how much money an account has. I am likely to have a number of accounts, and each account forms a Merkel tree. A root can represent all current account world states. As long as I have a root hash, I can know that it represents all account states. All I need to do is prove that each change of state is changing the Merkel tree.

As long as I can prove the transaction through the addition and subtraction between accounts, you can trust that the transaction has been made.

This process will also involve a smart contract. The smart contract will store every root hash. At the same time, we have a relay module to collect every transaction sent by everyone. This is the tx. After collection, we can construct the zero-knowledge proof for this batch of transactions. In fact, what we need to prove is the transformation of this world state. As long as I prove this matter truthfully, you will know that everything that takes place is honest and in accordance with the rules.

If everything takes place under the chain and not on the chain, why was the previous TPS so slow? Actually it’s because all actions have to happen on the chain.

As a result, we have made some small improvements to our design. The first one is that we have stratified the Merkel tree into three layers. For example, if I am depositing a token to an address, I just need to change the balance.

If it’s a transaction type, I have to first change the trade of my transaction, then change the balance, then change the account, and then change a hierarchical operation such as the Merkel root, which can greatly reduce the size of the circuit generation.

4.3 Quad-Merkle Tree With Poseidon Hash

In general, Merkel tree is a binary tree, with only two nodes left and right, which allows us to calculate a Greek value. Our method is to change it to a quadtree, and then use a Poseidon hash at the same time. This reduces the time of generating a proof.

With these changes, we have increased the proof by 10 times. And with this whole set of solutions, we increased from the original two transactions per second to the current 1400 transactions. This is another direction in which zero-knowledge proof can be applied. We call it capacity expansion.

We are open-source and believe that our blockchain protocol must embrace the open-source spirit. You can find out more about us here.