Now let's turn to Zerocoin and Zerocash, which are a completely different approach to Bitcoin anonymity. The approach is to bake it in at the protocol level. And these are cryptographic heavyweights. Zerocoin was first developed by cryptographers at John Hopkins. And later on they started collaborating with other researchers around the world who had been developing a very efficient cryptographic technique that would enable making some of the cryptographic operations and Zerocoin more efficient and that resulted in Zerocash. As you'll see, these techniques provided a qualitatively different level of anonymity than mixing solutions that sit on top of Bitcoin. But what's the catch? The problem is that this is not quite backward compatible with Bitcoin. Zerocoin and Zerocash are going to require Altcoins. Technically it's possible that Zerocoin can be deployed as, what is known as a softwork of Bitcoin. But the practical difficulties are high enough that this is not really considered feasible. And in fact the Zerocoin developers intend to deploy it as an Altcoin themselves, instead of trying to be compatible with Bitcoin directly. Let's start talking about the details here. Let's review some of the things that I've just said. So Zerocoin brings protocol level mixing. And being baked into the protocol, what it gives you is a cryptographic guarantee of mixing. What does that mean? You don't need to trust a single mix, or even a set of mixes or a set of peers, or anybody at all to ensure your anonymity. You just need to rely on the underlying crypto being solid. You don't even need to rely on the minors enforcing this in order to achieve anonymity. It's purely a cryptographic guarantee. So that's really great. That's qualitatively better than what we have so far. And, of course, it's not currently compatible with Bitcoin. And here's the paper if you wanna look it up. So how does Zerocoin work? I'm going to introduce a concept called BaseCoin. And I'm taking a few liberties with the presentation here in order to simplify and clarify the concepts. I'm gonna do that by mixing some concepts from Zerocoin and Zerocash, but toward the end I'll make very clear what the differences are between the two. So like I said, Zerocoin is an Altcoin, and I'm gonna call that Altcoin, Basecoin. I'm not calling it Zerocoin, because Zerocoin is something else. It's an extension of this Basecoin. It's something that sort of sits on top of this Altcoin. And the key property that gives you anonymity is that these basecoins can be converted into zerocoins and back again. And when you do that, it breaks the link between the original Basecoin and the new Basecoin. So think of this as a cryptographic mixing system that's provided by the protocol itself. So how might this work? Another way of looking at a Zerocoin is that it's a cryptographic proof that you owned a Basecoin, not anymore, but you owned it, and then you made it unspendable. A Zerocoin is something that allows you to assert that to say any miner who might care. And miners can verify these proofs. And that's what gives you the right to later redeem a new Basecoin in exchange for the Zerocoin. And the analogy is a little bit like poker chips. So how could that work, and what properties do these proofs need to have in order to enable this? So one challenge is how to construct these proofs. And the other trick is, how do you make sure that each proof can be spent only once, can be used only once to redeem a Basecoin? Because if you don't have that property, then it's going to lead to double spending. So let's see how to do that. It currently involves a concept called zero-knowledge proofs. What are zero-knowledge proofs? I am going to tell you at a little bit of an intuitive level, so I'm going calling it crypto magic again. What it is, is it's a way for somebody to prove a statement without revealing any other information that leads to that statement being true. A couple of examples are going to make this really clear. You might be able to prove a statement like, I know an input that hashes to this particular poly. And notice, that if the input video picks were long and random, if you did approve in such a way that you don't actually reveal the input, it won't necessarily allow somebody else to infer what that input is. A more complex version of this is you could say, I know an input that hashes to some hash in a following set of several different possible outputs. And the zero-knowledge proofs that Zerocoin is going to use is very similar to the second category here. Let's dive in a little bit more. So, zerocoins are minted. They come into existence by minting. And anybody can do this. And zerocoins come in standard denominations. Let's assume for the rest of this that zerocoins are worth one basecoin each. You can also imagine multiple denominations coexisting. How do you make a zerocoin? Well, we're gonna see that in the next slide. But let me just say for now that minting a zerocoin doesn't automatically give it any value. You can't get free money. It only acquires value once you put it onto the block chain. And so putting it onto the block chain is going to be about as expensive as the value of that zerocoin that you're later going to be able to redeem. So you have some sort of a conservation principle here. Okay, so here's how specifically, in cryptographic terms, we mint a zerocoin. It's something called a cryptographic commitment. What a cryptographic commitment is, is intuitively you can think of it as you are taking a serial number, a random serial number that you generated, and putting it into an envelope. So this intuitive notion of putting it into an envelope, cryptographically what does that correspond to? What it corresponds to is generating another random secret, r, which you're never going to make public, and computing the hash of the coin serial number together with this random secret. Now this is a little bit of a simplification, but it really helps you understand the properties of the system. So let's go with this description. So what just happened here? You generated arbitrarily, just like you generate Bitcoin public keys, a serial number for your zerocoin. And if it were long and random, hopefully no one else has ever picked that same serial number before. And you also generated this other random number that we are going to keep secret. And intuitively, generating a commitment to this serial number corresponds to putting it in an envelope and sealing it. And mathematically it happens by computing the hash of the serial number together with this random value. Once you have generated this commitment what do you do with that? At the next step is to put that commitment onto the block chain. That's when the zerocoin becomes real. And doing this requires in a sense burning a basecoin, and making it unspendable. So in concrete terms how would that work? You got the block chain over here, and one of those transactions might be a mint transaction. And if you zoomed in, it would be a transaction that's signed by Alice. Who created this zerocoin, who minted the zerocoin? And what we saw earlier in the structure of transactions, is that over here, you would have the recipients public here, the recipients' address. Instead of that, here you have this cryptographic commitment. And just like before, just like a transaction having a pointer to a previous transaction, the same structure is carried over for Zerocoin transactions as well. So what has happened here? We've spent this basecoin, in order to mint the zerocoin. And this commitment, the sealed envelope that we've put into the zerocoin, is what is going to allow us to redeem that zerocoin later in exchange for a basecoin once again. So how does that work? To spend the zerocoin later, you will reveal that serial number that you put inside the envelope. And what miners will do, it's their job to verify that the serial number has not been spent before. That the serial number has not been revealed as the number that was put inside some other envelope. That's what prevents double spending in the system. Next, you'll create a zero-knowledge proof, that we just talked about. And specifically, the zero-knowledge proof will say, I know a number, r, such that the hash of the serial number, together with r corresponds to one of the zerocoins of the block chain. And we'll make that statement more mathematically precise in a second. But think about what this says. It doesn't reveal that random number r. But somehow you're proving that you are in possession of that number. Combined with this serial number that you have just made public. Will result in the zerocoin that was once in the past put onto the block chain. So for somebody looking at this proof, this is all they need to know to verify that you earlier spent a base coin in order to get to this point. So this now should give you the right To redeem a base coin. But which base coin? And here's where the anonymity property comes in. You can pick an arbitrary zero coin in the block chain and use that as an input to a new transaction out of which comes a base coin and the miners will allow you to do that. So, put a zero coin in, take a zero coin out, but a different zero coin. And all that anybody needs to know is that you have the right to do that because you put in some zero coin in the past. It doesn't matter which zero coin. And you can't do that twice. You can't spend it twice corresponding to a single mint because the serial number now will become public. There's only one serial number corresponding to one zero coin, and you only know the serial numbers corresponding to your zero coins and not anyone else's zero coins. Great. So where does the anonymity property comes from. Here's the anonymity property. Since you've kept this random number r a secrets. and this is what is available on the block chain. There are a number of hashes, or commitments, corresponding to the different zerocoins that have been put on the block chain. Even though you've revealed the serial number, not knowing this other random input, r, nobody can try to brute force this and guess which of these zerocoins corresponded to your serial number. So even after the serial number inside an envelope has been revealed, and it has been verified that this serial number was inside one of the envelopes, we still don't know which serial number it is. So this is the sort of magical property that zero numbers proofs and cryptography can give us that you wouldn't get in the real world, physical world, envelope-based cryptology. So the next cool thing about this whole construction, is the fact that these proofs are efficient. I'm putting efficient in quotes here, and the sense in which they're efficient is that compared to what we know of zero knowledge proofs, and have come to expect on them, it's quite an achievement that these proofs are as efficient as they are. However, compared to the efficiency of the BitCoin transactions themselves, these are in fact quite slow. So it occupies a space in between those two. So exactly what I mean by efficient. The reason it's efficient is that it manages to avoid being linear in the number of zero coins on the chain, even though that is what you would expect. Why is that what you would expect? Think about the statement that the spender is proving here. I know a random number "r" such that either the hash of the serial number with "r" corresponds to the first commitment or the second commitment. Or, any one of these giant number of commitments that reside on the block chain. So it's a very long statement that the prover is proving. It's a statement whose length is proportional to the number of zerocoins on the watching. And yet, the proof is much smaller than that. It's not linear, it's only logarithmic in the value end here. And that's part of the magic of Zerocoin. That's what makes it possible to even run the system. All right, moving on, let's talk about Zerocash now. Zerocash kind of takes the cryptography sort of to the next level, it uses a cryptographic tool called Snarks, which we won't get into at all. But the upshot of the use of these more efficient cryptographic constructions for proofs, is that the efficiency gets to a point where the author suggests that you can in fact run the whole system without having any basecoin. All transactions can be done in this zero-knowledge matter. You don't need to have separate expensive transactions that are used only for mixing and a set of regular, everyday transactions that you use when you don't want special anonymity properties. That distinction is now gone. The claim is that you can run all of these transactions sort of inside these envelopes. And what I mean by that is the following. All transactions are zerocoins, and so Zerocash becomes untraceable in a sense, because there is no basecoin. And the reason for that, is that splitting and merging of coins are also transactions that are supported in Zerocash itself without going to basecoin. And, in particular, the transaction values, the transaction amounts, you can put those inside the commitments. Those won't be visible on the block chain anymore. The only thing that the ledger records publicly is the existence of these transactions. You know that Alice put in some transaction. You know much later that Bob redeemed some transaction, who might be the same user, might be a different user. But the only people who need to know what the amount is are the sender and receiver of any particular transaction. The miners don't need to know that. If there's a transaction fee, then the miners need to know that fee. But that doesn't really compromise your anonymity property. Right. So the ability to run Zerocoin in this different configuration, where it's not two different coins anymore, it's not a basecoin with a mix layer on top. But instead an entirely untraceable system of transactions, puts Zerocash sort of in the next level when it comes to anonymity. Because a lot of the possible side channel attacks that were true for mixing, that were true to a certain extent at least for Zerocoin and no loner true for Zerocash, because the transaction amounts will no longer be visible in the public ledger. But that almost sounds too good to be true, a completely untraceable electronic cash system. It is ledger-based, but the ledger doesn't record anything that might compromise anonymity or privacy. Well, there is one catch. Here's the catch in Zerocash. It requires a certain setup process to even set up the systems. Specifically, one needs random and secret inputs in order to generate the public parameters. Think of those as public keys, except that these are giant public keys, they're over a gigabyte in size. And not only that, not only is the size a bit of a problem, these secret inputs for this security system then have to be securely destroyed so that nobody knows what those secret inputs were, that were used in order to generate these public parameters. That seems like a bit of a problem. And the reason that no one can know them is because if somebody knows them, it doesn't mean that they will be able to compromise anonymity. But they will be able to create new zerocoins for themselves and nobody will be the wiser, which is also an equally bad problem for the currency. So it's kind of an interesting sociological problem here. How could some entity setup the system and then convince everybody that they've securely destroyed the parameters that were of course necessary in order to setup the system? So it's not entirely clear how that can be solved. There have been various proposals for it, but at the moment we don't have a very clear idea of how to go forward on this. So what have we seen so far in all of the different efforts to improve anonymity in Bitcoin? Well, if we put them on a line, as I'll show you in a second, we see that there are five clearly different levels of anonymity that we've seen in a difference of proposed solutions. And what are these? So let's look at not only the levels of anonymity that these systems provide, but also the deployability of these systems. Let's start with Bitcoin, which is already here. It's only pseudonymous, it doesn't even aspire to be really anonymous. And we've seen that pretty bad transaction graph analysis are possible. I showed you many beautiful graphs with clustering of different addresses and many cases how to go from those addresses to identities. So, not a lot of anonymity provided by Bitcoin. The next level is simply using a single mix, sort of a manual way in which people are doing right now with some of this dedicated mix services. And that still allows you transaction graph analysis, because, as you might remember from the four principles that I gave you, if you don't have this automated system that has uniform chunk sizes and so on, a lot of transaction graph analysis is still possible. And in addition, you have to worry that this mix might not be trustworthy for storing records. It might be sharing them with other people, and again, could get hacked, et cetera. The third level that we saw is a chain of mixes. And this can be in a centralized model or a decentralized model. It doesn't matter. Both models give you roughly the same level of anonymity. But where really the anonymity improvement comes in for this one compared to a single mix, is that you have these standardized chunk sizes, and you have a series of mixes, and you have a variety of other bells and whistles on top of it like automated clients and so on. And for this, some side channels are still possible, not as bad as before. Transaction graph analysis is no longer that easy. And you still have to worry about an adversary who might collude with multiple mixes or the decentralized model, some peers that might be malicious and compromise your anonymity. This is, of course, perfectly backward-compatible with Bitcoin, could be deployed and adopted any day. Hasn't quite happened yet in a way that we would consider to be truly anonymous. And then we saw Zerocoin, which is cryptographing mixing baked into the protocol. Doesn't depend on anybody promising to destroy their records or anything like that, you just need to trust the math. So that's a whole different level of anonymity. In my opinion, it still has some possible side channels, but it's not as bad as the other mixing base solutions that we saw, where it's not baked into the protocol. And Zerocoin, of course, as we saw as an altcoin. So, it's not quite Bitcoin compatible in a way that one might hope. And finally Zerocash. The difference between Zerocash and Zerocoin, is not so much at a fundamental mathematical level, but because of the fact that you can run Zerocash in a configuration where you get rid of the basecoin altogether and the efficiency is not too bad in that configuration. And so what that gives you is untraceability, which is something on top of unlinkability. So that's a new anonymity property. And there really aren't any anonymity attacks that I can think of at least. But the downside of course is that not only is it an altcoin, but it also has this very tricky setup process that we don't necessarily know how to make progress on.
