Intuitive explanations of the zero knowledge proofs on the web have been rare. There is the classic Alibaba's cave parable, but while it is generally comprehensible it's too simplistic, in my opinion, to explain the topic fully. Luckily, recent article by Matthew Green does a great job at providing an intuitive introduction to the topic:
http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.html
But while good explanations of zero knowledge proofs have been rare, intuitive explanations of non-interactive zero knowledge proofs are virtually non-existent.
This article tries to fill in the gap.
It builds on the foundation laid by the article linked above, so you'll have to read that one first.
Done? If so, let's move on.
First of all, let's note that the zero knowledge proofs, as introduced by the article, are based on conversation between the prover and the verifier: Google provides me with a solution covered by hats. I can decide to remove a pair of hats and check whether the uncovered part of the solution conforms to my original requirements. Then Google presents me with another solution covered by hats. Once again, I can remove two hats. And so on. This conversational style of proof is called interactive proof.
It's easy to see why the conversation is essential to the proof. If there was no conversation, Google would have to choose the hats to remove themselves. But if they did, it would be trivial for them to fake the correct solution. They would just have to colour the two nodes under those hats in two different colours and don't even care about colouring all the other nodes.
The same kind of reasoning, by the way, applies to any kind of interactive proof. To choose a simplest possible example, imagine you are a recruiter doing a job interview for a position that requires knowledge of Spanish. How would you make sure that the applicant actually speaks Spanish?
You can simply ask them about Spanish word for "cat". If they correctly reply that it's "gato" you'll ask what's the Spanish word for "dog". And so on. After, say, 20 questions you are reasonably sure that the applicant does speak Spanish.
However, the whole system breaks down if there is no conversation. If, for example, the applicant just sends their resume by mail and you are supposed to hire them based on that. In such case there is no way to know whether they actually speak Spanish. They can write down 20 words along with their Spanish equivalents but for all you know that may be the only 20 Spanish words they know.
All that being said, zero knowledge proofs that would not require conversation (so called non-interactive zero knowledge proofs) would be extremely useful. The case of sending a resume by mail gives you the basic idea. However, there are more ineresting use cases to consider.
Imagine, for example, that you want to prove something not to a single person, but rather to the general public. There's something like seven billion people out there, so having a conversation with each one of them is not physically feasible. If there was a way to do zero knowledge proofs in a non-intractive fashion you could just do the proof, publish it on your website and anyone interested could verify it.
Alternatively, you may want to prove something, but keep you identity secret. If you were required to have a conversation with the prover, they could track you down relatively easily. If, on the other hand, there were non-interactive zero knowledge proofs, you could just print the proof out and shove it under the verifier's front door.
Yet another interesting use case is when you want the proof to be long-lived. If you want it to work after you went offline or even after you are dead the conversation is not an option.
Ok, we are facing a dilemma here. Non-interactivity is a highly desirable property. Yet, interactivity seems to be essential to zero knowledge proofs. If there is no conversation, the prover can easily fake the solution. Now what?
Let's return to the original problem of colouring a graph. The engineers at Google will now play the part of both prover and verifier. They will take the solution, re-colour the graph in a random way and make a committment for each node (cover it by a hat). Then they will choose a vertex and remove the adjacent pair of hats. The whole process will be repeated multiple times and the results will be sent to me. The more iterations, the more confident I am about Google knowing the correct solution.
Everything works exactly as it used to except that the vertex to uncover is chosen by Google instead of me.
However, where I have just chosen a vertex in random fashion, Google has to go an extra mile to convince me that they haven't known which vertex will be chosen at the time when they were committing to the solution. If they did know, after all, they could have made a fake solution where only the two nodes to be uncovered were coloured correctly.
So, this is what they are going to do: They will take all the commitments (hats) from all the iterations of the proof, join them into a single batch and compute the hash of the batch. The hash will then be treated as if it was a sequence of integers. In each iteration of the proof one integer will be taken from that sequence and used as an index of the vertex to uncover.
I am sure you can see the beauty of the solution now. It is as if Google have caught themselves into a trap. They can compute the hash and thus find out which pair of hats to remove only after they've committed to a solution. There's no way to craft the solution in such a way as to force uncovering of any particular vertex. If, on the other hand, they want to cheat and change the solution post hoc they have to change at least one of the commitments (recall that the commitments encode the solution!), which in turn changes the hash. And different hash means that a different vertex will be uncovered. The trap have triggered!
I have already vaguely hinted at possible applications of non-interactive zero knowledge proofs, however, to give you a better idea, let me say a few words about the problem that made me thinking about the topic.
It had to do with Bitcoin.
While Bitcoin does a good job at creating a token of value independent of any state, it has the unfortunate property that all the transactions are public and thus trackable by either the state or some other malevolent entity.
What can we do to prevent that?
Well, the "amount" field for each Bitcoin address can be encoded by its owner's key. That way the attacker can track the entire blockchain but still have no idea whether any particular transaction corresponds to buying a box of matches or buying the entire country of Belgium.
The only problem with that kind of approach is that you have to convince the miners (who are in care of the distributed ledger) that you haven't created money from nothing. Sending 1 Bitcoin from one account, for example, and receiving 1,000,000 Bitcoins to a different account is not a valid transaction. Neither is sending 1,000,000 Bitcoins from an account that contains 1 Bitcoin.
This is where the non-interactive zero knowledge proofs kick in. Similarly to Google proving that the adjacent nodes in the graph have different colours you can make a proof that the Bitcoin transaction you are attempting to do plays by the rules. The proof is then sent to the miners along with the transaction itself. Each miner can thus independently verify that the transaction is valid and deserves to be included into the ledger.
December 7th, 2014