After introducing zero knowledge proof (ZKP) through an example, we demonstrate how it can be used as a powerful tool to increase privacy and further develop many applications building atop. We have implemented a ZKP-based escrow for purchasing physical goods using bitcoin.
Zero Knowledge Proof
A zero knowledge proof lets one party (i.e., a prover), who claims to know a secret, convince another party (i.e., a verifier) that the claim is valid, whilst not revealing the secret.
Where’s Waldo?
Finding Waldo is a game where you have to find Waldo among a sea of people that look like him.
Peggy (the prover) tells Victor (the verifier) that she knows where Waldo is in a scene but she doesn’t want to show him where exactly he is. So, how can she prove to him that she has found Waldo without showing his exact position?
Peggy finds a large piece of cardboard and cuts a Waldo shaped hole right in the middle.
She then takes the Where’s Waldo scene (which is on a piece of paper) and tapes it to the back of the cardboard so that Waldo is occupying the Waldo shaped hole in the center. Victor should stand in front of the cardboard while Peggy is taping it up.
When Victor sees Waldo through the hole, he is convinced that Peggy’s claim is valid, while not knowing Waldo’s exact location. That is a zero knowledge proof.
Applications in Bitcoin
Because of the hiding nature of ZKP, it can be used in many cases where privacy is desirable. More importantly, it can also be used as a building block to construct more sophisticated protocols, as we demonstrate below.
Escrow via encrypt-and-swap¹
Alice wants to pay Bob in bitcoin to purchase physical goods. Alice and Bob generate a random private key a/b, with public key A/B, respectively. Alice encrypts her private key a under an escrow’s public key E and sends the ciphertext c = Enc(a, E) to Bob. She also sends Bob a zero-knowledge proof that c is indeed a encrypted with E. Vice versa, Bob does the same thing.
Then, Alice sends the fund to a shared public key S = A+B, to pay for the goods.
- In the absence of a dispute, Alice sends a to Bob, who can move the fund.
- In the presence of a dispute, the escrow chooses a winner. If the winner is Bob, he sends c to the escrow. The escrow decrypts c to get a and sends it back to Bob, who can redeem the fund. Likewise, Alice can take the fund if she is the winner.
There are several advantages compared with a traditional 2-of-3 multisig escrow:
- Funds are locked in a normal bitcoin P2PKH address. Only parties involved know an escrow is involved, increasing privacy.
- The escrow does not have to participate to deposit or withdraw funds when there is no dispute, potentially reducing its operating cost.
We have implemented the full protocol and the ZKP part of the code is listed below.
[1] Escrow Protocols for Cryptocurrencies: How to Buy Physical Goods Using Bitcoin. Steven Goldfeder, 2017
