Privacy in Cryptocurrencies: Zero-Knowledge and zk-SNARKs (1/2)

Yan Zhang and Yi Sun

(This 2-part article is part of a series whose first 2 articles can be found here and here. The second half of this article is here.)

(EDIT: we added some edits from valuable comments by Alessandro Chiesa. We also added a link above to the second half of the article)

Even though we have already shown (e.g. in our second article) that it is possible, it should still be very mysterious that we can have a blockchain and transactions where so much of the state (such as identity of participants, the amount of the transaction, etc.) is private. Let’s take a step back and think about what such a system looks like.

Apparently, you’re part of some elite, exclusive, and eccentric club of people (why else would you want to join cryptocurrencies?), where all activities are under constant high-def video surveillance in a well-lit room with a giant podium. Every so often, a cloaked stranger walks up to the podium, and shouts, out loud, a bunch of numbers.

Then you and the other club members all nod, update your ledgers (your copies of the blockchain), accepting that the stranger (let’s call him/her/it A) indeed gave some other stranger B some coins, in a way that:

1. Nobody else knows who A and B are. Maybe they’re even the same person.
2. Everyone is convinced that no coins were destroyed or created from thin air.
3. Nobody knows the amount that was transmitted, even though everyone is sure that A did not give B more coins than what A already had.

These are absurd conditions. In particular, the next time some stranger shouts out a bunch of numbers that is meant to correspond to their trying to pay X coins to someone else, people will be able to detect if they were trying to cheat (e.g. they had less than X coins). In that case, the only thing that the other club members learn is that the stranger didn’t have enough coins! They don’t learn anything about X or the amount of coins the stranger had!

The above experience is what it is like to participate in a system based on Zero-Knowledge Proofs (ZKP). ZKPs are a beautiful part of theoretical cryptography very popular with the cryptocurrency community, mostly thanks to the well-known applications (and acronyms) of zk-SNARKs (made famous by Zcash) and zk-STARKs, though other ZKP systems such as Bulletproofs have recently been gaining traction.

Keeping with our theme, this article introduces the technical but not necessarily theoretically-trained reader to the main theoretical ideas as they relate to privacy, using a simplified version of Zcash as the main example (and the goal of this first half of the article).

All aboard. Source: Wikipedia.

Our goal is to have readers understand these concepts and their contrasts with each other at a slightly more detailed level than “cryptography magic” while still leaving the very technical parts in a black box. Corrections and suggestions are, as usual, welcome.

Proofs, Zero Knowledge Proofs, and zk-SNARKs

What do these letter soups mean? Fundamentally, they are proofs with additional guarantees. A proof is some string (which could just be a sequence of numbers) that allows a Prover to convince a Verifier that some statement is true. We need 2 conditions:

1. completeness: If the statement is true, the Verifier will be convinced. Obvious enough.
2. soundness: If the statement is false, it is “hard” to convince the Verifier of it. As in usual applications of complexity theory and cryptography, “hard” means with “very low probability”, i.e. 10^{-800}. While allowing the possibility of a “fake” proof sounds bad when money is involved, being able to lie with such a small probability is as good as any protection you have in real life.

Now, we say a proof is a zero-knowledge proof (ZKP) if “the Verifier learns no new extra information” beyond the truth value of the statement. This magic-sounding term is formally defined by requiring the proof to be indistinguishable from one created by a simulator; intuitively speaking, this means that “if someone who doesn’t know anything could have simulated the entire interaction convincingly, then there is no way you could have gained information by looking at the interaction.” We refer the interested reader to the Wikipedia article or Matthew Green’s post for more details, but the rough definition above is sufficient for our purposes, as simulators are important for formalism but not implementation (i.e. once you prove something is a ZKP, you do not need to make a simulator to use it).

To see why such ZKPs could be useful for privacy, it is helpful to look at what the more familiar digital signatures do. Philosophically, a (good) digital signature Tproves the statement “I know a secret SK such that when I run the program Sign(SK,M)on a (public) message M, I get the value T.”

Think about this for a moment. If SK were only given to Denise and it is assumed that it is hard to get Sign(SK,M) = T if you didn’t have SK, then if Denise proves the above statement and then supplies her signature T to her message M, she has proven her identity! Thus, you can think of a digital signature as a non-interactive proof that Denise knows the secret key SK. Such a signature scheme would in addition be zero-knowledge if the signature T reveals no information about the secret key SK.

This is a good intermediate rest stop, as ZKPs are one of the coolest theoretical parts of classical cryptography. A type of ZKP popularized by cryptocurrencies is zk-SNARK, which impose additional requirements (corresponding to additional letters) which are good to have in cryptocurrencies. 2 letters down, 5 more to go! (Yes, we know that the P disappears. We’ll get there too.)

