Zero Knowledge Proof

Zero Knowledge Proof

Chapter 1: Introduction

As we all know “Data is the new oil”, in light of this sentence one can say that in the new era of technology so many organizations cum companies are trying to collect as much as information or say data about you as they can, so in the race of collecting data for serving one’s purpose(s) or for selling goods and services to particulars and earn profit is the one of the top most agenda in the current time. So, to full-fill the just mentioned agendas the key is “Data” or to be more precise “information” of particular behaviour or taste patterns, and by observing so, one can determine the interest of the person and make them go on the path designed by the observers to serve individual’s purpose. And when we use such goods or say services, we are often forced to reveal more than we actually want. So, the question of “security “arises here. And there is where the term like “cryptography” was introduced.

There are so many Brute Force methods explored under cryptography intending “Security of data”. But these Brute Force or so-called conventional methods do not provide the needed security. As we all know in “Bit-coin” also data is public rather than private. And as so many companies trying to collect as much as information as they can, sometimes it seems impossible to keep our data private.

• So, is there is a way to provide information to such services without actually revealing the data?
• Like, kind of way to prove something without revealing the actual thing? And answer to above question is “ZKP” or “Zero Knowledge Proof”. It is a proof method in which proof “x” is being proved by an honest prover to an honest verifier without revealing any information about “x” but the proof “x”

Chapter 2: A simple view towards Zero Knowledge Proof

ZKP is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information. [1] It is the method in the proof system which is used to prove the proof to other person say verifier using the interactive and non-interactive type of proof methods. MIT scientists Shafi Goldwasser, Silvio Micali and Charles Rackoff first suggested the concept of ‘ zero knowledge ‘ in the 1980s. [2] It’s a method of proof system which reveal nothing other than the validity of assertion being proven.

Informal Explanation

There is a prover P and the verifier V. And prover P says that he knows some secret X and wants to convince the verifier V that he knows it without revealing any information regarding secret X. And here Secret X may be anything like “Secret of solving some complex Puzzle”, so prover wants to convince the verifier that he knows the secret of puzzle. So, for doing so he may use the conventional method like he actually shows the secret with the verifier and reveals the logic, so by having look at its verifier will be easily convinced that “yes, what the prover is claiming is actually valid”. [3] But by using such method for proving individual’s claim is not fruitful in every-case. Like by actually seeing the logic the verifier can go to some other party and proves the same thing to other person, as now verifier has the knowledge of the secret of solving puzzle and at the end person V will get credit of the work which is actually done by Prover P. And which is not desirable. [3] So, there is need of such proof method that proves certain claim without revealing any knowledge regarding the claim other than the fact that the claim is valid. And this type of proof system consists the Zero Knowledge Proof method which is used in Cryptography, in which the claim can be validate by performing “n” number of iterations or say “questions” and “answers at the both end of system. [3]

What is the need?

As our personal information like “our social contacts”, “behavioural patterns” and “our tastes” are the valuable data. So many companies are trying to collect as much information about you as they can, so that they can show us more advertisements of goods and services or keep us longer on their platform and these will lead them to earn more profit. [2] And so, one can say that if you don’t agree the way a company uses your data, you simply do not create account or if already have, then you can delete an account. But, do we always have choice like this? “No”, we don’t have choice like this. Like try to get loan of rupees 20 Lac from bank without revealing your financial history. Will bank give you loan? No loan won’t give loan, to get loan you have to show your financial history. So, in reality we are forced to reveal more then we actually want. [2]

• So, is there is a way to provide information to such services without actually revealing the data?
• Like, kind of way to prove something without revealing the actual thing? Yes, there is where comes the Zero Knowledge Proof.

Formal Explanation

Prover P interacts with the Verifier V convincing him that a proportion is true with some interactions at both ends. Interactions reveals nothing beyond the validity of the proportion. If proportion is true, any V* might as well have generated the simulation of the interaction on his own. And avoids the question “What is the knowledge?” altogether. Interesting things about ZKP:

• Completeness: It should convince the verifier that the prover knows what they say they know
• Soundness: If the information is false, it can’t convince the verifier that the prover’s information is true
• Zero-knowledge: It should reveal nothing else to the verifier

Let say P wants prove some instance string x ∈ L for some language L ⊆ ∑*.

𝐿 = { 𝑥 | ∃𝑥, 𝑉(𝑥, 𝜋) = 𝐴𝐶𝐶𝐸𝑃𝑇}

Definition: An ZKP proof system for membership in L is an algorithm 𝑉 such that ∀𝑥:

• Completeness: If 𝑥 ∈ 𝐿, then ∃𝜋, V(𝜋) = ACCEPT
• Soundness: If 𝑥 ∉ 𝐿, then ∀𝜋, V(𝜋) = REJECT
• Zero-knowledge: Verifier won’t get any knowledge about x

Two main types of Zero Knowledge Proof

