https://soundcloud.com/rdlmitedu/140113_0001-wav

13 January 2014

Real World Cryptography Workshop

New York, NY

Length: 00:27:45

Matt:	Hi. My name is Matt Green and I want to thank Arvin first off for pretty much teeing off my entire topic sending in about 20 slides. So I’m going to talk today on the other side, the constructive side.

So we’ve already learned that Bitcoin may not be a particularly anonymous currency. The question is what do we do about it? I’m going to talk about some work that we have, a couple of pieces of work, by so co-authors which I will introduce a little later in they’ll talk. Techniques called Zerocoin and Zerocash allow us anonymize the Bitcoin currency.

So here the quick summary of what Arvin just told us is that Bitcoin, as far as we know, is not a particularly anonymous currency. We know that the transactions are recorded through public ledger that everybody can download.

Right now, once you have this amazing public ledger, we don’t do anything very sophisticated with it. We just essentially write checks from one identity to another. And as Arvin said, “People can identify, map your address to an identity, in the real world you’re in a very bad place.

And I would say that, as our consentive, be very paranoid. You may be able to provide that from happening. But the truth is most of us are not very paranoid and particularly expert at this. So I think, in a general case, you’re not in very good position using Bitcoin for privacy.

The other point I want to make is that this is something that should matter to all of us. Not because that Bitcoin itself is necessarily the future. You may think that Bitcoin’s a bit goofy. But the technology behind Bitcoin is very important technology and something that is likely going to be with us for a longtime. You should be looking at ways to improve it.

The counter measures we have are very weak and they don’t seem to address the problem, even in the case of unsophisticated attacks. And the other thing that we should note is that, if we developed techniques to make Bitcoin private we may even find applications for them that go beyond currency.  So we’ll talk about that a little later.

The outline of this talk, though, is I’m going to talk about two different approaches that we’ve taken that hopefully will give some direction to build a new anonymous versions of Bitcoin. The first one is called Zerocoin.

And it’s a technic that allows us to implement electronic cash in the coin program. The second one, which has not been published yet, is called Zerocash. The way we describe this is this is a way to may Zerocoin practical, and deployable, and useable as an E-Cash account.

So I’m going to start with an introduction talking about Zerocoin.  Because I think that helps to [Inaudible 00:02:51] on both of these. This is joint work, by the way, with my students in and buyers, and Christian Garman and John’s Hopkins along with my colleague [Inaudible 00:02:59].

So when we started looking at Bitcoin, probably a couple of years ago, because we were certainly interested in bites, the first thing we observed was the Bitcoin doesn’t really give us much privacy.

And this was interesting because we had the definite ability to spend a lot of time thinking about how to fix this problem for currency in general. In fact, if you go back to the 1980s or so, you’ll find a whole line of works beginning, really, with the work of David Chaum talking about how to build something called an untraceable Ecash.

Ecash, as most academic works do, kind of trying to tackle one problem without thinking about all of the practical issues that go with it. E-catch sort of just assumed that we have a bank, and a center bank, that is willing to hand out anonymous currency to us. And once we have thing there are a whole bunch of different ways we can use bank to get coins.

Those coins can be produced with blind signatures and so on. Well, the problem is, is that nobody in the history of academic Ecash, has ever managed to set up a working centralized bank.

David Chaum even found a new company to do this and the company failed, in part, because, if you want to set up a bank, you have to get people to trust your currency first. It turns out that actually building the currency is a harder problem than making it a private currency.

But Bitcoin, fortunately, has solved that problem for us. The problem is we can’t use existing Ecash techniques with Bitcoin because to do that we would have to go introducing a centralized bank to currency that is fundamentally decentralized. So what we need is a different technic. We need to get rid of this need for a centralized bank.

And that brings us to Zerocoin. The basic idea of Zerocoin is that we’re going after a complete new approach to building Ecash. That gets rid of the need for the centralized bank.

Now, the approach we use in actually related to a previous technic that was proposed by Chong and Sandler. The basic idea is that we take advantage of the fact that we have a decentralized, public ledger, blockchain, that’s constructed by Bitcoin.

And what we do is we use this to construct a decentralized laundering. It’s a system that allows us to periodically wash our coins in the way that does not require us to trust one centralized market to help us. The great thing about this is the key ingredient of this technology, blockchain, has already given to us by Bitcoin for free. So we really don’t need to ask anything is protocol.

We just need to ensure that Bitcoin itself, in terms of building out [Inaudible 00:05:26] is a safe technology and the rest of it is just crypto we can apply on top. So I’m going to try to give the high level intuition of how Zerocoin works and I’m going to drill in a little deeper in just a second.