• First, the “S” means “succinct,” which promises that 2 things must be small/fast: proof length (as cryptocurrencies require the users as a whole to throw duplicates of the same data around) and verification time (because of decentralization, many people may want to independently verify each transaction).
• Then, the “N” stresses the non-interactive property of our proofs. We have this because theoretical computer scientists frequently work with interactive (zero-knowledge or otherwise) proofs where the Verifier may interactively query the Prover in the verification step. These are more general and easier to think about, but less well-adapted to cryptocurrencies for many reasons. For example, one reason would be that (for both scalability and security reasons) we want to avoid requiring the Prover and Verifier to be online at the same time to interactively verify a proof. Another deep philosophical reason would be that interactive protocols depending on the Verifier (which is the blockchain!) using some secret randomness usually needed as part of such protocols seems impossible.
• The “AR” stands for “argument,” which is a weaker form of “proof.” The technical difference is that the “soundness” property we talked about for proofs require that it is hard for a computationally all-powerful Prover to convince a Verifier of a false statement, while argument systems require that it is hard for a polynomial-time Prover to convince the Verifier of a false statement. At a zoomed-out level, this difference is negligible.
• Finally, the “K” means our arguments are about knowledge, a formal way of saying that we consider statements of the form “I know X” rather than straight mathematical statements like “Y=Z.” The formal definition of an “argument of knowledge” relies on the technical concept of an extractor, which specifies exactly what it means for a statement to take the form “I know X”.

To summarize, a zk-SNARK system for Prover Alice and Verifier Bob is where:

• Alice knows a piece of (K)nowledge.
• Alice can prove to Bob that she knows it with an (N)oninteractive (AR)gument (basically a proof), after which Bob can be convinced that Alice knew the piece of knowledge, while acquiring (Z)ero (K)nowledge about what that piece is.
• The length of Alice’s argument and the time Bob needs to check the argument are both (S)uccinct.

Of course, these are just the requirements for a zk-SNARK; we said nothing about how such things are actually implemented. When people in cryptocurrencies say “SNARK,” they usually mean a particular implementation of zk-SNARKs, like “Xerox” versus “xerox.” These SNARKs arose in a paper by Ben-Sasson, Chiesa, Tromer, and Virza (so we’ll call them “BCTV”), using algebra over a finite field, elliptic curves, and QAPs (quadratic arithmetic programs, which encode individual gates in an arithmetic circuit as multiplications between pairs of polynomials). If, like us, you’re excited to learn the mathematics more deeply, we would recommend going through Vitalik Buterin’s trilogy of posts (I, II, and III); we have also personally found learning from Pinocchio, a predecessor QAP-based SNARK implementation by Parno and Gentry, very educational to understanding BCTV.

The most important upshot for us is that BCTV produces zk-SNARKs for general computation! This means we can “zk-SNARK-ify” arbitrary arguments that sound like “I know some inputs X such that if you run a particular list of computations on X, then you get Y,” by turning these statements into e.g. lists of numbers. This is very, very powerful. With this result, we can create strings which prove statements like:

1. “I know a secret S such that when I run a hash function f(S), I get the value H” (because a hash function is just a computation)
2. “I know numbers X,Z such that X² + Y² = Z² (for some given Y)”
3. “I know a number SK that is the private key for at least one of UTXO_1 and UTXO_2.”

so that the recipients are convinced of these statements, but learn nothing about what you know after you convince them!

We will now see this “in action” in a hypothetical cryptocurrency.

What about Privacy in Cryptocurrencies?

We now describe how zk-SNARKs can be used in SnarkCoin, a hypothetical slimmed-down version of Zerocash (the protocol leading to Zcash), to perform something like the zero-knowledge club meetings we described in our introduction. We have removed some details specific to Zerocoin, such as the distinction between the “basecoin” and the “shielded coin,” to focus on the meat of the idea.

In SnarkCoin, a coin consists of 3 pieces of data:

• a value (amount of money)
• a serial number (an identifier for the coin which will later ensure it is not spent twice)
• an address (this is a public key. It ties the coin to someone with a matching private key, who is the only person that can spend it)

Each coin has a commitment, which is a number computed from the coin by some function (the idea of commitments and revealing appeared in our second post; the main idea is that it is hard for a commitment to one value to be reinterpreted as a commitment to some other value, so in our case once we have a commitment for 30 coins it is basically impossible to lie and say the commitment was for 50 coins instead). When we “put a coin on the chain,” we only put commitments on, and not the values or serial numbers. The SnarkCoin blockchain consists of transactions which are applied to create the current state, which consists of:

