Zero-Knowledge Proofs: The Simplest Explanation on the Internet

History, Principle, Realization

Overview

Cryptography is the cornerstone of blockchain technology, and zero-knowledge proofs within the field of cryptography have received deep attention to as it deeply fits with the technical characteristics and needs of blockchain development

In this article, we will introduce the history, concepts, principles, technical implementation, and development status of zero-knowledge proofs in the simplest language and form.

History and Origin

Cryptography is an ancient science dating back more than 2,000 years, and its development history can be divided into the following stages.

Classical cryptography

Cryptography in this period was mainly used in the military field, where the main consideration was how to effectively transmit the ciphertext while preventing it from being intercepted and deciphered by the enemy. The ‘Vigenere Cipher’ invented by an Italian cryptographer named Giovan Battista Bellaso in the 16th century was an important milestone in the development of classical cryptography. It uses a phrase as the key, and each letter in the phrase determines a substitution table, and the ‘Vigenere Cipher’ uses each substitution table cyclically to complete the change from plaintext to ciphertext letters. E.g: Plaintext: ilovebitcoin Key: satoshi

For the first letter i, take the ith row and sth column to get A. For the second letter l, take the lth row and ath column to get L… in turn, and finally get the ciphertext: ALHJWIQLCHWF. It can be seen that it is very difficult to crack such a password without the help of a computer and knowing the key.

Recent cryptography

The real beginning of this stage came from a series of papers published by Shannon in the late 1940s, especially ‘Communication Theory of Secrecy Systems’ in 1949, which pushed the thousands of years of cryptography into a scientific track based on information theory. Cryptography moved from art to science.

The major breakthrough of this period was the emergence of Data Encryption Standard (DES), which can only be cracked by exhaustive methods, even today. The DES encryption algorithm became popular worldwide and widely used in financial and other commercial fields.

Modern cryptography

In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman of MIT proposed the asymmetric encryption algorithm RSA (An acroynym for Rivest, Shamir and Adleman), which effectively solved the problem of key transmission and marked the modern stage of cryptography with a hundred schools of thought.

In 1989, MIT researchers Goldwasser, Micali, and Rackoff introduced the concept of ‘zero-knowledge proof’. Little did they know that the emergence of blockchain technology a few years later would completely activate the application of zero-knowledge proofs, which provides an excellent solution for blockchain technology. The method characteristics of zero-knowledge proofs and the system characteristics of blockchain technology have reached a perfect fit.

Zero-knowledge proof and zkSNARK

Zero-knowledge proof is proof to others that there is a high probability that someone does know or own something without revealing that something that someone knows or possesses. zkSNARK is the most widely used type of zero-knowledge proof in the blockchain, and its full name is ‘zero-knowledge Succinct Non-Interactive Arguments of Knowledge.

In this section, we will borrow an example to introduce these two concepts in a simple way. Alice, Bob, and Charlie loved to solve Sudoku problems. Sudoku is a game in which players need to reason out the numbers of all remaining spaces based on the known numbers on a 9×9 board and satisfy that the numbers in each row, column, and block (3x3) contain 1 through 9 and are not repeated.

One day, Bob, who was working on an especially difficult Sudoku that Alice designed complained to Alice that it must be an unsolvable question. Alice devised an ingenious ‘zero-knowledge proof’ method to prove that she really knew the solution without telling Bob the actual solution.

The Proof

Alice retrieved 81 blank index cards and wrote a single digit (from 1 to 9) on each card. Then she placed the card number representing the puzzle face up and the card number representing the answer to the puzzle face down, in a 9-by-9 matrix.

The Random Challenge

Next, how can Bob confirm that this is the correct solution? Alice let Bob randomly chose one of the rows, columns, or blocks for verification. If he chose a row, put the 81 cards into 9 opaque bags in 9 rows, shake them well and ensure the index cards inside were mixed well.

The Verification

Bob opened 9 opaque bags in turn. If each opaque bag contains 9 cards with numbers 1–9, the verification is passed, otherwise, the verification fails.

The following are characteristics of the interaction between Alice and Bob.

Succinct

Although there are three situations in the Sudoku that need to be verified (row, column, block), one of them is required to be verified each time. This effectively reduces the verification workload and the actual proof provided to the verifier is a much smaller proof than the original proposition. This is succinctness.

Repeated