1. Interactive Proof:

→ In this type of proof systems that are “n” number of interactions are involved of challenging (questioning) and replying(answering). And these iterations keep going on until the verifier is convinced and validate the claim. But drawback of this type of proof methods is that if the same thing is to be proven to some other person then these all iterations are to be performed again and again. [4]

→So, let say only one verifier is there and each iteration has the time complexity O(Tx), then for performing “n” iterations the time complexity is O (n * Tx), and if there are “m” verifiers are there then same thing is to be performed m times so then the time complexity is O(m*n*Tx) So interactive methods are good for small proofs.

2. Non-interactive Proof

→In this type of proof method, the claim is to be proven only once, and all the verifier can verify the claim anytime. So, there is no need to prove the same thing again and again so here the time complexity is low compared to Interactive type proof system and it is O(m*n*Tx)

→But here the space complexity is higher compared to Interactive type of proof system, so highpower computer systems are to be used for this and which lead to more computation power and which is also one type of overhead. But as in today’s era space is not major concern so this proof systems are used over Interactive proof Systems.[4]

Chapter 3: Protocols and Zero Knowledge Proof

Types and Protocols

• Interactive Proof type protocol:
• Fiat-Shamir protocol
• Guillou-Quisquater Protocol
• Non-interactive Proof type protocol:
• ZK-SNARK
• ZK-STARK
• BULLETPROOFS

Feige-Fiat-Shamir Protocol

This protocol is Interactive type of proof method. Steps involved in this protocol are shown in the above figure. In Zero-knowledge authentication the claimant does not reveal anything that might affect the confidentiality of secret. The Black Box interactions means, the interactions are so designed that they cannot lead to revealing or guessing secret. After exchanging messages, verifier only knows that whether claimant has the secret or not, nothing more than that. The result is Yes/No situation, just a single bit of information.[7]

In this protocol both the prover and the verifier agree on the two large prime numbers and the value of “N” is announced to the public but “p” and “q” kept secret. And let’s say that prover has 3 secret numbers as: s1 = 5 s2 = 7 s3 = 3

As the secrets s1,s2,s3 are known to prover only, so whenever identification is required, he says that “Yes, I am person X and I know secrets s1,s2,s3” . And the verifier will try to identify him by performing some series of actions and which are as following………………….

1. First the prover sends witness that can be used to identify himself.
2. And then the verifier sends challenge that if you are person X and claiming to know secret then respond to this challenge.
3. And then prover sends the response to verifier.
4. Then verifier performs some mathematical operation to identify the prover.

Step 1 :

1 st step is to send witness and for that prover chooses some, random ‘r’ and computes ‘x’ as witness and sends it to verifier. At the end of step 1 verifier should be able know only V and X. V is a public key of prover.

Step 2 :

And after receiving witness verifier send challenges to prover. Let say he sends three challenges c1 as 1 , c2 as 0 and c3 as 1

Step 3 :

Now, if the prover is really person X. He will be able to give right response by computing the “y”. S is the set of secret key and c is the set of challenges send by the verifier

Step 4:

After receiving response “y” from the prover, verifier will now perform identification operations. That if the prover is really the person whom he claims to be then the value of “(x * vc )mod N” and “y2 mod N” should be same, because…….

So, from the above equation 1 and equation 2 we can say that yes, the prover is really person X. So, this is how Fiat Shamir protocol works and it is of Type Interactive proof. And here at the end of this interactions between verifier will be able to know only the 1-bit information that whether the prover is really person X or not, no other information (Zero Knowledge) is known by verifier at the end of this protocol. So, the following figure sums up the overall idea behind the Generative Interactive Proof.

Block-Chain and Zero Knowledge Proof

Typically, blockchain is merely a shared database, where you are keeping score of who owns how much cryptocurrency or other digital assets[8]. And most of the private block chains possesses two use cases: 1st is to own the external assets and 2nd is How to increase the privacy and application related to the external assets.

And for storing the general data Block chains requires to know that….

• From where the data is coming?
• What is the time-stamp?
• How to make those data immutable? And by looking at the above questions, one can easily determine that in Block-Chain privacy is not one of the important concerns as anyone can see transactions of assets like from the asset is being transferred to which location at which instance of time the particular transaction is performed if Blockchains want to transfer any kind of assets, it needs to offer internal rules on the process validating those transactions[8][9]. And this is something that the block-chains lacks from the start. As we have seen that privacy is issue in block chains. Let’s go in some deeper into the issues.

Issue 1: (Name)

As we know that block-chains were used to use the names of entities which were involved in the transactions so that everyone in the network that knows that person “ABC” is transferring amount “100 Rs” to person “XYZ”. So, privacy was the issue there. So, they come with addresses that they use addresses rather than names

Issue 2:(Address)

