Mixing based privacy mechanisms are insufficient

Note: This post is based on the lightning talk I gave at Devcon 5 on the same topic. The slides for that talk can be downloaded from here.

Mudit Gupta Devcon
Me, Giving a talk on Mixers at Devcon 5

What are mixing based privacy mechanisms?

There are various coin mixing mechanisms like CoinJoin (used by the Wasabi wallet), Ring signatures (used by Monero) and the minimal mixer design by Vitalik. All of them share the same basic design principle though.

Mixing based privacy mechanisms blend different actions together in such a way that the viewers can verify that the actions happened but they can not see who did those actions. When talking about mixing in cryptocurrency transactions, the main thing that the mixer should do is to make sure that the senders of the cryptocurrency can not be linked to the receivers of the cryptocurrency. In other words, the most basic mixer would let everyone see who has deposited cryptocurrency to the mixer, and who has withdrawn cryptocurrency, but it will not reveal any linkage between deposits and withdrawals.

To understand mixers better, consider an example where Alice sends some crypto to Charlie while Bob sends the same amount of crypto to Dave. A simple mixer will mix these transactions together such that everyone will be able to see that Alice and Bob’s balances have reduced and Charlie and Dave’s balances have been increased. However, no one other than the participants will be able to tell if Alice sent crypto to Charlie or if she sent it to Dave.

Transaction Mixer
This is what mixers look like

Problems with the existing mixers

Anonymity set is limited in size

An anonymity set is a group of transactions that are indistinguishable from each other. The higher the number of transactions, the stronger the anonymity provided by the mixer. In the example above, Alice could’ve transferred crypto to either Charlie or Dave. The anonymity set size in this scenario is two. An attacker will be able to deanonymize Alice’s transaction if either of Charlie or Dave gives up information about their transaction. It doesn’t matter if Alice didn’t transact with the person who gave up their details. Using the process of elimination, it will still be possible to deanonymize Alice’s transaction. Due to the low volume of transactions on blockchain right now, the available anonymity set is usually rather small.

A lot of mixers don’t even scale enough to be used with large anonymity sets. Monero uses ring signatures to mix the senders and stealth addresses to protect receivers. It draws its anonymity set from the ring size. Initially, there was no minimum ring size in Monero. Thus, it was possible to select a ring size of one. A ring size of one essentially means anonymity set of one and that offers literally no privacy. Monero later increased the minimum ring size to 3 and then to 5 and then to 7 and now it is set at 11.

The gradual increase was done because a greater ring size is computationally more expensive. In the early days, it was infeasible to have such high ring sizes. However, optimizations have been made over time and it has become cheaper to have larger ring sizes. In summary, increasing ring size in Monero offers more privacy but comes with the cost of heavier computations. Monero will increase the ring size further when it becomes feasible to do so. By no means is a ring size of 11 unbreakable or as some may say, bullet-proof (pun intended :D).

Pro tip

Use churning to increase your privacy in Monero (and similar mixers). Churning is the process of sending your whole balance to yourself (on a different address, thanks to Monero’s stealth addresses). Since all transactions are “Mixed” in Monero, an outside viewer will not be able to tell where you sent the balance with certainty. They will be able to guess with a probably of 1/11 (11 is current ring size in Monero) in perfect conditions but you will have plausible deniability. Do churning twice and this probability reduces to 1/121 (Ring size ^ Number of times churning was done). This means that you can increase your transaction’s privacy by up to 11 times (ring size) for every churning transaction you do before your main transaction.

Bad actors can poison the anonymity set

Transactions selected for anonymity set are usually picked at random. If Alice’s transaction is included in the anonymity set of Bob’s transaction, Alice can immediately tell. Alice will be able to use the process of elimination to reduce the anonymity set. If a transaction that has an anonymity set of X, out of which Y transactions belong to Alice, the anonymity set of that transaction is reduced to X – Y for Alice. Hence, If someone has done many transactions, they have a high chance to be able to deanonymize other transactions. A bad actor can spam the network with tons of transactions that look normal at first sight. These transactions will then aid the attacker in deanonymizing future transactions.

You might think that spamming a network with transactions to execute this attack will be too expensive and infeasible. Unfortunately, you’d be wrong. It’s surprisingly cheap to spam Monero with transactions of your own and it has been done in the past. A paper detailing this attack was published this year – “FloodXMR: Low-cost transaction flooding attack with Monero’s bulletproof protocol“. The authors showed that it’s possible to deanonymize half of Monero’s transactions by spending less than 2000 USD per year. Although the paper had its flaws, it did bring attention to this possible attack vector.

Every deanonymized transaction reduces the anonymity of others

As I mentioned in the example above, the process of elimination can be used to deanonymize transactions in a mixer. If a transaction is deanonymized, it can be eliminated from the anonymity set of other transactions. This means that the anonymity set of all transactions that used the deanonymized transaction is reduced. Every reduction in anonymity set makes it slightly easier to deanonymize the transaction. Every deanonymized transaction has a domino effect in reducing the anonymity of the system.

Some exchanges are forced by the law to release all their transaction data to the public. This deanonymizes all the transactions of the exchange, reducing the anonymity of the whole system. Some other entities also release their transactions to the public (willingly and unwillingly, knowingly and unknowingly). All these public transactions hurt the overall system.

For instance, someone was caught reusing addresses in wasabi mixer earlier this year. This meant that their transactions are not anonymous and hence anonymity set of others was reduced too. People from Samourai Wallet eventually caught this and shared a very informative thread on twitter:

Analytics companies have access to more data than normal users

Average Joe does not keep track of all (publicly and privately) deanonymized transactions. Therefore, Joe can not deanonymize most transactions even if he wanted to. If you are looking into anonymous transactions because you want to buy a surprise gift for you SO, you are good to go. However, if you are doing serious business trades and deals, things aren’t that straightforward.

There are companies out there that keep track of all publicly deanonymized transactions. They use these track-records to deanonymize other transactions and they usually keep these new deanonymized transactions private. Then they use a combination of their private collection and public information to deanonymize even more transactions. They might even spam the network with their own transactions to boost their deanonymization rate.

Nodes can collect extra information over time

A node can keep track of extra data that it does not need to and shouldn’t keep track of. For instance, Information like which peer heard about a transaction first. It’s often possible to find out who is running a particular node. There are various techniques like analyzing other services running on that IP Address that can help in this. Once the identity of the person running a node is identified, all transactions that “originated” from that node can be guessed as belonging to that identity. This is not a foolproof method since the victim may not always use their own node to broadcast transactions. The attacker’s node can also incorrectly mark the originating node of a transaction. The attacker can partially overcome the second problem by running multiple nodes to collect more data.

Public nodes aren’t safe either. They can more reliably keep track of who initiated what transaction. They can even censor some transactions. There is no perfect solution to this problem but you can take actions that will make it much harder for attackers to exploit this method. If you really care about privacy, you should run your node behind tor and keep rotating your nodes as often as you can.

Closing thoughts

Mixing based privacy mechanisms are awesome but don’t blindly trust them. They are not fool-proof and can not guarantee anonymity. There is scope for a lot more research in this department. To keep yourself safe, churn your addresses, rotate your nodes and stay up to date with what’s going on with the mixer/coin you are using.

Leave a Comment

Your email address will not be published. Required fields are marked *