Topic: CoinShuffle: Practical Decentralized Coin Mixing for Bitcoin (Read 23801 times)

Mimblewimble allows for a very simple coin shuffling protocol [1] with the following properties:

* Users submit self-spends throughout the day. No interaction needed for shuffling.
* Shuffling is performed at the end of the day by a set of mixnodes that cannot steal any coins.
* Invalid self-spends are automatically filtered out. No need to abort or restart the shuffling.
* As long as at least one mixnode is honest, then no one learns the input output links.
* The size of the shuffle is limited only by blocksize and could easily be over a thousand.
* Each shuffle only grows the chainsize by a small constant (~100 byte), thanks to MW cut-through.

Widespread use of the protocol would leave the transaction graph mostly obscured.
We welcome review of the proposal.

[1] https://forum.grin.mw/t/mimblewimble-coinswap-proposal

I wrote a simulation of the P2P shuffling process of CoinShuffle. If someone is looking at this idea who's familiar with .NET, it can help in understanding it: https://github.com/nopara73/CoinShuffleSimulation2

Hi gmaxwell,

you and the joinmarket team helped me a lot to get this far with my joinmarket proxy and I feel bad for "betraying" you by saying negative things about JM maybe blind to CS having the same problems but as far as I understand it, JM does not aim to avoid the taker from learning the matching, which is at best a short cut to achieve some degree of mixing and at worst makes the whole endeavor of mixing pointless, as interested parties will inevitably outbid others just to get a glimpse at the matching. And they can do this under the radar, as knowing some UTXOs will help them to know a lot of the mixing without constantly probing every maker actively.

As far as I understand, in CS there is no obvious way to learn any matching as long as there are fair players at all. It allows you to single out the DOS players and that leaves the disruptors to spying, where they can only decrease the privacy probabilistically, to the point of learning one user's matching if they totally eclipse attack him. But as all would pay their share of the fee and makers can't earn from it, this would force attackers to provide activity that others would take for legit activity and use this great tool, which in turn would make the attacker fail to single out all honest players all the time.

In JM with its asymmetric structure with makers not actually caring about their privacy and having an incentive to share data among them, I also see the incentives aligned against anonymity.

That is remarkably inexplicable to me.  JM is very actively developed by a community of developers. It was created with basically no anti-DOS mechanisms, though the original CJ post (technically the "appendix" post I made right below it) went over several different anti-DOS mechanisms, because it's perfectly reasonable to get something working before making it strong-- especially since JM's main motivation is gumming up automated analysis more than itself providing strong privacy.

But it's quite straight-forward to add in strong anti-DOS and better privacy, on top of a working and vibrant system; doubly so in that the coinshuffle description provides no special structural immunity to those dos attacks: the same anti-dos mechanisms are needed.  You shouldn't let that fact that a single person in the JM space is advocating one anti-dos method that would harm casual usage as at all indicative of ... well, anything.

It's one of it's properties to not need a protocol change. All the blinding and shuffling happens outside of the protocol and then all parties sign the resulting transaction which again is just a regular coinjoin transaction.

The reason they are working on a BIP is probably to standardize the process, not to hard-fork bitcoin.

This loos nice, but if we need to change the core protocol for this, than I'm not really down. We have several altcoins to do exactly this.

Hi TimRuffing and Kristov Atlas,

sorry for having missed this last post somehow in my other comment.

I'd really love to help with such a reference implementation, with a wallet-integration-perspective. At Mycelium we see fungibility as a very urgent issue and having worked on a JoinMarket Proxy myself, I feel like JoinMarket might be a dead end precisely due to what CoinShuffle claims to solve. At least from the Wallet-perspective.

For this, I wonder what harm would be done if the current state of implementation was already public for others to tinker with.

I'm particularly interested in ease of integration with wallets and my focus in Joinmarket there was to not share private keys with the mixing module, which in the link above was a server but for mobile wallets could be an app working like the orbot TOR proxy locally on the device.

I see a couple of issues with this approach:

1. You need other participants in order to use coinshuffle. What happens when no one at the moment wants to coinshuffle X amount of Bitcoins with you? Do you just wait around?

