Table of Contents
- What is Zero-Knowledge Proof?
- How Does Zero-Knowledge Proof Work?
- Types of Zero-Knowledge Proofs
- Zero-Knowledge Proofs in Blockchain Applications
- Use Cases of Zero-Knowledge Proofs
- Challenges of Zero-knowledge Proofs
Zero-knowledge proof helps to prove that one party (the prover) know an information is true to another party (the verifier) without revealing any additional information.
There are two types of Zero-knowledge proofs being used on the blockchain currently, ZK-SNARK and ZK-STARK.
StarkWare is an L2 network that uses ZK-STARK and is not only cheap and fast, but also private and decentralized as well.
zkSync is an L2 network that uses ZK-SNARK and is also cheap and fast, but requires a trusted setup environment.
Optimistic rollups such as Arbitrum and Optimism are currently more popular but in the future ZK-rollups may win as the technology evolves.
Zero-knowledge proof may help to bring in the wave of users thanks to its privacy features which are likely important to businesses and users.
The growth in popularity of free internet applications used by billions of people worldwide has resulted in most user information and data being controlled by large technology companies, often resulting in an abuse of users’ privacy.
Blockchain technology, like Ethereum, was created to bring control back to the users where a user data is owned by them as well. However, apart from being pseudo anonymous, it does not have many ways to protect the privacy of users.
For example, if a user purchases something from someone with his wallet address, his wallet address is now known by that someone, and he will know everything that the user did in the past and the future, including what else he bought, or how much he has, etc, creating a real privacy concern for real-world adoption.
In this article, we will dive into zero-knowledge proofs, how it works, and how it can help us.
What is Zero-Knowledge Proof?
Simply put, zero-knowledge proofs (ZKP) uses encryption to prove something is true without revealing more than necessary, greatly improving privacy.
ZKP was invented in 1985 and is popularly defined as “A zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that something is true, without revealing any information apart from the fact that this specific statement is true.”
There are two main types of zero-knowledge proofs, interactive and non-interactive. We will provide some examples of ZKP later to make it easier to understand.
With the growing popularity of blockchains, ZKP is becoming popular due to the great benefits it brings when implemented together with blockchain technology as it will improve privacy, speed, and security, without impacting decentralization.
But how effective is it in real life and could it be the answer to our data privacy issues?
ZKP is a type of cryptographic evidence that allows a “prover” to demonstrate to a “verifier” if the prover is aware of certain values, without disclosing the actual answer to the verifier.
The zero-knowledge as a concept comes from the fact that no information is provided by the prover but still able to convince the verifier that the truth is being told. This secures your communication so that no one else can see what you are talking about or what files you’re exchanging.
Since ZKPs make it possible to verify a computational assertion, there are many use cases for it such as, a lender can use ZKP techniques to confirm that the borrower has a sufficient amount in their bank account to eventually return the money without learning further information about their balance. This takes away the need to reveal information or have a witness to prove the validity of any claims.
How Does Zero-Knowledge Proof Work?
Zero-knowledge proofs allow users to prove something is true without giving away any other information. To achieve this, it uses algorithms that accept certain data as input and produce “true” or “false” as output to show the validity of claims made by the prover.
The following requirements must be met by a zero-knowledge protocol:
If the statement is really true and both users are honest, the verifier would be convinced without any additional help.
If the statement is false, a lying prover should not be able to trick an honest verifier into believing an invalid statement is valid.
The verifier is not able to learn anything about the statement beyond its validity (true of false) which means they would have no knowledge of the statement. This keeps the verifier from being able to figure out what the original input was based on the proof.
There are three components that make up a zero-knowledge proof:
Witness: To demonstrate knowledge of some secret information, the prover uses a zero-knowledge proof. The “witness” to the proof is the secret information, and the prover’s assumption that the witness is aware of the evidence creates a series of questions that can only be addressed by a party with access to the information. Therefore, the prover selects a question at random, computes the response, and then sends it to the verifier to begin the proving process.
Challenge: Another question from the set is chosen at random by the verifier, who then asks the prover to respond.
Response: The question is accepted by the prover, who then determines the answer and gives it back to the verifier. The verifier can determine whether the prover actually has access to the witness based on the prover’s response. The verifier chooses additional questions to ask in order to make sure the prover isn’t just guessing and arriving at the right answers by accident. The likelihood of the prover falsifying knowledge of the witness decreases significantly if this interaction is repeated numerous times until the verifier is satisfied.
The structure of an “interactive zero-knowledge proof” is described above. Early zero-knowledge protocols used a method called “interactive proving,” in which the person making a claim and the person checking it had to talk back and forth in order to make sure it was true.
Types of Zero-Knowledge Proofs
There are two main types of zero-knowledge proofs, interactive and non-interactive.
Interactive Zero-Knowledge Proofs
Interactive ZKPs allow the prover and the verifier to interact several times. The verifier challenges the prover, who provides replies to these challenges until the verifier is convinced.
A famous example of non-interactive zero-knowledge proof is “The Ali Baba Cave”.
In the story, there is a cave with a magic locked door. Peggy (the prover) wants to prove to Victor (the verifier) that she knows the secret phrase to open the magic door in the cave without revealing the phrase. Both of them know that this cave has a circular path with a single entrance and exit and the magical door is at the end blocking the path in the middle and the only way to open it is by saying the magic phrase.
Image taken from Wikipedia
How can Peggy prove to Victor that she knows the magic phrase without telling him what the phrase is?
They label paths A and B from the entrance, and Victor waits outside the cave as Peggy goes in. Peggy can either take path A or B, but Victor is not allowed to see which path she takes. Victor can then shout which side of the path he wants her to use to return randomly. If Peggy really does know the magic word, this would be easy, as she will be able to open the door and return along the chosen path.
However, if Peggy does not know the magic phrase, she has a 50% chance of exiting via the path Victor chose. By repeating the test, her chances of tricking Victor would become exponentially slimmer, and the only way to guarantee that she always takes the correct path is by knowing the magic phrase. After a few attempts, the probability that Peggy really knows the magic phrase approaches 100%. Although it can never be 100%, the idea is to minimize the chances that someone is lying to you.
In summary, interactive ZKPs, as the name suggests, require interaction with the prover and verifier. For example, Victor uses interactive ZKPs to verify the validity of Peggy’s statement through back-and-forth communication between provers and verifiers.
However, interactive ZKPs have limited utility and transferability as it relies on the interaction between two parties and the proof would be unavailable for a third party to verify.
If Peggy brings another friend to the cave, she would have to go through the entire process to proof again, which is time-consuming and not scalable.
Non-Interactive Zero-Knowledge Proofs
Non-interactive ZKPs were created to show that the prover is aware of certain information without really revealing it.
A popular example of non-interactive proof uses the game ‘Where’s Wally’.
Imagine a competition of ‘Where’s Wally’, even the organizers do not know where Wally is. Whoever can prove that Wally exists receives a prize. You found Wally but you do not want to point him out with your finger because that would show the location of Wally to everyone and end the competition immediately.
Image taken from moonflowerdragon
To prove that you know where Wally is and that he really does exist, you take a giant piece of paper, many times the size of the Wally photo, and cut a small hole in it. You then place the small hole on top of Wally. This shows that Wally does exist, but because the big piece of paper blocks all other context information, Wally’s location has not been revealed and is still a mystery.
In summary, the above example is just an analogy for non-interactive ZKPs, but it showcases how they are non-interactive, as anyone that sees the hole showing Wally will agree that it is enough proof that Wally exists without you having to repeat any action, unlike in interactive ZKPs.
In reality, a non-interactive zero-knowledge proof is made by putting the secret data into a certain algorithm and running it. When the verifier gets this proof, he or she uses a different method to make sure that the prover knows the secret information.
Non-interactive ZKPs also make the prover and verifier share a key so that verification can be done by someone other than the prover and verifier.
Since the verifier can only check the information once at any given time, this takes more processing power than interactive ZKPs.
Zero-Knowledge Proofs in Blockchain Applications
There are two popular blockchain applications that utilize zero-knowledge proofs: ZkSync and StarkNet. They are ZK-rollups that uses zero-knowledge proofs that help to scale the Ethereum network. The key difference is that zkSync uses ZK-SNARK proofs while StarkNet uses ZK-STARK proofs.
MatterLabs released zkSync V1, a SNARK proof rollup protocol, to the Ethereum Mainnet in June 2020. In February 2022, MatterLabs released zkSync V2, the first ZK-rollup that was EVM-compatible. The ZK-SNARK acronym stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.”
The following characteristics describe the ZK-SNARK protocol:
Zero-knowledge: A verifier can confirm the truthfulness of a statement without being aware of any other information about it. The verifier’s only understanding of the statement is if it is true or false.
Succinct: The zero-knowledge proof is quicker to verify and smaller than the witness.
Non-interactive: Unlike interactive proofs, which necessitate numerous rounds of interactions, the prover and verifier only exchange information once in the non-interactive proof.
Argument: Since the proof complies with the “soundness” criteria, cheating is highly improbable.
(Of) Knowledge: Without having access to the confidential information, it is impossible to create the zero-knowledge proof (witness). For a prover without the witness, it is challenging, if not impossible, to compute a reliable zero-knowledge proof.
The term “shared key” refers to a set of open parameters that the prover and verifier agree to use when creating and validating proofs. Creating the public parameters, which together are called the Common Reference String (CRS), is a sensitive job because it is important to the security of the protocol. If a dishonest prover has access to the randomness that was used to make the CRS, they can make fake proofs.
Using multi-party computation (MPC), one can lower the dangers associated with creating public parameters. In a trustworthy setup process involving several parties, the CRS is generated using some random values provided by each participant. The ZK-SNARK protocol keeps computations safe as long as one honest party gets rid of their part of the randomness.
Users must have faith in and trust the people who are generating the parameters for trusted settings. However, the development of ZK-STARKs has made it possible to prove the protocols’ ability to operate in an untrusted environment.
Zigzag, a decentralized exchange using zero-knowledge proof and ZK roll-up technology, is already live on zkSync for traders to trade with low fees.
StarkNet, an L2 scaling network on Ethereum, utilizes ZK-STARK to enable cheap, fast, and private transactions without compromising on decentralization. ZK-STARK and StarkNet was invented in 2018 by StarkWare, and StarkNet went live on November 2021. The acronym ZK-STARK stands for “Zero-Knowledge Scalable Transparent Argument of Knowledge.”
The following characteristics describe the ZK-STARK protocol:
Scalable: When the size of the witness is larger, ZK-STARK generates and verifies proofs more quickly than ZK-SNARK. As the witness gets bigger, STARK proofs only see a modest rise in prover and verification times (SNARK prover and verifier times increase linearly with witness size).
Transparent: ZK-STARK generates public parameters for proving and verification using verifiable randomization rather than a trusted setup. Therefore, they are more transparent than ZK-SNARKs.
ZK-SNARK vs. ZK-STARK
Image taken from Consensys
In summary, ZK-STARKs are more trustless than ZK-SNARKs, but they generate larger proofs than ZK-SNARKs, resulting in typically higher verification costs. However, in some circumstances, such as when proving large datasets, ZK-STARKs may be more cost-effective than ZK-SNARKs.
Although both technology are supported by Ethereum developers, the Ethereum foundation has given StarkWare a $12 million grant, showing support for trustless technology.
ZK-Rollups vs. Optimistic Rollups
Now that we have a better understanding of ZK rollups, let’s compare them with optimistic rollups, the currently leading Ethereum scaling solution. Below is a table highlighting the differences between Optimistic and ZK-rollups.
Image taken from Tokeninsight
Compared to optimistic rollups, ZK-rollups can have a much smaller withdrawal delay and a higher level of security because there is no need to wait for the transaction validators to be trustworthy or wait for the fraud-proof window to close.
In addition, ZK-rollups may in the future make private transactions possible. zkSync has openly stated its intention to make future transactions private, and projects like Zcash and Aztec Network have implemented ZK-proof enabled privacy features.
ZK-rollups outperform Optimistic rollups in terms of theoretical transaction-per-second (TPS) cap, transaction finality time, and security. They fall short, though, in terms of EVM compatibility, which is why most developers are deploying on optimistic rollups first as they can reuse EVM code.
However, although Optimistic rollups such as Arbitrum and Optimism are currently more popular, as ZK technology continue to evolve, ZK-rollups may be a better solution for all types of applications in the future.
Use Cases of Zero-Knowledge Proofs
As mentioned at the start of the article, making payments on the blockchain would make your transaction and wallet known to multiple parties, from the business, payment provider to the banks. Although financial surveillance is useful for preventing illegal financial activity, it can be abused and also compromise the privacy of ordinary citizens.
On public blockchains, zero-knowledge proofs are also being used to anonymize transactions. Tornado Cash is an example of a decentralized, non-custodial service that enables users to conduct private Ethereum transactions by employing zero-knowledge proofs to conceal transaction details and ensure financial anonymity. Because these are “opt-in” privacy tools, they are unfortunately associated with illegal activity. To overcome this, privacy must become the default setting on public blockchains, which is being done on StarkNet.
Existing identity management solutions put sensitive data at risk. Zero-knowledge proofs can assist individuals in validating their identities while safeguarding sensitive information.
In the context of decentralized identification, zero-knowledge proofs are very useful. People who have decentralized identification, also called “self-sovereign identity,” can control who can see their personal identifiers. One great example of decentralized identity is being able to prove citizenship without sharing your ID using ZKPs.
Using internet services requires establishing one’s identification and access rights. Most of the time, this means giving personal information like names, email addresses, birth dates, etc. Additionally, you may have to memorize lengthy passwords or risk losing access.
However, zero-knowledge proofs can simplify authentication for platforms and users alike. Once a ZK-proof has been made using both public (e.g., data that proves the user is a member of the platform) and private (e.g., the user’s details) information, the user can easily send it to the service when they need to prove who they are. This improves the user experience and eliminates the need for companies to keep vast volumes of user data.
Another useful example would be when a user is applying for a house mortgage which requires the bank to know that the user has the income or net worth capable of paying the monthly payments. Using ZKPs, the user can prove that their salary or networth falls within their acceptable range without revealing their exact salary or net worth.
Zero-knowledge Password Proof
Zero-knowledge proof is also applicable to passwords. It enables one party (the prover) to demonstrate to another party (the verifier) that it knows a password without revealing anything to the verifier other than the fact that the prover knows the password.
Another use case for ZKP to improve blockchain technology is verifiable computation. It enables the outsourcing of computation while keeping verifiable results. The entity submits the result alongside a proof that the program was correctly executed. This is crucial for increasing blockchain processing speeds without compromising security.
On-chain scaling options, like sharding, necessitate significant alterations to the blockchain’s foundation layer. This approach is complicated, and implementation flaws can compromise Ethereum’s security mechanism.
Hence off-chain scaling solutions are being explored as they do not need to rewrite Ethereum’s code. To boost throughput on Ethereum’s foundation layer, they outsource the computational execution to a separate chain which then returns the results to Ethereum.
This means Ethereum does not do the execution which decreases network congestion and accelerates transaction processing (off-chain protocols are optimized for faster execution). However, the chain needs to validate off-chain transactions without re-computing them or else it defeats the purpose.
Verifiable computation comes into play at this point. When a node executes a transaction off-chain, it submits a zero-knowledge proof to demonstrate the transaction’s validity. This proof (known as a validity proof) ensures that a transaction is genuine, allowing Ethereum to immediately apply the outcome to its state without waiting for anyone to contest it.
Zero-knowledge rollups and validiums are two off-chain scaling techniques that allow secure scalability through the use of validity proofs. These protocols do thousands of transactions off-chain and submit proofs for Ethereum’s verification allowing Ethereum to handle more transactions without increasing computation on the foundation layer.
Challenges of Zero-knowledge Proofs
While ZKPs seem like a great solution for privacy on the blockchain, they do come with several challenges that we will discuss below.
Verification Not Guaranteed
ZKPs do not provide 100% assurance that the claim is true, even though the likelihood of verification while the prover is lying might be very low. The likelihood of a prover lying gets smaller with each ball-picking cycle but will never go to zero.
Both interactive and non-interactive ZKPs between the prover and the verifier have algorithms that require a lot of computing power. This means that the prover and the verifier would have to pay more fees when using devices with more computing power. For example, ZK-rollups pay 500,000 gas to verify a single ZK-SNARK proof on Ethereum, with ZK-STARKs requiring even higher fees.
Due to the extremely difficult computations required to generate ZKPs, devices that are able to run these protocols are more expensive, and not everyone can afford them. Applications that intend to use zero-knowledge technology must also account for hardware costs, which could also raise prices for users.
Quantum Computing Threats
For encryption, ZK-SNARK employs elliptic curve cryptography (ECDSA). Even though the ECDSA algorithm is secure at the moment, the development of quantum computers in the future could make it less safe.
Using collision-resistant hashes for encryption, ZK-STARK is considered immune to the threat posed by quantum computing. Collision-resistant hashing is harder to break with quantum computing algorithms than it is with the public-private key pairs used in elliptic curve cryptography.
Privacy is incredibly important for businesses and organizations to stay competitive. Blockchain’s open nature and lack of easy to use privacy features could be one of the main reasons why blockchain technology has not yet been widely adopted.
The creation of privacy-enabled blockchain solutions powered by zero-knowledge proofs, such as StarkNet and zkSync, has enabled blockchains that are cheap and fast to use while still being decentralized. It is possible that the next wave of mass adoption of cryptocurrencies could begin, driven by real-world demand for the convenience that zero-knowledge technology can give to both users and businesses.