So the basic idea of the original Zerocoin program is that I have some Bitcoin. First of all, there’s a layer that we’re going to apply on top of the actually Bitcoin program. I have some Bitcoin. When I want to anonymize my Bitcoin, when I want to break that link between my current address and some further address that I spend with, I will take my Bitcoin and I will turn them in to Zerocoins.

What’s going to happen in that process is they’re going to get mixed up? All of the people on the network who are making these Zerocoins are going to essentially shuffle their Zerocoins together so that you won’t be able to make a linkage between the creation of them and later protection on these Zerocoins.

At some future point I can now redeem my Zerocoins back in to Bitcoin preferably in a different and completely unrelated block. And this breaks all of this graphitizing stuff because every time I vanish in to that Zerocoin network there is essentially a break in that chain.

There’s no way to link the input address to the ultimate output address. And that should help you, as long as you do this from time to time, to reduce the amount of information leaking about your identity.

So let’s talk about how this would actually work. This is a very, very simple overview of what the Zerocoin protocol looks like. So the first thing is that Zerocoins are really just numbers.

They’re basically digitally commitments to some large random circular. If you don’t know what a commitment is probably you can think of this as the encryption of the serial number.

The important thing is that viewing that encryption with that commitment you should not be able to tell what the serial number is. You can think of this as putting a number inside of an envelope.

Once you’ve minted these things… And by the way, they’re very easy to make. Anybody can do this. They’re not worth anything since anyone can do them. Once you’ve actually created this Zerocoin value you need to put in on to the Bitcoin blockchain.

To do this, we introduce the new instruction in the Bitcoin system that allows you to go in and produce a transaction that spends, for example, one Bitcoin, in exchange for which you get to put the Zerocoin value on to the blockchain for everybody to see.

And the semantics of this transaction are such that anybody who sees this on blockchain will know by verifying the inputs are created at Bitcoin, that this is actually a valid Zerocoin. It’s now worth some money.

At soon later point you could redeem that Zerocoin back in to Bitcoin. To do this, this is where the complexity comes in. You first, reveal that secret serial number you used to make you first Zero product.

You put that out. Put that in to the transaction. But, secondly, you have to prove two things. You have to prove, first of all, that the serial number corresponds to the real Zerocoin. And secondly is that that Zerocoin is one of the set of the Zerocoins that was placed on the lock chain, one of the set of value Zerocoins for which somebody actually paid money.

If you do that proof in a convincing way you will be allowed by the protocol to transfer one Bitcoin in to a wallet of your choice. And that’s a high level of the entire program. The trick is in the way that we do that proof.

We actually prove that this is valid Zerocoin, or this is the opening or spend of a value Zerocoin, using the Zero-knowledge proof. Zero-knowledge proofs a pretty old technology, but they’re a very powerful technology.

The idea with Zero-knowledge proofs if you could prove any statements or most statement very efficiently, but without revealing any additional information author that the fact that the statement is true.

So here’s the statement that we’re proving again. It’s simply that their existences some Zerocoin, a set of Zerocoins, they put in place in to the block chain and simultaneously the serial number that we’re revealing is the actually serial number inside of it.

In other words, we know the opening of the commitment that causes that serial number to be revealed. Now, the great thing about this is since we have to prove that that serial number is what was inside that Zerocoin that will actually put on some blockchain.

If the proof is valid you will not be able to double spend because if we double spend we’re going to have to reveal that same serial number again. And that’s trivially detectable. If anybody sees a serial number being used twice they can reject that transaction. So again, the proof against double spending, providing that Zero-knowledge will perform.

Now, the trick here is, is that we’ll have to do this efficiently. This is only place where I’m going to getting in to a little bit of detail, but I just crossover to the high level. The approach that we use at Zerocoin is actually to take advantage of another [Inaudible 00:10:15] accumulator.

The one we use is based on strong buy, send. So, what we do is we collect all the Zerocoins on the block chain in to the accumulator. What that will prove is really that the Zerocoin we’re trying to spend is contained within this accumulator.

The important thing here is that we can do that very efficiently. He has a proof of knowledge that's about 4 or 5 kilobytes for that. The problem is that we also need to prove that the serial number we’re revealing is the one that’s inside the Zerocoin. And that is not an efficient proof.

In fact, the entire proof, the thing that you’d have to put on the blockchain adds up to about 25 kilobytes and that’s after we’re optimized it. So, after we’ve had this additional result we were very excited about it. By the way, for crypto this is great. With 25 kilobits it’s nothing. It’s very efficient.

