Interpreting Zero-Knowledge Proofs

This article includes the following: 1. What is a zero-knowledge proof? 2. Why do we need zero-knowledge proofs? 3. Application scenarios of zero-knowledge proof. 4. How zero-knowledge proofs work. 5. Classification and application cases of zero-knowledge proofs. 6. Flaws of zero-knowledge proofs.

PART.01

What is Zero Knowledge Proof

**Zero-Knowledge Proof (Zero-Knowledge Proof) was proposed by S.Goldwasser, S.Micali and C.Rackoff in the early 1980s. It refers to the ability of the prover to convince the verifier that a certain assertion is correct without providing any useful information to the verifier. **

To give a simple example, Puff said that he is a chef and can cook Chinese, Korean, and Italian dishes. My mother expressed disbelief because I hadn't cooked a single meal at home. So how can I prove that I can cook at this time?

I can have my mom watch me finish a meal in the kitchen and prove that I really know how to cook. But I don't want my mother to see me making a mess in the kitchen while cooking, or I will be nagged again, so what should I do? I went into the kitchen alone, and my parents were waiting outside. After I finished cooking and packed up, I brought out the dishes. This still proves that I can cook. As for what ingredients I used, what seasonings I put in, and how messy the kitchen was during the process, I don’t need it. As long as my mother knows that I can cook a meal, it will prove that I am not lying.

Simply put: Zero-knowledge proofs are trying to establish trust between two parties with the minimum amount of information exchanged. Without revealing more information, one party (the prover, the prover) can prove to the other party (the verifier, the verifier) that one thing is true.

PART.02

Why do you need zero-knowledge proof

Protect private data

Rogue vendors want to collect as much user data as possible, and some of the receipts that have nothing to do with their business also ask users for permissions (really hate them). They put the collected user personal identity information (PII) in a centralized database. These databases are very vulnerable to attack. Once attacked, the personal identity information will be leaked, which will lead to various fraud problems.

Authentication

When using the website, the user can prove to the website that he has a private key, or knows an answer that only he knows. The website does not need to know the key, but can confirm the user's identity through zero-knowledge proof. Through decentralized storage, the server can Prove to users that data is properly preserved and not leaked.

Computing compression and blockchain expansion

In the traditional block architecture, the same calculation is repeated many times, such as signature verification, transaction validity verification, smart contract execution and other places, because with the proof of calculation, the same calculation does not need Repeated many times, the calculation process can be proved compressed by zero-knowledge technology.

**Zero-knowledge proof really solves the trust of data, realizes the protection of private data, and makes the blockchain truly realize the concept of trusting machines. **

PART.03

Application scenario of zero-knowledge proof

**The main application scenarios of zero-knowledge proof are: anonymous payment, identity proof, verifiable calculation, and anonymous voting. **

Anonymous payment

Cryptocurrency transactions are publicly visible on the public chain. Users transact anonymously, but are also linked to real-world identities (for example, by including ETH addresses in their Twitter or GitHub profiles), or their real-world identities can be obtained through on-chain and off-chain data analysis.

There are specific "privacy coins" designed for completely anonymous transactions. Examples include Zcash and Monero, which mask transaction details including sender/receiver addresses, asset type, amount, and transaction timeline. By incorporating zero-knowledge techniques into protocols, privacy-focused blockchain networks allow nodes to verify transactions without having access to transaction data.

Zero-knowledge proofs have also been applied to anonymous transactions on public blockchains. Such as Tornado Cash, a decentralized non-custodial service that allows users to conduct private transactions on Ethereum. Tornado Cash uses zero-knowledge proofs to obfuscate transaction details and guarantee financial privacy.

personal I.D

On the premise of not revealing specific identity information, a specific identity certificate is issued. For example, using online services requires proving the user's identity and right to access those platforms. This usually requires providing personal information such as name, email address, date of birth, etc.

