Zero Knowledge Proof (ZKP) is a cryptographic protocol initially proposed by MIT researchers Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the 1980s.
In ZKP, one party (known as the prover) can prove to another party (the verifier) that they possess knowledge of a specific statement, without disclosing any additional information beyond the validity of their claim. The protocol ensures that the verifier can verify the authenticity of the prover’s claim, without gaining access to any confidential information or knowledge used to validate the statement.
In simpler terms, ZKP allows a prover to prove to a verifier that they know a piece of information without revealing what that information is. This technology has numerous applications in various fields, including cryptography, data privacy, and authentication.
How does zero-knowledge proof works?
ZKP is a fascinating concept that allows us to prove a statement’s validity without revealing any additional information beyond the statement itself. To better understand this idea, consider the following example:
Let’s say you have a color-blind friend who can’t differentiate between green and red balls. You must prove that two balls are different colors, but your friend needs more than just your word to be convinced. In this scenario, a ZKP method would come in handy.
Here’s how it works:
- Your friend takes the balls and shows you which ball is in each hand. They might then switch the balls between their hands behind their back, or they might not. They’ll then present the balls to you and ask whether they switched them.
- As someone who can tell the difference between green and red balls, you can easily answer the question. But your friend still needs to be convinced. There’s still a 50% chance that you guessed incorrectly, and the balls could still be the same color.
- However, if you repeat this process several times, the likelihood of you correctly guessing whether they switched the balls or not each time becomes increasingly slim. Eventually, your friend can verify that the balls are indeed different colors without knowing them.
- In real-world applications of ZKP, cryptographic algorithms are used to verify computational statements. For example, a payment receiver can use ZKP methods to confirm that the payer has sufficient funds in their bank account without disclosing any other information about their balance. This ensures privacy and security for both parties involved.
The properties of zero-knowledge proof
A zero-knowledge proof of some states must satisfy three properties:
- Completeness: if the statement is true, an honest verifier (one following the protocol properly) will be convinced of this fact by an honest prover.
- Soundness: if the statement is false, no cheating prover can convince an honest verifier that it is true, except with some small probability.
- Zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the information is accurate. In other words, knowing the message (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that “looks like” an interaction between an honest prover and the verifier in question.
Zero-Knowledge Proof protocols
The most popular interactive or non-interactive zero-knowledge proof (zk-SNARK) protocols can be broadly categorized into the following four categories:
- Succinct Non-Interactive Arguments of Knowledge (SNARK)
- Scalable Transparent Argument of Knowledge (STARK)
- Verifiable Polynomial Delegation (VPD)
- Succinct Non-interactive ARGuments (SNARG)
A list of zero-knowledge proof protocols and libraries is provided below, along with comparisons based on transparency, universality, plausible post-quantum security, and programming paradigm. A transparent protocol does not require any trusted setup and uses public randomness. A universal protocol does not require a separate trusted design for each circuit. Finally, a plausibly post-quantum protocol is not susceptible to known attacks involving quantum algorithms.
Applications and use cases of zero-knowledge proof
Zero-knowledge proof can use to protect data privacy in a diverse set of use cases, such as:
- Blockchain: The transparency of public blockchains such as Bitcoin and Ethereum enable public verification of transactions. However, it also implies little privacy and can lead to the deanonymization of users. Zero-knowledge proofs can introduce more privacy to public blockchains. For instance, the cryptocurrency Zcash is based on Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (Zk-SNAKR), a zero-knowledge cryptographic method.
- Finance: ING uses ZKP that allow customers to prove that their secret number lies in a known range. For example, a mortgage applicant can prove their income is in the acceptable content without revealing their exact salary.
- Online voting: ZKP can allow voters to vote anonymously and verify that their vote was included in the final tally.
- Authentication: ZKP can be used to authenticate users without exchanging secret information such as passwords.
- Machine Learning: ZKP can allow the owner of a machine learning algorithm to convince others about the model’s results without revealing any information about the ML model itself.
Challenges of zero-knowledge proof
- No 100% guarantee: Even if the probability of verification by the verifier while the prover is lying can be significantly low, ZKPs don’t guarantee that the claim is valid 100%. As demonstrated above, the probability of a prover lying decreases in each iteration of the ball-picking process, but it can never reach zero. Thus, zero-knowledge proofs aren’t actual proofs in a mathematical sense.
- Computation intensity: Algorithms used are computationally intense as they require many interactions between the verifier and the prover (in interactive ZKPs) or require a lot of computational capabilities (in non-interactive ZKPs). This makes ZKPs unsuitable for slow or mobile devices.