After repeating this random verification step, we assume that Alice is lucky, every time she can guess in advance which verification method Bob will choose, and use this to simulate a solution. The probability of her passing the verification once is 1/3, the probability of passing 2 verifications is 1/9, and the probability of passing 10 verifications is only 1/59049. After tirelessly performing 20 verifications, Bob reluctantly admitted that Alice knew the solution to the answer, because the probability of Alice passing the verification by luck is only 1 in 3.5 billion (This is why the zero-knowledge proof is a proof that holds in probability).

The Simulation

Then, Charlie also complained to Alice about the unsolvable problem. Alice and Bob repeated the proof just now, but they didn’t expect Charlie’s approval. Charlie proposed a loophole in this proof. If Bob and Alice are in the same group, each time Bob will tell Alice in advance the verification method he wanted to choose, then Alice can easily simulate a proof without a solution to pass these tests.

Non-Interactive Proofs

It is impossible for everyone who holds this kind of suspicion to repeat the random verification, and the three friends designed a magical machine. Alice only needs to submit the card once, and the machine can be set up according to the initial settings. The verification sequence is automatically repeated for these cards and the verification changed from interactive to non-interactive. We should note that it does not mean that the process of random experiments is not repeated in non-interactive proofs. It’s just that the random point is not given by the verifier, but by a trusted third party in the initialization phase. In this way, the prover can give the proof directly, and the verifier only needs to verify the proof. There is no longer any need for interaction between the verifier and the prover.

Trusted Setup Ceremony

The most interesting and important part is the initial setup of the verification sequence. Before the machine is started, there will be a row of setting knobs through which the verification method for each round can be selected. When setting these knobs, everyone enters the room where the machine is placed in turn, selects a knob and sets it, and then uses an iron box to completely weld the knob so that other people cannot see or change the selection of the knob. In order to make the initial setting as credible as possible, the friends invited the town mayor, the primary school principal and the police chief, the three most respected elders in the town, to participate in the setting ceremony. Everyone believed that they would never participate in fraud. Therefore, They call it the ‘Trusted Initial Setup Ceremony’.

A simple non-interactive zero-knowledge proof machine for Sudoku is born!

Technical realization of zkSNARK

In the previous section, we have understood the basic concepts and principles of zero-knowledge proof and zkSNARK. In this section, let’s take a look at the technical implementation of zkSNARK. It can be said that the whole implementation process is quite tedious and obscure, and requires certain background knowledge. This section only tries to explain the core idea clearly without sticking to overly complicated mathematical derivations Consider X³ + X + 5 = 35, which obviously has a solution of 3. Now, how does the prover prove to the verifier that he knows the solution to the equation is 3 without telling the verifier the solution?

First, let’s translate the equation into computer language, which is easy to do.

def qeval(x):

y = x**3 return x + y + 5

Next, we flatten the above code that can only do one thing at a time, like x = y op z. After slapping the code flat, the code becomes the following statement:

sym_1 = x * x y = sym_1 * x sym_2 = y + x ~out = sym_2 + 5

Then, we introduce the R1CS. R1CS is a sequence consisting of a set of three vectors (a, b, c) with a solution vector s, s satisfying s·a * s·b — s·c = 0. In this example, the structure of s is (~one, x, ~out, sym_1, y, sym_2), which can be seen to consist of a special ~one, the solution of the equation x, the output of the equation ~out and a series of intermediate variables (The variable on the left side of the equal sign after the statement is flattened), whose order is not important, as long as it is guaranteed to be ordered.

We transform the sentence into the following form to facilitate us to solve abc:

1：x * x - sym_1 = 0 2：sym_1 * x - y = 0 3：y + x - sym_2 = 0 4：sym_2 + 5 - ~out = 0

And we can easily get the three vectors corresponding to the first formula:

a = [0, 1, 0, 0, 0, 0] b = [0, 1, 0, 0, 0, 0] c = [0, 0, 0, 1, 0, 0]

The derivation process is actually very simple. We know that to satisfy s·a * s·b — s·c = 0, then corresponding to the first formula x * x — sym_1 = 0, only when s·a = x, s·b = x, s·c = sym_1. And s = (~one, x, ~out, sym_1, y, sym_2), then a is equal to 1 at the position of x, and the rest of the positions are equal to 0 to get (0, 1, 0, 0, 0, 0).

You may be baffled by the above series of dazzling changes. What are we doing? The essence of verifying that s·a * s·b — s·c = 0 for each equation is that we are verifying that the correct calculation is obtained at each step, and if we can verify that each step is correct, then the final result must be correct as well.

Each of the above steps may seem to be rounding off, because the solution x of the equation is contained in s itself, and the verifier only needs to substitute x for verification. But from another perspective, we have constructed a way to separate proof and verification through this series of transformations. In the proof process, the prover needs to know the solution and generate a series of intermediate results, while the verifier only needs to verify that the solution vector consisting of its series of results satisfies a set of constraints, without caring about the solution.

There is only one question left to be solved, and that is whether there is a way to prevent the verifier from seeing the naked solution x while still being able to proceed with the verification process. The answer is yes, and we can do this by a series of mathematical means, such as elliptic curves, bilinear pairwise operations, and exponential knowledge assumptions.

Because the derivation process is so complicated that we don’t describe it in this paper. The entire technical implementation process of zkSNARK is shown in the figure below, and someone who needs more details can read Vitalik’s article given in the references.

The development status of zero-knowledge proof

Zero-knowledge proof protocol

There are currently several protocols for zero-knowledge proofs. Each agreement represents a path to achieve zero-knowledge proof. Different roads will eventually produce different effects.

Among them, the most secure is the STARKs algorithm, which does not rely on mathematical puzzle assumptions, is quantum-resistant, and implements transparent universal strings. The snarks protocol with the smallest Proof size is the groth16 algorithm. Plonk is an algorithm in the SNARK protocol with a moderate Proof size and security.

SNARKs protocol algorithm

As the most widely used SNARKs in blockchain technology, many protocol algorithms with their characteristics have been developed.

• Groth16: Groth16 is currently the fastest and smallest data-volume zk-SNARK being used in Zcash, etc. CRS of Groth16 is not universal and its settings need to be bound to a specific circuit. It is often used by new zk-SNARKs to compare performance because of its speed and the small amount of data it proves. Groth16 paper

  
  

• Sonic: Sonic is an early universal zk-SNARK protocol that supports universal and upgradeable reference strings. The paper was published in January 2019. Sonic has a fixed proof size but high verification cost, which theoretically allows multiple proofs to be verified in batches for better performance. Many of the new zk-SNARKs listed below are based on Sonic. Sonic paper

  
  

• Fractal: Fractal is a zk-SNARK that allows recursion. The transparent setup is achieved by preprocessing the circuit. The maximum size of the proof is 250KB, which is much larger than the proofs generated by other builds. Fractal paper

  
  

• Halo: Halo supports recursive evidence organization without trusted settings, and unlike other new zk-SNARK builds, Halo’s verification time is linear. Halo paper

  
  

• SuperSonic: An improved version of Sonic, the first transparent zk-SNARK that is practical in terms of verification time and proof data volume. SuperSonic paper

  
  

• Marlin: An improved version of Sonic, the proof time is reduced by 10 times, and the verification time is reduced by 4 times. Marlin paper

  
  

• Plonk: An improved version of Sonic, the proof time is reduced by 5 times. Plonk paper

  
  

  Hardware cost

  
  

  The current lack of dedicated hardware of zero-knowledge proofs has led to high hardware costs, which are about $0.00031 per transaction when renting cloud servers under full load and about $0.0031 per transaction under empty load. Vitalik has proposed an idea that when the Ethereum consensus mechanism is changed to PoS and not so much mining hardware is required, the computing power can be converted to support zero-knowledge proofs after modification, which may effectively reduce the running cost of zero-knowledge proofs.

  
  

  
  

  Outlook for the future

  
  

  Zero-knowledge proofs are already making a big difference in the blockchain field, with examples including Zcash (ZEC) — the first anonymous cryptocurrency to implement zkSNARK, and zk Rollups, a major type of Layer 2 solution.

  
  

  The DeGate team will also use zero-knowledge proofs in our product implementation. With its powerful features, we will transfer orderbook matchmaking of transactions to Layer 3, so that users can place, cancel, and deal orders instantly, and place and cancel orders for free. Then, the proof of the order will be generated and sent back to Layer 2 for verification. This allows DeGate to inherit the security of Ethereum while hiding the key information of the order and effectively reducing the consumption of Gas fees on Layer 2. Our ultimate goal is to make the user experience of DeGate comparable in both operation and fee consumption to that of centralized exchanges.

  
  

  References

  
  

1. Aviv Zohar — The Incredible Machine
2. Vitalik Buterin — Quadratic Arithmetic Programs: from Zero to Hero