I took a lot of inspiration from joinmarket, which is the only coinjoin software I've ever used (other than testing my own). But I think I found a better way to banish sybils aka trolls, though I haven't yet implemented it.

The Kickout Protocol (not yet implemented in Emessbee)

Kicking trolls out of Round 1

Suppose in round 1, 100 people register for a coinjoin. If a troll never enters this round, no harm is done. If a troll sends a registration message for this round, there are three ways he can do it incorrectly: not register a valid change output, not register 1 or 2 valid inputs, or register 1 or 2 valid inputs but without proving ownership (you're supposed to sign a recent blockhash with the inputs' private keys). All of those are publicly detectable by every participant, so everyone simply ignores messages that fail any of these steps, and thus every honest participant continues to round 2 with the same set of other honest people. In other words, trollish "Round 1" messages are discarded by all honest parties, so they have no effect, it is as if the trolls never sent a message and thus never entered Round 1.

Kicking trolls out of Round 2

Suppose the trolls did round 1 correctly and are now in round 2. There are three ways a troll can do round 2 incorrectly: not register a valid "equal amount" output, register "too many" equal amount ouputs, or not provide a valid ring signature proving they were in round 1. All honest parties discard messages that lack valid ring signatures, so that part has no effect, it is as if they never sent the message. To detect a troll who uses either of the other two trollish behaviors (i.e. they register 0 or more than 1 "equal amount" output), all parties sum up the number of equal amount outputs and, if it is not equal to the number of people who were in round 1, they know a troll is among them. Therefore, every honest participant should send a new message to the group that unmasks their ring signature, thus revealing which of their inputs map to which of their outputs. If anyone does not do this, or if their now-mapped signature demonstrates that they submitted multiple outputs, the honest participants have identified a troll and the troll's inputs (they are whichever inputs were in a "round 1" message whose "ringsig pubkey" has not been unmasked as "belonging to" one of the outputs), so they kick that troll's inputs out of the group and restart with the remaining honest people. Continue this procedure until you enter round 3 or you are the only coinjoiner left, which just means there were no other honest coinjoiners in your group, so try again in the next round.

Kicking trolls out of Round 3

Suppose the trolls did rounds 1 and 2 correctly and are now in round 3. There are two ways a troll can do round 3 incorrectly: not provide valid "btc sigs" for their inputs or not provide a valid ring signature proving they were in round 1. All honest parties discard messages that lack valid ring signatures, so that part has no effect, it is as if they never sent the message. And if any troll did not send valid btc sigs, kick his inputs out of the group and restart with the remaining honest people. Continue this procedure until round 3 is done or you are the only coinjoiner left, which just means there were no other honest coinjoiners in your group, so try again in the next round.

Conclusion

If any troll goes through rounds 1, 2, and 3 properly, then they were not a troll, they did the coinjoin all the way through, so huzzah! But by the above methods you can kick a "real troll" out of any round (1, 2, or 3) and then redo the coinjoin with the remaining honest participants. This seems better than using fidelity bonds which make it so that many bitcoin holders cannot participate in joinmarket. Please let me know if you see any flaws in this protocol. I hasten to add, I have not implemented this "kickout protocol" yet, so Emessbee is currently flawed in exactly the way you identified: sybils can flood any attempt with fake messages to disrupt it and stop it from happening. But if Emessbee works in the happy path (it does) and if the kickout protocol can "enforce" the happy path, then I think we're in good shape.
415 sats \ 4 replies \ @oomahq 5 May
I think the problem of sybil participants is not that they stall the process, but that they enter the anonset with lots of UTXOs, manage to include several of their UTXOs in each coinjoin, and then trivially trace the other participants who coinjoin with several of their UTXOs.
reply
oh, I didn't realize that
oops
reply
23 sats \ 2 replies \ @oomahq 5 May
On the other hand it's not clear to me how (or even if?) Whirlpool and Wasabi were able to mitigate this threat.
Fidelity bonds arbitrarily raise the cost to be a sybil attacker (e.g. you need to cough up and provably freeze for some time 4X more BTC than you want to coinjoin, for instance).
reply
138 sats \ 1 reply \ @kruw 6 May
Whirlpool was extremely easy to Sybil attack since the attack victims pay the mining fees to move the coins of attackers.
Wasabi's coinjoins require users to pay for their own block space, which aligns incentives to defend against attackers passively spying on rounds for free.
reply
Emessbee also requires users to pay for their own block space. The mining fee is calculated after all change addresses are submitted, then divided up equally among all participants, and deducted from the amount that would otherwise go to users as change
reply
Kicking trolls is avoiding DoS attacks but sybil attacks are different in which attackers will participate in each round to deanonymize others.
reply
oh
oops
reply
Funny how people blindly zap you, even though you didn't address the mentioned issue.
reply
perhaps they appreciate the information about the kickout protocol even though it addresses something else
I talked with some folks about sybil resistance after making that post and it looks like the two main sybil resistance methods are:
  • ensure every coinjoin costs a high fee so that sybils bankrupt themselves by joining it with multiple fake accounts
  • make each coinjoiner prove they deposited 4x the coinjoin amount into a timelocked bitcoin address that they get back after a year, ensuring that sybils don't have enough money to make lots of fake accounts
Of the two models I think the first one is easier to implement (I can just increase the mining fee parameter) but I prefer the second option
reply