Let me clarify some things.

It's true that all solutions with a limited anonymity set somehow suffer from sybil attacks. However, if the possible anonymity set is large enough, and the system is indeed used regugarly, then it's quite probably that there will be some honest users in it. If you ask me, both ValueShuffle and TumbleBit provide reasonable anonymity sets; however TumbleBit scales a little better.

Regarding fees:
Yes, fees make sybil attacks harder, because the attacker has to pay them as well. But fees are not specific to TumbleBit. Both ValueShuffle and TumbleBit (and basically all other mixing solutions) require normal transactions fees, because they rely on some kind of Bitcoin transaction. If desired, you can artificially increase the fees to make sybil attacks more expensive (at the cost of higher fees for honest users).

Centralization:
That's right, both TumbleBit and ValueShuffle require some form of central point. (In theory, you can do ValueShuffle without central point. That would then use P2P connections between the nodes, so I would not call it "on-chain". However, then you need techniques that make the protocol quite slow and this is not what you use in practice.) Everybody can set up such a central point and people can chose which one they would like to use. In both TumbleBit and ValueShuffle, users do not need to trust the central point except for the fact that it does not help sybil attacks by excluding honest users. However, honest users could publicly complain about that, and then it's possible to switch to a new central point.

A difference between TumleBit and ValueShuffle is that the central point in TumbleBit is a "tumbler", which is a server specificially designed for running TumbleBit. ValueShuffle just requires some form of broadcast communication, e.g., a modern IRC server supporting timestamps. That may make a difference in legal terms: Maybe you don't want to run a server made for anonymizing money, but running an IRC server should not get you in trouble in reasonable jurisdictions.

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

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

 

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!

Hm, the security argument depends on the fact that the whole encryption scheme is IND-CCA secure, and CBC does not ensure that. I have even a concrete attack idea with CBC in mind but that would require some additional thinking... (and I prefer to think about countermeasures. ). The general problem is similar to the one with the duplicates. Instead of just duplicating a ciphertext, P2 can try to duplicate and change it such that it decrypts to something similar not exactly the same plaintext. Because it is not exactly the same plaintext, the duplicate check does not help here. A later peer then sees that there are two related plaintexts.
IND-CCA provides exactly the property that you cannot change the ciphertext in a meaningful way. If you try to change it, it does not decrypt at all (decryption error) or it decrypts to garbage, which is not related to the original plaintext anymore. 

Note that the signing that you've described does not help either, because the attacker is one of peers and not just in the network. 

The safe choice is to use GCM mode, which is available in BouncyCastle. Probably you just have to replace CBCBlockCipher by GCMBlockCipher but I haven't read the docs.


Okay, my point was the other way: I assume it's not obvious that it is okay to give out the secret key. Indeed, if you look at the description of NaCl, the security model section (http://nacl.cr.yp.to/box.html) and the referenced paper do not claim that the message stays secret in a situation where the senders's secret key is known, even if the recipient's secret key is not.

Still, publishing the sender's key seems to be for that NaCl scheme, and everything else would surprise me, but I haven't looked at it in detail...

Looks good. How exactly do you use AES? It must be something that provides authentication, i.e., either an authenticated mode (such as GCM) or a MAC must be added in the proper way.

Sorry, I forgot to reply to that. I offered that already to lyaffe some time ago. I'm not sure if I have the time to go through it line-by-line but I can certainly have a close look.

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

This is a misunderstanding actually. You don't get any privacy for the change, so we don't say that the change can be shuffled. The paragraph in the paper just clarifies that you can add change addresses to the list of output of the CoinJoin transaction in case some peer does not have the exact shuffle amount (which will be almost always the case, just as for ordinary transactions). As far as I understand, this is what your implementation does?

---

Right, this cannot be prevented. The reason checking for checking for duplicates is indeed different and there's more to it than just checking at the end.

Consider a shuffle of 50 participants with peers P1, ..., P50 (in that order). The attacker controls the two peers P2 and P50. Without the duplicate check, the attacker can break the unlinkability of P1 entirely.

The attack is as follows:
P2 (attacker) receives a single ciphertext from P1 (technically, it's a list of ciphertexts with one entry so far) and removes one layer of encryption, resulting in another ciphertext C1. C1 has still 49 layers of encryption and the inner plaintext is the output address OUT1 of P1.

P2 is now supposed to add his own ciphertext C2 (again 49 layers of encryption, inner plaintext his output address OUT2).
However P2 just duplicates the ciphertext C1, i.e., sets C2 = C1. So P2 sends in fact [C1, C1] to P3.

Then the protocol continues normally but P1's output address OUT1 is now the only one that is there twice. Now assume that the honest participants P3, ..., P49 do not check for duplicates after decryption. The last participant P50 (attacker), who removes the innermost layer of encryption, will obtain a list of 50 output addresses. All of these addresses will be different except for P1's output address OUT1, which is the only address that appears twice in the list! So P50 just knows P1's output address, i.e., unlinkability is totally broken for P1.

To ensure that the attack remains undetected, P50 corrects the list of output addresses before publishing it, i.e., P50 replaces one of the OUT1 entries by an address under the control of the attacker. Note that P2 will not complain that his output address is not there in the final list, because P2 is controlled by attacker, too.

So the attacker can fully deanonymize P1 with only two peers in the right positions. In contrast, if the protocol is implemented correctly, the attacker needs 49 peers to fully deanonymize P1, i.e., everybody expect P1 need to be malicious.

This example where the attacker is in the second and the last position is the worst case for P1 and easy to explain, but the attack works also if the attacker is in other positions and wants to decrease the size of the anonymity set for other peers.

---

I missed that indeed. However, it is still linkable even with new keypairs: assume again that the attacker controls P2 and P50. Then P2 sees which key belongs to P1, and P50 can use that knowledge the determine P1's output address.

You say that this is fixed now by using a common account. How does that work? Did you also change the encryption scheme? The current scheme needs a the secret key even for encrypting. So I don't see how that should work, because you obviously cannot give that secret key to everybody.

I'm one of the authors of the CoinShuffle paper. Really fantastic to see that people are interested in the protocol!

I had a brief look at the code and I think there are several severe problems:

• You use authenticated public-key encryption (from the NaCl library). It has the property that a recipient can be sure who created a given ciphertext. This is exactly the opposite of what we need in CoinShuffle. In fact, the whole point of shuffling is to hide that information from the recipient.
  We need normal IND-CCA encryption, e.g., or DHIES.
  So your implementation does not provide anonymity (or unlinkability as dubbed in the paper).
  
• Each peer must check that there are no duplicate plaintexts after decrypting. Otherwise attacks on unlinkability are possible.
• The whole blame phase is missing, so there is no robustness against DoS attacks as described in the paper. This is actually not a huge problem for a first implementation for a first implementation but should be noted because you implemented currently only a subset of the full CoinShuffle protocol.

(The list is not necessarily complete; these are just the problems that I've seen immediately.)

The problem is that the paper as-is is written for crypto researchers and is quite high-level. I think the protocol is not overly complex but the devil is in the details as with all crypto.

I've just started a collaboration with Kristov Atlas. We will write a BIP draft including a more detailed, development-oriented specification of the protocol including all the nitty-gritty details. We also plan talk to wallet developers and I will definitively write some code as soon as a reasonable version of the BIP is there. Contributions and collaborations are welcome in all stages, of course.

There are also some open questions, e.g., how to find participants for the shuffling, and what to use for communication (on a network level). How is that done in your implementation?

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.

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.

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.

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

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.