Zero-knowledge proofs can simplify the authentication of platforms and users. ZK proofs are generated using public inputs (eg, data proving that the user is a member of the platform) and private inputs (eg, the user's details), which users can simply present to verify their identity when they need access to services. For example, to prove whether the user is an adult or not, there is no need to issue ID card information, or the specific year of birth, but only the conclusion of whether the user is eighteen years old or not.

Verifiable Calculation

When the user's device cannot support the required computing, or the cost of computing locally is too high, third-party services will be considered. These third-party services can quickly and cheaply return output results to users (such as Chainlink's oracle service). Zero-knowledge proofs in this scenario allow third-party computing power providers to output computational integrity proofs to ensure that the output results received by users are correct.

Anonymous Voting

Under the premise of not revealing the specific identity, the user's identity is proved and the voting authority is obtained to complete the voting.

PART.04

How Zero-Knowledge Proofs Work

Zero-knowledge proofs were first proposed by MIT's Shafi Goldwasser and Silvio Micali in a 1985 paper titled "Knowledge Complexity of Interactive Proof Systems". The author mentioned in the paper that it is possible for a prover to convince a verifier of the authenticity of the data without revealing the specific data. Zero-knowledge proof can be interactive, that is, the prover has to prove the authenticity of the data once to each verifier; it can also be non-interactive, that is, the prover creates a proof, and anyone who uses this proof Can be verified. There are currently many implementations of zero-knowledge proofs, such as zk-SNARKS, zk-STARKS, PLONK, and Bulletproofs. Each method has its own advantages and disadvantages in terms of proof size, prover time, and verification time.

Zero-knowledge proof has three basic features, namely:

• Integrity: If the statement is true, the honest verifier can trust that the honest prover does have the correct information.
• Reliability: If the statement is false, no dishonest prover can convince an honest verifier that he has the correct information.
• Zero-knowledge: If the statement is true, the verifier knows nothing except that the statement is true from the prover.

In summary, to create a zero-knowledge proof, the verifier needs to make the prover perform a sequence of operations that the prover can only perform correctly if it knows the underlying information. If the prover fools a result, then the verifier is very likely to find and prove his mistake in the verification.

PART.05

Classification of zero-knowledge proofs

Zero-knowledge proof can be divided into "interactive zero-knowledge proof" and "non-interactive zero-knowledge proof" according to the interaction method.

Interactive zero-knowledge proof

The prover and verifier need to interact multiple times, the verifier will continue to ask questions to challenge the prover, and the prover will continue to respond to these challenges until the verifier is convinced.

Interactive Zero-Knowledge Proof - Colorblind Game

Alice is colorblind, but Bob is not colorblind. Bob has two balls of the same size and shape, but the colors of these two balls are different. One ball is blue and the other ball is red. Since Alice is Color blind, so Alice can't tell if the two balls are the same, Bob needs to prove to Alice that the two balls are different. Here, Alice is called the verifier. He needs to verify whether Bob’s statement is correct or not. Bob is called the prover. He needs to prove his statement (there are two balls with different colors). In the case of the colors of two balls, prove to Alice that the colors of the two balls are different, which is consistent with the definition of zero-knowledge proof.

Alice picks up two balls in front of Bob, the blue ball in the left hand and the red ball in the right hand, and then puts both hands behind her back so that Bob cannot see the ball in Alice's hand, and Alice randomly exchanges the balls in her left and right hands behind her back , after the exchange is completed, Alice stretches out her hand and asks Bob whether the two balls have exchanged positions. If Bob can see the color on the ball, then every time Alice changes the position of the ball, Bob can correctly answer Alice's question.

For the first time, Alice secretly exchanged the position of the ball in her hand, and then Alice asked Bob if she exchanged the position of the ball. If Bob answered Yes, then Alice has a 50% probability that Bob can distinguish the colors of the two balls, because Bob There is a 1/2 chance of getting it right, so Alice can try again. If Bob answers No, then Alice can be sure that Bob cannot distinguish the colors of the two balls.

The second time, Alice does not swap the positions of the balls in her hands, and then Alice asks Bob if he switched the positions of the balls. If Bob answers No, then Alice has a 75% probability of believing that Bob can distinguish the colors of the two balls.

After the first iteration, Alice can say that the assertion stated by Bob has a 50% probability of being true. If Bob answers correctly the second time, then Alice can say that Bob's statement is true with a probability of 75%. After the third iteration, it will be 87.5%. If Bob has passed the check for n consecutive times, Alice has a probability of 1-(1/2)^n and can think that what Bob said is true, and the two balls are indeed red and blue.

