What are Zero-Knowledge Proofs and what is the implication?

Submission by Lucas Howell

Zero-Knowledge proofs are quite a common topic in Cryptography, but I’m sure with all subjects in this environment some people don’t understand the history or implications of such a proof. Zero-Knowledge proofs are just now getting a lot of recognition because of their implications towards anonymous cryptos like Odin but they have been around for a long time.

Zero-Knowledge proofs were first conceived in 1985 by three computer scientists, Shafi Goldwasser who is currently a professor of electrical engineering and computer science at MIT, Silvio Micali who is also a professor of computer science at MIT, and finally Charles Rackoff who is an American cryptologist and is working at the University of Toronto. This paper they did introduced a hierarchy of interactive proof systems and conceived the concept of *​knowledge complexity*. Knowledge complexity is the characteristic of knowledge that is derived from a high number of actors and activities that are involved in a knowledge process or knowledge is differentiated among agents, or finally, neither inputs nor outputs of knowledge processes can be observed. What that means is just how much information is given to another party.

These three computer scientists also provided the first zero-knowledge proof. This proof was first used for deciding quadratic nonresidues mod m, this is basically saying finding any x where there is an equivalent to some given number. This plus a paper by ​László Babai who is a x2 Hungarian professor of computer science and mathematics at the University of Chicago, and Shlomo Moran who is an Israeli computer scientist, the Bernard Elkin chair in Computer science at the Technion — Israel Institute of Technology in Haifa. This landmark paper invented the interactive proof systems, for which all of these five authors received the first Gödel Prize in 1993.

Why is the interactive proof system that these five computer scientists invented so important? Well an interactive proof system is an abstract machine that models computation as two parties exchange messages. One party is the prover and the prover has all the power and computational resources, but they can’t be trusted. Then you have the verifier, the guy who checks the authenticity of the prover, but has bounded computation power. Messages are then sent between these two until the verifier can convince himself that the answer from the prover is correct. So without these systems you wouldn’t be able to properly prove your identity without remaining anonymous.

Zero-Knowledge proofs have been around a lot longer than most would think, and the use cases are huge for crypto. These proofs are crucial for the Zerocoin protocol to even be possible, because you need to prove that you have these coins with no more information being given than the fact that you have them and without this proof you wouldn’t be able to send your coins using the Zerocoin protocol through the Odin network.

Odin Blockchain Community
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade