CoinShuffle++, an improved peer-to-peer coin mixing protocol

Hey everyone, We're Tim Ruffing from Saarland University in Germany, along with Pedro Moreno-Sanchez and Aniket Kate from Purdue University in the USA. Back in April 2014, we introduced CoinShuffle, a practical way to mix coins in a peer-to-peer manner to boost anonymity for Bitcoin users. Now, we’re excited to share our latest work: CoinShuffle++, a faster and more efficient protocol for coin mixing. So, CoinShuffle++ keeps the same level of security and privacy as the original CoinShuffle but speeds things up a lot. What’s cool is that it doesn’t need to rely on external anonymity tools like Tor, and users don’t have to trust any mixing server for their privacy or security. We just use a server to help with communication, like a public IRC server. Plus, since we still use CoinJoin, it makes sure coins can’t be stolen, and it fits right into the existing Bitcoin system without needing any soft forks. In terms of privacy, nobody, not even participants in the protocol, can figure out which new addresses belong to which users. We’ve also built in ways to spot and kick out any malicious users who might try to cause trouble. The big breakthrough with CoinShuffle++ is how we handle anonymity: we switched to using Dining Cryptographers Networks (DC-nets) instead of mix-nets. Mix-nets have to process things one after the other, which slows stuff down. The original CoinShuffle had to go through several rounds of communication based on the number of users, even when everyone plays fair. But with CoinShuffle++, users can mix coins at the same time thanks to DC-nets, making the whole process way quicker.

Very nice. PHP / Javascript developer here. How can I help contribute?

Looks really interesting, thanks. Re: "Moreover, although CoinShuffle++ does not prevent malicious peers from disrupting the protocol, it provides a mechanism to identify the misbehaving peer so that it can be excluded and termination is ensured" (this is the blame part of the protocol, right, iirc) .. my concern with this is that such identification is not helpful if participants coordinate to make join transactions anonymously. Would you agree? There are some ideas to impose costs in advance (ideally without additional bitcoin transactions) so as to ameliorate this sybil attack vector (in the case where there is no persistent identity), but they seem to be orthogonal to coinshuffle(++).

Blacklist the txout, no? That is a basic level of protection.

I see now that I hadn't understood the idea; the protocol is going to complete for all the honest participants, right. In a likely scenario of 1 miscreant out of 3<N<10 say, that may be good enough. gmaxwell: yeah i was vaguely alluding to the various schemes we discussed before. But anyway I had misunderstood what this is achieving, at least somewhat.

jl777 was working on something similar many months ago. My critique at that time I think remains. Although I haven't read your paper, I note "and 4 + 2f rounds in the worst case of f malicious peers.". Afair, my critique of DC-nets for a CoinJoin were: 1. It can be effectively jammed by many malicious Sybil peers. 2. It can't scale, because it has a simultaneity requirement that all the peers to the join successfully communicate in unison. The only way I have found to resolve this conceptually fundamental weakness of CoinJoin, is to introduce some trusted nodes (a la Dash masternodes which were btw a forum documented result of my input) yet probabilistically remove the reliance on that trust.

These are some important points!!

Following.  Thank you for working on this important topic (privacy).

Just thinking out loud here.. but.. can we do this ... The problem is that a malicious node can hold up the entire procedure. So if there are 5 of you trying to do a coinjoin/coinshuffle, you set of, and one of you plays 'silly bugger' and boom, you can't complete. Why not try and complete EVERY combination of the five users, so you would actually be doing more like 20 different coinjoins, say all the combinations of minimum 3 from 5, and then just pick the one with the most valid users at the end ? You would be sending multiple messages at a time to each other, so I don't think it would require the same amount of steps as just doing 20 coinjoins in a row. But definitely more.. And since you would not sign a txn that didn't have your inputs/outputs, you wouldn't risk losing your coins. Whichever was the eventual successful txn. (In this case the 4 valid minus the malicious node.) Let's call it - CoinBomb!

That's exactly what the protocol is designed to handle. With 5 total and 1 not acting "honestly" (just means, not following the protocol), the remaining 4 will complete successfully with a few extra rounds of communication.

.. excellent.

Really nice. May I ask, I've heard and looked at coinshuffle before, but not in depth. Is it now defunct, or something? Is that why you're making this?

Check the usernames, I'm not the author Actually I only spent a couple of hours looking at it, want to come back to it later. The author of this thread is (one of the) author(s) of both the original and the ++ The paper discusses the differences a bit.

In step KE, sidH = H((sid, sid, P ∪ {my}, NPK[ ], run)) How is NPK[] determined prior to receiving NPK[p] from p? Thanks, --h