So we went out to the Bitcoin community and we ask them what they thought about putting 25 kilobyte groups on to the blockchain. And their answer was, not really a great idea. They were not particularly enthusiastic about putting this much expansion on to the blockchain.

We think there are some engineering solutions you can use to fix this, but really not something that is going to likely happen in the real Bitcoin currency. So the summary Zerocoin is we think it was a good approach.

It actually exists. It’s a real piece of software. There’s light [Inaudible 00:11:32] we produce called libzerocoin that you can download and play with. The problem is the proofs are just too big. The coins also all have the same value. The idea it that you can transfer one Bitcoin in to one Zerocoin and that denomination is fixed, which means that if you want to spend in actual fraction amounts on Bitcoin you have to turn your Zerocoins back in to Bitcoins and then, spend normally in Bitcoin world.

So it’s not really a full electronic currency. It’s more like a washing wire. To address these problems we have a new solution. This is called Zerocash. The motivation behind this, or the history between this, is that we presented these results in the open conference in May.

And we also presented a short version of this at the Bitcoin conference which also happened in San Jose in May. And it turns out that at both of those conferences there were teams who were working on a new technology that will allow you to make, it turns out, smalls or zero knowledge proofs. And these tools are called snarks.

So right there at the conference when we were presenting this and saying “We need a more efficient proof, a more efficient solution, we had some other pantographers who really had that solution kind of ready for us. Some snarks which stands for - Succinct Non-interactive Arguments of Knowledge. It’s a great crypto name.

The particular Snarks that we use are Pazines. In this case, they’re part of a technology by Brian Marnow and some other people that make Microsoft research. The basic idea of these groups is that you can prove arbitrarily complex statement in a proof that is only 288 bites.

In other of words, if you can express the statement you want to prove is an arithmetic snark language it comes as a lot of useful things. We can produce a tiny proof for almost all of them.

Two hundred and eighty-eight bites is not proof this is much more Bitcoin transaction side. This is not a disaster. The best news about this is that in addition to have to having these efficient proofs there a [Inaudible 00:13:25] that will take an arbitrary program and produce a proof that the program is actually executing correctly on some secret unknown entrance.

So the principle all we should have to do at this point is we should simply our code, our Lib Zero point code existing point code and run it through the complier and produce these very nice proofs.

The problem is that to compilers that exist produce large servants. And that leads to not very practical proofs. The proofs are very small. They’re 288 bites. But, the time it takes to make one could run in to the hours or even days. We really can’t use that in a system like Bitcoin.

So it turns out there’s a better way to do this. Now one of our coauthors [Inaudible 00:14:05] have spent a lot of time optimizing these proofs. It turns out that the right way to do this is to not to take or the existing Zerocoin construction, which uses RSA and so public [Inaudible 00:14:20] techniques.

But rather than throw all of that stuff away and replace the techniques with components that are much easier to prove, the ones that we actually use are based on hash factions. So it turns out that we can build commitments from Shock 256. We can build accumulators using [Inaudible 00:14:38] hashcash.

And the amazing thing about these proofs is that we can actually prove things, prove statements about inputs and outputs of hash functions using relatively small circuits. For example, the implementation Shock 2 that we use is about 30,000 gates. And that sounds like a lot, but it actually proves to be a very efficient to proving very complex statements using hash functions.

So our new construction looks like this: We use, each coin is really the hash of some randomness and a serial number. That’s the commitment. Once we have these coins we place them together inside hasher with now serves as an accumulator.

We place them at the very bottom on the leaves of the hash tree and it’s a 64 depth hash tree which means you can store 2 or the 64 Zerocoin, which is more than anything that you could possible imagine people create.

Now we can hash them up to our link tool. At any point we want to redeem all we have to do is to prove that we know the randomness, the R value, reveal the serial number. We prove that we know not only R, but 64 hash values along the way up to the root of that tree. And that turns out to be very efficient, using these snarks.

So at some point you realize that we had a very efficient proof system. We can do a lot of things with that that we couldn’t have done with the original Zerocoin. If these proofs are powerful and efficient why do we need Bitcoin at all anymore?

Why not take the entire Bitcoin transaction semantics and just throw it away? Put the entire system in to Zerocoins, make everything anonymous, from the creation of coins, through the use of coins, spending of coins, allow you to slit the coins, merge the coins, and do everything you ever want to do in a completely anonymous fashion.

In other words, the only information that ever makes it in to the blockchain is the fact that a transaction ever occurred. That’s actually very beautiful. You can do this with snarks. Essentially when we split the coin, all we have to do is show that we are creating two new coins where the value of those two new coins total to the original value of the coin that you’re slitting.