2. Given the huge political hurdle of adding anything at the bitcoin protocol level..I presume this is not going to be at the protocol level?

Bitcoin will never truly be fungible until changes at the protocol level are made for all bitcoins in existence.

Quoting myself:
We'll provide more information, including a mailing list, soon.

Regarding JoinMarket, I'm not sure. It seems that it is not so sophisticated as CoinShuffle, but that's rather a first guess. Is there a technical description of how it works under the hood? I can only find descriptions of how to use it.
Also, JoinMarket seems to understand the problem as a economic one and someone is gets fees for enabling the mixing. CoinShuffle is different here, the participants just pay the single transactions fee for the CoinJoin transaction, which is very low and can even be split among all participants. But there is no party that gets an additional mixing fee (on top of the transaction fee).

Jumblr implements a fully decentralized coinshuffle. The fee is 0.1% for bitcoin, it should work for other coins also, but bitcoin shuffling is the only one that matters.

I am looking for someone to head up the marketing for this. It just went into testing this weekend.

It uses the InstantDEX/SuperNET network for the directory, but the actual coinshuffle is all between the participating nodes.

James

I've followed the JoinMarket project which I recently discovered, but I just came across this.  Is this project still active, and if so, where can I find current information?  How would this compare to JoinMarket transactions?

NXT has implemented CoinShuffle now. It will be available in the next major release (1.6.x)

Darkwallet's webpage still lists coinjoin as their shuffling method. Anyone know the status of Dark Wallet's coinshuffle implementation or any other implementations?
https://www.darkwallet.is/

Dark uses coinjoin. A system like this would eliminate Dark and all the other altcoins using coinjoin.

Fibrecoin developed and released a privacy solution that is based on CoinShuffle
https://bitcointalksearch.org/topic/m.10834848

I thought they were implementing CoinJoin instead. EDIT: true, Amir confirmed that: https://www.reddit.com/r/Bitcoin/comments/2ijsw1/the_coming_of_darkwallet/cl2qow6

On the other hand, I see a problem with CoinShuffle. The participants are supposed to sign their messages "with their addresses"; this assumes that the inputs they provide were paid to standard P2PH addresses, but they cannot use outputs sent to P2SH (those starting with a 3, e.g., "multi sig" addresses). Participants could still be required to reveal their script and then sign their handshaking rounds with a key contained there (if there is any).

Amir says it's being worked on for Dark Wallet.

Is a full working version of coinshuffle being developed? The research site says the current version was just a proof of concept for testing and not usable for real coins.

paper looks pretty solid

Is anyone aware of ongoing blockchain forensics tracking notable coins?
Have pretty much all stolen/hacked/scammed coins been obfuscated via mixing/shuffling?

Kristov Atlas reviewed it, you might want to read it. Or wait a week, since open source is in a week.

Has the DarkCoin mixing algorithm been made open source?

Is this system better than DarkCoin (which is not CoinJoin like many people believe)?

Links to IP addresses would be broken?

It's actually mentioned it the related work section. But I agree, it would be clearer to mention it already at this point. We will clarify this paragraph.

CoinJoin refers only to the idea to use a joint transaction with several inputs and outputs to do mixing. There are several ways to create such a transaction. CoinShuffle is one way, using a server and blind signatures is another.

The essential difference is the following:
Creating a CoinJoin with a server and blind signatures provides unlinkability (against the server) only if the participants connect to the server already in an anonymous way, e.g., by using Tor. On contrary, CoinShuffle uses more communication between the participants to provide unlikability by itself without any other third (trusted or untrusted) party, so without a central server and without relying on an anonymity network.

It's not really about DoS actually. A simple decentralized CoinJoin, i.e., without server but also not like CoinShuffle, would be sufficient to identify participants that want to disrupt the protocol. However, in such a approach, all participants can link input and output addresses, see "Don't the users learn which inputs match up to which outputs?" in the mentioned CoinJoin FAQ.


@ Sergio_Demian_Lerner:
I'm not sure if the required zero-knowledge proofs are efficient enough, but it is an interesting idea to allow everybody to mix addresses.