Good catch! You're right, this is a small mistake. NPK[] is not determined yet. This should be VK[], not NPK[]... We try to include the whole view of the peers in the hash to make sure they cannot continue if something is weird. (Even though some inputs of the hash function may not be necessary it cannot be wrong to include them in the hash.)

1. sid that gets passed to RUN comes from where sid' is (sid, P, VK[ ]). Why do you need to have sid' if you are building a hash H((sid, sid, P ∪ {my}, VK[ ], run)). At this point sid is sid'. 2. I don't understand the commitment phase. "it is even for a rushing malicious peer a infeasible to have committed to an ill-formed vector that leaves mp intact". The DC-VECTOR exchanged between peers contain a DC-PAD component that cancels out when everything is summed up. Could you explain how would a malicious peer benefit from omitting it? Thanks, --h

As Tim pointed out in a previous comment, we try to include the complete view of the peers in the hash. In this manner, we ensure that  they do not continue if something is not as expected. (Even though some inputs of the hash function may not be necessary it cannot be wrong to include them in the hash.) The general idea of having commitments is to ensure termination. In order to understand what can we wrong if there is no commitment phase, you can imagine the following simple case: the malicious peer could wait for the DC-VECTOR from all other peers before he publishes his own (i.e., rushing malicious peer). At that point, he can locally sum them up and recover the m_p message from every other peer p.  Thus, now the malicious user have enough information to create an ill-formed DC-VECTOR that changes m_p for for a peer p but not for the rest. In this scenario, the tricked honest peer p won't sign the final output because her message m_p is not there (and she might be excluded), however she  correctly followed the protocol. The use of commitments thus is necessary to ensure termination for the honest peers: Intuitively, since the malicious peer has to commit to his DC-VECTOR before seeing the DC-VECTOR of the other peers, he cannot create a DC-VECTOR that changes m_p for a peer p but not for the rest.

I have just read this here: https://crypsys.mmci.uni-saarland.de/projects/FastDC/paper.pdf Forgive me, if I missed those points. It's too late and I have not spent much time reading. But I am curious how you would mitigate the two most obvious attacks here. - Let BTC() be the function returning the sum of BTC in a set of in- or outputs. Then find all subsets A of all inputs, and subsets B of all outputs so that BTC(A) = BTC(B). In most cases there should be a unique solution. This attack could be performed even when mixing occurs via multiple steps. Timing correlations would narrow down a set of transactions to be searched: from what I understood you want to keep that thing fast so the number of possible TXs is expected to be sufficiently small for a feasible brute force attack. - You are "broadcasting" signed spending outputs. Who prevents an attacker who participates in this system with zero knowledge to correlate which spending outputs are broadcast bundled together (or even from the same IP)? Surely, once the transaction is finally published this attack won't work. But for the inside man ... ? Does than mean you have to trust your anonymity set?

Your observation is valid. We require that each of the users contributes the same amount of money to a particular mixing to avoid this attack. This is of course not optimal for a number of reason (e.g., if the mixing amount is 0.1 BTC but you have 0.12 BTC, you cannot mix the  remaining 0.02 BTC in this run) but this is required for security. It's a standard problem in all mixing approaches compatible with Bitcoin, no matter whether you use a central party, a CoinJoin tx or similar. I'm not sure if I understand the proposed attack correctly.  Which step of the protocol do you refer to? The point is that the protocol guarantees anonymity even on the network level, i.e., against a network attacker. The attacker can observe that a broadcast originates from a certain IP but that information does not help to break anonymity. Actually, ensuring this is the whole point of the CoinShuffle(++).

I recently found out about CoinShuffle++, and it seems really interesting. However the only implementation I could find that is still active is the one by Decred. It makes a few modifications to the protocol. Namely they use DiceMix Light with a centralized server and ephemeral peer session keys (as stated on GitHub). Their docs state that it's okay, since "CSPP ensures anonymity even while trying to join a session hosted by a malicious server." Could you please clarify if that statement is still true given their modifications? I don't see how it could be. If my understanding of the paper is correct, a malicious server could perform an active MITM attack on the key exchange between the peers and later learn the contents of all the messages they exchange. However to do so the server would have to impersonate each of the peers using a fake signing key. Since that key no longer corresponds to an actual UTXO on the blockchain, the peer that is being impersonated would be unable to produce a valid transaction signature using the signing key which the other peers expect. This leads to confirmation failing, so no anonymity is lost. But if one used ephemeral keys, this is no longer a limitation. Am I missing something, or is there nothing stopping the server from performing this attack undetected?