A Non-Mathematical Introduction to Zero Knowledge Proof
A ZKP primer for those who flunked algebra.
00: Setting the Scene
Imagine you're playing a game of 20 Questions with a friend. Your friend has picked a secret word, and it's your job to figure it out by asking questions. But there's a twist: your friend has a rule that they can't tell you the secret word directly. They can only answer your questions with a yes or a no.
— What are zero knowledge proofs?
A zero-knowledge proof is a way for one person (the prover) to prove to another person (the verifier) that they know something without revealing any additional information about it. It's like a magic trick, but with math instead of rabbits and top hats.
In the 20 Questions game, the prover (your friend) can use a zero-knowledge proof to demonstrate to you (the verifier) that they know the secret word without actually telling you what it is.
— How do zero knowledge proofs work?
The prover and verifier agree on a list of possible secret words. In this example, let's say the list contains the words "apple," "banana," and "orange."
The prover selects the secret word "apple" and creates a cryptographic commitment to this word without revealing it to the verifier. A commitment is a value that is generated using a secret input (in this case, the secret word "apple") and a publicly known function, such that it is computationally infeasible to determine the secret input from the commitment.
The prover sends the commitment to the verifier, who can verify that it was created correctly but cannot learn the secret word from it.
The verifier sends a challenge to the prover, asking them to prove that they know the secret word without revealing it.
The prover responds to the challenge by providing a proof, which is a value that is generated using the secret word and a publicly known function. The proof is constructed in such a way that the verifier can verify that it is correct, but cannot determine the secret word from it.
The verifier checks the proof to make sure it is valid, and if it is, they can be convinced that the prover knows the secret word without learning any additional information about it.
By asking you these questions and using your answers to narrow down the possibilities, the prover is able to demonstrate to you that they know the secret word without actually telling you what it is. That’s the essence of ZKP.
— Interactive and non-interactive zero-knowledge proofs
In an interactive zero-knowledge proof (iZKP), the prover and verifier engage in a back-and-forth interaction in order for the prover to create a proof that the verifier can use to verify that the prover knows the secret information. The interaction between the prover and verifier can take many forms, such as the prover answering yes or no questions from the verifier or the prover responding to challenges posed by the verifier.
The 20 questions game example is an illustration of Interactive ZKP.
- In a non-interactive zero-knowledge proof (niZKP), the prover creates a proof that the verifier can use to verify that the prover knows the secret information without any back-and-forth interaction between the two. In a niZKP, the prover creates a proof that consists of a set of mathematical statements and a corresponding set of proof objects, which the verifier can use to verify the proof without interacting with the prover.
— House Rules: Properties of ZKP
Completeness: If the statement being proven is true, the verifier will be convinced of this fact by the prover's zero-knowledge proof.
Soundness: If the statement being proven is false, the prover will not be able to convince the verifier of its truth through a zero-knowledge proof.
Zero-knowledge: The prover does not reveal any additional information about the statement being proven beyond the fact that it is indeed true.
— But why would I want to prove something without telling anyone what it is?
There are many scenarios where a person might want to prove that they know something without revealing what it is. For example, consider a situation where a person wants to prove to a bank that they have a certain amount of money in their account but don't want to reveal their account balance to the bank.
In this case, the person could use zero-knowledge proof to demonstrate to the bank that they know the balance of their account without actually revealing the balance itself. This way, the person can prove to the bank that they have the funds they claim to have without revealing sensitive financial information.
Where privacy is a concern
Zero-knowledge proofs are also useful in scenarios where privacy is a concern. For example, a person might want to prove their identity to a government agency without revealing their personal information, such as their name, address, and date of birth. In this case, a zero-knowledge proof could be used to demonstrate that the person is who they claim to be without revealing their personal information.
In the context of web3
Private transactions on public blockchain networks
Normally, all transactions on a public blockchain are visible to everyone on the network. However, with ZKPs, it is possible to construct transactions that preserve the sender and recipient's privacy while still being verified as valid by the network.
Identity verification
In many online contexts, it is necessary to prove one's identity to access certain services or resources. With ZKP, it is possible to prove one's identity without revealing personal information such as name, address, or date of birth. This can be especially useful in contexts such as political activists or journalists operating in oppressive regimes.
Building dApps
Zero-knowledge proofs can also be used to build decentralized applications (dApps) that preserve user privacy. For example, a dApp could use this technology to allow users to prove their eligibility for a service without revealing their personal information.
01: The proof systems - ZK Snark vs. ZK Stark
There are different types of zk proof systems, each with its own strengths and weaknesses. Two of the most well-known proof systems are:
Succinct Non-Interactive Argument of Knowledge (zk-SNARK)
Scalable Transparent Argument of Knowledge (zk-STARK)
— zk-SNARK:
This proof system allows you to prove that you know something without revealing any additional information about it. It's known for having a small proof size (amount of data that is required to represent the proof), which makes it efficient and easy to transmit and verify. It's also a non-interactive proof system, meaning that the prover and verifier don't have to go back and forth during the proof generation process.
— zk-STARK:
This system is similar to zk-SNARK, but it's a little different. With zk-STARK, you and the person you're trying to prove something to will have a little back-and-forth interaction during the proof generation process. It's still a zero-knowledge proof, but it works a bit differently than zk-SNARK.
Before you go off, it's important to note that the zero-knowledge space is still an area of active research and development. There's still a lot of work to be done before these tools are widely adopted and used on a regular basis. But hey, that just means there's plenty of room for you to get in on the action and explore!
Just don't forget to pack your calculator (or better yet, hire a math wizard to do all the heavy lifting for you).
Also, follow me on Twitter to get notified about future posts and let me know what you think.