On Sat, Dec 21, 2024 at 03:16:09PM +0100, Yuval Kogman wrote: I've been reviewing Wasabi and other coinjoin implementations lately and I believe that your focus on lite clients with regard to Wasabi is incorrect. Let's go through the issues: # Sybil Attacks In General Let's get this out of the way first. As AdamISZ correctly noted in his Jan 7th reply¹ to you, sybil attacks in general are impossible to entirely prevent in any coinjoin protocol where participation is done anonymously. It is always possible for an adversary to simply flood the mechanism with coinjoin requests to the point where they are the only counterparty. What we can do is make sybil attacks costly. In general, Wasabi's current usage with user-settable centralized coordinators does that pretty well: typical coinjoin rounds on the most popular coordinator, https://coinjoin.kruw.io, are transactions close to the standard size limits, with hundreds of inputs and outputs, mixing millions of USD dollars worth of BTC per round. A trivial sybil flood attacker would have to spend a lot of money and hold a lot of coins to simulate that. # Attacks via Failed Rounds Secondly, there's a potential class of attacks via failed rounds; attacks via failed rounds are potentially cheap/free attacks, as no transaction fees are actually spent. A Wabisabi coordinator gets desired inputs and outputs from clients, which would allow them to learn something about which inputs are linked to each other, and which outputs were desired by the owner of those inputs, if the coordinator succesfully "sybil" attacks the client. This class of attack might be interesting if Wasabi reused outputs after rounds failed, in subsequent rounds. I have not verified whether or not this is actually true; AdamISZ did confirm to me that JoinMarket does *not* do this, resulting in large gaps between used outputs in typical operation (it's normal for a high % of rounds to fail). This is an implementation issue due to gap-limits in HD wallet implementations; Silent Payment-like functionality may be a way around this problem. Additionally, this class of attack would impact pay-in-coinjoin functionality, where a payment address is added directly to a coinjoin. # Attacks via "Successful" Rounds If the round actually completes, the transaction fees must actually be paid, and liquidity must be provided. So if the attacker wants to do a cheaper attack than the "dumb" attack that is always possible, they must find a way to get other participants to provide that liquidity and pay those fees. You keep bringing up lite clients, e.g. in your statement that: Unfortunately only full nodes can verify that a coin really is unspent. If a user has configured Wasabi to use a full node this is ideal but probably would not be the norm. -https://github.com/WalletWasabi/WalletWasabi/issues/5533 Your focus is mistaken. In fact, it's irrelevant whether or not a txin in a proposed coinjoin round is spending a coin that exists or not. The reason is there are two possible situations: 1) The coin is either spent, or never existed at all. The round will fail as the transaction is invalid, meaning we're actually dealing with a form of Attack via Failed Round. As described above, these aren't particularly interesting attacks. 2) The coin is unspent, and the round succeeds. Whether or not a reduced-cost sybil was successful depends on round identity consistency. Clients do *not* need to validate coins in coinjoin rounds. Whether or not they're real is irrelevant, as the Bitcoin consensus itself validates this for you. ## Consistency of Round Identity As you mention, here we have a form of MITM attack, leveraged to perform a sybil attack: if Alice and Bob are coinjoining at the same time, from Alice's perspective, if the coordinator can pretend to be Bob, the coordinator can run two simultaneous "rounds" that are actually creating the same transactions. Thus the coordinator is re-using Bob's liquidity and fees to sybil attack Alice. This type of sybil even works with N participants: for each participant the coordinator can create a round with N-1 other fake participants, MITM attacking each simultaneously. Since Wasabi already has coin ownership proofs and distributes them, I believe we can easily validate the round ID consistency of a coinjoin transaction after it's fully signed and confirmed by simply validating that the signatures on the inputs were in fact signed by the pubkeys of the corresponding coin ownership and round ID proof. Wasabi already evaluates the anonymity score of outputs. So performing this check would simply mean that we're validating that the round was not sybilled, and the anonymity score is valid. The only question left for this technique is a cryptography one: Is it possible to create an alternate pubkey p', that such that a valid signature s signed by arbitrary pubkey p for message m, also validates for p' for signature s and message m? I believe the answer is no for schnorr. But I'm not a cryptography expert, and I may have missed something. # References 1) https://groups.google.com/g/bitcoindev/c/CbfbEGozG7c/m/oJTF8wqRDgAJ > ### WabiSabi > > This affects Wasabi Wallet, and Ginger Wallet which is a fork of > Wasabi. Trezor Suite was also affected, but has subsequently removed > support for coinjoins[^18]. They too were made aware of various issues > and chose to ignore them, despite contributing the limited (read: > purely theater for privacy, only addressing hardware wallet specific > theft scenario) ownership proof verification. > > Here the issue is more complex, but ultimately reduces to key > consistency as well. > > In the protocol clients register their Bitcoin UTXOs independently. A > valid input registration request includes a BIP-322 ownership proof, > which commits to the so called *Round ID*. This in turn is a hash > commitment to the parameters of the round, including the server's > anonymous credential issuance parameters (analogous to a public key). > > The parameters are obtained by polling the server for information > about active rounds. If inconsistent round IDs are given to clients, > this effectively partitions them, allowing deanonymization. > > Although clients obtain the ownership proofs of other clients and > seemingly verify them, BIP-322 proofs verification requires knowledge > of the spent outputs `scriptPubKey` which light clients cannot obtain > on their own. This public key is included alongside the ownership > proofs, which makes their verification non-binding, the server can > generate unrelated public keys, and create ownership proofs with those > keys that commit to the per-client round IDs, which the client will > accept as valid. > > This issue was described before the initial release[^7] but never > addressed. Although subsequently ownership proofs were given to > clients[^8], this change only addressed the use of ownership proofs to > identify a wallet's own inputs in a stateless signing device, without > addressing the consistency issues. Because the server provides the > public key against which unknown inputs ownership proofs must be > verified, that places them under adversarial control. > > Related issues and comments I have posted over the years: > > - unimplemented consistency check that does not depend on prevout also > not implemented[^9] > - no commitment to coordinator address in the round parameters[^10], > although this was temporarily fixed the fix was reverted[^11] > - additional missing fields in the round parameter commitments, and > rationale addressing tagging attacks[^12] > - initial description of blind signature based protocol, which > predates my collaboration and design of the anonymous credential based > protocol which also addresses this explicitly[^13] > > Finally, although not in scope I will also note that poor coin > selection (bad randomization and de-randomization), improper > randomization of input registration timing, and tor circuit management > increase the probability of the success of such an attack, by making > it easier to target specific users. Additional concerns exist for > alternative clients due to use of JSON and HTTP in the protocol, in > the C# implementation serialization by a 3rd party JSON library, which > may canonicalize JSON differently (e.g. ordering of properties in JSON > objects), etc. Additionally, although designed with coordination fees > in mind, the anonymous credential mechanism did not enforce that > coordination fees are fair or incentive compatible (nor can it with > non-binding ownership proofs, though the main privacy concern there is > the coordinator lying about the values of other clients' prevouts > leading to poor amount decomposition), resulting in thefts of user > funds[^14][^15], but this has now been removed[^16]. > > Again a version of this with some preliminaries is also on github.[^17] > > [^7]: https://github.com/WalletWasabi/WalletWasabi/issues/5533 > [^8]: https://github.com/WalletWasabi/WalletWasabi/pull/8708 > [^9]: https://github.com/WalletWasabi/WalletWasabi/issues/6394#issuecomment-920225648 > [^10]: https://github.com/WalletWasabi/WalletWasabi/issues/5992 > [^11]: https://github.com/WalletWasabi/WalletWasabi/pull/8708/files#diff-04b849802b4adf5b34756a49b498f2ac97247cbb64424e5a69ee64c28a7033bcR120 > [^12]: https://github.com/WalletWasabi/WalletWasabi/issues/5439 > [^13]: https://gist.github.com/nothingmuch/61968fde675a596758bffd4c278ac096 > [^14]: https://github.com/WalletWasabi/WalletWasabi/discussions/13249 > [^15]: https://bitcointalk.org/index.php?topic=5499439.msg64309927#msg64309927 > [^16]: https://archive.is/xFRHO > [^17]: https://gist.github.com/nothingmuch/4d717e12e451ff4ce43474972e41c6ba > [^18]: https://blog.trezor.io/important-update-transitioning-from-coinjoin-in-trezor-suite-9dfc63d2662f > > -- > You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. > To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAAQdECCdRVV%2B3ZoJhOotKEvmUV4yrV7EYWE8SOWCE1CF9tZ6Yg%40mail.gmail.com. -- https://petertodd.org 'peter'[:-1]@petertodd.org -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Z5JtilN2k7HwRRXt%40petertodd.org.