Bitcoin right now is not really anonymous. While Bitcoin addresses aren't necessarily linked to real-world identities, they can be. And it’s possible to learn a lot about who’s using Bitcoin, and for what, by monitoring the unencrypted peer-to-peer network or analysis of the public blockchain, as well as through Know Your Customer (KYC) or Anti-Money Laundering (AML) regulations.
This is not great from a privacy perspective. Bitcoin users might not necessarily want the world to know where they spend their money, what they earn or how much they own, while businesses may not want to leak transaction details to competitors – to name just a few examples.
Additionally, selected bitcoins being traceable, possibly “tainted” and potentially worth less than other bitcoins is at odds with fungibility. These privacy-related issues could even challenge Bitcoin's value proposition as money.
But there are potential solutions to increase privacy and improve fungibility.
One of the oldest tricks in the book is coin mixing. More recently, this trick was dusted off, improved and re-introduced in the form of “coin shuffle” protocols.
Traditional Mixing
The concept of mixing coins is not too complicated.
If two or more people wish to obfuscate the trails of the coins they control, they can simply exchange their coins with one another. Each participant of such an exchange will end up controlling coins with a history that's not theirs, while ridding themselves of any coins that do reflect their own activity.
The most straightforward way to mix coins is for users to simply connect, for instance on an internet forum, and agree to send each other specific amounts of coins. However, this option has obvious downsides. Not only must two or more users wish to exchange coins at more or less the same time (and be able to find each other) ‒ they must also trust each other not to run off with coins after receiving them.
Alternatively, users can mix coins through a dedicated mixer, typically hosted on a central server. This concept is straightforward, too: users send coins to the mixer, and the mixer sends different coins back – usually minus a mixing fee. Several of these mixers already exist, such as bitmixer.io. Some dark net markets use built-in mixers, too.
Unfortunately, centralized mixers suffer from obvious weaknesses. For one, the counterparty risk still exists: Whoever controls the mixer must be trusted to actually send bitcoins back. Meanwhile, the privacy and fungibility problem is not entirely solved either: Whoever controls the mixer knows exactly which coins were exchanged for which coins, and can therefore re-establish the trail.
There’s an alternate solution in CoinJoin. CoinJoin allows users to obfuscate their Bitcoin trails to the outside world by essentially combining several transactions into a single big transaction. This makes it unclear which addresses sent bitcoins to which addresses since all “to” and “from” addresses are lumped together.
But with CoinJoin, trails are not necessarily obfuscated for all participants in the transaction. After all, in order to create a CoinJoin transaction, (some) participants must be able to see which addresses are sending bitcoins to which addresses.
This is the problem CoinShuffle protocols solve.
CoinShuffle
CoinShuffle was a major breakthrough when it was first proposed by researchers from Saarland University in 2014, because it had the potential to decentralize mixing to the extent that no one needed to trust anyone else.
As with typical CoinJoin transactions, CoinShuffle allows different users to submit output addresses to be included into a single transaction in order to obfuscate trails.
The innovation introduced by CoinShuffle is that users can submit an output address, without revealing to anyone else which specific address they submitted. As a result, all participants will know which addresses are receiving bitcoins – but no one will know from which addresses these bitcoins are sent.
This is achieved through a clever protocol.
In short, all participants generate a unique public key (a random string of numbers) with which others can encrypt data, and a corresponding private key with which they themselves can decrypt it. Along a predetermined (and random) order, all participants pass their public keys around, in such a way that one user ends up with all public keys, one user ends up with all-but-one, all the way down to the user who actually got none of them.
The user who got all of the public keys then encrypts his output address with all of the public keys, one for one, in the right sequence. These are layers of encryption that can only be decrypted with all the private keys, one by one, in the right order. This package is handed to the next user, who has all the public keys except for one.
This user decrypts this package with his own private key; he “peels” one layer of the encryption-onion, but still can't tell which output address is “hidden underneath.” Additionally, he encrypts his own output address with all the public keys (but one), and passes both encrypted packages on to the next user.
This next user has no idea which package originally came from which user. But he can peel another encryption layer off of both. And, of course, he can encrypt his own output address with all public keys that he got, and pass three encrypted packages on to the next.
This goes on until the very last user, who gets packages containing all the other output addresses, encrypted. But at this point, all the packages have only one layer of encryption left; and this last user can decrypt all of them at once. He then adds his own output address into the mix, constructs one big CoinJoin transaction, and sends it back to all participants to sign.
At this point, all participants can simply verify that their output addresses are included in the transaction, sign it and broadcast the transaction. (It doesn't really matter who broadcasts, exactly.) No one will ever know who provided which output address.
The much-used Mycelium Bitcoin wallet might soon include an implementation of the CoinShuffle protocol, that Mycelium has named Shufflepuff.
CoinShuffle++
While CoinShuffle works as intended, the protocol requires a significant number of steps to complete, which makes it somewhat impractical for day-to-day use. The same researchers from Saarland University, therefore, more recently proposed an improved solution: CoinShuffle++. CoinShuffle++ essentially does what CoinShuffle does, but faster and better.
Where participants in CoinShuffle generate public and private key pairs, participants in a CoinShuffle++ transaction create “mutual secrets” ‒ also unique strings of numbers. Each participant shares such a string with every other participant, but each shared secret is shared only among two of them; no more, no less.
All participants then “mask” their own output using all the secrets they share. But importantly, these shared secrets are used as both negative values as well as positive values for each pair of participants. (If one participant masks his output with the shared secret 12345, the other participant masks his output with -12345.)
This allows for a nifty trick, as descibed in the Dining cryptographers problem. Once all participants share their masked outputs, they can combine these in such a way that all shared secrets cancel each other out. What's left, at that point, is the grand combination of all outputs – unmasked.
The next challenge is to extract the specific outputs from the combination of all outputs. That's where another mathematical trick comes into play: so-called Newton Identities. The technical details of this trick are unfortunately beyond the scope of this article, as it wanders far into the complexity of advanced mathematics. But it is essentially accomplished using several different redundant encodings of the message, which participants can apply to locally extract all the original output addresses – without knowing who provided which address.
And importantly, this can be done in a single go, to make it much faster and more efficient than the original CoinShuffle protocol. According to the Saarland University researchers, up to 50 participants may complete the CoinShuffle++ protocol in about 15 seconds; potentially even fast enough for typical point-of-sale situations.
Trade-Offs and Weaknesses
Like most other anonymizing solutions, CoinShuffle protocols improve privacy and fungibility. But they are insufficient to provide full anonymity and fungibility in and of themselves – nor are they free from any weakness.
As one drawback of both CoinShuffle protocols, they can be frustrated by dishonest participants. If even just one of the participants wants to block a successful “shuffle” he can insert “fake” (encrypted) data in the process (or not partake in his part of the process at all).
It is, however, possible to trace the participant trying to frustrate the protocol. As such, the protocol can trivially be restarted without this specific participant. This increases the total time for all mixing, but mixing will complete.
Additionally, many of the weaknesses that pertain to typical CoinJoin transactions hold up for shuffle protocols as well. Most important, if the different amounts sent in the collective transaction aren't equal, it might be possible to figure out which inputs and outputs correspond – defeating the purpose entirely.
Likewise, if all of the “participants” are really one and the same entity pretending to be several – a Sybil attack – no amount of mixing will make any difference: that one entity can simply connect the only inputs and outputs that aren't his.
Details on CoinShuffle++ are explained in detail in the CoinShuffle++ white paper.
Thanks to CoinShuffle++ inventors Pedro Moreno-Sanchez and Tim Ruffing, and Mycelium’s Daniel Krawisz for info and feedback.