What is a Zero-knowledge cryptographic proof, and how does it work?

By November 1, 2016 No Comments

A zero-knowledge proof is a method in which one person can prove to another person that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.
The classic example of a zero knowledge challenge is called Yao’s Millionaire problem: how can two people determine who is richer without either person having to reveal how much money they have? Through a complex application of cryptography, it’s actually possible to do.
Craig Gidney , writing for the Twisted Oak Studios blog, provides a simplified version of the problem that can help you understand the process. In Gidney’s example, two workers — Bob and Alice — want to determine whether they’re being paid the same amount, without disclosing how much they’re being paid to each other or anyone else. The example assumes that Bob and Alice know that they’re each being paid exactly $10, $20, $30, or $40 per hour.
Bob goes and buys four anonymous comment card boxes — the kind a restaurant might have to gather opinions from customers. He labels each one $10, $20, $30 or $40, then throws away all the keys, except the one to the box that corresponds to how much money he makes. Alice then writes “Yes” on one slip of paper and “No” on three others. She puts the “Yes” slip in the box that matches her wage, and the “No” slips in all the others. Once Alice is gone, Bob can then open his box and see if the slip inside reads “Yes” or “No.” If “Yes,” then he and Alice are paid the same wage. If “No,” they will then know that their wages are different.
This example is obviously over simplified. Zerocoin is far more complex, and includes various protections to keep anyone from cheating. But it uses a variation of this same type of thinking.