Very interesting! What's the ring sig construct you're using here?
Discussion
I'm using this one:
https://github.com/beritani/ring-signatures
He has two types, "regular" ring signatures and "linkable" ring signatures. I'm using the regular (non-linkable) ones
Ah OK, I see.
Forgive me because I haven't reviewed in detail what you're doing but:
I vaguely remember seeing someone propose ring sigs before .. somewhere ..., and in particular, I remember musing about linkability in this context: surely, you do actually need it? You need that each person that owns one utxo (simplest model) gets to choose *one* output. Without linkability they aren't restricted like that right? So imagine alice bob and charlie all publish their ring sig key "with" their utxo, then in the second round alice can just publish 3 (cj_addr, ring_sig) pairs to the BB and since all the ring sig validates nobody is any the wiser?
Linkability will just mean each (ring sig) key only gets one usage.
(Using ed25519 keys or whatever instead of secp is ofc not actually a problem here, but that extra layer could get removed ofc; just mentioning it).
I think coinshuffle and coinshuffle++ had some of the most interesting thinking along these lines (purely p2p coinjoin with privacy of each party from each party, and using a BB only for communication, and very importantly, having blame protocols to eject miscreant peers). It's somewhat related to mixnets and dc-nets iirc but I'd have to look it up. Beautiful protocol in its base form. Tim Ruffing was one of the main authors.
> You need that each person that owns one utxo (simplest model) gets to
choose *one* output. Without linkability they aren't restricted like
that right?
I have an alternative way to stop someone from submitting more than one cj_addr. See my "kickout protocol," specifically the section "Kicking trolls out of Round 2." https://github.com/supertestnet/coinjoin-workshop?tab=readme-ov-file#kicking-trolls-out-of-round-2
Yep, you are describing there a "blame" protocol pretty similar to what happens in coinshuffle. Basically an "open the commitment" thing. The most crucial element is as described both in coinshuffle and in your protocol.: say 10 participants, the blame kicks out the bad behaviour and the remaining 9 continue, etc. I think a linkable ring sig makes a lot of sense though, as it cleans up one form of delay of the process. To note: there is another nuance in ring sig design that's relevant (I discussed it in https://reyify.com/blog/ring-signatures#culpability-exculpability-and-claimability ; it's the idea of "exculpability". Some versions of ring sig have a property that, if you reveal the private key, you still do not reveal whether it was *your* private key that signed; in your description, you would need the type that do not have that (so "culpability"). The LWW LSAG, Back-LSAG and MLSAG types are indeed "culpable" so you're probably OK just with that, but: if you have linkability, I don't *think* you even need culpability.
I'm not sure about blame on round 3 though, would need to think more about it.
I don't think I need to try as hard to place blame in round 3, which is where bitcoin signatures are shared. If anyone does not do that, everyone can detect it, so all of the honest users just remove their inputs from the transaction and their key from the ring, and they restart from step 2.