A zero-knowledge proof (ZKP) is a method of proving the validity of a statement without revealing 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.
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.”
Zero-knowledge proofs must satisfy three properties:
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.
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.
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.
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.
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:
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.
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.
Circularise is the leading software platform that provides end-to-end traceability for complex industrial supply chains. We offer two traceability solutions: MassBalancer to automate mass balance bookkeeping and Digital Product Passports for end-to-end batch traceability.