As suggested by some readers, to illustrate our idea better, let me give a small example with (say) four participants Alice, Bob, Charlie, Dave. The participants have exactly 1
BTC at each of their respective addresses A, B, C, D. Assume the participants already know that they would like to run the protocol with each other and they know the addresses of each other. (Finding other participants can be done via a P2P protocol, for example.)
The participants create fresh addresses A', B', C', D' but do not show them to each other. The goal of CoinJoin-based mixing is to create a mixing transaction with input addresses A, B, C, D and output addresses A', B', C', D' to hide the relation between the coins and their owners. (If it is not clear to you why such transactions are possible, I recommend reading the
thread about CoinJoin). However, if we would stick to that particular order A', B', C', D' of output addresses, everybody would learn that A belongs to A', B belongs to B', and so on. So we need to shuffle the list of output addresses to make sure that the linkage of input and output addresses remains hidden. But just shuffling the output addresses in the created transaction does not suffice: For example, if everybody just announced his output addresses during the protocol in plain, i.e., Alice announces A', everybody would learn that A' belongs to Alice. So we have to make sure that the messages that are sent during the protocol do not break the anonymity. CoinShuffle solves exactly this problem.
A successful run of the protocol looks as follows: (Note that the description is simplified; the full details are in the
paper.)
All messages are signed using the private signing key belonging to the input address of the sender of the message. I'm omitting the signatures in the following description to simplify the presentation.
Phase 1: Key exchangeEach participant (except for Alice) creates an key pair of a public key encryption scheme, consisting of a public encryption key and a private decryption key. We call the public encryption keys ekB, ekC, and ekD. Each participant announces his public encryption key, signed with the signature key corresponding to his/her input address.
Phase 2: ShufflingOnce everybody knows the public encryption key each other, the shuffling can start:
Alice encrypts her output address A' with all the encryption keys, in a layered manner. That is, Alice encrypts A' first for Dave, obtaining enc(ekD, A'). Then this ciphertext is encrypted for Charlie, obtaining enc(ekC, enc(ekD, A')) and so on for Dave. This resulting message is sent to Bob:
Alice -> Bob: enc(ekB, enc(ekC, enc(ekD, A')))
Bob gets the message, decrypts it, obtaining enc(ekC, enc(ekD, A')).
He also creates a nested encryption of his address, obtaining enc(ekC, enc(ekD, B')).
Now Bob has a list two ciphertexts, containing A' and B'. Bob shuffles this list randomly, i.e., either exchanges the two entries or leave them. Say we are in the case that they are exchanged. Bob sends the shuffled list to Charlie:
Bob -> Charlie: enc(ekC, enc(ekD, B')) ; enc(ekC, enc(ekD, A'))
Participant C does the same: He decrypts the two entries in the list, adds his own entry and shuffles the list:
Charlie -> Dave: enc(ekD, B') ; enc(ekD, C') ; enc(ekD, A')
Dave does the same again: He decrypts all entries, obtaining B', C', A'. He adds his own address D' and
shuffles the list. The resulting shuffled list is sent to everybody:
Dave -> everybody: D', B', C', A'
Phase 3: Creating the transactionEvery participant receives the list of output addresses and can verify that his output address is indeed there. If yes, he signs the transaction. If, e.g., Bob sees that his address is not there, he would lose his coin by performing the transaction, so he obviously does not want to sign. (This is the main idea of
CoinJoin.)
In the case that Bob's address is not there, somebody must have cheated during the run of the protocol. Bob complains and the participants enter an additional phase to find out who cheated. CoinShuffle makes sure that this "blame phase" always exposes at least one cheating participant (and none can be accused falsely). This cheating participant can then be excluded from a subsequent run of the protocol: Say Alice cheated. Then Bob, Charlie and Dave can run the protocol again without Alice.
The key point is that in phase 2, only the participant that performed the shuffling knows the relation between the messages in the list that he received and the messages in the list that he sent.
For example, only Charlie knows that he left the message containing B' in the first position, because the encryption ensures that nobody can relate enc(ekC, enc(ekD, B')) and enc(ekD, B'). But even Charlie does not know that this was the message with Bob's address.
In the end, all addresses of honest participants are shuffled as explained in my previous posting.
Nobody knows the permutation. (A detailed argument can be found in the
paper.)
An overview over a successful run of CoinShuffle.
[svg] [png] The protocol works even if participants do not have exactly 1
BTC at their input addresses. It suffices that they have at least 1
BTC. In that case, they create a transaction that sends 1
BTC to each of the shuffled output addresses and the remaining coins to a change addresses that the users announce in the beginning. This can be done as for normal Bitcoin transactions. (This idea is also described in
CoinJoin already.)
By the way, we managed to improve the execution time. Using our
prototype implementation, a protocol run with 50 participants takes roughly 3 minutes now in the setting that we consider in the paper.
A comparison with other approachesMixcoinThe main innovation of Mixcoin is accountability for mixing servers (
mixes): If the mix server steals coins, the user obtains a cryptographic proof of this theft and can hold the mix accountable. This is done in public: Everybody can verify this proof and the mix will hopefully lose its reputation, and nobody will use the mix in the future. The mix can still steal money but it will be caught and probably has to go out of business.
In contrast, the advantage of CoinShuffle is that it prevents stealing of coins in the first place instead of providing accountability only after the theft. Additionally, a centralized mixing server is not at all necessary in CoinShuffle.
Zerocoin / Zerocash / AnoncoinZerocoin (and the upcoming optimized Zerocash) are great because they provide "built-in anonymity" by using quite novel cryptography, e.g. ZK-SNAKRS. However, are their own currencies. Zerocoin and Zerocash are not compatible with Bitcoin, they need their own protocol extensions and chain. For instance, Zerocoin is being implemented in Anoncoin, an altcoin. CoinShuffle works directly on top of Bitcoin, without changing the Bitcoin protocol or forking the chain.
CoinSwapMost important, the participants know which coins belong to which user in CoinSwap, so the anonymity is limited. Furthermore, CoinSwap needs at least 4 transactions and the corresponding fees. CoinShuffle needs only one transaction. However, CoinSwap is essentially a two party protocol, so it requires less interaction and coordination. The
original CoinSwap thread provides a detailed comparison to CoinJoin, which provides the basis for CoinShuffle.
If anyone would be interested in developing (and testing) a working prototype for it, I would be happy to contribute with some of my code.
