A zero-knowledge proof (ZKP) is a method of proving the validity of a statement without revealing anything other than the validity of the statement itself. It is a proof system with a prover, a verifier, and a challenge that gives users the ability to publicly share a proof of knowledge or ownership without revealing the details of it.  

In cryptography, zero-knowledge proofs let you convince me that you know something, or have done something, without revealing to me what that secret thing was. It is one of the most powerful cryptographic tools that has ever been devised. In this article, we dive deeper into what zero-knowledge proofs are, and provide different examples to help you understand how they work.

A short history of ZKPs

Zero-knowledge in cryptography first appeared in the 1985 paper “The knowledge complexity of interactive proof systems [GMR85]” by pioneers Shafi Goldwasser, Silvio Micali, and Charles Rackoff. They provide a definition of zero-knowledge proofs that is widely used today:

“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.”

Or in simpler terms: “I know X, which I’m not going to tell you, but I can prove to you that this statement involving X is true.”

Zero-knowledge proofs must satisfy three properties:

• Completeness: if the statement is true, an honest verifier will be convinced by an honest prover.
• Soundness: if the statement is false, no dishonest prover can convince the honest verifier. The proof systems are truthful and do not allow cheating.
• Zero-Knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true

Interactive zero-knowledge proofs require the prover and verifier to engage in a back-and-forth dialogue in order to complete the proof. Non-interactive zero-knowledge proofs are those in which the prover sends a single message to the verifier, who is then able to check the validity of the proof without any further communication from the prover.

The zk-SNARK (Succinct Non-Interactive Arguments of Knowledge) is probably the most popular form of zero-knowledge proof, first coined in the 2011 Bit+11 paper. By 2013, zero-knowledge proof could be used in real life applications thanks to the Pinocchio PHGR13 paper which made zk-SNARKS applicable for general computing, though at a slower pace. The Groth16 algorithm proposed in 2016 greatly reduced computational complexity, and made zk-SNARKS so efficient, it is still the standard used today.

However, a trusted setup is essential for the security of these zero-knowledge protocols. An initial process used to generate the cryptographic parameters is necessary in order to be able to run the zero-knowledge protocol. This is done by a third-party to ensure that the cryptographic parameters are random, unpredictable, and secure.

Bulletproofs (BBBPWM17) were subsequently introduced in 2017, and zk-STARKs (BBHR18) in 2018. Differing from their predecessors, they are types of range proofs that do not require an initial trusted set up. The 2019 PlonK paper implemented the Universal Zero-Knowledge proof algorithm, which meant that the trusted setup only needs to be initiated once, while in comparison, Groth16 required every circuit to have a separate trusted set up.

Thanks to developments in the field, zero-knowledge proofs have transitioned from being purely theoretical to having useful real-life applications in blockchain, secure communications, electronic voting, access control and gaming. As they continue to be put into commercial use, there will be even more exciting developments to advance the technology.

Here are some conceptual examples to help you intuitively understand the zero-knowledge proofs (ZKPs) at different levels without going into the complex theories and advanced mathematics behind them.

‍

Level 1: Explaining ZKPs to a child

Example: Where’s Wally?

The simplest way to prove that you have knowledge of something without giving it away can be shown with the often-used “Where’s Wally?” example.

You and a friend want to find Wally. You have knowledge of where Wally is in the image, but your friend doesn’t believe you. How do you prove to your friend that you know where Wally is without giving away his location?

You take a massive piece of paper to cover up the entire image, showing your friend the image of Wally through a cutout. You can prove that you really know Wally’s location, yet your friend will not gain knowledge of where Wally is since the exact coordinates of Wally relative to the image would still be unknown to him.

This is a simple analogy of a non-interactive zero-knowledge proof. Anyone seeing Wally through the hole has the proof that Wally exists, and that the prover has knowledge of where he is, without giving away any other information.

‍

Level 2: Explaining ZKPs to your friend

Example: Proof of Membership

Another way of thinking about zero-knowledge proofs is with this example of the locked safe.

