This text includes the following: 1. What is Zero-Knowledge Proof? 2. Why do we need Zero-Knowledge Proof? 3. Applications of Zero-Knowledge Proof. 4. How does Zero-Knowledge Proof work? 5. Classification and application cases of Zero-Knowledge Proof. 6. Defects of Zero-Knowledge Proof.
BlockingRT. 0 1
What is Zero-Knowledge Proof
Zero-Knowledge Proof, which was proposed by S.Goldwasser, S.Micali and C.Rackoff in the early 1980s, refers to the situation where the prover convinces the verifier that a certain proposition is correct without providing any useful information to the verifier.
- Mint Ventures: zkSync Top Dex Showdown, Syncswap vs iZiswap
- In-depth analysis of the differences between Eigenlayer and Cosmos ICS and their impact on ETH security
- Overview of Binance Labs investment strategy: DeFi and infrastructure lead the way
For example, suppose that I claim to be a great cook who can make Chinese food, Korean food, and Italian food. My mother does not believe me because I have never cooked a meal at home. How can I prove that I can cook?
I can let my mother watch me cook a meal in the kitchen, which proves that I can cook. However, I do not want my mother to see me making a mess in the kitchen, otherwise she will nag me again. So what can I do? I go into the kitchen alone, and my parents wait outside. When I finish cooking and cleaning up the kitchen, I bring the food out. This still proves that I can cook. As for what ingredients I used, what spices I added, and whether I made a mess in the kitchen during the process, none of that matters. As long as my mother knows that I can cook a meal, it proves that I did not lie.
In simple terms: Zero-Knowledge Proof attempts to establish trust between two parties with the minimum amount of information exchange. Without revealing more information, one party (the prover) can prove to the other party (the verifier) that something is correct.
BlockingRT. 0 2
Why do we need Zero-Knowledge Proof
Protecting privacy data
Rogue vendors try to collect as much user data as possible, and some of them require users to grant permissions for irrelevant receipts (which is really annoying). They then put the user’s personally identifiable information (PII) that we collect in a centralized database, which is very easy to attack. Once attacked, personal identity information is leaked, leading to various fraud problems.
Authentication
When using a website, users can prove to the website that they own a private key or know an answer that only they know. The website does not need to know the key, but can confirm the user’s identity through zero-knowledge proof, and through decentralized storage, the server can prove to the user that the data is properly saved and not leaked.
Computing Compression and Blockchain Expansion
In traditional blockchain architecture, the same computation is repeated multiple times, such as signature verification, transaction validity verification, and smart contract execution. Because of the proof of computation, the same computation does not need to be repeated multiple times, and the computation process can be compressed through zero-knowledge technology proof.
Zero-knowledge proof truly solves data trust, realizes privacy data protection, and also truly realizes the vision of trust machine of blockchain.
BlockingRT. 0 3
Application scenarios of zero-knowledge proof
The main application scenarios of zero-knowledge proof are: anonymous payment, identity proof, verifiable computation, and anonymous voting.
Anonymous payment
Cryptocurrency transactions are publicly visible on the public chain. Users conduct transactions anonymously, but they are also linked to real-world identities (for example, by including an ETH address in a Twitter or GitHub profile), or they can obtain the user’s real-world identity through on-chain and off-chain data analysis.
There are specific “privacy coins” designed for completely anonymous transactions. For example, Zcash and Monero will shield transaction details, including sender/receiver addresses, asset types, quantities, and transaction schedules. By incorporating zero-knowledge technology into the protocol, privacy-centric blockchain networks allow nodes to verify transactions without accessing transaction data.
Zero-knowledge proof is also applied to anonymous transactions on public blockchains. For example, Tornado Cash, a decentralized non-custodial service, allows users to conduct private transactions on Ethereum. Tornado Cash uses zero-knowledge proof to obfuscate transaction details and ensure financial privacy.
Identity proof
Specific identity feature proofs can be issued without revealing specific identity information. For example, online services require proof of a user’s identity and the right to access these platforms. This usually requires providing personal information such as name, email address, date of birth, etc.
Zero-knowledge proofs can simplify identity verification for both platforms and users. Using public inputs, such as data that proves a user is a member of a platform, and private inputs, such as a user’s detailed information, a ZK proof is generated that the user can simply present when accessing a service to verify their identity. For example, a proof can be generated to verify if a user is of legal age without revealing their ID information or specific birth year, only the conclusion of whether they are over 18.
Verifiable computation
When a user’s device is unable to support the required computation or when local computation is too expensive, third-party services are considered. These third-party services can quickly and inexpensively return output results to the user, such as Chainlink’s oracle service. In this scenario, zero-knowledge proofs allow third-party computing providers to output a proof of computation integrity to ensure that the output result received by the user is correct.
Anonymous voting
Without exposing specific identities, it is possible to prove a user’s identity and obtain voting rights to complete voting.
BlockingRT. 04
How Zero-Knowledge Proofs Work
Zero-knowledge proofs were first proposed by Shafi Goldwasser and Silvio Micali of MIT in a 1985 paper entitled “The Knowledge Complexity of Interactive Proof Systems.” The authors noted that it was possible for a prover to convince a verifier of the truthfulness of data without revealing the specific data. Zero-knowledge proofs can be interactive, meaning the prover must prove the truthfulness of the data to each verifier, or non-interactive, meaning the prover creates one proof that anyone can use to verify. Zero-knowledge proofs have multiple implementation methods, such as zk-SNARKS, zk-STARKS, PLONK, and Bulletproofs, each with its own advantages and disadvantages in proof size, prover time, and verification time.
Three basic properties of zero-knowledge proofs:
-
Completeness: If the statement is true, then an honest verifier can be convinced by an honest prover that they truly possess the correct information.
-
Soundness: If the statement is false, then no dishonest prover can convince an honest verifier that they possess the correct information.
-
Zero-knowledge: If the statement is true, then the verifier learns nothing except that the statement is true from the prover.
To create a zero-knowledge proof, the verifier needs to have the prover perform a series of operations, and the prover can only correctly perform them if they know the underlying information. If the prover guesses a result incorrectly, the verifier is very likely to discover and prove their mistake during verification.
BlockingRT. 0 5
Classification of Zero-Knowledge Proofs
Zero-knowledge proofs can be classified into “interactive zero-knowledge proofs” and “non-interactive zero-knowledge proofs” based on their interaction mode.
Interactive Zero-Knowledge Proofs
The prover and verifier need to interact multiple times, with the verifier repeatedly questioning the prover to challenge them and the prover continuously responding to these challenges until the verifier is convinced.
Interactive Zero-Knowledge Proof – Color Blind Game
Alice is color blind, but Bob is not. Bob has two balls that are the same size and shape but are different colors, one is blue and the other is red. Since Alice is color blind, she cannot tell if the two balls are the same, so Bob needs to prove to Alice that the two balls are different. Here, Alice is the verifier who needs to verify Bob’s statement’s correctness, and Bob is the prover who needs to prove his statement (that there are two balls of different colors). Bob needs to prove to Alice that these two balls are of different colors without Alice being able to determine the color of the balls. This is consistent with the definition of a zero-knowledge proof.
Alice picks up two balls in front of Bob, one blue and one red, then puts them behind her back, randomly switches them in her hands, and asks Bob if the two balls switched places. If Bob can see the color of the balls, then every time Alice switches the balls’ positions, Bob can answer Alice’s question correctly.
The first time, Alice secretly switched the balls’ positions, and then asked Bob if the balls had switched places. If Bob answered “Yes,” Alice had a 50% chance of believing that Bob could distinguish the colors of the two balls because Bob had a 1/2 chance of guessing correctly. Therefore, Alice could perform the test again. If Bob answered “No,” Alice could be certain that Bob could not distinguish the two balls’ colors.
For the second time, Alice did not swap the position of the balls in her hand, and then Alice asked Bob if he swapped the position of the balls. If Bob answers “No”, then Alice has a 75% chance of believing that Bob can distinguish the colors of the two balls.
After the first iteration, Alice can say that the probability that Bob’s statement is true is 50%. If Bob answers correctly the second time, then Alice can say that the probability that Bob’s statement is true is 75%. After the third iteration, it will be 87.5%. If Bob passes the test n times in a row, then Alice has a probability of 1-(1/2)^n of believing that Bob is telling the truth, and that there are indeed two balls of different colors, one red and one blue.
Interactive zero-knowledge proofs are a probabilistic way of verification. The verifier asks questions to the prover based on a certain randomness. If the prover can give the correct answers, it means that the prover probably has the “knowledge” that he claims to have. Zero-knowledge proofs are not mathematical proofs because they have a small probability of error, and deceiving provers may deceive verifiers with false statements. In other words, zero-knowledge proofs are probabilistic proofs rather than deterministic proofs, but there are also techniques that can reduce the error to a negligible value.
This interactive method has some limitations:
-
Each verification requires the entire lengthy process to be performed.
-
Both the proving party and the verifying party must be present at the same time, whether online or in person.
-
Can only be trusted by one verifier. If you want to trust multiple verifiers, you need to go through the proof process for each verifier.
Non-interactive zero-knowledge proofs
Interactive zero-knowledge proofs require two parties to be available and interact repeatedly. Even if the verifier is convinced that the prover is honest, the proof cannot be used for independent verification (computing a new proof requires a new message between the prover and verifier).
To solve the problems faced by interactive zero-knowledge proofs, non-interactive zero-knowledge proofs have emerged. Manuel Blum, Blockingul Feldman, and Silvio Micali proposed the first interactive zero-knowledge proof, in which the prover and verifier have a shared secret key. This allows the prover to prove their knowledge of certain information without providing the information itself.
Non-interactive zero-knowledge proof—Sudoku game
Sudoku is a logic game originated from Switzerland in the 18th century, which is a mathematical game played with pen and paper. Players need to deduce the numbers of all remaining blank spaces on a 9×9 board based on the known numbers and make sure that each row, column, and 3×3 block contains all numbers from 1 to 9 without repetition.
To prove that she has solved a Sudoku puzzle, Alice created an tamper-proof machine. Alice put her solved Sudoku into the machine, and the machine can send the proof to Bob. Alice’s machine follows a publicly verifiable protocol: First, Alice puts the unsolved original Sudoku puzzle into the machine, with three cards for each puzzle cell facing up. Then, Alice puts her answers on the corresponding cells, also with three cards for each cell, but facing down. Finally, Bob asks the machine for the proof, and the machine returns 27 bags:
The machine takes out 9 cards from each row of the Sudoku, mixes them up, and puts them into a bag, using 9 bags in total; The machine takes out 9 cards from each column of the Sudoku, mixes them up, and puts them into a bag, using 9 bags in total; The machine takes out 9 cards from each 3×3 block of the Sudoku, mixes them up, and puts them into a bag, using 9 bags in total;
Bob checks these 27 bags separately. If all bags contain cards with numbers from 1 to 9, and no number is missing or repeated, then Bob can confirm that Alice has indeed solved the Sudoku, and Bob has not gained any knowledge about the solution from the proof returned by the machine because the data in the bags is randomized.
Non-interactive zero-knowledge proof overcomes some of the drawbacks of interactive zero-knowledge proof and does not require lengthy online interaction. It can be trusted by many people (even everyone) and the proof is always valid, but additional machines and programs may be needed to determine the order of experiments. For example, in the Sudoku example, the program decides which row or column to verify. The verification sequence must be kept secret, otherwise the verifier may pass the verification without knowing the true “knowledge”.
Interactive Zero-Knowledge Proof VS Non-Interactive Zero-Knowledge Proof
Interactive proofs require a new round of communication for each verification, while non-interactive proofs only require one round of communication between participants (prover and verifier). The prover passes 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 information.
Non-interactive proofs reduce communication between the prover and the verifier, making ZK proofs more efficient. Additionally, once a proof has been generated, anyone else (who has access to the shared key and verification algorithm) can perform verification.
BlockingRT. 06
Technical Solutions and Applications of Zero-Knowledge Proofs
Zero-knowledge technology allows developers to take advantage of the security of underlying blockchains such as Ethereum, while also improving transaction throughput and speed for dApps, and keeping user personal information off-chain to protect user privacy. Transactions are packaged and uploaded to the chain to reduce end-user costs. Ultimately, projects can use these features to build advanced dApps that not only rival Web2 systems in performance, but also maintain the decentralization advantages of Web3.
(Image source: Chainlink)
In Layer2, zk-rollup will bundle multiple transactions together and publish them to the Layer1 blockchain, along with a zero-knowledge proof that verifies their validity. The proof published to the chain is also called a “validity proof”. There are two types of validity proof technology: SNARKs and STARKs.
zk-SNARKs
SNARK stands for “zero-knowledge succinct non-interactive argument on knowledge.” This is an encryption proof that is small in size and easy to verify. It uses elliptic curves to generate an encryption proof that assumes that the discrete logarithm of random elliptic curve elements cannot be found from a public base point. The computational cost of elliptic curves is lower than that of the hash function used in STARK, so the gas cost of the SNARK protocol is lower.
Examples: Zcash, Loopring, zkSync1.0, zkSync 2.0, Zigzag, Mina
zk-STARKs
STARK stands for “zero-knowledge scalable transparent argument of knowledge.” This encryption 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 scale. In addition, because STARKs use hash functions, they are also resistant to quantum attacks.
It is worth mentioning that the inventor of STARKs is Eli Ben-Sasson, who is the co-founder of StarkWare. This team also developed StarkEx and StarkNet.
Case studies: StarkEx, StarkNet, Immutable X, Starkware
BlockingRT. 0 7
Disadvantages of zero-knowledge proofs
High hardware costs
Depending on the proof system, the process of generating zero-knowledge proofs differs. However, they all face the problem of multiplication of large number vectors (fields or groups), especially multi-scalar multiplication (MSM) of variable base and fixed base, or fast Fourier transform (FFT) and inverse FFT.
The operation speed of MSM and FFT is slow. In systems where both FFT and MSM are involved, about 70% of the proof generation time is spent on MSM, and 30% of the time is spent on FFT. Hardware acceleration is required to achieve complex calculations. FPGAs are generally considered the most important technology for ZK hardware acceleration, rather than GPUs (due to cost and energy efficiency) or ASICs (due to their inflexibility and long iteration cycles). Top FPGAs are about three times cheaper than top GPUs. Moreover, the energy efficiency of FPGA is more than 10 times higher than that of GPU, mainly because GPU needs to be connected to the host device, which consumes a lot of electricity.
Verification costs
Verifying proofs requires a large amount of complex calculations, which also increases the computational cost. For example, ZK-rolluos requires about 500,000 gas to verify a single AK-SNARK proof on Ethereum, and the cost for ZK-STARKs is even higher.
Trust assumptions
The prerequisite for zero-knowledge proofs is that both parties are honest, eager to know the true answer, and will not falsify data. In ZK-SNARK, generating public parameters once can allow parties participating in the zero-knowledge protocol to reuse them, assuming the data provided by the participants is correct.
In fact, users have no way to evaluate the honesty of the participants, and even if the participants input false data, users must trust them. There is no trust assumption in ZK-STARK, and now researchers are making non-trusted settings for ZK-SNARKs to improve the security of the proof mechanism.
Quantum computing threat
ZK-SNARK uses elliptic curve digital signature algorithm (ECDSA) for encryption, which currently appears to be secure, but the development of future quantum computers is likely to crack this algorithm.
It is generally believed that ZK-STARK is not threatened by quantum computing because it uses collision-resistant hashing for encryption, which is different from ECDSA’s public-private key pairs and more difficult for quantum computing to crack.
Like what you're reading? Subscribe to our top stories.
We will continue to update Gambling Chain; if you have any questions or suggestions, please contact us!
