Basics of Zero Knowledge

Midnight is supposed to be a data protection blockchain that will be able to safeguard sensitive commercial and user data. Zero-knowledge proofs will be used for this. In the article, we will explain the basics of Zero-Knowledge (ZK) proofs.

Say It's True Without Revealing The Truth

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while avoiding conveying to the verifier any information beyond the mere fact of the statement's truth.

ZK proofs are a fascinating concept in cryptography. They allow the prover to prove to the verifier that they know a value x, without conveying any information apart from the fact that they know the value x. The verifier will not know the value of x but will have proof that the prover knows it. The trust in ZK proofs comes from their mathematical properties.

A classic example of a ZK proof involves a scenario where Alice (the prover) wants to convince Bob (the verifier) that she knows the password to a secret door in a cave without actually revealing the password. Alice goes into the cave and comes out of an exit chosen by Bob, thus proving she knows the password without revealing it.

The cave has only one entrance, which is also the exit. Right behind the entrance, Alice can go in two directions A or B. Behind the entrance is a single long corridor. In the middle of the corridor is a door that can only be opened with a password. Alice wants to prove to Bob that she can get through the door, that is, that she knows the code.

Look at the picture of what the cave looks like and where the door is located. To open the door it is needed to know the password. Note that Bob is not looking into the cave and does not know if Alice went in direction A or B.

From an interaction perspective, it looks like this. In the beginning, there is always some commitment of the prover. The prover tries to prove a statement is true and the verifier wants to verify it. Verification takes place in a challenge-response manner. Firstly, the verifier challenges the prover. The prover has to provide a response. Verification is done based on the response. The verifier examines the response to verify whether the statement is true or false.

Let's continue our story with the cave. Alice's claim that she knows the secret password to the door is a commitment. She enters the cave and decides on direction A. Bob does not know which direction Alice chose. Bob enters the cave entrance and shouts to Alice to return in either direction A or B.

Even though Bob is in the cave, he can't see Alice. He chooses direction B and shouts this choice to Alice. You can see the described situation in the following picture. Bob challenges Alice.

Alice must provide a response. In our example, this means that she has to use the secret password and go through the door, as that is the only option for her to return from the B direction. Bob walks a little further into the cave to see which way Alice will come out. In the picture below you can see that Alice is coming from direction B.

Note that if Bob had shouted direction A, Alice would not have had to use the secret password at all and would have come from the correct direction. In other words, she had a 50% chance of fooling Bob. It is necessary to repeat this process several times. If Alice can consistently return from the path that Bob specifies, he becomes convinced that she knows the secret password. However, he learns nothing about what the password actually is, hence this is a zero-knowledge proof.

Alice is able to prove to Bob that her statement is true. If Bob wants to buy a secret password, he has proof that Alice knows it.

More Practical Use

Let’s consider a scenario where Alice (the prover) wants to convince Bob (the verifier) that she is at least 18 years old using a zero-knowledge proof.

Bob can be a seller of alcoholic beverages, a doorman at an adults-only club, or any service on the Internet that is only for adults, such as a crypto exchange.

If Alice only has a regular ID, she can show it to Bob physically, or make a photocopy and send it to Bob over the Internet. The problem is that this way you often reveal all the information that is on the ID even though the verifier may not need it. The law may require verification of age and nationality to enable the use of the service, without the need to reveal name or residence. In theory, users could better protect their privacy, but this is currently not possible. ZK proofs make this possible. It can even provide proof in such a way that the information itself is not revealed. Alice can prove she is over 18 without revealing her age.

This is how the interaction via the ZK protocol could look like.

The first stage is the preparation of the commitment. Alice starts by committing to her age. This could be done by hashing her age with a secret random number (also known as a nonce). Alice sends the commitment to Bob. The commitment scheme should be hiding and binding. Bob is unable to determine Alice's age from the received commitment, but at the same time, Alice cannot change the age after she sends the commitment. Bob verifies the fact that Alice committed to.

Once Bob has a commitment, he can challenge Alice. So, Bob sends Alice a random challenge. This could be a simple binary question, such as if her age is older than 18.

Alice responds to Bob's challenge by providing proof that satisfies the challenge without revealing her exact age. In this case, she could use a zero-knowledge range proof to prove that her age lies within a certain range that is above 18.

Finally, Bob verifies Alice's proof. If the proof is valid, Bob becomes convinced that Alice is at least 18 years old without learning her exact age. Bob will not learn any information from Alice's ID. Notice that Bob doesn't even get to know the exact age of Alice he was interested in. He settles for proof that Alice is an adult.

The commitment itself doesn’t provide any proof of the validity of the claim. Commitment is only a setup process before the challenge-response and verification phases. The actual proof comes later when the prover successfully responds to the verifier’s challenges.

If Alice were to provide a false commitment, she would not be able to consistently respond to Bob’s challenges in a way that convinces him of her claim. Challenges are randomly generated, so Alice can’t predict them in advance. If her commitment was false, she would fail to respond correctly to at least some of the challenges, and Bob would not be convinced.

The commitment in a ZK proof serves a crucial role. It’s a way for the prover (Alice) to “lock in” her claim without revealing any information about it. The commitment is designed to be a one-way function, meaning Alice can’t change her claim after the commitment has been made (binding). The security of ZK proofs comes from their interactive nature and the use of random challenges. Even if Alice tries to cheat by making a false commitment, the protocol ensures that Bob has a high probability of detecting this.

Conclusion

Zero Knowledge proofs have the potential to significantly improve the usability of the blockchain, especially in the areas of scalability (zk-rollups), privacy of transactions, and privacy of smart contracts. So, while encryption can only secure data to prevent unauthorized access, ZK proofs allow for the secure and private computation and verification of that data. ZK proofs will allow participants to work with data in a private way without revealing any sensitive information. ZK proofs can be seen as an additional layer of privacy on top of the encryption used in blockchain technology.

Midnight will be a very useful blockchain for businesses, banks, institutions, companies, and especially users, as it will be possible to protect sensitive data and at the same time use it for various services.