This subject of this is about the possibility of active tagging deanonymization attacks by a malicious coordinator, so I will address the claims pertaining to that first, and the rest of the claims in order of relevance.

There's also an important correction, due to Sjors: I overlooked a relevant detail of BIP 341 and misremembered the related behavior when I did consider it. The implication is that transactions that spend at least one P2TR input partially mitigates the simplest form of this attack, but as detailed below it's not a sufficient mitigation.

A brief summary:

Your proposed mitigation for the tagging attack is inadequate and is redundant when P2TR inputs are spent.
Your unsubstantiated minimization of issues relating to input-input link disclosure, in failed rounds and otherwise, can be dismissed by 3 separate lines of argument. such leaks are very relevant for this attack.
Your account of sybil resistance ignores important nuances, but at any rate that isn't really relevant to the subject.
You neglect to disclose a relevant conflict of interest which is relevant context re (2).

On Thu, 23 Jan 2025 at 17:25, Peter Todd [email protected] wrote:

Tagging Attack by Active Adversary

As you mention, here we have a form of MITM attack, leveraged to perform a sybil attack

While it's nice to see that you're acknowledging that the attack is indeed possible, i.e. that the protocol is not trustless, your account of how it works is somewhat misleading. The idiosyncratic use of "sybil" is pretty common, but you go a bit further than just using it as a convenient shorthand in your framing, confusing different attack scenarios. This is a distraction. While sybil attacks are relevant to deanonymization, that's qualitatively different and using "sybil" attacks to refer to deanonymization attacks more generally obscures the concern raised here.

So to be clear, this is not a sybil attack, where by definition the attacker controls many apparent users. This attack is by a malicious coordinator, and does not require it to control any of the coins used as inputs. n-1 deanonymization attacks can be executed by means of sybil attack, so often sybil attacks refer to n-1 deanonymization attacks in this context, but sybils are not at all the mechanism involved in this attack on anonymity.

Attack Overview and Adversary Capabilities

Here's a more detailed and accurate description of how the attack is performed, which at Sjors' request includes more details and preliminaries about the transport layer. Note that not all steps need to be executed for this to be an attack, see the details below for the choices available.

n honest (i.e. not sybil) clients query round information from a malicious coordinator. The coordinator responds to each request with a unique round ID.
Each client then registers its inputs using isolated tor circuits, but with respect to the maliciously chosen round ID, which links all of these requests to the initial status request.
The coordinator terminates the connection confirmation phase for each round, and misleads clients into thinking the n-1 other clients are also participating in the same round.
Clients register their desired outputs, and again clients are partitioned with each output registration uniquely identifying which client it belongs to using the per client round ID.
The coordinator terminates the output registration phase, providing clients with the unsigned transaction, and they submit their signatures.

Tor Circuits & Connections

