A zero-knowledge proof is a verification method made up of two parties; a prover and a verifier. In this proof method, the prover is able to prove to the verifier that they have certain knowledge or information without revealing the actual information. Zero-knowledge proofs provide increased levels of privacy and security for blockchain-based transactions and are most frequently used in financial and authentication-based blockchain applications.
In 1989, MIT researchers named Goldwasser, Micali, and Rackoff published the first research paper outlining the premise of zero-knowledge proofs. Goldwasser and Micali would go on to win the Turing Award, the highest honor for computer scientists, for research such as this which has laid the groundwork for modern computational cryptography. Here is a link to the original paper published in 1989.
Here’s a well-known story from Jean-Jacques Quisquater’s paper “How to Explain Zero-Knowledge Protocols to your Children” which helps illustrate the roles that the prover (known as Peggy) and verifier (known as Victor) play in a Zero-Knowledge Proof.
~~~~~
In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a ring, with the entrance on one side and the magic door blocking the opposite side. Victor wants to know whether Peggy knows the secret word; but Peggy, being a very private person, does not want to reveal her knowledge (the secret word) to Victor or to reveal the fact of her knowledge to the world in general.
They label the left and right paths from the entrance A and B. First, Victor waits outside the cave as Peggy goes in. Peggy takes either path A or B; Victor is not allowed to see which path she takes. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path.
However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path by which she had entered. Since Victor would choose A or B at random, she would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would become vanishingly small (1 in 220, or very roughly 1 in a million).
Thus, if Peggy repeatedly appears at the exit Victor names, he can conclude that it is extremely probable that Peggy does, in fact, know the secret word.
~~~~~~~
It’s important to note that traditional mathematical proofs show certainty that a given statement will always lead to the same end result, but zero-knowledge proofs rely on a computer’s ability to quickly run the same test numerous times and provide ‘statistical proof’ that there is an infinitely small possibility that the provider could be lying to the verifier. If you’d like to read more examples that explain zero-knowledge proofs you can check out this link.
A zero-knowledge proof must meet three criteria to be considered a complete implementation:
Completeness - the test can fully convince the other person that you know what you say you know
Soundness - the test can only convince the other person of the truth, not a lie
Zero-knowledge - the test can reveal nothing else to the other person
Thinking back to the example that we just read, we can see that each of these criteria is met. The test is complete since Peggy can always come out of the correct side of the cave by going through the door if necessary, the test is sound since it only convinces Victor that Peggy has the knowledge of the secret word which allows her to come out of the correct side, and the test does not divulge the secret word that Peggy wishes to keep secret.