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. Zero knowledge proofs (ZKP) are a type of cryptographic protocol that allows one party (the prover) to demonstrate to another party (the verifier) that a certain statement is true, without revealing any additional information beyond the truth of that statement. In other words, a zero knowledge proof allows one party to prove to another party that they know a certain secret, without revealing the secret itself.

The concept of zero knowledge proofs was first introduced in a 1985 paper by researchers Goldwasser, Micali, and Rackoff. Since then, zero knowledge proofs have become an important tool in cryptography, and have a wide range of applications in fields such as blockchain technology, digital identity, and secure authentication.

A simple example of a zero knowledge proof is the following: Alice wants to prove to Bob that she knows the solution to a particular mathematical problem, but she doesn’t want to reveal the solution itself. Using a zero knowledge proof protocol, Alice can demonstrate to Bob that she knows the solution to the problem, without actually revealing what the solution is. Bob can then verify the proof and be confident that Alice does indeed know the solution.

Zero knowledge proofs are a powerful tool for privacy and security, as they allow for secure communication and authentication without revealing sensitive information. They are also an active area of research, with ongoing work to develop new zero knowledge proof protocols and applications.

How do zero knowledge proofs work?

Zero knowledge proofs work by allowing one party (the prover) to demonstrate to another party (the verifier) that they know a certain secret, without revealing the secret itself. This is accomplished through a cryptographic protocol that involves several steps:

Initialization: The prover and verifier agree on a statement that the prover wants to prove, as well as a set of rules for how the proof will be constructed.

Commitment: The prover makes a commitment to the verifier that they know the secret, without revealing the secret itself. This is typically done by performing a series of computations or transformations on the secret, such that the commitment contains no information about the secret itself.

Challenge: The verifier issues a challenge to the prover, typically in the form of a random value or question that the prover must answer correctly to demonstrate knowledge of the secret.

Response: The prover responds to the challenge with a proof that they know the secret, constructed according to the agreed-upon rules. The proof should be convincing enough to the verifier that it is highly unlikely that the prover could have constructed it without actually knowing the secret.

Verification: The verifier checks the proof provided by the prover to confirm that it is valid and that the prover does indeed know the secret. If the proof is valid, the verifier accepts it and the prover has successfully demonstrated knowledge of the secret without revealing any additional information.

Human explanation on how 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.

Interactive and non-interactive zero-knowledge proofs

Zero-knowledge proofs can be categorized into two types: interactive zero-knowledge proofs (iZKP) and non-interactive zero-knowledge proofs (NIZKP).

Interactive zero-knowledge proofs involve a series of interactions between the prover and the verifier, with each party sending messages to the other. The prover typically generates a proof of knowledge, and the verifier responds with a challenge based on the proof. The prover then generates a response to the challenge, and the verifier checks the response to determine whether the prover actually knows the secret or not. This process continues until the verifier is convinced that the prover knows the secret.

Non-interactive zero-knowledge proofs, on the other hand, are designed to be a one-shot protocol where the prover generates a proof and the verifier checks the proof without requiring any further interaction. This is achieved using a technique called a “commit-and-prove” approach, where the prover generates a commitment to the proof that can be verified by the verifier without revealing any information about the proof itself. The verifier can then check the proof by verifying the commitment, without requiring any further interaction with the prover.

Non-interactive zero-knowledge proofs are typically faster and more efficient than interactive zero-knowledge proofs, since they only require a single round of communication between the prover and the verifier. However, they can be less secure in some cases, since they rely on cryptographic assumptions that may be easier to break than those used in interactive zero-knowledge proofs.

Conclusion

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.

I will post more information about this technology with examples. Please refer on Awesome list https://github.com/matter-labs/awesome-zero-knowledge-proofs