Zero-knowledge proofs are generating excitement lately due to their potential to increase privacy and security in blockchain applications. The concept itself is not new, as cryptographers have been working with zero-knowledge proofs for years, but the technique is only just now poised to redefine the concept of online privacy. In this piece I am explaining the basic principles of zero-knowledge proofs and how they can be applied in the context of blockchains.
What is zero-knowledge proof?
The notion of zero-knowledge was first proposed in 1985 by MIT researchers Shafi Goldwasser, Silvio Micali and Charles Rackoff in their paper “The knowledge complexity of interactive proof systems”:
A zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that something is true, without revealing any information apart from the fact that this specific statement is true.
In other words; zero-knowledge proofs let you validate the truth of something without revealing how you know that truth or sharing the content of this truth with the verifier. This principle is based on an algorithm that takes some data as input and returns either ‘true’ or ‘false’.
There are three requirements that must be met by any zero-knowledge application:
- Completeness: If the input is true, the zero-knowledge proof always returns ‘true’
- Soundness: If the input is false, it is not possible to trick the zero-knowledge proof to return ‘true’
- Privacy: The input can not be obtained by any other party
How does zero-knowledge proof work?
The best way to explain the process of zero-knowledge proofs is with a non-digital example which is, of course, far from the complexity of zero-knowledge proofs but very well explains how they work.
Let us assume there is a blind person and two balls, one black and one white. To the blind person the balls seem completely identical. Yet, you would like to prove to the blind person that these balls are indeed non-identical without revealing that they are colored differently.
For this, you ask the blind person to hide both balls under the table and bring one ball back up for you to see. After that, (s)he should hide the ball back under the table and then either show the same ball or the other one. As a result, you can prove to the blind person that the colors are different by saying whether he changed the balls under the table or not.
Obviously, the other person might think that you were just lucky and is not yet completely convinced that both balls have indeed different colors. Zero-knowledge proofs solve this problem by repeating the experiment over and over again. After every round, your chance of being consistently right by pure luck goes down by half. So with 5 rounds, you have a 1 in 32 chance of successfully faking. With 10 rounds, it is 1 in 1024, and with 20 rounds, it is about one in a million. This way one can reach any probabilistic level of proof that is desired, although an absolute certainty can never be achieved.
Actual zero-knowledge proofs do not deal with balls, of course, but proof the validity of any kind of data. This includes financial data (transactions) or personal data (passwords, names, etc.).
What are zk-Snarks?
You might already have stumbled upon the term ‘zk-Snarks’. The term was introduced in 2012 by Nir Bitansky, Ran Canetti, Alessandro Chiesa & Eran Tromer and describes a special variation of the zero-knowledge technique. zk-SNARKs introduce a number of innovations that render them usable in blockchains. Most importantly, zk-SNARKs reduce the size of the proofs and the computational effort required to verify them.
Zero-knowledge proofs in blockchains
Zero-knowledge protocols enable the transfer of assets across a distributed, peer-to-peer blockchain network with complete privacy. In regular blockchain transactions, when an asset is sent from one party to another, the details of that transaction are visible to every other party in the network. By contrast, in a zero knowledge transaction, the others only know that a valid transaction has taken place, but nothing about the sender, recipient, asset class and quantity. The identity and amount being spent can remain hidden, and problems such as “front-running” can be avoided.
The most prominent blockchain-based system using zero-knowledge proofs is ZCash, which was also the first cryptocurrency to implement zk-SNARKs. Other blockchain-based systems have since also incorporate zero-knowledge proofs into their solutions to allow for transactions to be verified while protecting user/transaction privacy. Probably the best known of which is Ethereum, which implemented zk-SNARKS as part of the Byzantium upgrade.