2024.07 Vol.1

The Road to Zero Knowledge

A cryptographic proof scheme between two parties, a prover and a verifier, is considered zero knowledge if it has three properties:

1. Completeness – A prover is able to prove they know something to a verifier. The verifier is somehow fully convinced.
2. Soundness – A prover cannot fake it, they must know this something in order to convince the verifier of the knowledge.
3. Zero-knowledge – The verifier learns nothing beyond that the prover knows this something.

These rules feel both very thorough and very vague at the same time. But they allow for cryptographic tools to be described in an abstract fashion. If someone is designing a system that requires a zero-knowledge proof, there are quite a few implementations to choose from which could be plugged in. Those options have all sorts of other trade-offs between them such as performance to compute and verify, proof size, and level of required interaction.

The prover and verifier lingo sounds a lot like the Schnorr digital signature, where a prover convinces a verifier that they know a private key without telling them the key itself. Is that protocol considered zero knowledge? Turns out, not quite. To prove that a protocol is zero knowledge it needs to be shown that even if a verifier breaks all the rules, they still learn nothing. This is done by showing that there is simply nothing being exposed by the prover to learn. The Schnorr signature protocol cannot say this with certainty since the verifier is supposed to choose a challenge scalar randomly, but a bad actor doesn’t have to and could theoretically use this to somehow calculate the private key with some algebra. Now, it has been a few decades and no one has actually thought of an attack which does this. And we use this protocol all over the place so must we feel pretty good about it. But it hasn’t been shown to be perfect, it is possible that in the future some kernel of knowledge is discovered which breaks this assumption (crazier things have happened). So we add a caveat to the zero knowledge rule to describe this: honest verifier zero knowledge. If the verifier is honest (follows the protocol), it is definitely zero knowledge, but we just don’t know for sure in the case that they are dishonest.

While the Schnorr signature doesn’t meet the requirements for zero knowledge, it does meet the requirements for a different cryptographic abstraction: sigma protocols. A sigma protocol has some much more specific rules than the three above for zero knowledge, it describes the “handshake” used by a prover and verifier. But it also has three requirements which line up perfectly with Completeness, Soundness, and Zero-Knowledge except that, funny enough, Zero Knowledge has been swapped out with Honest Verifier Zero Knowledge. What are the odds! This is another abstraction “lens” to view cryptographic tools with. It turns out that sigma protocols are just so useful it is worth having its own description even if it requires the zero knowledge caveat.

Thinking back on the Schnorr signature scheme, it is possible to make it non-interactive by adding a hash function. This removes the step where a verifier chooses a random challenge. Does this make the protocol meet the three rules of zero knowledge? Ah, oh so close, but not quite. While a dishonest verifier no longer has a path to manipulate things, this now depends on the hash function really being a random oracle. If for some reason that assumption is broken, the protocol is not zero knowledge. Cryptographers are not quite ready to declare this straight-up zero knowledge, but give it the distinction Non-Interactive Zero Knowledge.