In other words, we’ll reveal the serial number of the first coin. We invent two new coins. And we can show a proof that just says the value of the two coins is the same as the original. When we merge the coins, which is the opposite side, we spend two coins and then, we prove that we’ve made a new coin that totals the value of the two currency coins.

We can even do transfers in a full anonymous way. I can send my money to you such that nobody observing the blockchain knows who you are or how much I gave you. To do this I simply give you the secrets that are inside of the coin. I can encrypt it to you public key. I can even place that on the blockchain. And additional, I embed an address.

The address is really the hash of some secret X, where you know X. But, the proof is you can redeem that coin later by simply proving that you know that secret, that number. It’s a one way transfer. I give you the secrets along with embedding this hash and x, and since you know X you are the only person who could later redeem that coin.

So we can do all the things you want to do with your currency with one exception, which is transaction fees have to be public, but everything else could be anonymous. We have need for this process. The generic transaction that we use is called a four.

The idea is that you can take [Inaudible 00:17:56] arbitrary number of coins and you output an arbitrary number of coins, and even send them to other people. Who call that pouring coins.

Now the important question is, is this actually efficient? Here’s the place where they’re…Here’s one little detail. You should always ask if there’s a detail. There’s one little detail I should mention. Before we I get to that I’m going to show you [Inaudible 00:18:15] times.

So I mentioned before that the probably with 0.1 was that the proofs were huge. And it took a little bit of time to verify them. It took about a third of a second. Well, these results it’s a little bit less.

In order to spend a coin or to merge a coin you want to actually make one of these proofs. It’s not instantaneous. It takes about 87 seconds to 178 seconds. So that a little bit of work. [Inaudible 00:18:40] processor by the way.

But, on the bright side, Bitcoin already takes about 10 minutes to merge a transaction maybe up to an hour, so adding 2 or 3 minutes to the spending time is not that much of a problem. We think it will be optimized in the future. The proofs are timing at 288 bites. Verification time is extremely small, milliseconds. So really it would complement to Bitcoin today.

The important thing is all of the hard work happens inside the network. All of the fast stuff, the verification, happens inside the network, and the small proofs are theirs so we’re not going to drag the Bitcoin network down.

Now I want to come to the one catch. In order to make these proofs work. In order to spend coins, not verify them, but spend them, you need a large set of public parameters. And they total to about 1.2 gigabytes in size.

Now at 1.2 gigabytes in 1995 I think we’d all be freaking out that’s a lot. But, it’s 2013. That’s about a dollar worth of storage. So I don’t think that’s a deal breaker. The best part is, is that if they’re running a Bitcoin know you already need to have about 16 gigabytes of data just to store the blockchain. So this represents about 7% of the total cost of the blockchain. So it’s feasible. We hope for further improvements, but it’s feasible.

The other thing you should know is that something has to generate these parameters. Right now that requires a trusting party, the same Zerocoin. Finding somebody to do that can be a bit of a challenge. You’d think that it’s possible to find a dozen people on the Internet who everybody trusts. We’re hoping any way because we want to do this.

So to sum up, we have a system that we think works, is efficient enough for deployment, but it’s probably not going to line up with the side of the actual Bitcoin system. We want to release though. We’re going to do that starting in May.

So what do we do next if we want to get people to use this? This is real world crypto. You want people to use this stuff that we’re building. So then what we’re going to do with it next is we’re going to release blockchain. We’re going to release a client that implements all of this stuff I talked about here that allows these anonymous payments and so on.

And we’re going to put it out there in alternate currency. If you are tired of using dog coin, for example, you can use our Zerocoin. [Inaudible 00:20:45] But we’re really hoping that nobody comes out of the gate and puts a lot of money in to it because these are very encrypt graphic techniques and it’s possible that the entire thing will breakdown.

We don’t really know if they’ll at least give us a chance to test this in an environment that’s different from Bitcoins and you don’t have to break anyone else’s stuff in the process of seeing if this will work.

There’s one last thing that I want to address before I finish up here. The question is that should we do this? Should we even be doing this research? They’ve been a lot of people who have been criticizing us because we want to build anonymous currencies. I just want add quickly that I think this is important research, not because we want to make it easier for people to commit crimes.

The total size of these anonymous currencies is tiny. They’re not going to make appreciative difference in the amount of crime that occurs. But, we think it’s important because right now you spend money your transactions are hidden from you neighbors.

But, with Bitcoin, as I think Arvin pointed out, it’s very possible that if you spend money, for example, visiting a doctor or going to a psychiatrist that transaction will wind up being public everybody you know.