So, by changing the names with addresses were the normal phenomenon. But by using “addresses”: Privacy is not achieved because at first a user wants transact or send an asset on the join, then He/she needs to know the addresses. So, when you send money, others can see at which addresses it is going. And if a user knows anything about another ser from the real world, then he can track and figure out what addresses the other is using. Well yes, it is time consuming but it’s not possible. That’s why having addresses instead of names, does not help to preserve the privacy of the network, but it is not directly know that who is transferring how much amount of money to whom. It shows only that some amount “p” is being transferred from Address X to Address Y.

Issue 3:(Encryption)

As we have seen in the above paragraph that the use of addresses instead of names is more secure. But at first when a user wants to transact or send assets on the chain then he/she needs to know the addresses. So, when you send money you can see at which addresses it is going . And if a user knows anything about another person from the real world, then he can track and figure out what address the other is using. It is time consuming but not impossible. So, they came up with Encryption. They encrypt the general data while storing, they can achieve the following …

• Data preservations
• Immutability
• preserved time-stamps

And as the above three has no relations with the Data-type, therefore, we would still be able to use the distributed ledger to store any data. But there are issues with encryption too. That we would still need to rely on others to validate its existence to help and create the block in the first place. So, it’s the same process as before. And if you and your friend encrypt your transactions, nobody on the chain can ever safely use the asset any more, because everyone will be unsure of exact locations of the assets as they are encrypted. So, the asset can lose its value on the ledger. So, encryption can’t be the answer. Transparency is considered by many to be one of the block chains important traits. However, there are business such as finance businesses, which deal with sensitive information. In these situations, transparency takes a step behind the Privacy.

Introduction to Z-cash

Block chains one application is Bit-Coin which is decentralized system and it’s a public scheme. Anyone in see transaction every transaction, so privacy was not there and some financial organization can’t use this scheme. The following figure shows how transactions are open(public) in the domain(network).

So here ZKP can be used to validate the transactions between entities. without revealing any information of transactions and one of the examples of that is Z-cash which uses ZKP so the transactions are being validated privately.

And Z-cash uses Non-Interactive ZK-SNARK proof.

Comparison between Bit-Coin and Z-cash

Applications of Zero Knowledge Proof

The following list consists some of the applications of ZKP in various area.

• Anonymous credential verification
• Anonymous signatures validation
• Online voting
• Zero Knowledge Range Proofs
• Authentication systems
• Ethical behaviour
• Block Chains
• NP problems
• Abstract Examples like:
• The Ali Baba cave
• Two-balls and colour-blind friend
• Where’s wally?

Summary:

We know that the data is new treasure, and we use so much services which are trying to collect as much as information about you as they can. And to keep our data private in such phase seems nearly impossible to keep our data private. So, one can use Zero Knowledge Proof to provide information’s to such services, without revealing the actual data. So, the Zero Knowledge has the advantage that it reveals nothing more than the assertion itself. So, it can be used for so many authentication and security processes, also in finance organizations these protocols have put their very important prints and in current time it’s the one of the most popular trends in the IT era.

But with so many advantages, I also observed some drawbacks or say limitations of Zero Knowledge Proof,

Disadvantages of Zero Knowledge Proof

• ZKP does not give 100% guarantee that the claim is valid, we can minimize the probability of prover lying to almost zero but it can’t reach to exact zero
• And the algorithms used are so intensive that they require either large number of interactions between the Prover and the Verifier or require a lot of computations. That could make it impossible to run on slow or mobile devices.
• Zero knowledge proof are so good at keeping secret that we might lose access to them together. Assume that person “X”, person “Y” and person “Z” knows some recipe of some dish and this assertion they prove among all 3 of them only, so every knows only the fact that these persons knows the recipe but everyone doesn’t know “what is the recipe?” and now if 3 of them dies, so we may lose the access to the recipe. So, these are some of the drawbacks of Zero Knowledge Proof.

References

[1] Wikipedia. (14 July 2020, at 22:03 (UTC)). Zero-knowledge proof [Online]. Available: https://en.wikipedia.org/wiki/Zero-knowledge_proof

[2] Prof Bill Buchanan OBE. (16 Aug,2018). “Feige-Fiat-Shamir and Zero Knowledge Proof.” Medium Article [online]. Available: https://www.bath.ac.uk/publications/library-guides-tociting-referencing/attachments/ieee-style-guide.pdf

[3] YouTube. (Jan 14, 2019). Zero Knowledge Proof — ZKP[Online]. Available: https://www.youtube.com/watch?v=OcmvMs4AMbM

[4] Behrouz Forouzan, “Cryptography & Network Security”, TMH., Special Indian edition (if not first), McGraw-Hill Forouzan networking Series: Tata McGraw-Hill Publishing Company Limited, 2007, 426–429.

[5] HACKERnoon. (14 January 2019). WTF is Zero-Knowledge Proof [Online]. Available: https://hackernoon.com/wtf-is-zero-knowledge-proof-be5b49735f27