Zero-Knowledge Proofs

To ensure MobileCoin users can communicate securely with each other and send and receive MOB tokens while preventing adversaries from tampering with or learning about their transaction amounts, we at MobileCoin have implemented Zero-Knowledge Proofs (ZKPs) with computational indistinguishability. ZKPs make sure that no one, except you, and not even the messaging application's service provider or the MobileCoin developers, can access your personal data.

To a Grandparent:

Suppose an older gentleman is getting up in years and he is nearly blind. In the morning he dresses, reaches into his sock drawer and pulls out two socks. He asks his wife what the colors of the socks are. His wife tells him one is red and one is yellow. She says he can't wear those because they don't match. He knows that she can see the socks and that she can tell if they're red or yellow. But, he also knows that she could just be messing with him for her own amusement. She has a weird sense of humor. So, he doesn't really trust her. In order to tell what the truth is, he plays the sock game.

He places the socks behind his back and he swaps them a number of times, so she can't see which ones they are. But, he keeps track of them and knows which one is which. He asks her, which one is the red sock? If they're both red and indistinguishable, she has to guess with a 50/50 chance the sock is the one she previously said was red. But, if they are yellow and red, then they are distinguishable and she can just point to the red sock. If, by chance, she guesses the correct color of sock three times in a row, then he knows that she knows that they're different somehow. Note: He'll never be 100% sure that she wasn't playing with him, but after enough iterations, he is fairly convinced because the probability of her guessing right is so low that it's negligible.

This answers the first property of ZKPs, which is completeness. If the socks are indeed different colors, she will be able to answer the test questions 100% of the time.

The second property is soundness. If the socks are not different colors, her chance of passing all of the tests is very low.

The third property is zero-knowledgeness. If the statement is true, and the socks are different colors, the verifier (the old man) only learns that the statement is true and nothing else. In this case, the zero-knowledgeness is true. However, suppose we videotape this interaction with a black and white camera. Suppose you watch the video tape and this interaction where his wife guesses right every time. And, at the end you see that the older gentleman believes that the socks are a different color.

Does watching the video convince you that it's true? The answer should be, "No, watching the video does not convince me." You can't tell by watching the black and white video what color the socks are. The proof convinces the old man and he knows he chose the sock randomly. But, if you're an observer, you can't know that the two didn't collude, and you can't know that those numbers aren't random, because you didn't choose the number of times that he should swap the socks. He could just be pretending to be satisfied with her answers when the socks are actually the same color. Indeed, anyone could make such a video, whether or not the socks are the same or different colors. Because anyone could make such a video, whether or not they know the color of the socks, we can be sure that the video doesn't convey any information at all about the socks. So, in this case, the interaction is zero knowledge.

To a First Year College Student:

When learning about cryptography, ZKPs, or computer algorithms, are a protocol where one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids expressing any additional data except that the statement is indeed true. For example, ZKPs are a generalization of digital signatures. I want to sign a message and prove to you that I signed it. The secret is my secret key that is associated with a public key in any asymmetric cryptology system used to connect to the internet securely. A particularly simple form of ZKP is proving that I possess this key. And so I produce the signature and in order for it to work correctly, there has to be this random challenge aspect. But if I just look at the output, a bunch of raw bits of signature, I shouldn't be able to distinguish them apart from essentially just random noise.

In addition, ZKPs can be either interactive or non-interactive ZKPs. Interactive proofs are primarily used in theory to provide the definition of ZKPs, which rely on the verifier randomly challenging the prover through multiple steps until the verifier believes the statement is true.

