Zero Knowledge Proofs (ZKPs)

Last updated on Sep 21, 2021 security, zettel, zkp

Motivation

I first got introduced to ZKPs through the crypto world, through a currency called Monero. I always thought money laundering with Bitcoin was possible, but it’s not really. Bitcoin is pseudo-anonymous, and there are lots of marked and ‘poisoned’ bitcoins out there people know were acquired through hacks or other black market activity. Apparently there are now even ‘virgin’ bitcoins, newly minted, unstained ones that might be worth more in the future.

ZKPs come into Monero by maintaining the integrity of transactions. Monero can allow black market trades and money laundering because it fuzzes its transactions with many recipients, making it ‘security by obscurity’. But through this chaos, we need to be able to prove transactions ARE still happening, the system actually works. You fooled other people, but are you also fooling yourself?

Bitcoin and ethereum are transparent between addresses. Monero is not. How can we verify something as real, without actually showing it, such that the skeptic is 100% convinced?

Zero-knowledge proofs

In essence, these proofs are usually interactive (think handshake), and iterative (multiple rounds of communication) between a prover and a verifier. The prover proves they know a piece of knowledge, without revealing any knowledge about it to a verifier.

Examples

Colored Balls

Imagine you have two identical looking balls, except one is red and one is blue. You, the prover, can perceive color, but your friend, the verifier, is color blind. You want to convince him color exists, without revealing the colors of the balls.

Answer

Have your friend hold each of the balls behind his back, and mentally note the balls as left hand and right hand. Turn your back to him so he can place an original ball on the table for you to see, then turn your back again after you've noted the color. Have him take the ball back, and either put the original ball back or replace it with the other ball. You, being able to see color, can tell him whether it's the same ball or a different ball each time.

Play numerous rounds, as many as needed for your friend to be convinced you are not getting lucky guesses $0.5^{number of rounds}$.

Formalization (Ignore me)

Further

Ethereum hack relevancy
Cold war
IP protection