Interactive zero-knowledge proof is a probability-based verification method. The verifier asks questions to the prover based on certain randomness. If the prover can give the correct answer, it means that the prover has a high probability of having all his Claimed "knowledge". Zero-knowledge proof is not a proof in the mathematical sense, because it has a small probability of error, and the deceitful prover may deceive the verifier through false statements. In other words, zero-knowledge proofs are probabilistic proofs rather than deterministic proofs, but there are techniques that can reduce errors to negligible values.

This interactive approach has some limitations:

• Each verification requires a whole lengthy process.
• Both the prover and the verifier need to be present at the same time, whether online or face-to-face.
• Only one verifier can be trusted. If multiple verifiers are to be trusted, each verifier needs to go through a proof process.

NON-INTERACTIVE ZERO-KNOWLEDGE PROOF

Interactive zero-knowledge proofs require two parties to be readily available and interact repeatedly. Even if the verifier is confident that the prover is honest, the proof cannot be used for independent verification (computing a new proof requires a new set of messages between the prover and verifier).

In order to solve the problems faced by interactive zero-knowledge proofs, non-interactive zero-knowledge proofs came into being. Manuel Blum, Paul Feldman and Silvio Micali proposed the first interactive zero-knowledge proofs - where the prover and verifier have a shared secret. This allows a prover to prove their knowledge of some information without providing the information itself.

Non-interactive zero-knowledge proof---Sudoku game

Sudoku is a mathematical game originated in Switzerland in the 18th century. It is a logic game that uses paper and pen to perform calculations. Players need to deduce the numbers of all the remaining spaces based on the known numbers on the 9×9 board, and satisfy that the numbers in each row, each column, and each thick-line palace (3*3) contain 1-9. repeat.

To prove to Bob that she has solved a Sudoku puzzle, Alice creates a tamper-proof machine for this. Alice puts the generated Sudoku answer into the machine, and the machine can send a proof to Bob. Alice's machine follows the following publicly verifiable protocol: First, Alice puts the unsolved original Sudoku puzzle into the machine, and the three puzzle cards in Sudoku face up. Next, Alice puts his answer face-down on the corresponding cell on the machine, also placing three cards in each cell. Finally, Bob obtains the proof from the machine, and the machine returns 27 bags to Bob:

The machine takes out 9 cards from each row of Sudoku, mixes them separately and puts them into a bag, there are 9 rows in total, and uses 9 bags; the machine takes out 9 cards from each row of Sudoku, mixes them up and puts them in Put them into a bag, there are 9 columns in total, and 9 bags are used; the machine takes out the cards in each thick line palace (3*3) in Sudoku, mixes them up and puts them into a bag, a total of 9 , use up 9 bags;

Bob checks each of the 27 bags individually, and if the cards in each bag contain the numbers 1 to 9, and none of the numbers are missing or repeated, then Bob can confirm that Alice has indeed solved the Sudoku and that Bob has not taken any numbers from the machine. Any knowledge about the Sudoku solution can be obtained from the returned proof, because the data returned by the machine to Bob's bag is randomly shuffled.

Non-interactive zero-knowledge proofs overcome some of the shortcomings of interactive zero-knowledge proofs, do not require lengthy online interactions, can be trusted by many people (or even everyone), and the proof is always valid, but additional machines and programs may be required to determine the experimental Order. For example, in the case of Sudoku, it is up to the program to decide which column or row to verify. The verification sequence must be kept secret, otherwise the verifier may pass the verification without knowing the real "knowledge".

Interactive zero-knowledge proof VS non-interactive zero-knowledge proof

Each verification of an interactive proof requires a new round of communication, and a non-interactive proof requires only one round of communication between the participants (prover and verifier). The prover passes the secret information to a special algorithm to calculate the zero-knowledge proof. This proof is sent to the verifier, who uses another algorithm to check whether the prover knows the secret.

Non-interactive proofs reduce the communication between the prover and verifier, making ZK proofs more efficient. Also, once a proof is generated, it can be verified by anyone else (with access to the shared secret and verification algorithm).

