Bitcoin has been called “cash with wings,” but does it really live up to this name? Cash is the most anonymous form of payment we have today, and thus it provides for two things: First, when you hand a dollar to someone, your identity doesn’t matter and it’s not needed to verify the authenticity of the transaction. Second, you can be nearly certain no one is tracking where that dollar was before you had it and where it will end up down the line. But Bitcoin possesses only one of these features. Each time the network processes a transaction, it identifies the users with a string of letters and numbers—their Bitcoin “addresses”—rather than using real names. In this way, the Bitcoin protocol itself couldn’t care less who you are. But what about tracking coins? Not only does Bitcoin track and record the spending history for every little scrap of the currency, but it’s a fundamental characteristic of the protocol, the very thing that makes it secure.
The database that records these movements is called the block chain. It is massive, constantly growing, and publicly available. If someone knew your Bitcoin address, he could easily look up exactly how many coins you have, when you spent them, and where they went. If you wanted to, you could obfuscate the link between this pseudonym and your identity by creating more addresses and shuffling your coins around, but honestly, who has time for that?
Matthew Green, a computer scientist at the Johns Hopkins Information Security Institute, in Baltimore, wants to make Bitcoin truly anonymous. He’s one of the developers behind Zerocoin, a proposed extension to the Bitcoin protocol that would provide true anonymity. Essentially, Zerocoin works like a money laundering pool. If the protocol is implemented, anyone with a bitcoin could spend it to create a temporary new currency called a zerocoin, the existence of which is recorded alongside bitcoins on the block chain. The bitcoins spent on these zerocoins are deposited into an escrow pool, and users can come back at any time, turn in their zerocoins, and redeem them for bitcoins. But the bitcoins they get out are not the same ones they put in.
The concept of a laundering pool is not new. The allure of Zerocoin is in anonymizing the act of jumping in and out of the pool. IEEE Spectrum’s Morgen E. Peck spoke to Green to find out how this works.
Morgen E. Peck: Can you explain on a conceptual level how Zerocoin works?
Matthew Green: It’s almost like you have a hat and people throw dollars into the hat, and each time they throw a dollar, they get a token. And let’s say all the tokens look exactly the same. Now, I can come back with a mask on, or I can give it to my friend and he goes back. He exchanges his token, and he takes out a totally different dollar. And that’s the same thing that we do with Zerocoin.
Morgen E. Peck: So in Zerocoin, the hat is really an escrow pool recorded on the block chain, and it’s full of random people’s bitcoins?
Matthew Green: We put some bitcoins into the block chain and make them go into that limbo. When we come back to spend the zerocoin, we take out any not-yet-redeemed bitcoin that somebody else used to make their zerocoin.
Morgen E. Peck: Okay, so there are two aspects to that scenario that protect anonymity. First, all the tokens in the hat look exactly alike and therefore can’t be traced. Second, the guy making the exchange is wearing a mask, and all he needs to do to get his dollar back is hand in the token. He doesn’t have to prove who he is in order to redeem it. How do you re-create this with Zerocoin?
Matthew Green: There’s a serial number inside of every zerocoin, but each zerocoin is kind of like the encryption of that serial number.
Morgen E. Peck: So the people who are exchanging bitcoins for zerocoins, they’re the only ones who know the serial numbers of their zerocoins?
Matthew Green: That’s exactly right.
Morgen E. Peck: Going back to the tokens-in-a-hat analogy, that’s how you make all of the coins look the same. How then do you put a mask on the person reaching into the hat? How do you simulate that aspect of it?
Matthew Green: So you have all these people, hopefully thousands of them, throwing these coins into this pool, and the question is, How do they get their coins back without leaving their fingerprints all over it, so that somebody looking at the transaction could say, “Hey, I know that that was Bob who put the coin in and then got it out”? That’s where we kind of use some special crypto magic. We use a thing called a zero-knowledge proof.
The most important thing you should know about zero-knowledge proofs is that when I use a zero-knowledge proof, I can convince you that some things are true. Like, for example, I could convince you that I work for Johns Hopkins. I could convince you that I live in Baltimore. But the zero-knowledge part means that besides the things that I exclusively want to prove to you, you shouldn’t learn anything else. You shouldn’t learn who I am at Johns Hopkins or where in Baltimore I live. That’s kind of a high-level intuition of what zero-knowledge proofs do.
We found a way to write a zero-knowledge proof that basically says two things. It says, first of all, I am an owner of a zerocoin and I know a serial number that’s inside of the coin I made. And the second thing you prove is that you actually paid for it. Otherwise it wouldn’t be that good.
And then what you do is you take that serial number that’s inside your zerocoin, and you just release it. You take that whole thing, the zero-knowledge proof and the serial number, and you wrap it up and you send it as a transaction on the block chain. And anybody who sees that thing can then be convinced with really, really high probability that you actually had the zerocoin and you actually put it on the block chain.
The key here is that they didn’t know which zerocoin it was. It could have been any of the ones that are already outstanding. They just don’t know.
Morgen E. Peck: So you’re dissociating the act of putting the zerocoin onto the block chain from the subsequent act of proving it’s real and reimbursing it for a bitcoin.
Matthew Green: Exactly.
Morgen E. Peck: Do you have to make a new zerocoin every time you do this?
Matthew Green: Yes. Zerocoins, right now they’re one-time use. You make the new zerocoin in exchange for one bitcoin. Then you come back later and you essentially destroy it. By releasing that serial number, those zerocoins can never be spent again.
Matthew Green: With existing laundry services, the problem is I need to get a hundred people together today and get them to exchange their coins. One of the nice things about this, anytime I redeem a zerocoin, it could be any one of the zerocoins that got created ever in history.
Morgen E. Peck: One of the criticisms of Zerocoin is that this process of verification requires oodles more computing power than it currently takes to verify a Bitcoin transaction. Is this true?
Matthew Green: Verifying a transaction, it’s like the difference between 2 milliseconds and 2000 milliseconds. So it’s really expensive computationally. In theorems of the size of the proof, it’s maybe 40 times larger. We hope we can get that down by a factor of 10, in which case we’re talking 4 times, which isn’t bad. But right now it’s very expensive.
Morgen E. Peck: And who is picking up all this extra work?
Matthew Green: The bulk of that work is actually going to fall on the people who are already mining. These are the guys who are already spending all the energy. They’re going to have to spend just a little bit more. So the current zerocoin is not probably what we would use. Right now it’s expensive.
Morgen E. Peck: Have you made any progress on that since you presented the idea?
Matthew Green: This summer we released a relatively polished library that contains the core crypto. We’re currently working on what we hope will be a significantly more-efficient version of Zerocoin that could solve some of the objections people have raised.