Sybil Defense

[nopara73]

@EthanHeilman

I think you need to discuss Sybil attacks as Zerolink is particular vulnerable to it. (a). malicious mixer targets a particular users to deanonymize, (b). Refuses to mix with all other users except fake users with the mixer controls. Selling point of Zerolink is that it is very simple and unlikely to contain bugs, but this entails trade offs such as vulnerability to sybil attacks. If I have this wrong and this attack doesn’t work, you should explain why since I think many people will ask about it.

[nopara73]

It does certainly work, although there can be many ways to defend it. I cannot think of anything not complex, so I leave it as is and added a new section.

E. Sybil Attack

It is possible to deanonymize a user if every participant of the mix is the attacker, except the user. The cost of this attack grows as the liquidity grows. This attack is only feasible if the Tumbler is the attacker. If the attacker is not the Tumbler, it would have to figure out exactly in which rounds the targeted user participates and it must make sure nobody else gets to participate in that mix. However executing a covert Sybil attack as a Tumbler is not evident, it depends on the protocol implementation. Overt Sybil attack as a Tumbler is always possible, however in that case the Tumbler is accountable.

To execute this attack: when Tumbler notices an input is registered that it wants to deanonymize, it must refuse all following input registration and all the input confirmation that has already been registered and is not from the target. Refusing input registration can happen for many raeason, therefore it can be done in a covert way, however refusing input conformination cannot. It can only happen if the input has been spent, therefore malicious Tumbler can be noticed. Clients whose input confirmations are refused and they did not prematurely spent their inputs SHOULD NOT use the Tumbler anymore.
The cost of the Sybil attack at $1 tranasction fees is 1.2 * number of sybils * $1. If the number of sybils is 100 and the denomination is one bitcoin, the Tumbler must first predivide 100btc into 100 one btc outputs, which is about $1*(100*0.2)= $20, wait until the transaction confirms, then it must pay the CoinJoin fees, which is about $100, so the cost of this attack is $120 per round.
This pattern can be noticed by the post-mix wallet. In this case the post mix wallet MAY require re-mixing the coins.

There are various other ways to address Tumbler Sybil attacks in expense of the complexity of pre-mix wallet implementations. Defending Sybil attack should be an interest of future research.

[EthanHeilman]

"Sybil-Resistant Mixing for Bitcoin" has a neat analysis of sybil resistance in a semi-similar setting.

[nopara73]

mix partners based on ads placed in the block chain.

Makes the scheme too expensive today.

We show that Xim’s design increases attacker costs linearly with the total number of participants

As I described the same applies to ZeroLink, the difference is in XIM, because of the ads are placed in the blockchain, in ZeroLink because the inputs must be predivided per participants.

Question: Why Figure 1 is saying CoinShuffle is centralized?

Final note: There might be many hidden gems I missed.

[EthanHeilman]

Question: Why Figure 1 is saying CoinShuffle is centralized?

Some possibilities:

(1). It could be a typo. Later in the paper they refer to Coinshuffle's pairing protocol as decentralized

Decentralized Pairing and Mixing. Only two protocols provide fully distributed pairing and mixing: our protocol Xim, CoinShuffle [24].

For example, Barber et al. [7], CoinShuffle [24], CoinJoin [1], and others have proposed methods for two or more parties to directly mix their coin. These approaches obviate centralized trust and are compatible with existing Bitcoin-like currencies.

To our knowledge, there are no detailed proposals for partner selection to review here: all use a trusted third party, except CoinShuffle, which we describe below.

(2). It could be a reference to the fact that Coinshuffle's bulletin board requires a mostly untrusted communication party to reduce the communication costs fro n^3 to n^2. Whereas XIM uses the most decentralized blockchain for this purpose.

[nopara73]

@EthanHeilman

I finally had the time to take a closer look at Xim.  Chaumian CoinJoin has stronger Sybil attack resistance than Xim, because only the Tumbler can launch Sybil, as explained above.  However the Tumbler Sybil attack resistance in  Chaumian CoinJoin is exactly as good as in Xim.

We show that because of Xim’s participation fees, launching inference or DoS attacks based on Sybil identities are costly. For a given success rate, a Sybil attacker’s costs grow linearly with the number of mix participants, while honest participants’ costs remain small, fixed, and constant. 

Exactly the same applies to Chaumian CoinJoin. In our case the participation fee is the (1) predivision of a big output by  denomination, (2) pay the CoinJoin fees per participants.