MPC Techniques Series, Part 8: Zero-Knowledge Proofs — What Are They and What Are They Good For?

By Ivan Damgård, Professor and Chief Cryptographer at Partisia

When you make a public transaction e.g. on a blockchain, this transaction may depend on your personal information. For instance, if you pay an amount to someone else from your account, that account should contain an amount at least as large as the payment you’re making. This is easy to verify if the balance on your account is public. But what if you want to keep both the amount on your account and the amount you’re paying private?

If you know a bit about cryptography, you will know that privacy can be obtained by keeping all amounts in encrypted form. This way, any outsider will see only meaningless encrypted information. But now there is a problem: while the receiver of the money can decrypt the payment, the parties running the blockchain cannot. So, why should they accept your transaction if they cannot verify that your payment amount is less than the amount on your account?

This is exactly the type of problem you can solve with zero-knowledge proofs. In such a proof, we have two parties: Peggy the prover and Vic the verifier. In the example Peggy would be the owner of the account. She has some public data we call x, in the example the encrypted account and payment information. She makes a claim about x, in the example the claim would say: “if everything was decrypted, you would find that the payment is valid”. Peggy now wants to convince Vic that the claim is true, in such a way that Vic is convinced beyond any reasonable doubt (that’s why it’s called a proof). But also in such a way that Vic learns nothing except for the fact that the claim is true — that’s why it’s called a zero-knowledge proof.

If Peggy sends her encrypted payment along with a zero-knowledge proof that it is valid, then everybody is happy: the bakers running the blockchain can play the role of Vic, verify the proof and only post the transaction if they are convinced by the proof. Peggy, on the other hand, is assured that nothing is revealed about her private data, except for what is absolutely necessary, namely that she did not cheat. It may seem strange or even impossible that such a proof can be given, but I’ll try to explain in a moment.

Note that the claim Peggy makes in the example has a particular property: if Peggy was willing to reveal her private data (the decryption keys and the amounts) then everyone could easily check that the claim is true. This type of claim “if I told you more information you could check it easily yourself” is known as an NP statement in computer science lingo. Amazingly, any NP statement can be proved using a zero-knowledge proof, and this covers virtually anything you would ever want to prove. In general, this is not always efficient enough for practical applications, but there are lots of important settings where it really does work in practice. In many blockchain settings, zero-knowledge proofs are used all the time for many different purposes.

Zero-knowledge is also an important tool to make multiparty computation protocols secure against malicious behavior. For instance, they can be used to get Oblivious Transfer and Garbled Circuit Protocols with active security. The principle is the same as in the example: whenever you send a message that your peers cannot immediately verify, you use a zero-knowledge proof to convince everyone that your message is correctly formed, and so you did not try to cheat them.

I will now give an example to illustrate intuitively why zero-knowledge proofs are possible. Let us go back a few years and imagine that Peggy is the first kid on the block who can solve a Rubik’s cube. She is dying to demonstrate her skills, but on the other hand does not want to make it easier for the other kids to solve the cube. So, the setting is as follows: we have a cube in position X. Peggy claims that the cube can be moved from X to the solved position S, and she knows how to do it. She wants to convince Vic, but he should learn nothing except that Peggy can solve the cube from position X. This goes as follows:

1. Peggy takes a fresh cube in position X. While turning her back to Vic, she scrambles it randomly to get to a position R, and shows the cube to Vic.
2. Vic flips a coin and shows it to Peggy.
3. If the coin is heads, Peggy must show Vic how to move the cube from R to X. She can do this by remembering the random moves she made in step 1 and doing them in reverse order.
   If the coin is tails, Peggy must show Vic how to move the cube from R to the solved position S. Peggy can do this because she can solve the cube from any (solvable) position.

We are going to repeat these three steps a large number of times, and Vic will only accept Peggy’s claim if she meets the challenge in Step 3 every time.

Now, why should Vic be convinced by this? Let’s assume Peggy is cheating: she has no way to take the cube from X to S. But then, in Step 3, Peggy cannot meet both of the challenges she may be facing: if she could, she could produce a sequence of moves taking the cube from R to X, but also one taking it from R to S. But then, doing the first sequence backwards and then the second, we can go from X to S — and that’s exactly what we assumed Peggy cannot do! It follows that if Peggy is trying to cheat, she will fail with probability 50% each time — because the coin flips are random. Already after, say 20 iterations, there is only a1 in a million chance that she will convince Vic.

Finally, why does Vic not learn any side information? Consider what he actually obtains from the interaction: a bunch of cubes in random positions R1, R2,… and for each of these, a sequence of moves M1, M2,.. where Mi takes Ri to either X or S. However, this is not very interesting information, Vic could have generated all this stuff on his own, without even talking to Peggy! Namely, for each i, take a cube in either position X or S, scramble it randomly, let the position you arrive in play the role of Ri, and let Mi be the random sequence of moves you made, in backwards order. This requires no special skills for solving the cube and the result will look exactly like what Vic gets from Peggy. But this means that whatever Vic can learn to do with the cube after talking to Peggy, he could also learn on his own!

Perhaps, after thinking about this a bit, your head will start spinning: I claim that talking to Peggy convinces Vic, but also that Vic can fake the whole interaction on his own, without knowing how to solve the cube. How can both be true? Here, you have to remember that when doing the proof, Peggy must do things in a particular order: she has to show R to Vic before she learns which challenge she has to meet. This is why Vic is convinced. On the other hand, when generating the same information on his own, Vic is in a completely different position: he is free to do things “backwards”, by starting from X or S and constructing R from one of the two.

About the author
Ivan is professor and head of the research group in cryptography at Aarhus University. Ivan is co-founder of Cryptomathic, Partisia and Sepior. He is one of the top cited and publishing researchers in cryptography, is a fellow of the IACR (International Association for Cryptologic Research), and received the 2015 RSA Award for Excellence in the Field of Mathematics.