So the fact that this mixed ecosystem currently doesn't exist is a big part of the reason why many people have proposed decentralized mixing. And there were a variety of reasons for decentralized mixing some of which we have talked about in that there is no bootstrapping problem. So the reason there's no bootstrapping problem is that in decentralized mixing, you don't go through a particular dedicated mixed service. Instead, you find a community of peers who all want to do mixing and somehow without any central coordination or at least a central service that collects your funds, you manage to mix with each other. So that avoids the bootstrapping problem because as long as there is enough interest from Bitcoin users, they can meet with each other and start mixing. How to do that? We'll see in a second. Also theft is impossible and this is enforced through technical means because nobody is explicitly sending Bitcoins to another user, again we will see how this is accomplished. It could possibly provide better anonymity and we'll look into more details on that as well. And finally, I just wanna point out that this is just more philosophically in line with Bitcoin. If you can get rid of having to have a centralized service for some purpose then there are a lot of users who are BitCoin users who find that appealing. So how might this work? The main proposal for a decentralized mixing is called a Coinjoin and this is something that was proposed by Greg Maxwell. Who is a core Bitcoin developer who we'll meet again in the next lecture actually. So what he proposed is different users coming together to create a single Bitcoin transaction. And what are the outcomes of this transaction, we'll see in a second. But somehow create a single Bitcoin transaction that combines all of their inputs and presumably of equal value. Now, let's think about this for a second. What is necessary in order for these three users to create a single transaction? Well one way of thinking about it, we might imagine that in order to produce a signature, somebody has to collect all three private keys. That's not actually how it works though. In Bitcoin, all the signatures corresponding to the different inputs are totally separate. So each input signature is entirely separate. So what it allows the users to easily do is create different inputs that correspond to different users and also different output addresses that correspond to different users and randomize the order between them. So in this situation maybe the users participating in the protocol might necessarily have to know which input address corresponds to which output address, although we'll see in a second if we can avoid that as well. But certainly someone looking at the block chain, looking at only this single transaction even if they realize that this is a Coinjoin transaction will not be able to find the mapping between the input and the output. It's that simple. That's the essence of Coinjoin. Of course, this is just one round of mixing. On top of this, you have to apply the same principles that we talked about before. So the principles that I discussed they're not only for centralized mixes, they apply essentially with very few modifications even to the Coinjoin scenario. So you wanna do a sequence of Coinjoins, you wanna make sure that these chunk sizes are standardized. So that you don't introduce new side channels, etc. Okay, but let's look into the single transaction though. Exactly how would this work? There are a lot of details that are still not clear. So let's look at this in algorithmic form. So if we write out like this what needs to happen is that a group of peers who all want to mix somehow need to find each other. That's the first difficulty, and then they have to exchange their input and output addresses with each other and one of these users it doesn't matter who will construct this transaction. Not yet a sign transaction but just the transaction that corresponds to these different inputs going to these different outputs. And then they'll pass it around to collect signatures from each of the peers. Now, if the peer who constructed the transaction were disruptive and for example, left out one of the peer's outputs then the whole thing will collapse. Because when that particular peer gets the transaction in order to sign it, they will simply refuse to sign and the process will not be able to go forward. But if everything is okay, everyone acts honestly then the transaction is constructed. And now any peer, it doesn't matter who can broadcast a transaction to the network. Two of them could do it independently it doesn't matter, the transaction with of course be counted only once. So that's it, that's the whole protocol. The entire security property comes from each peer checking that their output address is represented and that their output of course receives at least as much value as went in from their input. So that seems simple enough. But what are the remaining problems here? Well, there are three problems. One is, how did this group of peers find each other? And the second is that as I described in the previous slide, this protocol involves each of these peers finding out the mapping between inputs and outputs or at least one of those peers. So that seems like a problem. In fact, I wanna point that this is a worse problem for decentralized mixes than for centralized mixes and why is that? In the centralized mixing case, you could hope that these different mixes are run by entirely different entities who are not colluding with each other. And at least in some cases, these will be reputable real life entities who, you would imagine have incentives not to collude with each other because they have different goals or for whatever reason. Again, the reasoning is similar to Tor, you have a variety of different types of people who are running Tor nodes, they don't all have the same incentives. So we imagine that they're not all going to collude with each other and also that they're not all going to get compromised by the same attacker. A similar principal holds for decentralized mixes, and that only works because you know something about the identities of this mixes. So these mixes having known identities and being reputable entities helps anonymity in this case. We don't have that luxury with decentralized cases because we have no idea who any of these peers are. It could be a single attacker creating lots of civil accounts. And Accounts, in the sense of just creating lots of civils. And try to get into every single Coinjoin transaction that's ever carried out in order to learn the essential output mappings. And so even if you do a series of Coinjoins it might be the case that in each of those Coinjoins at least one of those participants was an attacker or was controlled by the same attacker in which case your entire anonymity is lost. So that seems like a problem. And the third problem and kind of a tricky one, is denial of service. What does this mean? Well, it could happen that after providing the input output pairs, one of the nodes disappears and refusing the sign the resulting transaction. So the transaction is not able to proceed forward. And secondly, even after creating the signature before the transaction can get broadcast to the network and confirm that I'm watching, one of the nodes, who might be malicious might take this input and spend it in some other transaction that's unrelated to this Coinjoin. And so this Coinjoin will look like a double spend attempt and will be rejected by the big coin network. So that's another way in which you can launch denial of service against Coinjoin. So now, let's look at what are some possible solutions to each of these three problems. Well the first one, how to find peers is a very simple solution. It's not a perfect solution but people consider this to be somewhat okay. You simply use an untrusted server, it's sort of like a watering hole where different users can connect and find each other. But the server is not necessarily involved in any way that the users have to trust in running the protocol. And as we're gonna see, each of these steps for solving these problems introduces a little bit of engineering complexity. So this already requires a whole peer to peer protocol for finding these Coinjoin peers on top of the Bitcoin protocol. And we're gonna see similar factors that introduce engineering complexity for solving each of the other problems. So the next one, how do we solve the anonymity problem? There's a simple Strawman solution. You can frame the anonymity problem in this way, you need to communicate the set of inputs to all the peers and also you need to communicate the set of outputs, but break the linkage between the input and the output. Now, this becomes a communications anonymity problem instead of a Bitcoin anonymity problem. Because it's simply the matter of communicating these output addresses that needs to be unlinked from communication of the input addresses. So a Strawman solution to that since we already have seen Tor a little bit is simply this. These peers come together. They exchange input addresses and they disconnect and then reconnect over Tor after a while and then exchange the output addresses. So this is pretty simple but it may not be very robust in practice. A better solution might be to build a special purpose anonymous routing mechanism for these participants to utilize just for this protocol. And there are things called decryption mixnets that allow you to do exactly that and such solutions have been proposed. So let's move to the third problem which is a denial of service attack. Let's think about it this way. What's a traditional solution to a denial of service attack? Well, one possible solution to a denial of service is to make it a little bit expensive for the client to connect to the server and to receive service. Well this is not a client server model, it's a peer to peer model but we can still try to adapt the same principles. And that's the principle behind the first two of the proposed solutions for denial of service, either a proof of work or a proof of burn. So what do I mean by this? Proof of work is simply repurposing the algorithm behind Bitcoin's proof of work to require each of these piranodes to do a little bit of computational work before they can join a Coinjoin protocol. And the rationale is that if the adversary is going to disrupt every Coinjoin that exists out there, they're going to be burning a lot of competing power which will make it very expensive for them. Proof of burn is a similar concept. It's also called Fidelity Bonds in Bitcoin. It allows you to irreversibly destroy some Bitcoins that you own by sending it to an unspendable address. There by curving that you've made a little bit of an expensive signal in order to get into the system. So that's the rational between the first two solutions. The second two solutions next to the third and fourth also have a similar rationale, which is to identify one or more malicious participants who launched the denial of service to kick them out and to run the Coinjoin with the remaining participants. And that could be done if you trust the server a little bit to carry it out. It could also be done in a purely decentralized manner, like this paper called CoinShuffle proposed. And they came up with a cryptographic blaming protocol for doing this. And it involved something called zero knowledge where you learn at least one of the players who misbehaved without necessarily learning much more about what happened. And then the rest of the peers can then redo the protocol. At various points, I've talked about side channels. So let's look at an example of that. And I wanna point out that these side channels can be very tricky. Not all the mixing in the world can save you from what I call high level flows, that could be identifying. And here's a neat example of this. Let's say a user Alice, receives a very specific amount of Bitcoins, let's say on a weekly basis as income. And has the habit of always automatically and immediately transferring, let's say 5% of that to her retirement amount. So think about the patterns that will be visible on the block chain here. No matter what she does to obscure the link between the address that which she receives her income and the address to which she transfers to her retirement account. The patterns here are going to be uniquely identifying because this is a very specific value and the 5% of that is also going to be a specific value. And there's also a timing pattern, every time money appears here, every time money goes to this address as well. So this is a problem. How do we protect ourselves from this? Well, one suggestion that has been proposed is not only in the context of mixing but even the context of regular Bitcoin wallets where users are not even trying to do any mixing as by Mike Hearn. And he calls this merge avoidance. Merge avoidance is a very simple idea. When users wanna do payments the proposal is that instead of creating a giant transaction that combines as many inputs as necessary in order to pay the entire payment to a single address. Why not have a protocol by which the receiver can provide multiple output addresses as many as necessary. And the sender and receiver can agree upon denominations and the sender can avoid combining different inputs and can make up a variety of different transactions that send money from different input addresses to different output addresses. So this avoids a lot of the problems both of high level flows because even these multiple input and output addresses cannot be linked to each other. So an adversary might not even be able to observe the fact that this is a high level flow that this is that's happening but also avoids problems like clustering addresses together because of evidence of share in spending. And this is a proposal that one could think about incorporating right now, into Bitcoin based payment flows in order to improve anonymity for everyone.
