It looks like this has no concept of sybil resistance (ie Chainanalysis can just join and spam things and trivially de-anonymize everyone), it just picks a (few?) peers and CJs with them. Instead, you might want to take a look at JoinMarket, which has existed for quite some time and has reasonably good liquidity and sybil resistance in the form of fidelity bonds.
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.
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.
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.
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.
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.
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.
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).
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.
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
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
OK, so after digging a bit the most interesting thing by far here is the use of ring signatures (like those leveraged in Monero) to prevent any mixing round participant from being able to deterministically link other participants inputs to outputs all without a central coordinator.
In the ZeroLink protocol used by Samourai Wallet, this blinding is done as a part of the "Chaumian Coinjoin" aspect of the protocol, but AFAICT there is no similar protections in JoinMarket today as it's more difficult to coordinate this in a decentralized fashion. This is actually significant, as it reduces the vulnerability of takers to both Sybil attackers and malicious makers.
Perhaps I'm missing something, but this could be extremely useful for JoinMarket to implement! This enhances the Sybil resistance of fidelity bonds and also better protects makers against takers that attempt to reveal their outputs.
Monero uses ring signatures to hide the true spend in each transaction, while Bulletproofs are a form of zero-knowledge range proof used to hide transaction amounts while still allowing them to be verifiable.
Both are core to Monero's privacy, but are different.
Right a combination of Adam Back's proposal called "confidential transactions" and "bullet proofs". Thought you guys lumped them together and just called it "v2" or something.
The implementation of confidential transactions in Monero is called "RingCT" because it's implemented as a part of the ring signature construction, so you're definitely on the right path with that thought :)
Note that bulletproofs are a drastically more efficient way of handling the proofs in confidential transactions and are just a part of them.
Great work as always! But if you use nostr as a "bulletin board", wouldn't they make the argument that the relay operators are coordinators? Are there any other ways you could run a "bulletin board" without the semi-centralization of relays?
if you use nostr as a "bulletin board", wouldn't they make the argument that the relay operators are coordinators?
They can make any argument they like but good luck shutting down every nostr relay e.g. in Jamaica, Russia, and Cuba. Also, this argument would imply that every text forum is a money transmitter. Good luck getting a court to agree.
Are there any other ways you could run a "bulletin board" without the semi-centralization of relays?
Yes, you could post the messages in a group chat on Twitter, Telegram, Signal, IRC, Session, Simplex, Tor, or literally any other place where it's possible to (1) send a message and (2) read other people's messages
You could probably even find a government website where you can do that
The only way they can stop this service is by taking down the entire internet
Yes, you can find a "regular" coinjoin coordinator that's running behind tor and hope whoever is running it continues to successfully hide from the government
The Kickout Protocol (not yet implemented in Emessbee)
Kicking trolls out of Round 1
Kicking trolls out of Round 2
Kicking trolls out of Round 3
Conclusion