We think that this type of technology not matter how we deploy it is very important. It’s the next step we should take. And so we’re hoping to get this technology out there and see what people do with it. That’s it. Thank you very much.

[clapping]

Speaker 2:	We have time for a couple a few questions.

Participant 1:	It’s more of a comment. I think that you are aware of some similar work that we are doing. I think that Bitcoin doesn’t matter. I just think if this works is too important to kind of just forget the second it’s [Inaudible 00:22:38]

Participant 2:	 In the paper, which already should be released this week, there is another world for ‘independent’ at Microsoft research that’s doing some of this as well. We do cite that. I’m sorry. I’ve been rushing the slide. I did want to give [Inaudible 00:22:50] credit because it’s really nice work. And we are going to be doing some a good competition with. A good approach will hopefully emerge from this.

Participant 1:  I think also to give you credit about this work. In any words you [Inaudible 00:23:06] It think there’s plenty of work to do. [Inaudible 00:23:09]

Participant 3: Do you have these proofs from actual scripts from Bitcoin?

Speaker: 	So writer now Bitcoin has a really powerful scriptive language. That theory when it’s activated lets you do all kinds of things. These proofs right now, will be supported the number of statements. Like joining, current coin, spending coins and current spending coins for a different month and so on.

In theory you can build script, some version of script, in to these proofs, so I can actually execute a few arbitrary programs and then, prove them to be secure or prove them to be valid. We don’t support that. It would probably be very expensive. I think [Inaudible 00:23:47] go as quickly as possible.

Participant 5: 	With the secure hash root thing that you’re doing. Is it necessary to have a single universal trusted party to decide how well these rates are is that or is [Inaudible 00:24:00]

Matt: 	It can be done distributed. So network can help out, but [Inaudible 00:24:00] any party who has the hashing ending as well.

Participant 6:	Can you say anything about minting transactions?

Matt:  	Sure. So minting transactions is actually very efficient. All you have to do is pick a serial number and a random number and then, hash them together to produce a coin. Then, you put that coin in to a special transaction and that transaction is send to the network.

There’s no need for Zero-knowledge proofs at all. You put that together and you send it in along with your payment, or whatever that it is that you use as an input and that produces the results. So it could be a point based transaction for example.

Participant 7:	I think this is a very exciting thing. It could have a lot of impact on the real world. And my question is part about the public parameters that when their generated, people that generate them could [Inaudible 00:24:53] Is it the case that we would have to rely on any one of the dispensive threat on [Inaudible 00:25:00].

Matt:  	So I want to clarify [Inaudible 00:27:04] a little bit better. Any tractor that exists, let’s say, in the worst case, somebody does retrain that tractor, it would not allow you to deanonymize transactions.

The worst case is it will allow somebody else to basically make fake coins, counterfeit coins. Your privacy will be protected no matter what, which is a better deal. But, the answer is that is it possible to build a system where multiple people collaborate to build those parameters such that as long as every one of them is honest or a form is honest, you would have secure parameter. We don’t have that built yet, but it’s something we’re considering.

Participant 8:	 You say you planning to deploy [Inaudible 00:25:43] in the near future, and you make a lot of money, how much money? [Inaudible 00:25:50] But the question I have is how are you going to generate yourself parameters before you’re in its real form?

Matt: 	So we’re going to come over and we’re going to have you generate them because everybody trusts you. The answer right now is that we’re going to find a group of people who are interested in this, who are considered trustworthy. We’re going to give them the code for generating it and ask them to review it. And we’re going to go to [Inaudible 00:26:15] to find a computer.

But maybe that answer is not sufficient for people thinking we need to do something a little bit more complex that uses multiply party calculations that use kind of a parameter generation, but we’re going to find out.

Speaker 2: 	Any more questions?

Participant 9: Does Zerocoin keep the ‘there will only ever be this many Bitcoin property' that Bitcoin has?

Matt:  	Yes. So right now we’ll keep the same restrictions that exist on Bitcoin, which is that there are a fixed number of coins [Inaudible 00:26:53]. It would be trivially possible to change that. You could change that to Bitcoin as well, but fundamentally there’s no technical difference here.

Participant 9: Okay. Thanks.

Participant 10:	You mentioned [Inaudible 00:27:10] property for the Zerocash system? Do you need them to be honest all the time or just one person being honest at one time and destroy the hidden parameter he had?

Matt:  	That’s a great question. One person being honest at one time take the computer they used, set it on fire, and you’ll never have to think about this again. It’s not an online partner who has to trust to do this.

Participant 10: I hope that we live in a world where one person can be honest one time.

Matt: 	I agree.

Speaker 2: 	Okay. Let’s thank the speaker again.

[applause]

EOF