In practice, it is typically highly desirable to eliminate interaction from ZKPs. Non-interactive ZKPs can be produced entirely by the prover, and then verified by anyone. There is a general technique for making interactive proofs non-interactive, called the Fiat-Shamir transform. In fact, Bulletproofs are constructed by applying the Fiat-Shamir technique to a secure interactive zero-knowledge range proof, which is where the security ultimately comes from. This works for any "public coin" interactive proof, where the verifier's messages are always simply random challenge values, and the verifier does not need to hold any secrets. In the Fiat-Shamir transform, the verifier is "simulated" using a hash function. Whenever the verifier needs to create a challenge value, we determine this challenge value by taking all messages the verifier has seen so far in the protocol, and feeding them into a hash function. Then the results of this hash function are used as the challenge value. The idea is that the hash function typically produces uniformly distributed output values, and it is intractable for a malicious prover to "tamper" with the hash function by driving it to produce specific chosen challenge values. As long as the output looks random and the prover can't influence the challenge values, the security of the protocol is the same as the interactive version.

This is very useful also in cases where repetition is used to increase confidence in the interactive proof. For instance, suppose we wanted to drive the chance of successfully cheating in the sock game down to 2^{-100}. In the interactive protocol, we have to play the sock game 100 times, so that's 100 back-and-forth messages. If we can make it non-interactive, then there's only one message, which contains all 100 challenges and responses.

To an Engineer:

Now, for ZKPs to be useful, what we really want to do is get rid of the need for interaction. Ideally, the proof is just a message that one party can send to another without knowing who it will be in advance. For many useful ZKPs, the only interaction the verifier has to do is send random challenge values. Cryptographers can make these "interactive proofs" non-interactive by replacing the challenge values with the output of a cryptographic hash function. A hash function is not strictly speaking random -- it is deterministic based on its inputs. However, cryptographers agree that hash functions' output can look random and are hard to tamper with in any way. So, instead of the prover interacting with a verifier to convince a statement is true, the prover "simulates" the verifier using the hash function. The prover may play the sock game 100 times (against the hash function). The prover then writes down the entire transcript of messages in the protocol, and can send this to anyone. Anyone can verify that the hash function was evaluated correctly to compute challenge values, and that the verifier indeed was convinced each time successfully. Such transcripts can then be committed to a blockchain so that anyone can later verify the correctness of the chain.

We incorporated a specific kind of ZKP called Bulletproofs, to build "range proofs" for encrypted values, proving that commitments to value lie in a specific range, without revealing the values to the verifier. These range proofs are critical to ensure our transactions remain private and balanced without revealing to the verifier the amounts of the transactions. Bulletproofs are short non-interactive ZKPs, and are used in the transaction math constrained to small positive numbers existing within a specific range -- which is all part of the specification for the protocol. Bulletproofs are designed to allow efficient confidential transactions in cryptocurrencies where the amount that is transferred in the transaction is hidden.

In every instance, ZKPs must satisfy three properties:

1. Completeness: If the statement is true, the prover can prove to the verifier that the statement is true (with overwhelming probability). With reference to MobileCoin, this means that whatever the specifics of your transaction are, if it is well-formed then a proof of balance can be formed.

2. Soundness: Alternatively, if the statement is false, the prover cannot succeed in convincing the verifier that the statement is true (with non-negligible probability). In other words, the prover can only convince the verifier if the prover is actually telling the truth. In reference to MobileCoin, this means that no one can convince the network to accept a bad transaction.

3. Zero-Knowledgeness: If the statement is true, the verifier only learns that the statement is true and nothing else (the proof does not leak any additional information). This is established within MobileCoin with reference to the Fiat-Shamir technique of taking an interactive ZKP and creating a digital signature based on it. The Bulletproof is equivalent to the transcript of an interactive proof, which is itself zero knowledge. Anyone can sample correct transcripts of that interactive proof, without even knowing the committed values. So, we know that those transcripts convey no information about the committed values.

A technical subtlety here is that the hash trick actually makes it difficult for an adversary to sample the proof. Once you replace the challenge values with hash function outputs, the adversary can't sample the proof on their own anymore -- you would actually need to know the secret values to be able to build the proof after that point. We agree it's zero knowledge before we replace it with hash functions. Then we agree that replacing it with hash functions can't do any damage in real life. That's how we construct non-interactive ZKPs.