• the set of commitments, playing a completely analogous role to UXTOs (unspent transaction outputs) in Bitcoin
• the set of revealed serial numbers, which will play the role of the list of spent coins

To describe transactions in SnarkCoin, suppose a user Alice knows the private keys for coins Coin_A and Coin_B , each of value 50 and wants to send 30 SnarkCoins to another user Bob by spending Coin_A and Coin_B and creating two new coins Coin_C (of value 30 for Bob) and Coin_D (of value 70 for Alice). She can accomplish this by broadcasting a transaction called Pour(Serial_A, Serial_B, Commit_C, Commit_D) with the following information:

• the serial numbers Serial_A and Serial_B for Coin_A and Coin_B
• commitments Commit_C = Commit(Coin_C) and Commit_D = Commit(Coin_D) for Coin_C and Coin_D
• a zk-SNARK (of any type, e.g. BCTV, that can prove such statements) proving that Pour(Serial_A, Serial_B, Commit_C, Commit_D) is valid, i.e. a zk-SNARK for the statement: “I know the data of some coins Coin_A, Coin_B, Coin_C, and Coin_D and the private keys Key_A and Key_B such that…”

1. “private keys Key_A and Key_B are valid keys corresponding to the public keys of Coin_A and Coin_B.” The validation of private keys simply performs a computation, and we can make zk-SNARKs for a computation!
2. “the commitments Commit(Coin_A) and Commit(Coin_B) appear on the ledger.” As commitments are functions, the first part is another computation check to compute the commitments. The second part is just checking that we have certain elements in some set, which is easy to implement (in Zerocash, this is done via a Merkle tree check).
3. “the commitments Commit_C and Commit_D are equal to Commit(Coin_C) and Commit(Coin_D).” Contrasting this to the previous bullet is educational: Commit_C and Commit_D are public, while Commit(Coin_A) and Commit(Coin_B) are not. We also don’t do a ledger check, because Commit_C and Commit_D are new.
4. “the serial numbers Serial_A and Serial_B of the old coins are not in the list of spent coins.” We need something like this to ensure coins are not spent multiple times.
5. “the values of Coin_A , Coin_B, Coin_C, and Coin_D are all nonnegative numbers and Value(Coin_A) + Value(Coin_B) = Value(Coin_C) + Value(Coin_D).” These statements ensure coins are not created or destroyed.

Understanding the specific bullet points here will help, but the main idea is that we have encoded what we want into mathematical statements, and BCTV knows how to turn these mathematical statements into zk-SNARKs.

All transactions in SnarkCoin will take this form. Some things to notice from just the input of Pour are:

1. The serial numbers Serial_A and Serial_B of the old coins are exposed, but the coins themselves are not. This is because we want the value and the address corresponding to the coins to be private, but exposing the old serial numbers allows us to ensure the coins are not spent again.
2. The commitments Commit_C and Commit_D of the new coins are exposed (because we need to put them on the public ledger) but again, the coins themselves (even their serials) are not.

While Pour only allows Alice to turn two coins into two other coins, it is a building block that can be combined to handle arbitrarily complex transactions involving many people.

For another coverage, we recommend this video by Alessandro Chiesa on the main ideas of the Zerocash protocol.

What’s Next

And there you have it — a simple cryptocurrency that realizes our seemingly-impossible skit in the introduction. As people transact coins (i.e. go to the podium and shout out strings of numbers, updating everyone’s ledgers), the coins start to move around, with nobody in the club knowing anything beyond how much coins they own. And if you think SnarkCoin is not sufficiently exciting, we leave you with the following (strange!) properties:

• By agreeing on the sequence of transactions, nodes agree that a valid notion of coin ownership exists (no coin has been spent twice, and coins have only been spent by owners who know their private keys), but no node knows who the owners or values are.
• Nuanced caveat to above: as Alessandro Chiesa points out, our simplified scheme allows payees to be recognized by the payer when the payee spends the coin created by the payer later. This is fixable, as in Zcash, but requires more work.
• In particular, it is even possible for users to remember their private key, but be unable to spend some of their SnarkCoins if they forget the relevant serial numbers.
• To validate transactions, users must store the full set of commitments, even of spent coins, since they do not know which coins have been spent.

(Totally not what we were thinking of as we wrote our introduction. Really! Source: VeChain)

We are now at a natural place for a break. The second half of this article, coming soon, will be about other ZKP protocols inspired by zk-SNARKs and the comparisons between them.

— to be continued.

We thank Mihaly Barasz, Albert Ni, Vitalik Buterin, and Alessandro Chiesa for helpful comments and feedback on both halves of this article.