**PART.**06

Technical solutions and applications of zero-knowledge proof

Zero-knowledge technology allows developers to not only take advantage of the security of underlying blockchains such as Ethereum, but also improve transaction throughput and speed for dApps, and at the same time put users' personal information off-chain to protect user privacy. Transactions will be packaged and uploaded to the chain to reduce the cost of use for end users. Ultimately, projects can leverage these capabilities to create advanced dApps that not only rival Web2 systems in performance, but also maintain the decentralization benefits of Web3.

(Image source: Chainlink)

In Layer2, zk-rollup will package multiple transactions together and publish them on the Layer1 blockchain, and will also publish a zero-knowledge proof to verify the validity of the calculation. Proofs posted on-chain are also called "validity proofs". **Validity proof technology is divided into two types: SNARKs and STARKs. **

zk-SNARs

The full name of SNARK is "zero-knowledge succinct non-interactive argument on knowledge" (succinct non-interactive zero-knowledge proof). This is a cryptographic proof that the file is small and easily verifiable. It generates a cryptographic proof using an elliptic curve that assumes that the discrete logarithm of a random elliptic curve element cannot be found from a public base point. The calculation cost of the elliptic curve is lower than the hash function of STARK, so the gas cost of the SNARK protocol is lower.

Case：Zcash, Loopring, zkSync1.0, zkSync 2.0, Zigzag, Mine

zk-STARK

The full name of STARK is "zero-knowledge scalable transparent argument of knowledge" (zero-knowledge scalable, transparent knowledge proof). This cryptographic proof requires almost no interaction between the prover and verifier. The biggest advantage of STARKs over SNARKs is that the proof time is shorter and it is easier to expand. In addition, since STARKs use a hash function, they are also resistant to quantum attacks.

It is worth mentioning that the inventor of STARKs is Eli Ben-Sasson, the co-founder of StarkWare, the team that also developed StarkEx and StarkNet.

Examples: StarkEx, StarkNet, Immutable X, Starkware

PART.07

Disadvantages of zero-knowledge proof

High hardware cost

Depending on the proof system, the zero-knowledge proof generation process is different. But in the end, you will face difficult problems: multiplication of large number vectors (fields or groups), especially multiscalar multiplication (MSM) with variable and fixed bases, or fast Fourier transform (FFT) and inverse FFT.

Both MSM and FFT are slow operations. In a system where both FFT and MSM exist, about 70% of the proof generation time is spent on MSM and 30% on FFT. Hardware acceleration is required to implement in complex calculations. It is generally considered that the most important technology for ZK hardware acceleration is FPGA rather than GPU (due to cost and energy efficiency) or ASIC (due to their inflexibility and long iteration cycle). Top-of-the-line FPGAs are about 3x cheaper than top-of-the-line GPUs. Also, FPGAs are more than 10 times more energy efficient than GPUs, mainly because GPUs need to be connected to a host device, which consumes a lot of power.

Verification Cost

Verifying the proof requires a lot of complex calculations, which also increases the computational cost. For example, ZK-rolluos need to pay about 500,000 gas to verify a single AK-SNARK proof on Ethereum, and ZK-STARKs require even higher fees.

Trust assumption

The premise of zero-knowledge proof is that both parties are honest and want to know the real answer, and will not falsify data. In ZK-SNARK, generating public parameters once can be reused by parties participating in the zero-knowledge protocol, which means that the data provided by the participants is correct by default.

But in fact, users have no way to evaluate the honesty of participants, even if participants input false data, users must believe it. There is no trust assumption in ZK-STARK, and now, researchers are working on non-trusted settings for ZK-SNARKs to improve the security of the proof mechanism.

Quantum Computing Threat

ZK-SNARK uses the Elliptic Curve Digital Signature Algorithm (ECDSA) for encryption. It seems that the ECDSA algorithm is safe at present, but the development of quantum computers in the future is likely to crack this algorithm.

It is generally believed that ZK-STARK will not be threatened by quantum computing because it is encrypted using anti-collision hashing. Unlike ECDSA's public-private key pair, anti-collision hashing is more difficult to be cracked by quantum computing.