CoinShuffle++, a fast peer-to-peer coin mixing protocol

[TimRuffing]

Hello,

we are Tim Ruffing (Saarland University - Germany), Pedro Moreno-Sanchez and Aniket Kate (both Purdue University - USA). In April 2014, we presented CoinShuffle, a practical peer-to-peer coin mixing protocol to improve users' anonymity in Bitcoin (website, forum thread).
Continuing our research, we now are ready to present CoinShuffle++, a much more efficient protocol for peer-to-peer coin mixing.

CoinShuffle++ basically offers the same security and privacy properties as CoinShuffle but is significantly faster. Even though the protocol does not rely on external anonymity services such as Tor, users are not required to trust a mixing server for privacy or security. (A server is just used to facilitate communication and broadcasts, e.g., a public IRC server.) As we continue to use CoinJoin, theft of coins is excluded and the protocol is fully compatible to the current Bitcoin system; not even a soft-fork is necessary. For privacy, noone (not even a user in the protocol) learns which of the new addresses belongs to which of the users. Additionally, malicious users that just want to disrupt the protocol can be detected and excluded.

The key innovation of CoinShuffle++ is the use of a more efficient mechanism for anonymity: CoinShuffle++ uses Dining Cryptographers Networks (DC-nets) instead of mix-nets. A mix-net requires sequential processing. Thus, the original CoinShuffle needs a number of communication rounds linear in the number of users, even if everybody is honest. CoinShuffle++ instead uses DC-nets and thus allows users to process mixing in parallel. As a result, CoinShuffle++ requires only a constant number of communication rounds independently of the number of users in this case.

We have prototyped CoinShuffle++ in Python and tested it in the same network configuration as we did for CoinShuffle. As a preliminary result, our (very unoptimized and not-ready-to-show) implementation of CoinShuffle++ requires only about 15 seconds for a CoinJoin with 50 users. In comparison, the original CoinShuffle needs about 3 min in a comparable setting. So our protocol provides a huge improvement in terms of running time. And we think CoinShuffle can be made even faster with a nice implementation, which we plan to work on soon.

For all the technical details, see the preprint of our paper, which actually presents a general mixing primitive that can be used not only for crypto-currencies but also for credit networks such as Ripple. We made a lot of effort to make the protocol "ready for implementation" by providing detailed pseudocode including a lot of details that were not made explicit in the CoinShuffle proposal (e.g., exact code for handling offline participants).

We would be glad to hear your feedback and suggestions on our proposal.  Talk to us if you're interested in contributing to the development!

[btcsql]

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

[waxwing]

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(++).

[gmaxwell]

(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?

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

[waxwing]

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.

[iamnotback]

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.

[somacoin]

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!!

[CohibAA]

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

[spartacusrex]

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!


 

[waxwing]

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.

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.

[spartacusrex]

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.

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.

[Decoded]

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.

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.

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?

[waxwing]

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.

[hhanh00]

In step KE,
sidH = H((sid, sid, P ∪ {my}, NPK[ ], run))

How is NPK[] determined prior to receiving NPK[p] from p?

Thanks,
--h

[TimRuffing]

In step KE,
sidH = H((sid, sid, P ∪ {my}, NPK[ ], run))

How is NPK[] determined prior to receiving NPK[p] from p?

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.)

 

[hhanh00]

1.
sid that gets passed to RUN comes from

Code:

Run(P, my, VK[ ], sk, sid', 0)

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

[pedrorechez]

1.
sid that gets passed to RUN comes from

Code:

Run(P, my, VK[ ], sk, sid', 0)

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'.

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.)

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?

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.

[Evil-Knievel]

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?

[TimRuffing]

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

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.

- 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?

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(++).

[lushly]

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?