Zero-Knowledge Proof was proposed by S. Goldwasser, S. Micali and C. Rackoff in the early 1980s.

It refers to the prover’s ability to convince the verifier that a certain assertion is correct without providing any useful information to the verifier. That is to say, the prover proves to the verifier and makes him believe that he knows or possesses a certain message, but the proof process cannot reveal any information about the proven message to the verifier.

Sudoku verification game

The Sudoku verification game is a classic example of zero-knowledge proof, written by Aviv Zohar, the leader of the founding teams of the two protocols Ghost and Specter.

The prover Alice wants to prove to the verifier Bob that she knows the solution to a certain Sudoku game, but does not want to reveal the specific content of the solution to the verifier Bob. The proof can be achieved through the following process:

1. Alice writes 9 groups of numbers 1 to 9 on 81 cards, and arranges them according to the solution arrangement when Bob avoids them, with the puzzle numbers facing up and the answer numbers facing down;

1. Bob randomly selects one of three methods for verification: row, column, or box;

1. Under the witness of Bob, Alice puts 81 cards into 9 opaque bags in groups of each row/column/palace according to Bob’s choice, shuffles the order of the cards in each bag, and hands them to Bob;

1. Bob opens 9 bags. If each bag contains 9 non-repeating numbers from 1 to 9, then this verification passes.

The probability of Alice successfully deceiving Bob by guessing in advance which verification method (row/column/house) Bob will choose is 1/3. Therefore, Bob can randomly select different verification methods each time and repeat the above proof process multiple times until Bob believes that Alice knows the solution to the Sudoku game, and Bob does not know any specific information about the solution during the entire process.

What the above game wants to prove is the solution to a Sudoku problem. Alice asks Bob to randomly select rows, columns, and nine-square grid cards each time, and collect them together and randomly shuffle them. Bob cannot know the solution to the problem by opening the bag, but he can I believe that Alice has a high probability of knowing the solution to the problem.

Since Alice and Bob can pass Bob’s verification after multiple rounds of interaction, it is called interactive zero-knowledge proof. Interactive zero-knowledge proof requires the verifier Bob to continuously send random experiments after the prover Alice puts the answer (commitment).

Suppose there is a zero-knowledge Sudoku non-interactive proof machine. This machine basically automates the Sudoku proofs of Alice and Bob, no longer requiring human interaction.

Alice only needs to put the card on the conveyor belt, and the machine will automatically choose to collect the cards by row, column, or palace, put them into the bag out of order, and then send the bag out through the conveyor belt. Bob can then open the bag and reveal the cards inside.

The machine has a control panel that opens to a series of knobs that indicate the selection (row, column, palace) for each trial.

This is called Non-Interactive Zero-Knowledge (NIZK), but it will require some additional machines or programs, and a sequence of tests that cannot be known by anyone. With such a program and test sequence, the proving machine can automatically calculate a proof and prevent any party from falsifying.

Technical principles

Zero-knowledge proof involves many cryptography and mathematical theories, including computational complexity theory content such as Computationally/Statistically Indistinguishable, Simulator, and Random Oracle models. In order to facilitate understanding, we describe the three basic properties of the zero-knowledge proof protocol in more popular language as follows:

1. Completeness: If the prover knows that the evidence can prove the correctness of the proposition, it can be trusted by the verifier with a high probability.
2. Soundness: It is difficult for a malicious prover to deceive the verifier with a wrong proposition.
3. Zero-knowledge: After the proof process is executed, the verifier only obtains the information that the prover has this knowledge, but does not obtain any information about the knowledge itself.

“Knowledge” vs “Information”

1. “Knowledge” is related to “computational difficulty”, but “information” is not;
2. “Knowledge” is related to what is publicly known, while “information” is mainly related to things that are partially public.

Zero-knowledge proof originated from interactive proof protocol. Taking Schnorr protocol as an example to analyze the principles and characteristics of interactive zero-knowledge proof. The Schnorr protocol is an identity authentication protocol and is also used by many PKI digital signature schemes today.

PKI is the abbreviation of Public Key Infrastructure. It is a standard-compliant technology and specification that uses public key encryption technology to provide a secure basic platform for the development of e-commerce.

In the Schnorr protocol, prover A proves that it possesses the private key sk corresponding to the public key pk by interacting with verifier B three times, but verifier B cannot obtain the information of the private key sk during the entire process.

Interactive zero-knowledge proof protocols rely on random attempts by the verifier and require multiple interactions between the prover and the verifier to complete. Non-interactive zero-knowledge proof reduces the number of interactions to one, enabling offline proof and public verification. For example, in zero-knowledge proof application scenarios such as blockchain, the proof usually needs to be published directly instead of relying on interactive implementation, and it needs to support multi-party public offline verification.

There are currently three mainstream algorithms in zero-knowledge proof technology:

zk-SNARK

zk-SNARK (Zero-Knowledge Succinct Non-interactive Arguments of Knowledge) is a widely used universal zero-knowledge proof scheme. By converting any calculation process into the form of several gate circuits, And use a series of mathematical properties of polynomials to convert gate circuits into polynomials, and then generate non-interactive proofs, which can realize the application of various complex business scenarios. At present, zk-SNARK has been implemented in blockchain fields such as digital currency and blockchain finance, and is currently one of the most mature universal zero-knowledge proof solutions.

