So there are a variety of solutions to what we've been calling transaction graph anonymization. Or transaction graph analysis, pardon me. The first of them is called mixing. So what is mixing? Well, the intuition behind this is very, very simple. It's the same intuition that comes up in a lot of contexts, which is that if you want anonymity, use an intermediary to route your communications, or your funds, or whatnot. So let's look at what that might look like visually. Here's an intermediary, and in a second we'll get to who these intermediaries might be. But assume that there is some intermediary, some service, that allows users to put in Bitcoins. But the key property that it gives you, is that after these Bitcoins have been put in, it forgets who put them in and treats its entire store of Bitcoins as indistinguishable from each other. And in fact, it might further combine them all into one giant transaction, or it might further mix them or split them and merge them in different ways, whatever. But the key property is that when users later come in to withdraw their Bitcoins, it's not tied to the coin they put in, they're going to get some other, say, randomly picked deposit that the intermediary receives. So when these three users come back, they're going to withdraw these coins in a random order. And so somebody looking at this in the blockchain, who doesn't have the records that the intermediary might or might not store, just from the publicly available information in the blockchain, is not going to be able to link the ultimate input addresses to the ultimate output addresses corresponding to the same user. So that's the intuition behind intermediaries. Now, looking at this, does that strike a chord? Have we seen in previous lectures something that offers services that are similar to this, that allows you to deposit Bitcoins and then withdraw them later at a later time? You might recall that this is exactly what online wallets do. There are services where you can just store your Bitcoins online until you need them. And so you might wonder, well is that the solution to our problems? Do online wallets provide anonymity? Let's think about that. The answer to this is not obvious. But I will start by mentioning that it's taken well-known researchers by surprise. Here was a post on the New York Times Bits blog reporting on a preprint of a paper released by two Israeli researchers, saying that there was a link between Dread Pirate Roberts, the pseudonymous creator of SO Crib which we're going to see more about and Satoshi Nakamoto. This was of course very surprising. But as it turned out, all that had happened was that they had mistook this link, that went through an intermediary, and that intermediary just turned out to be ModGaks which you can think of sort of as an online wallet service. So a few days later, this other post was published at the same menu, see if you can spot the difference. They had to retract their study, and I think they had made a very simple mistake of not accounting for the presence of this intermediary. So it's clear that at least in some sense, online wallets provide some sort of anonymity because at least somebody tried to make a connection between an input and output address and completely failed at that. So let's try to understand exactly the sense in which online wallets provide anonymity. And I think a good way to do that would be to in fact contrast online wallets with online services that exist specifically for the purpose of acting as these intermediaries for anonymity. And those are going to be dedicated mixing services. We'll talk about mixing services in much more detail. But very briefly, the two things that they promise that you won't get simply by putting your Bitcoins into an online wallet and retrieving that again, is that they promise not to keep records. It's not just as a side effect they randomly give you Bitcoins that came from some other address. But they specifically say that they won't keep records. So even if they tried to, they wouldn't know which Bitcoins were the one you put in. So with the high probability you're going to get some other good coins back. And furthermore, even if someone came knocking for the records or if they got hacked and so on, there would be nothing to find. There would be no records. So that's something that a mixing service promises and the other thing is that you don't need your real life identity in order to interact with these services. And this is in contrast to most of these online wallets. Why? Because online wallets are typically reputable and in fact often regulated businesses. And this fact has two consequences. One is, the bill typically require your identity. In banking there is the know your customer principle, which essentially at a technical level translates to learn the customers identity and store those records. And in fact, they will keep records if they receive a deposit they will keep the link between the identity and the Bitcoin address. If they move money around internally, they will probably keep records of all of that. And just because when you withdraw your Bitcoins they come from a different address, does not mean that the online wallet does not know the link. That link probably does exist in their records, and will exist for all eternity. Even if they don't explicitly ask for your identity, think about this, to even interact with an online wallet you do need a persistent long term identity. You can't possibly use a different pseudonym every time, because if you did they'd have no way of associating an account with you, knowing how many Bitcoins they owed you, right. So, because of that, even if they didn't ask for your identity, at the very least, the online wallet knows the address of every single deposit that you made of the Bitcoins that you put into the system, and more importantly, every single withdrawal that you made. And so, when you make a series of withdrawals from an online wallet and proceed to spend those Bitcoins, the wallet service can now connect all of those together in a profile. And of course it's not just the wallet service. People who care about anonymity are also worried about those records getting hacked, insider attacks, somebody who has a subpoena for getting those records, and so on and so forth. So with respect to the wallet service itself and whoever they might be cooperating with, you have no anonymity in this context. On the other hand, there is something cool about this. If you are willing to trust them with your Bitcoins, then what's gonna happen is you're gonna keep them in the wallet service for much longer than you typically would with a mixed service. Why? Because you don't trust in a mixed server as much. You want to put it in your Bitcoins and you want to receive it back immediately from some other address, an address of your choosing. So unlike that, for an online wallet service you're going to have a bigger anonymity set. Why? Because your anonymity set, from the point of view of someone with no privileged information, from the point of view of someone who's merely looking at the blockchain, your withdrawal could look indistinguishable from every single withdrawal ever made from that service provider. So with respect to the wallet service, you have no anonymity. With respect to everybody else, you have a bigger anonymity set than you possibly would with using a mixing service. Or at least with using the single mixing service. So if we look at this, this looks suspiciously similar to the kind of privacy properties that you have with the traditional banking system. There are the essentialized intermediaries that know a lot about our transactions. But from the point of view of a stranger with no privileged information, we have a pretty good amount of privacy. So even if this gives you some sort of anonymity, it's almost, at best what you get with the traditional system. And so those were not the kind of people who were typically looking for anonymity in Bitcoin anyway, if they were happy with the anonymity properties of the traditional system They would have probably stayed with that system and so generally, people who are looking for anonymity properties in Bitcoin simply do not want to accept the trust requirements that these online services, online wallets services require and they don't want the sort of anonymity properties that it gives. They don't want to have to trust that service with their anonymity. And in fact, we've seen that there have been a lot of closures of these exchanges and services and so there's good reason for believing that if you put all your trust in an online service, you might simply lose your money. Okay, so having rejected online wallets as an anonymity solution, let's turn to these dedicated mixing services that I told you a little bit about. Before looking at their details, let's talk about the terminology a little bit. I like to call it a mix. Some people call it a mixer. These are really the same thing. Some people also call them laundries. I don't like this term at all and the reason for this is that it needlessly attaches moral meaning to something that's a purely technical term. As we've seen earlier, there are very good reasons why you might want to protect your privacy in Bitcoin and use mixes for entirely good reasons for everyday privacy. Of course, we must also acknowledge the bad uses, but it seems a little bit weird to me to use the term laundry that implies that your coins are dirty and you need to clean them and attaching a negative moral value to the whole thing and for that reason, I'm not going to use that term in this lecture. We'll go with the technically neutral term, which is mixing. So in talking about mixing, there are several of us, about six of us that got together, researchers at Princeton, Concordia, and Maryland, including all four of us who are doing this on-line lecture series and analyse the existing mix ecosystem and proposed a series of changes for improving the way that mixes operate both in terms of anonymity and the trustworthiness of mixes. So let's look at those principles. Before I show you those principles, as a quick reminder at a very fundamental level, how does a mix operate?. It asks for an address at which you want to receive bitcoins, and it gives you an address to send bitcoins to the mix and then you both execute that transaction. It's a swap, basically. In a second, I'll show you what that looks like visually. But what were our principles for running these mixes properly? Well, the very first one is that you might wanna use a series of mixes instead of just a single mix and this is a very well known principle. Using a series of routers is the same principle and the anonymous communication system tour, and it's a good idea because it allows you to not have to trust a single mix but instead to be sure as long as any one of these mixes is promising to delete it's records, then you have a good guarantee of anonymity. And in particular, mixes should implement a standard API so that this can be very easy for clients to accomplish, and right now, this not quite the case and this is our paper for your reference. So now let's go in and look at what a series of mixes would look like visually. So here it is. Here is a user who starts with a coin or an input address that we assume that the adversary has managed to link to this particular user. They're going to send it to the mix at this address and get back a bitcoin at this other output address that they provide. They freshly generate this output address and provide that address to the mix. The mix will hopefully return the same amount of bitcoins at this output address. There's no way for the user to force the mix to do that. The user has to trust the mix and this is, as we will see a recurring problem with the whole notion of mixes. And either immediately or after a time gap, it doesn't matter, the user will take the bitcoin or bitcoins of whatever value they have received at this address and send it to a different mix which is hopefully not cooperating with the first mix, and repeat this process over and over again. So from an adversary's point of view, looking at the public block chain, they're merely going to see, along with all of these transactions, a variety of other mix transactions that other users are executing and hopefully, the adversary will have no way to tell apart which of those transactions correspond to this particular user and which one corresponds to some other users. So that's the first principle and the second one, if you think about what I've just said, in order to make that possible, you want to make these transactions as uniform as possible, so that this link ability is minimized. What does it mean to make these transactions as uniform as possible? One important consequence is that all of these mixed transactions, not only from a particular mix but from all of the mixes in this mix ecosystem should have the same value. So we think that all mixes out there providing service should agree upon a chunk size, a standard chunk size and of course, there can be multiple denominations. But there can be too many, and you can't simply allow the users to put in whatever amount of bitcoins they wish to, that wouldn't work. So you need this kind of standardization. In addition to this, we found that there are a variety of possible attacks in which a clever adversary might infer various things, not just the amount, even if you remove the amount, some other properties including timing for example in order to try to link users input addresses and output addresses together. This type of linking can be avoided. But human users if they interact with the mix, are not going to be able to take into account all of those possible linking attacks. So instead, what needs to be done is, this client side software must be automated and built in to desktop wallet software so that this desktop wallet software automatically knows how to interact with these mixes in order to preserve the user's anonymity. So that was our third principle. Our fourth principle is a subtle one. Now these mixes, why do they provide this service? Typically, it's because they're a business and if they are a business, they want to be paid. How are they going to get paid? Well it turns out that pretty much the only way for these mixers to get paid is to take a cut of the transaction that the user is sending to the mix. That seems a bit weird because if a mix takes a standard percentage, then an adversary might be able to use that to link the input transaction and the outward transaction. So some current mixes try to randomize the transaction fee, they might say we take a random cut between 1% and 3%. We found that this is not a good idea either because if you put that through a chain of mixes, then the amount of the value in the chunk is going to dwindle in a predictable way and this is an important side channel for the adversary. So what is a way to avoid this? We proposed that these mixed fees should be all or nothing. In other words, the mix should either swallow the whole chunk with a small probability or should return the whole chunk. So if the mix wants to charge a 0.1% mixing fee, this is by the way, very different from the transaction fee that mining notes charge, this is a mixing fee on top of that. So if the mix wants to charge a 0.1% mixing fee, then one out of 1000 times, the mix should swallow the entire chunk and 999 times out of a 1000, the mix should return the entire chunk without taking any mixing fee. This is a tricky property to accomplish which means that the mix should generate a random number in a way that can convince the user that the mix is not cheated in generating this random number and has genuinely flipped a coin which has a 99.9% chance of coming up one way versus the other. But we do show how to do this using cryptography in a way that both parties can be satisfied and has worked correctly. We think that really all four of these principles are necessary to have anything approaching mathematical confidence and having a large anonymity set. And in our ability to resist clever inferential attacks by an adversary that looks at the botching, to try to link input to output. The sad news is that virtually none of the current mixes follow these principles. They're in a very different model where each mix operates completely independently and they have a web interface. And the user interacts with them totally manually instead of automatically through their wallet software. And will manually put in the amount, Instead of standard chunk size, it's whatever amount the user chooses typically. And the mix will take some cut of that as a mixing fee, and send the rest to the user. So this is, we don't think this is a situation that gives mix users a lot of anonymity, but we think that by moving to a slightly different model based on these four principles, the anonymity properties of the mixed ecosystem can be dramatically improved. All right, so through these four principles we've seen how the anonymity properties of mixed in can be improved. But there is still one major problem, which is that users still have to trust these mixes. So again we had a few ways that we talked about in our paper for what to do about this. Mixes can do several things to improve their trustworthiness. One is, that simply by staying in business for a long time and not stealing users' money, they can build up a reputation. You might wonder, does this reputation count for anything, because it's simply a matter of he said she said. In fact a mix operator can claim that a competing mix operator stole all their money even if that did not in fact happen. Well, generally reputation systems in the real world manage to operate even though they can be conflicting claims that are made. In this context for example, users might learn to only trust the word of prominent members of the BitCoin community, who they think have the best interests of the ecosystem at heart. Another way is that, in the system that we proposed, the chunk sizes are going to be so small, that in the regular course of mixing, users are going to mix a pretty huge number of chunks. Or at least the system can be configured in that way so that the chunk sizes are relatively small. So in that context if a mix has even a one percent probability of stealing a user's chunk, then after a 100 or so interactions with small chunk sizes with a particular mix. The user is going to know. The user is going to detect the theft. And so, the user will learn to never use this mix again. And so, the system might sort of correct itself by users testing mixes for themselves for trustworthiness. An important thing to keep in mind here, is that the chunks that users are sending to mixes have typically already been through other mixes. So the mix itself can't know which user the chunk is coming from, and so the only thing the mix can do is to essentially steal randomly from users. The mix can't steal from a particular user. So, from the user point of view, on average, they won't suffer losses that are more than the average rate at which the mix steals. So they don't have to worry that a mix might particularly have it in it for that particular user, and steal all of their money. There's no way that that can happen. So that's what I mean when I say users can test this for themselves. And finally, we proposed a cryptographic mechanism where the mix can issue sort of a promissory statement to the user. That once it receives a chunk at a particular address, it will send a chunk back at some other address that the user provides. And so if the mix fails to keep this promise, our idea is that the user can publicize this warranty,and everybody will know that a particular mix has cheated. And so everybody will stop using this mix, and the mix will lose business. In combination, all three mechanisms provide incentives for mixes to act honestly. So these were our calculations anyway, and our proposal. We haven't proved that this will work in practice. That remains to be seen. All right, on that note, let's quickly look at how things are in practice right now. It doesn't seem that there are any reputable services providing dedicated mixing that users have learned to trust, or at least enough to use on a regular basis. In fact this is from the Bitcoin Wiki where the original is also highlighted in red, so I took the liberty of doing that myself. Mixing services may themselves be operation with anonymity, and so if you're funds are not delivered you have no recourse, you use at your own discretion. So we're proposing moving to a different model, where mixes stay in business, become reputable entities and so on. That hasn't quite happened yet. And note that there's a sort of a bootstrapping problem here. If mixes were reputable entities, they would have a big volume of transactions. And so by interacting with them, you'd get a pretty good anonymity set. So users would be more confident in interacting with them, and mixers would realize that they're making more money by staying in business and taking a small cut. Than by trying to steal the small amount of money that they're controlling at any given time. And so mixes would be further incentivized to stay in business. So you can imagine that once a mixed ecosystem gets going, it will be self- sustaining. But whether or not that can eventually happen, we can say for sure that it hasn't quite happened yet.
