Variants of zero knowledge proofs (ZKP)

Introduction

Concerns about data privacy in shared environments are arising as distributed ledger technology is increasingly touted as a decentralized data transaction infrastructure that removes centralized control, in popular domains, such as finance , supply chain , and healthcare. Vital information that could be used to identify an individual, such as date of birth, social security numbers (in the U.S.), employment information, and bank statements, is paramount to the safety and financial well-being of the identity owner. To safeguard sensitive information, initial applications of zero-knowledge proof (ZKP) techniques have surfaced in DLT projects like the zk-SNARKS protocol in ZCash. A zero-knowledge proof (ZKP) is a two-party( sometimes Multi-Party) protocol between a prover and a verifier, which allows the prover to convince the verifier that he knows a secret value that satisfies a given relation (proof of knowledge property), without the verifier being able to learn anything about the secret (zero-knowledge property). ZKP is a complex scheme designed to incorporate encryption techniques to enable a prover to certify the truthfulness of a statement(the witness) to a verifier without disclosing any more specifics other than the statement itself. A true ZKP must possess the following three key properties:

•Completeness—if the statement is true, an honest prover will convince the verifier,

•Soundness—if the statement is false, verifier will find out the prover is dishonest with very high probability, and

•Zero knowledge—if the statement is true, no extra information is revealed to the verifier other than the statement being true .

Variants of Zkps

Zero knowledge proofs (zkps) are generally classified into two variants : • Interactive

• Non-interactive

Interactive zero knowledge proofs

Generally speaking, an interactive zero-knowledge proof works as follows: The prover sends a witness to the verifier. The witness works as a commitment in the protocol. The verifier sends a challenge back to the prover. The challenge could be the outcome of fair coin toss. The prover sends a response to the verifier. The calculation of the response needs to take into account the witness, the challenge, and the secret. In the interactive zero-knowledge proof, both the prover and the verifier need to be present during the execution of the protocol. Well, let me explain it with two most famous examples. Let's dive into it :

Ali Baba Cave

This is one of the favorite scenarios to properly investigate how the zero knowledge proof authentication works. Here the prover is known as Peggy, and the verifier is Victor. So, to keep things on the same level as zero knowledge proof authentication, the prover would know a value z, and the verifier would know that the prover knows the value z. The example starts like this, imagine that Peggy somehow knows a secret word that can open a magic door inside the Ali Baba cave. The cave looks like a ring with the door blocks the pathway to exit. The entry and exit meet in a similar location. Now, Victor wants to make sure that Peggy is telling the truth. Meaning, she knows the secret word. But Peggy is a private person and is unwilling to say the magic word to Victor. So, how can Victor know whether she is telling the truth or not?

A Different Scheme

Victor comes up with a plan to solve the situation. He marks the entrance path A and exit path B. However, as they meet at the same position, path A and B are just left and right path. During this examination, Victor stays put outside, while Peggy goes into the cave. Peggy now has the option to take path A or B, but whatever she takes Victor can’t know that. After Peggy chooses a path, she goes in, and Victor enters the cave. He then shouts the path name where he wants Peggy to return. He can select randomly – either A or B. Well, if she actually knows the secret word, it’ll be really easy. She can use that word to open the door and return to Victor. Or she can also return the same path if necessary Suppose, Peggy doesn’t really know the word. In that case, she would only be able to return to Victor, if Victor shouts the name of the path, she chooses at first. As the selection process is random, Peggy would get a 50% chance to follow Victors instruction. But if Victor repeats this process let’s say 15 time or 25 times, then Peggy would not be able to make a lucky guess to fool him. Anticipating Victors move will become next to zero and Peggy would get caught. But even after repeating this process so many times, Peggy manages to come back wherever Victor wants her to be; then Victor can safely assess that she does know the secret word.

A Color-Blind Friend and Two Balls

You can also perform this experiment using two colored cards. It goes thus : imagine you have a color-blind friend and two balls. The balls need to be red and green and of the same size. Your friend thinks they are the same thing and is doubting your statement that they are different. So, you need to prove that they have different colors without telling him which is which. You give the balls to your friend, and he keeps them hidden behind his back. After that, he brings out a ball randomly and lets you see it. He then puts that ball back and then randomly chooses the ball again. You get to see the ball this time too. After that, he would ask you whether he switched the ball or not. He will be repeating this process for some time to be sure. Now that you are not color blind, you can definitely tell that if he switched the ball or not. If the balls were of the same color, your probability for answering correctly would be 50%. So, after repeating this process and when you are able to answer each time correctly, your friend would be convinced. The probability of anticipation would become zero, and you would achieve the three zero knowledge properties. But make sure that your friend doesn’t know which one is green and which one is red. This way you will be able to preserve the third property “zero knowledge.”