As background, it's important to distinguish between circuits and connections made over these circuits. Circuits are multi hop, onion routed end to end encrypted channels utilizing the tor relay protocol, between a client node and a tor relay. The client directly communicates (TCP + TLS) with its guard node (1st hop), which is directly connected to the 2nd relay to which the client's onion encrypted messages are forwarded, and the 2nd relay is similarly connected to the 3rd relay, which is used as an exit node. There are/were 1500-2000 exit nodes in operation since Wasabi 2 was released (https://metrics.torproject.org/relayflags.html). Hidden service connections are no longer relevant for Wasabi (or its derivatives, e.g. gingerwallet and to a lesser extent the btcpay plugin) so will not be discussed here, but they were relevant at the time of launch.

Once a circuit is established to an exit node, the client can ask it to make connections - which are full duplex streams analogous to TCP connections - to the coordinator over clearnet. These connections (called "streams" in the relay protocol documentation https://spec.torproject.org/tor-spec/) are multiplexed over a circuit, and circuits are multiplexed over the underlying TCP connections to and between relays, but over clearnet map 1:1 to TCP connections made by the exit node on behalf of the client. TLS is employed, so the exit node can't MITM traffic, but cloudflare with SSL termination was used for the zksnacks coordinator and is still used for kruw's coordinator, so thinking of "the coordinator" as adversarial includes cloudflare, they effectively MITM all connections, and see all unencrypted traffic.

Wasabi uses SOCKS to connect to the local Tor daemon. Tor daemon treats any SOCKS authentication credentials (which are always accepted) as isolation IDs: connections associated with differing IDs may never share a circuit. The same ID may end up being mapped to multiple circuits as necessary, as circuits are a dynamic resource. Wasabi then uses HTTP to make requests over these connections. Previously a bespoke HTTP 1.1 client was used, with keep-alive explicitly requested, but now the standard dot net HTTP client is used, with HTTP 1.1 still being preferred, and IIUC keep alive is also used by default with this implementation. https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WebClients/Wasabi/WasabiHttpClientFactory.cs#L130

Initiating multiple SOCKS connections with distinct isolation IDs in quick succession will not result in Tor building circuits concurrently, but sequentially. Any failures in allocating circuits or opening connections can appear as increased latency from the point of view of the SOCKS interface, or as a dropped connection depending on whether the failure occurs before or after stream data was sent to the intended endpoint. The time to first byte can be on the order of tens of seconds even on success during bursty activity.

Wasabi uses distinct isolation IDs for input registration, reissuance and output registration requests, and a long lived one for status polling. Wasabi also randomizes the timing of requests, but inadequately.

Step 1

The GetStatus API is repeatedly polled to obtain data about in progress rounds, including MultipartyTransactionState, essentially an event log. This includes registered inputs, the ownership proofs and previous transaction outputs, and outputs. When I refer to the "transcript" I mean this ordered log of events, including hashes of all credential requests associated with the events.

These requests use the same isolation ID throughout https://github.com/WalletWasabi/WalletWasabi/blob/b49e69d48e6f599235cc3c518c2cf8e3e9206571/WalletWasabi/WabiSabi/Client/WabiSabiHttpApiClient.cs#L16

For each round the client knows about it asks the server to only respond with whose index is greater than a given checkpoint. When input registration events are observed by the client, it verifies the ownership against the scriptPubKey also included in the event data, and ensures that the ownership proof commitment data includes the expected round id.

The index (which is under the coordinator's control given it chooses how many events to return in reply to each request), and the connection & request patterns all makes it relatively straightforward for the coordinator to maintain different views for different clients. Furthermore, the client respects the precedence order of rounds, so divulging other clients' round IDs as necessary is not an issue for a coordinator attempting to cause a client to register inputs for a specific round ID.

An initial request from a client that has no checkpoints and comes from an isolated tor circuit at a random time can be anonymous, as it does not reveal any linking information to the client (apart from the potential HTTP related client version fingerprints which I will ignore henceforth).

Step 2

During this step the full mapping of input-input links is revealed, because all input registration requests from a particular client will be sent with respect to the round ID that uniquely identifies that client. As of today, the client software does not mitigate or even detect this at any step. This is a serious concern, see the section on input-input linking below for discussion of why. In this section I will focus on the how.

Since round initiation time is not known, clients repeatedly confirm their input registration, until a final confirmation request that issues credentials.

A malicious coordinator can affect coin selection criteria (constraints and suggestions). In particular, by flooding more than one round per client and offering relatively disjoint valid selections a coordinator can ellicit information about the preferences of the client, on top of common ownership clusters, can aid it in optimizing for higher rates of wallet clustering by repeated disclosure attacks (e.g. by aborting rounds). The coin selection code has no memory of the adversarial inputs or its own selections. Deliberate de-randomization with ad-hoc rules makes this algorithm more susceptible to harmful choices, for example the bias towards larger valued coins interacts with the maximum allowed and suggested values.

Unlike the common input ownership heuristic applied as applied to confirmed transactions this can be iterated by the attacker. The iterative nature and cluster revelation bears some resembles the privacy leaks in BIP 37 filters discovered by Jonas Nick (https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/155286/eth-48205-01.pdf), as well as this more recent work which investigates clustering using unconfirmed transactions (https://arxiv.org/pdf/2303.01012). Qualitatively it seems to me that this is more harmful, given the nature of the coins that are meant to be selected into privacy enhancing transactions. The client's leniency makes focusing on input clustering only a costless and practically covert attack, even though technically it's an active one, so the client need not trust the coordinator not to do it.

Step 3

Only at this step are the input registration events published by the server, but note that this apparent phase change can be different for each adversarially constructed round. Although the initial input set is finalized at once, this is represented as many discrete events in the log, which if clients are sharing the same round ID (see step 5 for why), which affords the coordinator a tagging vector (manipulating the checkpoint index). In addition to there being sufficiently many indexes to identify each input uniquely, the order of these events is not constrained, since nowhere is the transcript (see above) actually committed to.

After this no additional inputs are allowed (incidentally this is a perverse incentive to de-randomize input registration timing). From an adversarial point of view this mean given a set of inputs whose real ownership proofs commit to distinct round IDs, it can choose for each input cluster what subset of other forged inputs it can see, and which input (clusters) to reject, for example by aborting with "not enough participants" or "load balancing" conditions, which are considered normal (but are at least logged).

For an adversarially chosen input set, which can contain entirely made up coins with arbitrary values, real ones controlled by the adversary if the coordinator is also doing a sybil attack, chosen in order to influence output registration decisions, there is no restriction on the same set of outpoints to be used unless the coordinator wishes to also obtain output registrations or signatures.

Step 4

Here the client reveals its intended output registrations, linking them to the already linked inputs (i.e. the full sub-transaction of that client). Inputs signal their readiness to sign. When all inputs have signalled, the output registration phase terminates. Here too there is room for partitioning clients in a more covert variation, since all individual clients know is how many of their inputs have signalled readiness to sign. This information is not included in the MultipartyTransactionState event log, but should be part of the transcript.

Step 5

At this stage the client calculates the final transaction by sorting the inputs and outputs from the event log, first by amount then outpoint or scriptPubKey.

The coordinator can freely ignore/censor certain signatures (valid or invalid ones), and trigger a blame round. In blame rounds the allowed outpoints must be a subset of the previous round's outpoints. By equivocating the BlameOf field of the round parameters in conjunction with the other tagging vectors (i.e. not unique round IDs), clients can be misled into believing the same blame round ID is associated with more than one previous round ID, because his field is not hashed when deriving round IDs: https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WabiSabi/Crypto/RoundHasher.cs#L13-L32

P2WPKH inputs sign according to BIP 143, where each signature commits to the list of outpoints. P2TR outputs sign according to BIP 341, which also commits to the scriptPubKeys and amounts, which are taken the event log. This means that taproot inputs will not produce valid signatures if they observe equivocated ownership proofs. Thanks to Sjors for this correction, I misremembered this as only committing to the values of the coins. No such restriction exists for P2WPKH outputs. This restricts a malicious coordinator ability to tag using equivocated round IDs when P2TR inputs are spent, but this does not preclude tagging those outputs by other means (i.e. checkpoint leak, differential timing as discussed in more detail here WalletWasabi/WabiSabi#83 and exploiting soft aborts to allow unbounded iteration of these attacks) nor the interaction with the BlameOf field in the round ID derivation, see below for details.

In other words even though taproot signing prevents equivocated ownership proofs from being used to successfully tag a fully signed transaction if it contains at least one P2TR input, it's possible to use tagging to reveal the input clusters, and then restrict subsequent blame rounds to only the already tagged inputs, and only permit transactions which the adversary is confident sufficiently link the outputs to the input clusters to succeed.

Issues with Peter's Mitigation

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.

This mitigation, which is redundant with BIP 341 signing, is strictly inferior to the 4 possible mitigations already mentioned in this thread, none of which were implemented:

redundant queries of round information over isolated tor circuits
best effort validation of ownership proofs under SPV assumptions
deterministic shuffling of transaction data seeded by transcript hash
have the coordinator publicly sign the transcript before signatures are submitted

Unlike (1) and (2) this check is not done before proceeding with the protocol, and unlike (3) and (4) it is not done before aggregating signatures, and so does not prevent going through with a maliciously constructed transaction. The victim pays for the attack (mining fees and optionally contributing to coordinator revenue), and only discovers it occurred after the fact. See below for some additional consequences of this flaw.

Unlike (3) and (4), which can confirm the full transcript, this only checks consistency of the round ID. That makes sense for (1) and (2), but not for a check done after the fact.

Unlike (4), a public signature is non-repudiable making it possible to prove that a malicious coordinator equivocated. With the aid of a 3rd party, something analogous to (1) can be used to prove equivocation, assuming the 3rd party is trusted by the verifier of that claim (something like TLS notary). a variant of this was considered during the design, but without taking into account waxwing/AdamISZ's insight about the non-repudiation property.

Finally, as mentioned above for P2TR outputs this mitigation is already redundant with the hashing specified in BIP 341. That has an effect similar (3) but unfortunately does not commit to the full transcript but only the set of ownership proofs. Like mitigation (3) this happens too late in the protocol, and without additionally implementing mitigations (1) and/or (2), is insufficient.

(1) and (2) are not protocol breaking changes. I previously erroneously described a weak form of (3) as possible, because I misremembered this as only performing a stable sort by amount, but that is not the case as they are explicitly sorted by outpoint / script, so unfortunately that makes mitigation (3) a protocol breaking change.

The only question left for this technique is a cryptography one:

No. The question, and far from the only one, is why were none of the stronger and fully described (before mainnet release) mitigations implemented at launch or at any subsequent point, despite repeated claims of the protocol being trustless?

https://web.archive.org/web/20240521010051/https://blog.wasabiwallet.io/wasabi2-0-released/#:~:text=that%20implements%20trustless%20WabiSabi%20coinjoin%20over%20the%20Tor%20anonymity%20network.
https://archive.is/dtPd9
https://archive.is/Vi46a
https://archive.is/vexOP
https://archive.is/l5Qko (two lies in one tweet, cloudflare was a trusted 3rd party and still is with kruw's coordinator)
https://bitcointalk.org/index.php?topic=5482818.msg64055886#msg64055886

Why were the concessions with regards to section 7.2.2 of the paper not justified? Why did two of the named authors not not disown or retract the paper if they don't stand by its contents? Especially as they were representatives of a for profit coordinator?

https://eprint.iacr.org/2021/206.pdf

At least I agree with the framing of this as an essentially solved problem, just with respect to the proper mitigations, which just makes their omission from the implementation even more baffling.

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?

Malleability of the signature or public key under weak fiat shamir (i.e. ECDSA) is irrelevant, as waxwing points out in his reply the commitment data is strongly bound by the challenge hash. The public keys bind that commitment to an unforgeably costly resource (UTXOs), and for all relevant output types this key is still strongly bound by the scriptPubKey (P2{W,}PKH) and so also made available in the ownership proof data (since BIP 322 proofs have the same format as transaction signatures) and the final signature data.

Waiting for confirmation merely proves that either this was consensus valid, or that the attacker was willing to expend PoW on it although that too is irrelevant since Wasabi doesn't actually validate difficulty / chain work unless it is configured to check against a trusted node, in which case mitigation (2) would provide complete certainty.

Input-Input Linking, Consequences for On Chain Privacy

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.

This is only true if one ignores all aspects of the protocol apart from liveness, which the coordinator is trusted with anyway (which is OK, unlike trusting it with respect to privacy, "semi honest" threat model) and security against theft which excluding the concern for stateless signers (which if the ownership proofs are faked, a stateless signer would not recognize as its own) is at least verified by clients. See below on the topic of light clients.

However, this does not follow with regards to privacy. You write:

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.

Intersection attacks, first introduced in the context of mixnets, have been considered in the context of coinjoins since at least 2014 (https://people.cs.umass.edu/~gbiss/mixing.pdf) and applied to coinjoins and wallet clustering since 2017 (https://petsymposium.org/popets/2018/popets-2018-0038.pdf). This work is not explicitly cited in the wabisabi paper as the on-chain aspects were considered out of scope in the paper, which is only concerned with the KVAC DoS control mechanism and its privacy consequences. That you don't find it interesting without any further justification is, most charitably, a reflection of the depth of your research into this subject.

Concerns about intersection attacks, especially as described in the cookie meets the blockchain paper (i.e. use of out of band leaks that can't be accounted for in anonymity set estimates based only on on-chain data) are justified if the coordinator is only considered semi-honest (trusted with liveness, not with privacy).

As a concept, intersection attacks are also taken for granted in the code when estimating anonymity set sizes: https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/Blockchain/Analysis/BlockchainAnalyzer.cs#L161-L183

Of course, as the cookie meets the blockchain paper discusses, intersection attacks are part of a broader family of clustering attacks. Note especially the caveats in the paper about limitations of the result when clusters are disjoint, making the input-input links particularly relevant for an attacker attempting to cluster coinjoin outputs. Intersection attacks both rely on and are amplified by other wallet clustering techniques. The Wang et al paper linked above, which discusses clustering based on unconfirmed transactions, includes a useful and fairly up to date survey of these techniques. Other recent notable work is the cited Kappos et al (https://www.usenix.org/system/files/sec22-kappos.pdf) and Moser & Narayanan's recent work (https://arxiv.org/pdf/2107.05749) both of which improve clustering by utilizing wallet fingerprinting. Fingerprinting is another subject that has seen recent progress recently (https://ishaana.com/blog/wallet_fingerprinting/).

Given the adversarial control over aborts, the more minor tagging vectors, the lack of binding of the BlameOf field and the gamable coin selection a strategic malicious coordinator can manipulate clients into only completing successful rounds when it is able to successfully cluster the outputs even if reliant on the round ID equivocation mechanism, as must be the case for taproot inputs.

So to put it bluntly, because there is no other way to put it, your theory of "anonymity set size" as calculated by wasabi is simplistic, and ignores the vast literature on privacy such as work on mixnets, and the entropic anonymity set perspective (the way deanonymization attacks generally compound typically resulting in an exponential decay of privacy). This all has been well understood for more than 2 decades, and applies doubly so in Bitcoin's case due to the transparent and highly replicated nature of the transaction graph, as demonstrated by the small selection of papers I've shared here.

Secondly, there's the matter of what was specified. Leaking information about input-input links is discussed in the wabisabi paper, mainly discussed in section 7.2.1 and mentioned several times throughout. Just two quotes for your consideration:

In order to maintain privacy clients must isolate registration requests using unique network identities. A single network identity must not expose more than one input or output, or more than one set of requested or presented credentials. ... Since every registration request is only associated with a single input or output, the only information that would need to be broadcast publicly on the blockchain if the protocol succeeds is revealed directly.

If this is justifiably not "interesting", then again, why are two named co-authors of the paper evidently unable to justify lack of consideration for this subject when it was time to implement the protocol they are supposed to understand? Throughout all of the references I provided, including the paper, there is not one substantiated counter argument to anything of what I said: no serious errors, no arguments against the assumptions, no refutation or even discussion of the prior work which I had studied to substantiate my claims.

That this was included in the threat model is again supported by the code, which as we know uses a distinct isolation ID for each input registration request. This is a rather expensive (in terms of latency, failure rates, etc) implementation choice, and one which is seemingly important (though not enough to merit an investigation how tor circuits actually work, as can be seen here WalletWasabi/WalletWasabi#8420). The fact that isolating circuits is insufficient to prevent leaks is clearly a bug, otherwise a single isolation ID would have been considered.

Thirdly, it has been claimed by support staff and the official account that the coordinator can't learn this information:

So even though you don't find it "interesting", apparently they seemed to think that paying customers of the service do.

In other words there are 3 separate reasons to dismiss your claim that this is not interesting:

published and well cited research on this concern (with supporting evidence in the code that this is in scope for wasabi's threat model)
claims made in the wabisabi paper (again, the code agrees up to implementation flaws)
marketing and support claims made to paying users

And just to reiterate, the adversary isn't just the coordinator operators, but also cloudflare, which as mentioned above, since as a MITM it can surveil and censor any traffic between the coordinator and the client.

Ownership Proofs w.r.t Light Clients

Returning to light clients, not that it's that important but mainly because you misconstrue and/or misrepresent my views and past statements on this.

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. ... You keep bringing up lite clients, e.g. in your statement that: ... 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:

Your framing of my "focus" being "incorrect" is, apart from being unsubstantiated, also disingenuous.

Wasabi is a light client, except when used in the aforementioned hybrid mode where it's configured to query certain information from a trusted full node. The quote you gave is explicitly talking about the difficulty of validating ownership proof before the round commences, to avoid disclosing any actions to a malicious coordinator. It was made under the assumption that at least wasabi clients configured to use a full node would protect against these issues. They don't, with no reasonable explanation given other than that the full node integration is "not real", which for reasons I'm yet to understand allows making some RPC requests but precludes others (which the backend is able to make https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WabiSabi/Backend/Rounds/Arena.Partial.cs#L345C33-L345C46).

When I said what you quoted out of context I was working under the assumption that one of the most basic aspects of trustlessness, namely lack of mitigation against tagging attacks which are the subject of this thread, would be addressed before the release. I don't know why you seem to insist it's my "focus", when it's just a constraint imposed by the project. Perhaps the reason is that you're confused about what the ownership proofs actually were meant to provide assurances against. Let's recap.

Note the opening paragraph of the issue you quote from, emphasis added here:

Clients need to verify ownership proofs to ensure uniform credential issuer parameters for all round participants (otherwise they might be subject to tagging attacks), and to prevent denial of service by a malicious coordinator (being tricked into creating invalid coinjoins that can't be broadcast, but which may leak information about intended outputs).

This is separate from the concern of the coordinator validating user's ownership proofs to protect against denial of service attacks by malicious users, attacks on stateless signing devices (as I already mentioned, the only reason ownership proofs were eventually given to clients: at the time of the mainnet release only the coordinator saw them, precluding even consistency mitigations reliant on the use of more than one input per client) as described here https://gnusha.org/pi/bitcoindev/CAB3F3Dv1kuJdu8veNUHa4b58TvWy=BT6zfxdhqEPBQ8rjDfWtA@mail.gmail.com/

However, as alluded to by the 2nd emphasis a primary concern with the ownership proofs in addition to consistency of the round parameters and transcript, is that prevout amounts are critical information for making choices about the choices of output values. Poor output denomination choices are a potentially catastrophic privacy leak especially in conjunction with input-input links (addressed above) under the sub-transaction model (https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf) when considering P_{O,O}, P_{I,O} values associated with a particular output. In ginger wallet not only are these apparent prevout values potentially under adversarial control, the coordinator simply explicitly tells the client which denominations to use, another unnecessary trust assumption.

This is elaborated on in this issue from which I will quote some more: WalletWasabi/WalletWasabi#5945

Clients must opportunistically verify as many ownership as possible with already available blocks, and additionally verify at least one or two random ownership proofs, ideally more. Full nodes can verify all ownership proofs trivially, with spend status validation as well, but light clients with no full node integration enabled can only check for inclusion in a block (see #5533). .. With some verification the confidence that the amounts given by the coordinator is valid increases, but is not certain without, so it is still possible for a coordinator to partition users and hide some inputs from some users to bias their actions.

Without knowing the set of other users' input values, the wallet's balance may be decomposed into a combination of output values that is not underdetermined in the sub-transaction model, as I mention here: WalletWasabi/WalletWasabi#5994 (comment) Also note that this follows discussion of mitigations (1) and (2) and the lack of header validation are discussed here with no substantive defense of the lack of such mitigations, and what exactly is assured in the light client security model (but thank you for explaining it as though i'm confused).

Sybil Attacks

Sybil Attacks In General

Let's get this out of the way first.

This is also addressed in the paper, section 7.2.2. Have you read it?

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.

waxwing brought up targetted attacks in relation to the coordinator's ability to censor honest parties, a distinction which you are glossing over here.

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.

Targeted attacks are inherently cheaper. In this setting the coordinator can try to influence the targeted user in the numerous ways described above, and only let the transaction go through if circumstances favor deanonymization. You yourself mention the failure rate for rounds is high, though it's not clear if you referred to JoinMarket or wasabi. In wasabi's case, they are much higher than they need to be for reasons described in previous messages. There are also incentive incompatibilities inherent in the protocol design (e.g. WalletWasabi/WalletWasabi#6654) that make it rational for honest users to defect under some circumstances, and indeed the client implements defection behavior in places that could be prevented before comitting to a round WalletWasabi/WalletWasabi#7216

Secondly, coordinator revenues also need to be considered (also discussed in the paper) in the context of sybil attacks. Notably, kruw's coordinator earns revenues despite being advertised as "free", and with mining fees being low recently the mining fee cost is about as low as it can be, so really the liquidity requirement is the only deterrence under these circumstances even for non-targeted attacks.

Bolstering this deterrent significantly is straightforward (verifiably randomization of selected inputs), but that too was rejected by the wasabi team, despite discussions about the value and simplicity of this approach and its benefits over samourai's 'trust me bro it's random" input selection. This was not fully documented, but is mentioned in passing here (discount mechanism to incentivize honest, low time preference users to impose a higher liquidity requirement by earning discounts, no negative externalities to honest high time preference users) WalletWasabi/WalletWasabi#5439

Address reuse avoidance

Anyway, the final technical thing you brought up, the address gap:

I have not verified whether or not this is actually true;

Wasabi uses a non standard address gap limit (114 by default), and retains information in persistent storage about the state of keys (see KeyState enum).

This is problematic with recovering from seed, because upon recovery the last key used on chain will determine the next index to use. The last key used in a failed round is not known.

This is an implementation issue due to gap-limits in HD wallet implementations;

This is a privacy issue due to the dependence on off-chain state and the inability to restore it when recovering from seed.

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.

With silent payments avoiding this reuse can be done statelessly under the assumption that input sets never repeat (which they shouldn't if the coordinator is honest and is very unlikely even if it isn't). This does not require full receiver support at the cost of a linear scan of the wallet's full transaction history upon recovery, discovering root transactions starting from keys (e.g. from a normal external address chain), if the silent payments derivation is only used for self spend outputs.

This assumes the private scanning key is accessible (which it should be) but requires no protocol modifications (whereas sending to 3rd parties, or more generally without knowledge of the private scanning key, requires cooperation of the other parties and requires blinding to preserve privacy). With the private scanning key self spend addresses can be computed using silent payment derivations using the public spending keys obtained from the ownership proofs, allowing the script pubkeys to be known for output registration.

Unfortunately this can lead to unspendable outputs, because without strong validation of ownership proofs: if the final transaction does not match the keys in the ownership proof then the data required for computing the tweak is not available from the confirmed transaction. As discussed above, if P2TR inputs are spent into the transaction consensus validation protects against this, but P2WPKH only ones would not, nor would their owners know their self spend tweaked outputs are safe (spendable using only BIP 32 seed & BIP 352 scanning rules) at the time of signing.

Under the active tagging scenario, either the tweaked private key or the malicious ownership proofs need to be durably persisted in order to maintain access to funds. This is not a viable solution without validating the consistency of the ownership proofs before signing, which your proposed mitigation fails to account for (but which mitigation (3) protects against for all input types, and mitigation (4) also protects against with the additional assumption that other clients are honest, in both cases an honest coordinator that refuses to accept signatures that don't match the ownership proofs eliminates this issue).

While spitballing can be fun, a serious response would work through the details. One might even "say that I'm disappointed so far in how little real engineering thinking" is in your suggestions. https://archive.is/xDVCl

Conflict of Interest

And for the record, the post you are retweeting in that last link, apart from being a deflection from the technical content of this thread, contains numerous demonstrable lies about me and my conduct, which you appear to be endorsing as fact.

It would have been appropriate for you to disclose that your review is paid for by an interested party, as a direct response to accusations I have made:

kruw has had literal months to simply retract his misleading claims that the protocol is "trustless" -- which by his own admission he can't actually verify (https://archive.is/qoPtG) -- and stop portraying his service as "free", despite having a profit motive which he consistently lies about by omission:

https://youtu.be/v952Fd1vmOs?t=2073 - here, months after launching his service, he fails to disclose until pressed to elaborate, then admits he's collecting revenues and casually misrepresents the "optimistic" behavior of wasabi (which a bug) as a "little known secret" that justifies his appropriation of excess funds, which under the zksnacks coordinator went to the mining fees (thereby bolstering sybil resistance, not undermining it).
https://x.com/i/spaces/1ypKdpkmRgdKW?clipID=6b95caeb-6831-4603-8542-b3ad0240ef1c
at 10:32, fails to correct nopara when discussing the risks of regulatory crackdown, a risk he exposes his users to perhaps even unwittingly given cloudflare's involvement as a trusted 3rd party. at least they seem to take these issues seriously https://www.cloudflare.com/trust-hub/law-enforcement/
https://bitcointalk.org/index.php?topic=5498549.msg64157663#msg64157663
https://bitcointalk.org/index.php?topic=5498549.msg64273147#msg64273147

In other words, your deeply unserious foray of this subject was bought for the express purpose of refuting the claims I have made about the lack of trustlessness of kruw's service, his unwillingness to clearly disclose this, which I have corrected him on repeatedly both privately and publicly. When his willingness to collect revenues in an underhanded way by exploiting an implementation flaw in the wasabi client became apparent I escalated to accusing him of being a scammer, and that's when he sought your services.

Funny how motivated reasoning works, that whenever someone stands to gain financially from this farce they seem incapable of making substantive refutations of my criticisms, only minimizing on the basis of vibes. I also observe that disinterested parties don't seem to have the same difficulty engaging with the subject and its nuances, and indeed some have helpfully pointed out mistakes I have made. And as for the criticism that it's never simple with me, that I produce walls of text, well I guess here's another. They only have Brandolini's law to thank for that, not my willingness to put in the work and actually take this subject seriously, along with its complexity.

Here's a helpful reminder about the standard to which those with a profit motive should be held accountable with regards to privacy software and the claims they make about it:

nothingmuch/01 reply.md