What are Zero Knowledge Proofs?

This post is part of our Privacy-Preserving Data Science, Explained series.

With the advancements in the field of Artificial Intelligence, our economy has become increasingly data-driven. Organisations harvest our data en mass in order to tap into information held between the data points. For this reason, there's an ever growing economic incentive for organisations to store your digital footprint as you participate in their technological ecosystem. Surveillance capitalists may use this data to learn what makes us tick, generating revenue through targeted online advertising. While this is relatively innocuous, this technology has since been adapted into far more insidious sectors than retail. The previous 10 years has seen use of these scalable tools of mass persuasion in order to undermine democracy and even as an incitement to violence.

With these tools surveillance in ever increasing use, consumers of technology find themselves in a catch-22. Consumers can continue to engage in extremely useful online services, relinquish control of their data, and in many cases have their agency manipulated. On the other hand, they can choose not to participate in the digital economy and be cut off from a host of high utility services like social media, map software and search engines.

With this in mind, there is a growing appetite for tools to help manage the the trade-off between privacy and participation. One tool archetype in this intended transformation is Zero Knowledge Proofs (ZKPs).

What are Zero Knowledge Proofs ?

The concept of zero-knowledge proofs was first conceived in 1989 by Shafi Goldwasser, Silvio Micali and Charles Rackoff in their paper "The Knowledge Complexity of Interactive Proof-Systems". This paper introduced the concept of interactive proof systems which deals with Knowledge complexity, a measurement of amount of knowledge about the proof transferred from the prover to the verifier.

In simple terms, ZKP can be described as a mathematical method to prove to a party that you possess some knowledge without actually revealing the underlying information.

For example, let's say you go to a bar. The bartender asks for your drivers licence so they can verify your age. You want the bartender to know you're over 18 so they can sell you a drink. However, you don't really want the bartender to know where you live or even how old you actually are. However, you need to present all of that information to the bartender because it's all contained in your drivers licence. Under a ZKP method like CL Signatures, you could prove the value of your age is over a given threshold value without revealing the actual value of your age.

Properties of Zero Knowledge Proofs:

ZKPs as a type represent a smorgasbord methods which all must possess the following three properties;

1) Completeness: If a statement is true, and the protocol followed by the prover and verifier is true, then the verifier will accept the proof.
2) Soundness: If the statement is false, even-though the verifier follows the protocol, the verifier will not be convinced by the proof
3) Zero-Knowledge: If the prover follows the protocol, and the statement is true. then the verifier will be convinced that the provers' proof is right, without learning any information from their interaction

Consider the following, very basic, ZKP protocol.

Imagine, your friend Alice is colour blind. Your friend Bob has two identical balls, however, one is red and another is blue. Alice has no way of perceiving this difference in colour and will not refuses to trust Bobs assertions that they are different. Alice has zero-knowledge of the ball colour, Bob must prove that the two balls are different colours to Alice. The following ZKP method solves this particular problem;

1) Alice takes the balls and and passes them between her hands behind her back.
2) Alice then presents both balls to Bob and challenges him to identify the 'blue' one.
3) As Bob can see the colour of the blue ball, they correctly identify it.
4) These steps are repeated over a number of times. Eventually the probability of Bob predicting the correct ball each time will be so low that it is beyond all reasonable doubt that Bob is telling the truth.

Source: https://blog.goodaudience.com/understanding-zero-knowledge-proofs-through-simple-examples-df673f796d99

Probability of choosing from 1st time swap = 50%
Probability of choosing from 2nd time swap = 25%
Probability of choosing from 3rd time swap = 12.5%

On repeating this experiment several times, the probability gets reduced by 50% every time. When the probability of choices reduces to zero, Alice will be able to tell if the balls are of different colors.

Relating this experiment to the properties that was mentioned before, we find that

Property 1 (Completeness): Your friend must be convinced that the balls are different
Property 2 (Soundness): The probability of all switches/non-switches approaches zero, which convinces that the balls are different coloured
Property 3 (Zero-Knowledge): Your friend has no knowledge about the colour of the balls
There are many such abstract examples and implementations of ZKPs, they can be viewed in the below mentioned links.

Application of Zero Knowledge Proofs:

1) Used in cryptographic protocols for maintaining privacy. With the properties of ZKP, we ensure that the privacy of the user is not compromised
2) Used in Blockchain like Bitcoin or Ethereum transactions, which keeps the transactions transparent while abstracting the sender/recipient details
3) In 2016, the Princeton Plasma laboratory demonstrated a technique for nuclear disagreement talks, without revealing information about its working.
4) Used in Authentication systems where one party wants to proves its identity to other party without revealing the secret like password.

Further reading/implementation on ZKP: