What is ZKP? Intuition for Beginners

April 16, 2020 inThoughtby Findora

Read this article on Medium.

Over the past decade, the meaning of “blockchain” has evolved significantly. Ever since its inception in the Bitcoin whitepaper, it has taken on a life of its own, evolving into an entire industry. Similarly, the technologies surrounding and empowering blockchain are maturing at a rapid pace. Zero-knowledge proofs are one such example.

While transparency is a major feature of public blockchain systems, it has also become a major hurdle for mainstream adoption. For instance, one of the reasons why cash is still being heavily used is due to its privacy. In Mexico, cash is used in 90% of all transactions. Even in the USA where cash is being actively phased out, a quarter of all Americans use cash for all purchases. 

Many privacy-enhancing features—such as hierarchical deterministic wallet key derivation, CoinJoin, and transaction aggregation—have been applied to major crypto-systems. But rarely do the features address privacy on the blockchain at a fundamental level, causing many traditional use cases to shy away from adopting this new breed of infrastructure that has massive cost-saving potential. The likely route to mainstream adoption lies in a blockchain that has native support for privacy and compliance, which is exactly what the Findora platform does. This article will introduce the magic ingredient that allows us to build such a blockchain: zero-knowledge proofs. 

We shall start from the very basics. But for those who are familiar and just hoping to learn about its uses, feel free to skip ahead to the “Use Cases” section.

Usually, the purpose of a “proof” is to convince someone that a certain statement is true. For example, we all suffered from geometry proofs in middle school mathematics. Traditional mathematical proofs are static objects: a prover writes down a sequence of mathematical statements; at some later time, a verifier checks that these statements are consistent and correct. Over the years, computer science has changed the notion of mathematical proofs. First came the change to push for more efficient verification for practical purposes. Then in the pursuit of efficient proofs, computer scientists started introducing interaction and randomness into the mix. Introducing interaction allows a computationally bounded (but randomized) verifier to check extraordinary claims efficiently. Thus Interactive proofs were born. 

Interactive proofs give rise to proof systems that satisfy the additional property of zero-knowledge. A zero-knowledge proof is a system that proves a statement without revealing anything else other than the fact that the statement is true. 

How It Works

To illustrate how ZKP works, let’s introduce a simple classic scenario involving your colorblind friend and two colored balls.

Imagine your friend is colorblind. You have two billiard balls; one is red, one is green, but they are otherwise identical. To your friend, they seem completely identical, and he is skeptical that they are actually distinguishable. You, as the prover, want to prove to your friend, the verifier, that they are in fact differently colored. You are in control of the information, and you want your friend to know that you know the color of the balls. On the other hand, you do not want him to learn which is red and which is green, thus preserving the zero-knowledge nature of the proof. 

Here is the proof system. You give the two balls to your friend. He is holding one in each hand. You can see the balls at this point, but you don’t tell him which is which. Your friend then puts both hands behind his back. Next, he either switches the balls between his hands or leaves them be, with probability 1/2 each. Finally, he brings them out from behind his back. You now have to tell him whether or not he switched the balls.

By looking at their colors, you can, of course, say with certainty whether or not he switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way you could guess correctly with a probability higher than 1/2.

If you and your friend repeat this “proof” t times, your friend should become convinced that the balls are indeed differently colored; otherwise, if you had been guessing every time, the probability that you would have succeeded at identifying all the switches is at most 2-t, or (1/2)t. For large t, that probability approaches zero. Furthermore, the proof is “zero-knowledge” because your friend never learns which ball is green and which is red. He gains no knowledge about how to distinguish the balls, and only learns what you wanted to initially prove: that they are of different colors.

One thing to note is that this simple physical example is interaction; it requires multiple rounds of interaction between the prover (you) and the verifier (your friend). However, interactive proofs are not necessary for zero-knowledge; in fact, at Findora, we use non-interactive zero-knowledge proofs, which are much more efficient and suitable for the blockchain and distributed ledger setting. 

Use Cases

We now know that it is possible to prove a fact about something without revealing what it is. But what is a zero-knowledge proof good for? What are the use cases of zero-knowledge proofs?

In authentication, zero-knowledge proof protocols offer a way to authenticate without exchanging passwords, which means identity cannot be easily compromised as there’s nothing to be stolen. 

In data privacy, when we want to keep our data private from certain people, we can prove something without revealing it using a zero-knowledge proof. For example:

In daily transactions, zero-knowledge can also help. Let’s say I am buying a car, and the seller of the car wants to sell locally. I need to prove that I live in California without telling her my specific address. Combined with a trusted oracle, a zero-knowledge proof protocol can achieve this. 

Let’s say I need to let my health insurance provider know the fact that I’ve never had a heart attack, so I can get a cheaper insurance rate. But I do not want to reveal other information on my health record. With a zero-knowledge proof, I can keep my other information confidential while letting the insurance provider know my cardiac health condition, as digitally signed by my medical provider. 

I am a business and I want to borrow from a bank. I want to prove to the bank that I have the required repayment ability by demonstrating that the assets on my balance sheet exceed my liabilities. This is doable with a zero-knowledge proof protocol. In fact, this is exactly a tool from Findora’s wide-ranging Auditability Toolkit.

Technical Use Cases

Aside from merely demonstrating knowledge, the same modern techniques that are used to build highly efficient zero-knowledge proofs also have the surprising application of increasing efficiency of a transactional system, such as a blockchain. The techniques can be used to create a proof of correctness for a computation, such as verification of a large block of transactions, which is faster to verify than the computation itself. 

ZK-Rollups is one such method, currently being explored by various developers, including Findora and some Ethereum 2.0 teams. Put simply, it increases scalability by rolling hundreds of transfers into a single verifiable transaction, effectively reducing computing and storage resources for validating nodes of public blockchains. 

Recursive SNARKs are another scaling technique based on zero-knowledge proofs. Essentially, every time a new blockchain state, i.e. block, emerges, a new proof is computed based on the previous proof and the new state. The result is that a blockchain user only needs to store a single cryptographic proof to check the validity of future transactions, thus significantly reducing storage constraints, making it available in a wider range of use cases, such as mobile. 

The development of zero-knowledge in both theory and practice is changing rapidly, and it is increasingly being applied to blockchains. The above examples and techniques are only a simple overview of what a zero-knowledge proof is, and only demonstrate a glimpse of its true potential. Once more use cases mature, it is without a doubt that zero-knowledge proofs will power future use cases, similar to how public-key cryptography is powering all secured online communication today.