Your algorithm provides a way to agree on a random permutation such that nobody can influence the result. However, the participants learn the the resulting random permutation. In CoinShuffle, they don't learn the permutation.

If multiple entities - e.g. US NSA, SVR (Russian CBP), Chinese MSS, any private entities etc - are all attempting to de-anonymize mixing they will end up interfering with each other and help anonymity.  So it seems beneficial to encourage more than one group to attempt to de-anonymize mixing and not cooperate with each other.

Private entities/people using large balance addresses to avoid transaction fees could enable multiple groups to take part in each mix at no cost to them while increasing the number of parties in the mix and consequently increasing anonymity for everyone involved.

:-)

Another related question to help me confirm my understanding of the contribution of CoinShuffle:

Is the following algorithm be semantically equivalent to the algorithm presented in your paper?

Communication is done peer-to-peer using public-key, authenticated encryption. 'Broadcast' in this context means a player sends a message to all the players over these links.

Each player i (1 < i < N) does the following:
1 Generate a random permutation P_i of (1, 2, ..., N)
2 Broadcast H(P_i), where H is a collision resistance hash.
3 For all j != i, receive H(P_j) from player j
4 Broadcast P_i
5 For all j != i, receive P_j from player j and confirm the hash value
6 Calculate output list = P_1 (P_2 ( ...P_N (1, 2, ..., N)...)), broadcast, and agree on that value

Player 1 creates the join transaction with the output list, and the transaction is signed by all players. The transaction is broadcasted to the blockchain.

Please help me better understand exactly how CoinShuffle improves upon what already can be achieved with Coinjoin

The whitepaper mentions a weakness of CoinJoin and fails to point out that a more viable solution was proposed. The whitepaper states speaking of CoinJoin:
Then you go on to describe how unviable SMPC is.
While I agree that SMPC may be unviable, you seem to fail to mention another solution from the OP in CoinJoin thread:

in FAQ


Having established the fact that a centralized CoinJoin server will not learn the input/output mappings, is my assessment correct that the only advantage of CoinShuffle over CoinJoin is that
CoinShuffle can be implemented in a fully DEcentralized manner and still identify the DOSing party,
whereas CoinJoin can identify the DOSing party only when implemented with a CEntralized server?

Somebody asked for some other ways for anonymization: you can check my old paper on AppeCoin at
https://bitslog.wordpress.com/2014/04/24/appecoin-anonymous-cryptocurrency-draft/

It uses universal encryption, so everyone can mix every other peoples outputs without asking for permission, and it's impossible for dishonest mixers to prevent honest mixers from mixing with high anonymity set (at least of course if 99.9% of the outputs in the blockchain are controlled by the attacker).

BM, I have been exploring a strategy using N-way mixing, where by 'mixing' I mean the proper sense of creating separate transactions to exchange the coins. Whitepaper/ppt/git forthcoming.

The gist of the idea is:

(1) N players use a randomized Byzantine process to agree on a mixing specification, and then
(2) Execute multiple pairwise transactions atomically on the Bitcoin blockchain, ala TierNolan's atomic cross-chain transfer solution. This is an N-way, same-chain atomic transfer within Bitcoin (ie not cross chain).

Atomic Cross Chain Transfer discussion
https://bitcointalksearch.org/topic/alt-chains-and-atomic-transfers-193281
https://github.com/TierNolan/bips/blob/bip4x/bip-atom.mediawiki

Example:
Alice wants to mix 1 BTC
Bob wants to mix 2 BTC
Charlie wants to mix 3 BTC

In step 1, they decide on the following mix:
Alice --> Charlie 1BTC
Bob --> Charlie 2 BTC
Charlie --> Alice 1 BTC
Charlie --> Bob 2 BTC

In step 2, Alice executes her transfer to Charlie, Bob does his to Charlie, and Charlie does his to Alice and Bob. This is done in a way such that either all transfers succeed or they all fail.

I'm currently working on final steps of extending TierNolan's solution and a prototype.