You meet someone you do not know, yet she claims to also be a member of the group you are part of. How can you know if you can trust her? Luckily, your group has a locked safe, and only the members of your group know the secret combination code to gain access to the safe. So write a secret message and place it in the locked safe.

‍

1.

Verifier writes a secret message and put it in a locked safe

‍

2.

Prover, who fulfils the requirements, has knowledge of the combination code and opens the locked safe

‍

3.

Prover returns the secret message to Verifier

‍

4.

Verifier is convinced that the prover really knows the combination code and can therefore be trusted

‍

If this stranger is who she says she is, she would have knowledge of the combination code. Therefore she would be able to open the locked safe and find your secret message, which would prove to you that she is a trusted member of your group after all.

This is an analogy of how an interactive zero-knowledge proof works. Only those who are truly part of the group will have the secret combination code that gives them access to the locked safe, making it possible to prove their membership without giving anything else away.

‍

Level 3: Explaining ZKPs to your team

Example: Opaque Pricing

In this example, you and a competitor discover that you are buying the same materials from the same supplier. You want to find out if you are paying the same price per kilogram. However, there isn’t enough trust between the both of you to divulge the prices you are each paying, and you are also contractually bound to not share this information.

Assuming the market rate for the materials can only be 100, 200, 300 or 400 per kilogram, we can set up a zero-knowledge proof for this situation. Let’s follow these steps to explain the idea:

‍

1. You and a competitor want to know if you are paying the same price without revealing how much each of you are paying.

‍

‍2. We obtain 4 lockable lockboxes, each with a small slot that can take only a piece of paper. They are labelled 100, 200, 300, and 400 for the price per kilogram, and placed in a secure, private room.

‍

‍3. You go into the room alone first. Since you are paying 200 per kilogram, you take the key from the lockbox that is labelled 200 and destroy the keys for the other boxes. You leave the room.

‍

4. Your competitor goes into the room alone with 4 pieces of paper, 1 with a check, and 3 with crosses. Because your competitor is paying 300 per kilogram, they slide the paper with a check inside the lockbox that is labelled 300, and slide the papers with crosses into the other lockboxes. They leave the room.

‍

5. After they leave, you can return with your key that can only open the lockbox labelled 200. You find a piece of paper with a cross on it, so now you know that your competitor is not paying the same amount as you.

‍

6. Your competitor returns and sees that you have a piece of paper with a cross on it, so now they also know that you are not paying the same amount as them.

‍

If you get a piece of paper with a check on it, both of you would know that you are paying the same amount. Since you got the paper with a cross on it, both of you know that you are not paying the same amount, but also without knowing how much the other is paying.

Both of you leave knowing only that you are not paying the same amount, but neither of you has gained knowledge of what the other is paying.

This is another analogy of an interactive zero-knowledge proof with a primitive semi-range proof. It is important to note that all of the examples have limitations and have to take on certain assumptions, but they adequately illustrate the ways they could work.

‍

How ZKPs can help your business

Zero-knowledge proofs and protocols are not magic, but they are an exciting frontier in blockchain technology. They have immense potential in a wide variety of applications where sensitive information is required, such as providing proof of password, proof of identity, and proof of membership.

Cryptocurrencies like Monero and ZCash make use of ZKPs to maintain a high level of user and transaction privacy for their users, while companies like Nuggets and Mina also use ZKPs that allow users to identify themselves with verified real-world information that does not compromise their personal data. Even ING Bank has implemented the use of ZKPs, allowing their clients to provide proofs such as proving the amount of money in their bank account without revealing the amount in a mortgage application, or proving that they live in an EU country without revealing the country.

By understanding how zero-knowledge proofs work, you can allow authentication with untrusted or unidentified parties over an untrusted communication channel. They are a fundamental tool in cryptography that can be used to prove other properties about data, making it a versatile and exciting tool for traceability with privacy in complex supply chains, paving the way for the circular economy to become mainstream.

Are you interested in finding out how zero-knowledge proofs can help your business? Read more about Circularise's revolutionary Smart Questioning solution for supply chain traceability.

‍