From the above scenarios and explanation ,it is crystal clear that the following exists on the interactive zero knowledge proof: Effort intensive : it requires a lot of efforts when you want to prove it to more than one people. This is because you would have to repeat the same process over and over again to each person as just by watching they can’t agree with you. hence not scalable Interaction based : This protocol would need any kind of interactive response from the verifier to execute. Or else, the prover can never prove it on their own. The interactive input could be a form of challenge or another kind of experiments. Obviously, the process has to convince the verifier about knowing the knowledge. In other cases, the verifier could record the process and then play it for other so that they can also see it. But whether other people would actually be convinced or not depends solely on them. They may accept it or not.

This is why interactive zero knowledge proof blockchain is more efficient for few participants rather than a large group.

Non-interactive proof (NIZKP)

Sometimes, it will be more convenient if the prover can generate a transcript of the protocol so that the verifier can verify it at some later time. By using the Fiat-Shamir heuristic , this can be achieved by transferring an interactive proof into a non-interactive proof. The non-interactive zero-knowledge proof (NIZKP) normally works as follows:

•The prover generates a witness.

•The prover takes the witness as well as some other necessary information as inputs, and outputs the challenge using some hash function.

• The prover calculates the response and then sends the transcript, which includes the witness, the challenge, and the response to the verifier.

Non-interactive zero knowledge proof is here to verify one’s statement to a larger group of people. You don’t always have to go for the non-interactive zero knowledge proof to check though. Often, you might be able to find any trusted verifier source who can vouch for you. But when you can’t find anyone, then non-interactive zero knowledge proof blockchain is the way to go. Non-interactive zero knowledge proofs are those ZKPs that do not require interaction between a verifier and a prover. Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) is a ZKP-based protocol with the following additional features:

• Succinct: The size of the proof is small enough to be verified in a few milliseconds.

•Noninteractive: The proof transcript consists of a single message—from the prover to the verifier.

•Argument of knowledge: A computationally sound proof: soundness holds against the prover that leverages polynomial-time—i.e., a bounded computation.

The Sudoku Challenge with Cards

Sudoku is one of the most difficult games but with simple rules. All of the rows, sectors, and columns need to have the number 1-9 only once. In this case, imagine you know the solution of this puzzle, which may take days for even computers. So, if you want to sell the solution, how will the verifier know that you are not tricking him? You would have to prove your knowledge without revealing the solution to the verifier. Let’s see how you can do it.

A Way to Solve

You would need 27 cards where they are numbered from 1-9. So, 27 cards would contain the number 1 and then another 27 the number 2. In total, you would need 243 cards. Now you would have to put three cards in a corresponding box with the solution. Meaning if the correct number for that box is five, you will put three number 5 cards in that box. In a Sudoku table, you see some answers are always visible. In these boxes, you will place the card face up. On boxes that don’t have the answer, you will place the cards upside down. Now you need to prove that you have placed all cards in the right position without revealing it. You have to: Take the topmost card from each column until you have nine piles. Repeat the same thing for rows and sector. Then you would need to shuffle every pile and then turn over to reveal the numbers. You know the basic rule, all numbers from 1-9 have to appear once in every row, sector, and column. So, if all of your pile has the number 1-9 appearing only once then the verifier would know that you have the solution. Non-interactive can be the best way to prove your statement to a lot of people without increasing resources and costing. Hence it is very scalable .

Non-interactive zero knowledge proofs can be summarized to include the following : • The prover creates a two-part challenge (a part to create an initial proof,another part to finalise the proof) for the witness(statement to be proved ) that doesn't require a Personal Identified Interaction (P.I.I) • The prover then sends his results from the challenge . • The verifier in turn verifies the challenge result by the other part of the challenge that evaluates to true or false.

The variants of Zk proofs are both efficient in usage but the non interactive variant is better because of its ability to scale.

Ways zero knowledge proofs can be used for Scalability.

• Zk-Rollups : this is a zero knowledge approach used in increasing Scalability of a blockchain by mass transfer processing rolled into a single transaction. ZK-Rollups bundle hundreds of transfers into a single transaction. The smart contract will deconstruct and verify all of the transfers held in a single transaction. A "zero knowledge proof" approach is used to present and publicly record the validity of the block on the blockchain. ZK reduces computing and storage resources for validating the block by reducing the amount of data held in a transaction; zero knowledge of the entire data is needed . This in turn helps scale the Blockchain efficiently.

• Reduction in latency / block time : a zkp is able to reduce the confirmation period of blocks ,this is done by non-interactive zero knowledge proof , a prover ( spender of a transaction) generates proof of transaction which in turn is verified by selected node would greatly reduce latency time