Yes, this means the players pay for more transactions. One of the advantages is that the temporal locality of the transactions is loosened.

But accomplishing this within a client would be a trustless solution and a time saver, so using a 3rd party exchange wouldn't make sense when you could use an internal exchange/shuffle such as the case with Coinshuffle/Nxt.

right, this is why if you use an exchange that lies outside of eg. US jurisdiction, they are unlikely to comply with any requests to produce such logs.

This is likely the reason why the American/European currency authorities in particular are always vilifying the Chinese exchanges.  The Chinese exchanges are a doorway in and out of Bitcoin that they don't have any control over.

-bm

But then you're trusting the exchange not to keep logs that link your incoming tx to the outgoing one.

The fact is you can get fairly good anonymity simply by putting your coins on an exchange that doesn't require ID, and then transferring it out to an address that you have never used.  If you use Tor for all your interactions with the exchange website, then the coins are mostly untraceable.  Any exchange in the US, Singapore, most of Western Europe does not offer you anonymity.  If you issue the outgoing payment TX using Tor as well, the payment is mostly untraceable.  It's possible to automate all this in the wallet.

I don't know of any ideas that are not in this class of input/ouput mixing although it may be possible to implement something using cryptographic blinding.

-bm

I think that's the most popular as no one is about to change BTC core to include anonymity at a protocol level.  Do you have any other projects to review?  Input/Output can always be correlated but it would take QC power to do so.

the fact is, that even if you were to have 100% reliable and untraceable mixing of inputs/outputs the transactions are still temporally correlated.  As in: the transfers occur at the same time and thus are statistically related.

-bm

Has anyone explored other anonymity strategies aside from input/output mixing?

-bm

@wladston: thanks.

The obvious attack vector here is I operate many anonymity nodes, do all the mixing pretending as though I were many people(sybil attack).  Then I possess all the identity credentials and can de-anonymize the transactions.  One way to prevent this occurrence is some kind of rating system for the nodes, but this would be difficult to impose.  It seems this system is a step up from CoinJoin though.

-bm

@bluemeanie1, yes, every kind of mixing anonymization strategy will inevitably have this drawback.

a shortcoming of Dissent is that anonymity can be compromised if all the protocol round participants collude.  Does Coinshuffle have this same drawback?

-bm

Unlike you, he can program and is a creative person. He will deliver, unlike other persons we know, that rather take the easy road and just steal 1,000,000 NXT.

Give me back my stolen NXT which i payed for works,you were not going to do at all, first.
Fucking theoretician

How is Come From Beyond going to implement Coinshuffle if NXT doesn't have inputs and outputs?

#Vaporware!

-bm

Not sure about the biggest, but definitely the best looking, which I think is the most important aspect of any dev team.  Anyway, looking forward to coinshuffle on Nxt.

Awesome! Not sure, but I think Nxt seems to have the biggest developer team behind it, they really role out one innovation after another 

If all those innovations prove to be working, which they seem to, maybe Bitcoin can copy some of them.Would be cool!

Funny that a "non-bitcoin"-coin will be the first(probably) to implement this: https://twitter.com/comefrombeyond/status/485429369268350977

#NXT!

Aha, ok.  I suspected something like this had been baked in at a low level.  I was just surprised when I didn't see something like your "enc(ek, m, r)" in Section 5.2, or a note in Section 5.1 explaining that this was included in the definition of "Enc", or even a note about this in the otherwise quite verbose Section 6.1 - Unlinkability.

I think I was thrown off the scent a little by the use of "the ciphertext" from Section 5.1.


Anyway, thanks for the explanation.  I was sure it wasn't a problem; I just wanted to understand.

The communication does not have to be secret. And you already indicate a possible answer to your first question: In the case that a participant, say Charlie, claims not to have received a message from his predecessor, broadcasts are a possibility to find out which of the parties really failed. Without going into details, the PeerReview protocol is one possible fully-fledged solution that we mention in our paper but explaining the whole idea would be too much for this thread. To demonstrate that those problems are solvable, I can sketch a simpler (but probably not so efficient) solution later if you are interested.