The launch of zk-SNARK requires a trusted setup. A trusted setup means that in a trusted setup, multiple parties each generate a partial key to launch the network and then destroy the key. If the secrets of the keys used to create the trust setup are not destroyed, these secrets could be exploited to forge transactions through false verifications.

zk-STARK

zk-STARK (Zero-Knowledge Succinct Transparent Arguments of Knowledge), representing zero-knowledge concise and transparent knowledge argumentation), is a technical evolution of the zk-SNARK algorithm, which solves the weakness of SNARK relying on trusted settings and does not rely on it. Any trust is set up to complete blockchain verification, thereby reducing the complexity of launching the network and eliminating any risk of collusion.

Bulletproofs

Bulletproofs (Short Non-interactive Zero-knowledge Proofs protocol) take into account the advantages of SNARKs and STARKs, can run without a trusted setup, and can reduce the size of cryptographic proofs from more than 10kB To less than 1kB, the compression ratio reaches more than 80%, while reducing transaction fees by 80%. It has attracted great attention in the field due to its relatively low transaction fees, algorithm size and lack of trust.

Application of zero-knowledge proof

Zero-knowledge proof can ensure the security of data and solve many privacy issues. The proof process requires a small amount of calculation and the amount of information exchanged by both parties is greatly reduced. It has the advantages of security and efficiency. Zero-knowledge proofs were initially often used in identity verification, digital signatures, authentication protocols, etc. The emergence of blockchain has provided more new directions for the application of zero-knowledge proofs.

Ethereum scaling

Blockchain is unable to meet current needs due to its own performance issues. Zero-knowledge-based scaling solutions are expected to solve the performance bottleneck of blockchain. Scaling refers to increasing transaction speed and transaction throughput without sacrificing decentralization and security. ZK-Rollups is a Layer 2 scaling solution based on zero-knowledge proof. It improves the throughput of the blockchain by transferring calculations to the chain, that is, packaging a large number of transactions into a Rollup block and generating a valid block for the block off-chain. The smart contract on Layer 1 only needs to verify the proof to directly apply the new state, which can achieve lower Gas and higher on-chain security.

Privacy protection

In the context of blockchain, zero-knowledge proofs can be used to verify the validity of transactions without revealing the sender, recipient, amount involved, and other sensitive data in the transaction. Therefore, zero-knowledge proofs play a huge role in protecting data privacy on the chain. Typical applications include privacy L2, privacy public chains, privacy coins and privacy KYC.

Aztec Network is the first Layer 2 privacy blockchain project on Ethereum, aiming to provide privacy and scalability for centralized applications. Aztec uses a UTXO model similar to the Bitcoin account principle. In this model, the note note is the basic unit of protocol operation. When an asset is traded, the value of the note is encrypted, the note ownership changes, and the note registry will record the status of each note. The user’s AZTEC assets are all in the note registry. The sum of valid tickets owned by this user address.

Aleo is the first platform to provide complete privacy protection applications and is a public chain based on zero-knowledge proof privacy protection. The core of Aleo is ZEXE, which is decentralized private computation DPC (decentralized private computation), which separates calculation and consensus, provides zkCloud to execute transactions off the chain, and submits the proof to the chain after the execution of the transaction. Since only proofs are submitted to the chain, it is technically impossible for anyone to see or exploit knowledge of any transaction details, thus enabling transaction privacy.

Zcash is nicknamed the originator of privacy coins. The privacy of confidential transactions relies on hash functions and stream ciphers in standard cryptography. The sender, recipient, and transaction volume in the transaction record are encrypted on the chain. Users can choose whether to provide others with a viewing key (only those with this key can see the contents of the transaction), and use zk-SNARKs off-chain to verify the validity of the transaction.

zkPass is a decentralized KYC solution based on secure multi-party computation and zero-knowledge proofs, allowing users to anonymously prove their identity claims to third parties through Web2 identity credentials. For example, the Ufile Chain integrity file alliance chain platform is an alliance blockchain platform focusing on the authentication, storage, circulation, rights confirmation and privacy protection of personal information. It is an alliance chain system with authoritative institutions such as universities, enterprises, and government departments as core nodes. Ufile Chain uses zero-knowledge proof technology to ensure the privacy and security of personal information. Data users can only obtain limited information related to their business, ensuring that it is difficult for data users to obtain complete and effective plaintext user information. No one, including UfileChain officials, can obtain valid user personal information.

Summary

Thanks to the development of emerging technology applications such as blockchain and privacy computing in recent years, zero-knowledge proof technology has become an important technology for building trust and an indispensable part of the organism of blockchain.

In essence, zero-knowledge proof technology can distrust the blockchain and bring it from economic assumptions to cryptography-based assumptions to further expand native functions such as off-chain data availability and native abstract account wallets, especially for Ethereum. It provides a solution, or even the only solution, to the problems related to scalability and privacy protection that underlying chains such as Fang are facing.

Disclaimer：

1. This article is reprinted from [web3朱大胆]. All copyrights belong to the original author [小猪Go]. If there are objections to this reprint, please contact the Gate Learn team, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute any investment advice.
3. Translations of the article into other languages are done by the Gate Learn team. Unless mentioned, copying, distributing, or plagiarizing the translated articles is prohibited.