The Idea Behind ZKPs
A non-mathematical introduction to Zero-Knowledge Proofs.
János Bolyai published his work on non-Euclidean geometries in 1932, three years after discovering them. His father Farkas Bolyai received an interesting letter soon after. Gauss wrote to Bolyai: "To praise it (János's work) would amount to praising myself. For the entire content of the work... coincides almost exactly with my own meditations which have occupied my mind for the past thirty or thirty-five years." His friendship with Bolyai was strained as a result of this unsubstantiated accusation of plagiarism on Gauss' part. Whatever the case might be, Bolyai never published any work in the field thereafter.
A paradigm change in the field of mathematics was brought about by the discovery of non-Euclidean geometries. The erroneous notion that Euclid's axioms were the only method to make geometry consistent and non-contradictory was shattered among mathematicians. Further research on these geometries led to, among other things, Einstein's theory of general relativity, which describes the world as non-Euclidean. Whom do we owe this wonderful finding, then?
Gauss is one of history's greatest mathematicians. He had an exceptional influence in many fields of mathematics and science. If he really had discovered non-Euclidean geometry before 1829, why didn't he publish it? Was he bluffing? Throughout history, it hasn't been uncommon for mathematicians to plagiarise the work of their peers.
From another letter of 1829, it appears that Gauss was reluctant to publish his findings because he believed the mediocre mathematical community would not be able to accept a radical rejection of Euclid's geometry. If Gauss had only discussed his findings with someone, there'd be no questions raised about who discovered non-Euclidean geometry first. Then again, maybe that person would have stolen Gauss's work and published it under their name?
This mystery remains unsolved. But it makes us wonder– what if there was a way for Gauss to only convey that his findings were true without giving away any additional information? Crazy, right?
Well, zero-knowledge proofs make this possible. ✨
Who This Is For
Zero Knowledge Proofs (ZKPs) are one of the greatest recent advances in cryptography, nothing short of (mathematical) magic! There has been a lot of ZK-based innovation in the blockchain space of late. The proofs are complex and the mathematics is hard to wrap one’s head around.
Although there is an abundance of content about different ZKP implementations, there is a lack of comprehensive resources that start from the very basics and then delve into the details of all the wonderful things being built using ZKPs. This is my attempt at creating such a resource.
This article is the first part of a series of articles explaining how ZK based architecture works. The article does not assume any prior knowledge about ZK Proofs and their mathematical foundations. Here is a tentative list of topics that we'll cover in this series:
A mathematical introduction to ZKPs
ZK for all NP
Proofs of knowledge
Constant round ZKP
Witness Indistinguishability
Non interactive ZK
ZK limitations
Sigma protocols
ZK implementations
ZK-EVM
I'll get started with a non-mathematical introduction to ZKPs now. Hope you like it!
Proofs have long served as the foundation of mathematics; we know something is true by proving it. The statement "the sum of the angles of a triangle equals 180°" can be proven by finding the sum of the angles of any triangle in the world. Anyone, even someone who didn't know the proof was true beforehand, can follow the steps of the proof and see that it is correct. We use proofs to establish the validity of an assertion.
Informally, the goal of a proof is to convince someone that a certain statement is correct. Since the ability to prove certain statements is crucial for many cryptographic applications, proofs were formalised in computer science.
Interactive Proof Systems
In computer science, an interactive proof system is an abstract machine that models computation as an exchange of message between two parties: a Prover and a Verifier.
- The Prover P has unbounded computation power, but is untrustworthy.
- The Verifier V has bounded computation power, but is always assumed to be honest.
The Prover attempts to convince the Verifier that a mathematical statement is correct. They exchange messages until the Verifier either accepts or rejects the statement. An interactive proof system has two characteristics:
Completeness: If the assertion if true, the Prover will eventually persuade the Verifier.
Soundness: The Prover cannot dupe the Verifier into believing a false statement (except with a negligibly small probability).
The majority of the early work on interactive proof systems focused on its soundness. Then an entirely different question was raised by Goldwasser, Micali and Rackoff (GMR) in 1985: what if you can't trust the Verifier? The concept of "zero knowledge" was then proposed by them as an answer to that question.
Zero Knowledge Proofs
The issue Goldwasser, Micali and Rackoff were concerned about is "information leakage". How much information is the Verifier going to learn during the course of this proof, beyond the mere fact that the statement is true? Hence, the concept of "zero knowledge proofs" was born, where no information is revealed to the Verifier beyond the validity of the assertion. But this seems counterintuitive– don't we associate conviction with knowledge transfer?
When fully realized, zero knowledge proofs allow you to prove a statement to anyone without revealing anything about it. I won't know what you know, I'll only know that what you know is true.
ZKP Properties
In addition to completeness and soundness, zero knowledge proofs have a third additional property called "zero-knowledge" (no surprises there). So, the third property of ZKPs can be stated as:
Zero-knowledge: If the statement is true, the Verifier learns no other information except this fact.
What Zero Knowledge Really Is
So, we're talking about protocols that don't leak any information, but what do we really mean by that? What really is zero-knowledge? The idea is explained really well by Matthew Green in this article .
The gist is, the Verifier can't really compute anything after the interaction that they couldn't have before the interaction took place. They learn no additional information during the course of the interaction, it'd be as if they could've spoken with themselves.
This marks the end of the first part– the second part comes out soon. It covers the ideas we’ve discussed about from a mathematical PoV.
Subscribe to stay tuned!
If you have any suggestions, comments or just want to send a pepe meme– you can find me on Twitter at @gryptooo . Thanks for reading. :)