Zero Knowledge Proofs

Jarred McGinnis
January 25, 2021

It was typical of renaissance and early-modern scientists to use anagrams or proto-hash functions of their scientific discoveries. The anagram of a Latin sentence would be published as a way of staking a claim to a scientific discovery that still required further research or results. It was a way of demonstrating information was known without revealing the information that another scientist could use to steal the credit for the discovery. When the research was completed, the scientist would reveal the original sentence, which could be verified against the published anagram. This type of commitment scheme was used by Galileo to lay claim to the discovery of Saturn’s rings, though at the time his telescope showed them as two lobes on either side of the planet. Newton sent an anagram to Leibniz to let him know calculus wasn’t big enough for the both of them.

In a world of tech-giant panopticons and an increasing amount of privacy legislation, it is important to have a finer grain of control over how and what information is being shared. Renewed interest in Zero Knowledge Proofs (ZKP) is due to their unique way of guaranteeing that knowledge or information exists while ensuring that information is kept private from a third party, or even the verifier. ZKP is being used for blockchain ledgers to keep transaction details private while still ensuring they were legitimate transactions. The Dutch bank ING has seen zero knowledge proofs as a way of offering products such as loans to customers without the customer needing to reveal personal information like salary. More recently, ZKP have been employed for COVID-19 contact tracing apps.

What is Zero Knowledge Proof, without using the word tuple or non-empty set?

Okay, but tuple is a fun word to say. A tip-top triple tuple from Tupelo.

There is a maze, and it has a number of exits and entrances. To be able to solve this maze, you need to know how to go from any one entrance to any one exit. If you solve the maze, you get to be in the maze-solver club. You want this. Maze-solver club’s canapés are top-notch. You also don’t want to give away the solution because that means everyone could get into the club, and that means fewer awesome tiny blinis with caviar on top for you. One of the club members is going to verify that you can prove that you know how to solve the maze. The easiest way would be for the verifier to follow you through the maze, but what if the verifier is an imposter? Well, you just lost a share of the little hot dogs wrapped in bacon, because you gave away the solution. There needs to be zero knowledge exchanged in this proof. You can go into an entrance and come out of an exit, proving you can solve the maze without giving any of that information away.

However, the verifier will be damned if he’s going to miss out on the club’s canapés to some upstart who hasn’t solved all of the maze’s routes. What if you only know how to get from entrance 1 to exit A, that’s not enough for the club. So it’s the verifier that tells you which entrance and exit you have to take. You dutifully do the course. There’s a possibility that the verifier happened to pick a route you knew. So, he chooses another and another until he’s comfortable sharing the club’s lovely salmon mousse on a slice of cucumber with you. And, there’s the rub with ZKP, they are a probabilistic proof. By increasing the number of verification interactions, it’s possible to minimize the chance that the prover is cheating, but it can never reach zero.

Who is Using ZKP

The mathematics for Zero Knowledge Proofs was developed in 1985. The more recent interest has been driven by blockchain projects, most notably Zcash. They want to ensure that the ledger can be verified by every node in the network through a non-interactive approach without revealing the details of the transaction. The maze example above is an example of an interactive approach, which has some serious scaling issues. You’d starve to death if you had to verify millions of routes with millions of club members. Blockchain applications exist beyond the wild west of crypto-currencies. In fact, we should be thankful that these blockchain projects have proven to be an incredibly useful ‘real-world’ sandbox to produce more robust and mature solutions using ZKP and other cryptographies. Besides ING’s zero knowledge range use case, J P Morgan and EY have also been researching ZKP protocols.

The next time, and there will be a next time, a news story announces a titanic data breach because a company had an expired certificate for almost a year — side eye at Equifax –, you’ll remember why it might be a good idea to keep your data to yourself. As an aside, we’ve got a webinar coming on certificate outages. However, unless you are going off the grid completely, we live in a world that runs on data. ZKPs are seen as an alternative to the centralized warehouses storing enormous indiscriminate amounts of personal data on you and your behavior. When you consider that some of that data has probably been collected without your consent, it is of increasing interest to be able to limit what organizations need to see. For companies, holding that personal data is seen as a liability, and 2018’s GDPR is the beginning of governments taking privacy concerns seriously. Companies see ZKP as a way to still offer their products and services without falling foul of increased public awareness (and litigation) around privacy.

Should I be using ZKPs?

There are two types of cryptography: ones that have been cracked, and those that will be.

Applications using zero knowledge proofs are brand new. It’s early days. Even without the threat of malevolent actors, the counterfeit Zcash bug is a warning to proceed carefully. Now is a good time to remind you that ZKP are never a proof in the sense that they are 100% secure. Repeating iterations of verification is about getting the level of doubt to somewhere you are comfortable with. However, proof by probability is probably — pun intended — going to be okay for most applications. There is also an argument that interactive ZKPs have limited transferability as the verification process has to be done over and over. For non-interactive ZKP such as the zk-SNARKS that are at the heart of a number of blockchain projects, will be limited by their computational intensiveness. The other risk is that zero knowledge means zero knowledge, it is possible that though you can still prove you knew the information, the information itself might be lost and irretrievable. With that health warning, there’s a lot of development in this space, and it will be something to watch out for in the future.

To find out more:

With ZKP’s unique balance of security and anonymity, it is becoming a part of the cryptography ecosystem. The finance and insurance industry’s interest in blockchain ledgers and, more recently, contact-tracing, ZKP are moving beyond theory and into practice.

Watch our recent webinar on avoiding certificate outages.

The Isaac Newton Institute at Cambridge University has an interview with Eli Ben-Sasson, the co-founder of StarkWare, and one of the early-proponents of ZKP.

Some more references:
Simply Explained
What the Fintech