What are Zero Knowledge Proofs?

Before we begin to break down the technical aspects of the protocols, it is important to understand the underlying technology behind a zero knowledge proof (ZKP).

ZKPs originate from a cryptographic method called interactive proofs (a system where a prover can exchange messages with the verifier to convince them that some statement ‘x’ is true, which allows two parties (the prover and verifier) to share secrets – with a high degree of probability and without actually having to reveal any information about proving the statement.

The term “zero knowledge” comes from the fact that no information is shared regarding the secret, but the second party (the verifier) is convinced that the first party (the prover) knows the secret. Three properties that every zero-knowledge protocol must satisfy are: completeness – convince the verifier of the truth with a high degree of probability, soundness – can only convince the verifier of the truth if they are telling the truth, and zero-knowledgeness – the verifier doesn’t learn anything about the solution/secret.

Let’s quickly illustrate a couple very basic implementations for zero knowledge proofs:

First example, there are 2 people (Person A and Person B) and they are trying to determine if they have the same amount of money in their wallet.

If we assume they can either have $10, $20, $30 or $40 in their wallets then Person A will have 4 lock boxes that are each labelled accordingly.

Person A will be the only person with the key to every lock box and will throw out every key except for the lock box that is labelled with the amount of money he has – for this example let’s say $40.

Person B then takes a piece of paper and writes a ‘+’ sign on it, then slips the piece of paper into the lock box that corresponds to the amount of money they have in their wallet – let’s say $30.

When person A returns to the box and unlocks his box with the only remaining key he will discover that Person B does not have the same amount of money as he does. Person A knows they have a different amount of money, but no way to tell how much more they have.

In essence, both people in this example can only surmise evidence from the statement being proven. Person B cannot know how much money Person A has (and vice versa) because the statement being proven was if they had the same amount of money. However, this example assumes reasonable and fair actors with no incentive to lie throughout the protocol.

Now let’s go through one more example that fulfils the 3 characteristics of a sound zero knowledge proof protocol discussed above.

One of the most popular examples begins outside a circular cave with a locked door at the back.

The ‘Prover’ is trying to convince the ‘Verifier’ that they know the code to the door to get to the other side of the cave. The prover goes into the cave and stands at the back; the verifier then goes into the entrance and shouts a direction (A or B) for the prover to walk out.

This protocol will be repeated ‘X’ number of times, each time making the likelihood of the prover to be a malicious actor more unlikely. There are a couple scenarios that could occur: if the prover is lying and does not know the combination to the door then there is an extremely high probability (exponentially increasing with each trial) that the verifier would call a direction the prover did not enter in the cave (the verifier would see this), if the prover does know the code then they will be able to exit the cave the right direction 100% of the time.

This covers every property for a sound ZKP protocol because a malicious actor cannot convince the verifier successfully after ‘X’ number of trials, the verifier will be convinced after ‘X’ number of protocol completions and the code to the door (or the secret) is not revealed

Why are they important?

On public blockchains, such as Bitcoin or Ethereum, it is well known that every single transaction is recorded into the public ledger that can be accessed by anyone. This ledger contains information about both the sender and receiver, the quantity of the asset and the specific digital asset. However, this is not an ideal solution for every blockchain use case. The first iteration of ZKPs was called zk-SNARKs that made the proofs usable on the blockchain by reducing the size of the proof and the amount of computational energy needed to verify the proofs. The protocol allows for complete privacy on the ledger including the quantity, asset type and information about the sender and receiver. The rest of the chain only recognizes that a valid transaction took place.

Where has this form of cryptography been implemented?

The most popular implementation is Zcash, which was the first cryptocurrency that baked this form of cryptography (zk-SNARKs – Succinct Non-Interactive Argument of Knowledge) into its protocol layer. The main problem with the protocol for Zcash is how the chain was created. There is no way to audit the supply to determine if the chain/security has been compromised at any point. This would occur if the master keys were not destroyed after the creation ‘ceremony’ and they were in fact compromised.

To combat this, the Zcash foundation has been releasing annual audits to prove that the supply is what they claim it to be, but unless you trust the creators/investors then there is no way to prove these claims with 100% reliability. A co-author of the Zcash whitepaper has also said that the trusted setup can be compromised efficiently by quantum algorithms, meaning that in the currency’s current state it is not “future-proof.”

It is important to note the massive incentive that a person or entity would have by compromising the master keys – they would have the ability to print infinite amounts of the currency and slowly sell them off without people knowing.

A more recent implementation of zero knowledge proofs comes from a company called Starkware that recently popped up claiming investment from the likes of: Vitalik Buterin, Polychain, Bitmain, Zcash co. and Pantera to name a small number of investors. The founders of Starkware plan on implementing the second iteration of SNARKs, called zk-STARKs (Scalable and Transparent Argument of Knowledge) and claim that it is the more trustless and secure than SNARKs.

While it also does not require the “trusted setup,” it promises to be cheaper, faster, more scalable and post quantum secure when compared to the current iteration of zero knowledge proof protocol. Many researchers/developers from the Zcash project are currently working to develop and implement the STARKs solution, giving the project a ton of credibility (at the time of writing).

Zero knowledge proofs are an important form of cryptography that top researchers and developers are using to create a private, scalable and secure blockchain protocol. The upcoming developments for the second iteration of ZKPs (zk-STARKs) are exciting, and now you have a basic low-level understanding of how they work.

Article written by Gavin P.