Yes, all messages are signed using the private signing key belonging to the input address. I added that to the posting. (Sorry, I simplified too much with respect to that aspect. )

Your example is already quite nice. It shows the most interesting case, namely what happens if something goes wrong during the shuffling. Then the participants publish their private decryption keys and everybody is able to replay every step of the shuffling to find out who misbehaved. (Publishing the decryption keys is not a problem, because the participants have to restart the protocol anyway. Somebody may be able to link, e.g., A and A', but no transaction involving A' is generated. The output address A' is just discarded and in the subsequent run, the users will create fresh output addresses and fresh encryption/decryption keys.)

Things can also go wrong in other phases too. Let me give one example, namely for phase 1: Somebody could send different encryption keys to different users in phase 1, e.g., Dave sends ekD1 to Bob and Charlie, but ekD2 to Alice. (This is called equivocation.) Dave will then learn that A' is Alice's output address: It's the only output address encrypted with ekD2. And if Charlie colludes with Dave, Charlie would not report that he obtained ciphertexts encrypted with different keys during the encryption. To exclude this attack, the full protocol contains an additional equivocation check between phase 2 and 3: Everybody signs the list of all encryption keys and broadcasts the list together with the signature.  Only if everybody has the same view on the encryption keys, the protocol continues normally. (I did not include this step the posting above for simplicity, the goal of the posting was rather to get the core idea across.)
If the participants have different views on the list of keys, this will be detected in this additional step. In the example above: Alice would publish the signed list (ekB, ekC, ekD1) but Bob would publish (ekB, ekC, ekD2). In that case, the blame phase would be entered too. From the point of view of the users, there are two possible cases now: Either Dave has really equivocated, or one of Alice and Bob is claiming to have received a key from Dave that he/she actually has not received. To find out who is malicious, Alice and Bob can just publish the signed messages that have they received from Dave in phase 1. That will clarify if they have published a wrong list of keys or if Dave has equivocated by sending different keys. So one malicious user is exposed at the end of the blame.

---

There seems to be a misconception about encryption in general. Every secure* encryption scheme always uses randomness for the encryption to make sure that encrypting the same message twice does not yield the same ciphertext. This is exactly to exclude attacks like the one described above; such attacks are a general problem in cryptography,  not only in this protocol. The added randomness is built in the encryption algorithm itself, one does not have to add randomness manually to the message before giving it to the algorithm. One typically leaves the randomness implicit: When I write enc(ek, m), I actually mean enc(ek, m, r), where r is fresh randomness.
Try it: Take any encryption tool and try to encrypt the same message twice.

* This holds for every standard cryptographic definition of "secure". In particular, it holds for IND-CCA, the security definition that we require to be achieved by the used encryption scheme.

---

@BitcoinDream:
A trusted third party does not help here! (That's why we would like to avoid it.) Mixing is not possible if you are the only honest user. You need at least one other user that is also honest.
Assume you are Bob. Further assume that Alice, Charlie and Dave are malicious and collude. No matter how you organize the mixing with a trusted third party or not, Alice, Charlie and Dave can observe the output of the mixing (e.g., by looking at the blockchain). Thus they observe four output addresses A', B', C', D'. Because they know that A', C' and D' are their own addresses, they can determine that B' is your address.

Perhaps your idea of a trusted third party in this situation is just a special case of an honest 5th party, called Erik say.

This was my first thought.  I checked out the paper to see if something along these lines had been included but found nothing.  I'd add to this and suggest that all participants add some random data to each level of the layered encryption.  If they add random data just to their address at the beginning, then Bob and Dave, working together, could determine Alice's (and therefore also Charlie's) address.

I assume something in the presented method tackles this, for if everyone is able to rebuild and compare in this way, then there's simply no point to the layered encryption in the first place.  Participants could pass unencrypted addresses with the same result.

Another potential remedy is to undergo multiple rounds, where each participant has a chance to be somewhere in the middle of the chain.  Assuming no more than one dishonest node, I'm fairly sure "maximum mixing" can be achieved in O(log(n)) rounds (where n is the number of participants) but it's not clear to me how devastating colluding members would be in this model.

Clarification would be appreciated.

@BitCoinDream, @TimRuffing is correct, this attack (all other participants colluding) isn't fixable by mixing. If Bob, Charlie and Dave are malicious, no matter how you mix the coins, these bad guys can look at the output transaction and determine Alice's address (it will be the only address in the transaction not owned by them).

I think a trusted third party approach is required to nullify this attack...

@teukon's observation seems relevant. However if Alice includes some random data along with her address, but Dave only publishes a list of addresses (without the extra random data) them Bob couldn't determine Alice's address.

With reference to the overview diagram given above and assuming all participants are honest and all communications secure:

Once the procedure is complete and everyone receives the shuffled addresses from Dave, it appears that Bob can determine Alice's new address by encrypting each of the new addresses first with Dave's key, then with Charlie's, and comparing the results with the data he received from Alice.  What is it that I'm missing?

Interesting.

More info on the blame system would be nice.

How do you handle a case where a participant refuses to send on a message to the next person?

Does each of the communications have to kept secret? 

When you say Bob -> Charlie, do you mean it is a broadcast?  Are the messages digitally signed too?

You should explain the blame stage too.

Assume that Bob cheats, he includes 2 addresses for himself.

Alice to Bob: enc(ekB, enc(ekC, enc(ekD, A')))

Bob to Charlie: enc(ekC, enc(ekD, B')) ; enc(ekC, enc(ekD, X'))

Charlie to Dave:  enc(ekD, B') ; enc(ekD, C') ; enc(ekD, X')

Dave to all: D', B', C', X'

Alice complains that her address is missing.

Each participant publishes their private key.  The process can be stepped backwards, until the "mistake" is detected.

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 exchange
Each 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: Shuffling
Once 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 transaction
Every 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.)


Note: 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 approaches
Mixcoin
The 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 / Anoncoin
Zerocoin (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.

CoinSwap
Most 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.

Yeah, that's what I meant.  You get maximum mixing.

A client could be created that constantly mixes your coins.  Leaking zero info would be hard though. 

Since you cannot know who is honest, you always mix with everybody.

To clarify:
Assume there are 10 participants in the protocol. 3 of them are honest, including you, and 7 are malicious and collude. Assume the protocol has been finished successfully.
If the 7 malicious guys would like to find out which of the 10 output addresses is yours, they always know that your address is not among their 7 addresses, just because they know their own 7 addresses. Thus your address can only be among the 3 remaining addresses.
(This "attack" is always possible in every form of coin mixing, no matter how you organize the mixing.)

However, the protocol ensures that the 7 guys cannot tell which of the 3 honest output addresses is your output address.

So in a nutshell: You shuffle all 10 addresses, but shuffling your address with the 7 malicious addresses does not help you. In the end, you get "anonymity among the 3 honest addresses".

The effect is that your output is mixed with all the honest participants?  If there was 3 honest and 7 colluding, then your output is sent to one of the 3 remaining outputs at random.

Would really like to know the opinion of Gmaxwell and the rest of the dev team regarding this research. To me this looks like something that could be well integrated into Bitcoin Thin clients.

A very nice paper, guys, thanks. Will be in touch to exchange more ideas.

I have a similar paper with another approach that I will share with the community.

Hello,

we (Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate) are group of researches at Saarland University in Germany.
We have written a research paper in which we propose a new coin mixing protocol to improve anonymity in Bitcoin. The protocol is called CoinShuffle.

The key innovation is that it is decentralized and it does not require a mixing server. Among other advantages, this means that no mixing server learns which output addresses and input addresses in a mixing transaction belong together. Since CoinShuffle is based on the idea of CoinJoin, theft of coins is excluded as well. CoinShuffle does not require complex cryptography and performs well in practice, even in scenarios with a large number (about 50) of participants.

A preliminary version of the paper is available.

This is the abstract:


A comparison to other approaches to improve anonymity, e.g., Zerocoin and Mixcoin, can be found in Section 8 in the paper.

We would be happy to hear your feedback and critique about our proposal. All details can be found in the paper.