Understanding Zerocoin
In this article, we’re going to take a practical look into how the fascinating Zerocoin protocol works to provide anonymity.
Important notice:
In May 2019, after this article was originally published, a series of vulnerabilities were discovered in the Zerocoin library which sits at the core of most Zerocoin-based protocol implementations, including Veil’s.
After extensive review, and discussion with the Zerocoin community, the Veil project, along with a number of others, concluded that Zerocoin can not be relied upon to form the anonymity core of the protocol, and at the time of this writing, the project is working to implement a new core privacy protocol.
History of Zerocoin
The Zerocoin protocol was conceived in 2013 by Johns Hopkins researcher Matthew D. Green1, as an extension of Bitcoin, providing for optional anonymity in the Bitcoin network. We say “optional” anonymity since the Zerocoin model involves converting public bitcoins to anonymous zerocoins, and back.
So the first concept to understand is that in Zerocoin networks, there are two types of tokens (coins)—public tokens, known as basecoins, and anonymous tokens, known as zerocoins. (Misunderstanding of this concept is a common source of confusion in networks such as PIVX, where one finds “PIV” and “zPIV” coins.)
In Veil, the on-chain coins are called Basecoin Veil, and the anonymous coins are called Zerocoin Veil. Since the Veil wallet automatically converts basecoins to zerocoins, however, the general use of “Veil” is meant to imply the anonymous coin.
(You’ll notice that for Basecoin Veil, we used the term “on-chain”, rather than “public”, since in the Veil network, Basecoin transactions are also anonymized using “RingCT” technology, but explanation of that will be saved for another post.)
The logic behind Zerocoin
Imagine we’re considering how to design an extension to the bitcoin network that would allow us to convert bitcoins to zerocoins, and then be able to spend them later anonymously.
In order that the bitcoin monetary supply remains auditable, the creation of zerocoins can’t be anonymous, i.e. when we bring a zerocoin into existence, through a process known as minting, we necessarily have to take a bitcoin out of circulation, in a process known as burning, and since bitcoin is a public token, its removal (burning) also has to be public.
Therefore, if I minted 1.73458 zerocoins—something we’ll later see isn’t technically possible, but for the moment we’ll ignore that—by burning 1.73458 bitcoins, and if the world can know, since bitcoin is public, that I owned those 1.73458 bitcoins, then the world will also know that I now control 1.73458 zerocoins.
So the challenge in a network like this is:
If my creation of zerocoins is public, how can I later spend those zerocoins anonymously?
Fixed denominations
The above example already presents the very first challenge. If I created such a precise amount of zerocoins in the past, like 1.73458, then when that precise amount of zerocoins gets spent in the future, it wouldn’t be very hard to assume that the spend came from me. Why? Because there simply won’t be very many other zerocoin address “outputs” out there holding precisely 1.73458 coins.
Considering this problem, Green may have thought, “What if zerocoins only existed in fixed denominations, like cash bills or casino chips? If there only existed denominations of, say, 1 zerocoin, 10 zerocoin, 100 zerocoin, and 1,000 zerocoin, then maybe I could design a system in which, if you spend a 10 zerocoin, the network won’t know which of all the 10 zerocoins you spent.”
This idea of fixed denominations was ultimately implemented in the Zerocoin protocol, and made to work through the concepts of accumulators and zero-knowledge proofs.
Accumulators
In Zerocoin networks, an “accumulator” exists for each denomination supported by the network. So if the Bitcoin network supported denominations of, say, 10, 100 and 1,000 zerocoin, it would have three accumulators.
Conceptually, most people think of accumulators as “buckets”, holding all the coins of a particular denomination. But in reality, as we’ll see later, an accumulator is actually a single number, that cryptographically embeds knowledge of the existence of each outstanding zerocoin in that particular denomination.
As you might imagine, the particular choice of denominations in a Zerocoin network has to be carefully considered, and the trade-off is between convenience and anonymity.
To understand this, consider that when I spend a 10 zerocoin token, its traceability back to me—i.e. back to my minting of a 10 zerocoin token—is a function of the total number of 10 zerocoins that exist. If there’s only five 10 zerocoins in existence, and I spend one of them, it might not take much sleuthing to figure out it was me. On the other hand, if there are five million 10 zerocoins in circulation, the problem becomes much more difficult, if not impossible.
For this reason, a network that only has six denominations would likely provide greater anonymity than one that has a hundred different denominations (all other things being equal). For the Veil network, there will exist four denominations, and hence, four “accumulators”: 10, 100, 1000 and 10000 Zerocoin Veil.
Zero-knowledge proofs
Zero-knowledge proofs2, to most mortals, are akin to black magic. We won’t get close to the math behind them, but here’s what a zero-knowledge proof is in practice:
A ZK proof is a method by which one party can prove to another that a given statement is true, without conveying any additional information apart from the fact that the statement is indeed true.
Mind blowing, I know. Don’t get scared!
How the Zerocoin protocol works
With all that as background, we can now proceed to explain how the Zerocoin protocol works in practice.
Let’s start by walking through the process of what happens when you mint zerocoin by burning basecoin—something that happens automatically in the Veil wallet.
Burning & Minting
Say you received an incoming payment of 10.73458 Basecoin Veil. Looking at that number, your wallet would know that it can convert 10 of those to a single 10 Zerocoin Veil token. (The remaining 0.73458 Basecoin Veil would stay as Basecoin Veil in your wallet.)
To create your new 10 Zerocoin Veil token, your wallet creates a unique serial number, that we’ll call “S”, and a random number, that we’ll call “V”. Your wallet then performs what’s known as a “one-way” cryptographic calculation known as the Pedersen Commitment, that takes V and S, and computes a number called, “C”:
C = comm(S,V)
This formula simply means that “comm” is a mathematical function—the Pedersen Commitment—that takes S and V as inputs, and produces the number C as an output. It’s “one-way” in the sense that S and V can’t be back-calculated from C.
Having computed C, our wallet now “burns” 10 Basecoin Veil—taking them out of circulation—in a blockchain-recorded transaction in which the value “C” is publicly recorded.
The “10 Zerocoin Veil” network accumulator number is then updated cryptographically to embed knowledge of the newly introduced “C” value.
By burning 10 Basecoin Veil in this way, we have also “minted” a brand new 10 Zerocoin Veil token, that is associated with the recorded number “C”, which is linked to me, and to the unique serial number, S, which at this point is only known to my wallet!
Before moving on, let’s review where we are:
-
We have burned 10 Basecoin Veil in a blockchain transaction that minted the creation of a 10 Zerocoin Veil token, recorded with the number, C.
-
Since the burned Basecoin Veil is public (or for Veil, more precisely “on-chain”), the number C is publicly visible.
-
Only our wallet knows the random number, V, used along with S, in the calculation of C.
-
Only our wallet knows the serial number, S, which is the unique identifier of our particular 10 Zerocoin Veil token, among all the tokens.
Spending anonymously
Now comes the interesting part: How do we later spend those 10 Zerocoin Veil anonymously? To do that requires that the spend can’t be linked back to the mint. Let’s look at how that’s done.
When I’m ready to spend my 10 Zerocoin Veil, my wallet calculates two zero-knowledge proofs, the first of which can be used independently, and the second which can only be used in tandem with the first.
In the first ZK proof, I mathematically prove that the coin I want to spend (the 10 Zerocoin Veil) exists in the 10 Zerocoin Veil accumulator, without revealing which coin that is. Mathematically, I have to prove that the value “C” I wrote to the blockchain during my mint exists in the accumulator, without revealing the particular value of “C” I’m proving—since that would point directly back to me!
To do this, I compute the Pedersen Commitment function using C and another random value, R, that I choose and is only known to me, to produce the output Y.
Y = comm(C,R)
(The inclusion of a random number R is critical, because if I just computed comm(C) to produce Y, then by computing comm(C) on all the recorded C’s in the blockchain, you could easily figure out which C I’m proving!)
When I provide the value Y to the network, the network can validate my proof using Y and the current accumulator number to confirm that, yes, I do control a particular coin in the accumulator, but without knowing which one, i.e. the network doesn’t know which “C” I used in the computation of Y.
Then, I publicly reveal the unique serial number, S, corresponding to my particular 10 Zerocoin Veil, and provide a second ZK proof demonstrating that I know some random value V, that, in turn, proves I control the still-unrevealed “C” used in the first proof.
That’s a mouthful, but is why the second proof is only meaningful in tandem with the first.
So in summary:
-
Proof 1 proves that the coin I’m going to demonstrate control of in Proof 2, corresponding to the minting recorded with C on the blockchain, exists in the accumulator but without revealing which C that is.
-
Proof 2 allows me to reveal the unique serial number, S, corresponding to my particular coin, without revealing which burn and mint transaction, C, it corresponds to.
Or said another way:
Zero-knowledge proofs have allowed me to prove that I control a specific token among all the 10 Zerocoin Veil tokens, without any connection to the specific blockchain transaction that created that coin.
At this point, my spend transaction will be recorded on the blockchain:
-
The transaction will publicly record my unique serial value, S, so that that coin can’t be double spent in the future.
-
10 fresh Basecoin Veil will be put into circulation and delivered to the destination address of my transaction, and my 10 Zerocoin Veil can not be re-spent due to the public recording of its unique serial number, S.
And so, through the use of zero-knowledge proofs, I have spent my 10 Zerocoin Veil anonymously!
Conclusion
In this article, we’ve described the Zerocoin protocol—one of the beautiful technologies underlying the strong anonymity you’ll find in the Veil currency3.
Footnotes
-
Thanks to Veil developer Random.zebra for helping me wrap my head around the concepts like zero-knowledge proofs described in this document, and to Veil team members for editing feedback. ↩