Zero-knowledge proofs are one of the more abstract and fascinating concepts in applied cryptography today. From potentially being applied to nuclear disarmament talks to providing anonymous and secure transactions for public blockchain networks, zero-knowledge proofs are a profound example of cryptographic innovation.
Background and Applications
The concept of zero-knowledge proofs was first introduced in 1985 by Shafi Goldwasser, Charles Rackoff, and Silvio Micali and actually appeared in The New York Times in 1987. They designed the notion of knowledge complexity, a metric for the amount of knowledge that is needed to transfer from a prover to a verifier for it to be considered valid.
Eventually, they were able to prove that, with some interaction between a prover and a verifier they could essentially reduce the amount of knowledge that needed to be conveyed between the two to zero. The problem that they were solving was proving that a number was quadratic non-residue mod m. Their primary concern centered around information leakage, meaning how much information will a verifier learn over the course of verifying that a claim is valid.
The math behind the concept is exceptionally sophisticated (disclaimer – I have no idea how the math works, but you can try) and their work won them the Godel Prize in 1993 for advances in Theoretical Computer Science.
Further developments saw the creation of zero-knowledge proof systems for the graph coloring problem and that anything that can be proved with an interactive proof system can be proved with zero-knowledge. Building zero-knowledge proofs over Internet protocols was more challenging and required the development of witness-indistinguishable proof protocols. Now, their integration into decentralized networks is pushing their application even further.
Non-interactive zero-knowledge proofs were eventually invented and are where the interaction between the prover and verifier is removed. Instead, a common reference string shared between the prover and verifier is all that is needed to achieve computational zero-knowledge. These types of mathematical and computational assumptions are why zero-knowledge proofs are commonly referred to as “crypto magic,” that are exceedingly difficult to understand even from an abstract perspective.
Regarding cryptocurrencies, non-interactive zero-knowledge proofs could also be obtained in the Random Oracle Model using the Fiat-Shamir heuristic. This introduced the concept of zk-SNARKs, which has formed the foundation for anonymity within the Zcash cryptocurrency. Subsequently, bulletproofs were introduced by the Stanford Applied Cryptography group as short non-interactive zero-knowledge proofs that removed the need for the controversial trusted setup within Zcash and other protocols using zk-SNARKs. Finally, zk-STARKs were created earlier this year and also eliminated the need for a trusted setup.
Zero-knowledge proofs have a wide variety of applications due to their unique nature. They are particularly effective in secure communication, authentication, and privacy.
The application relevant to cryptocurrencies is anonymity in transactions. Platforms that use some form of zero-knowledge proofs include ZCash, Monero, PIVX, and Zerocoin. Importantly, these cryptocurrencies use zero-knowledge proofs to obfuscate the details of transactions on public blockchain networks. These details include the sender, recipient, and the amount transferred.
The use of zero-knowledge proofs across a decentralized public network where value transferred is a groundbreaking advancement. The ability to completely anonymize network transactions over a public network is an incredible feat that should not be overlooked.
Another prominent application of the technology is in authentication systems. A zero-knowledge proof of knowledge can be used to prove secret information like a password without actually revealing the password. Zero-knowledge proofs are typically too cumbersome for usefulness with just passwords, but eventually, this could provide very useful for protecting user passwords across the Internet.
Zero-knowledge proofs can also be applied in identity verification. For simplicity, to access a high-security facility you would either need a PIN number or authenticated identity card to gain access through a door. The authenticating component of the door represents a security hole as it could potentially be manipulated to learn the access PIN. Using a zero-knowledge proof, the component could contain a number n without its factorization.
Authorized users would be given the solution to this particular problem instance, and they can prove to the authenticating component that they know the solution without actually entering anything specific to the solution into the authenticating component. Therefore, manipulating the authenticating component to find the PIN will not work since it does not actually store the PIN (solution).
How They Work
A zero-knowledge proof is where a prover (Alice) can prove that she knows information x to a verifier (Bob) without communicating any other information to Bob other than the fact that she knows x.
By definition, a zero-knowledge proof must satisfy the following three properties:
Completeness is the high-probabilistic chance that if Alice is telling the truth, Bob will eventually be convinced that she is telling the truth.
Soundness is the fact that Alice can only convince Bob if she is telling the truth.
Zero-knowledgeness is that Bob doesn’t learn anything about Alice’s secret knowledge (solution).
The complexity of zero-knowledge proofs results in them typically being described with abstract examples. Several are available including the Ali Baba Cave, Two Balls and the Colour Blind Friend, and The Telecom Giant. All of them do a solid job at elucidating the concept of zero-knowledge proofs but let’s focus on the first one, the Ali Baba Cave.
The story comes from a paper titled “How to Explain Zero-Knowledge Proofs to Your Children” by Jean-Jacques Quisquater and generally goes as follows:
A slightly tweaked and more useful example can be used with Alice and Bob.
Alice discovers the secret phrase to open a secret door in a strange cave. The cave is shaped like a ring with the secret door blocking the paths from connecting at the end. Bob wants to know the secret word, but Alice will not reveal it to him.
To solve the situation, they label the two pathways A and B. Alice takes a path while Bob waits outside and cannot see which path she chooses. Bob enters the cave and shouts which path he wants Alice to return on. Because Alice has the secret phrase to the door, she can return on either path, easily returning on the path that Bob shouts. She also does not need to reveal the secret phrase in order to do so.
If Alice does not know the secret word, she will have a 50 percent chance of returning on the desired path. However, over continuous attempts, the odds of her being able to anticipate Bob’s request would be negligent.
Since she has the secret phrase, her ability to return on the desired path consistently demonstrates to Bob (with extremely high probability) that she knows the secret phrase. To third-party observers, they cannot see Alice in the cave due to its shape so they would only see Alice return on the correct path. This effectively makes the whole interaction between Alice and Bob anonymous.
Zero-knowledge proofs will continue to be applied wherever they are useful as they continue to develop. The underlying technology may be extremely complex, but their potential for privacy, authenticity, and security cannot be overstated.
The use of zero-knowledge proofs in cryptocurrencies is pushing the innovation of the technology even further. If you’re looking for a more technical breakdown or real-world examples from a technical perspective, Matthew Green provides an excellent analysis of the technology with some cool thought experiments.
Zero-knowledge proofs rightly take their place as one of the most complicated and unique technologies used in blockchain networks. Their implications are forward-thinking and have even attracted the admiration of Google’s co-founder Sergey Brin.
The application of zero-knowledge proofs in cryptocurrencies will continue to lead the way in revealing one of the most exciting and anonymous technologies available today.