From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 04 Feb 2025 06:06:45 -0800 Received: from mail-qt1-f192.google.com ([209.85.160.192]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tfJZb-0006Lo-5u for bitcoindev@gnusha.org; Tue, 04 Feb 2025 06:06:45 -0800 Received: by mail-qt1-f192.google.com with SMTP id d75a77b69052e-467bbc77b05sf111214901cf.0 for ; Tue, 04 Feb 2025 06:06:43 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1738677997; cv=pass; d=google.com; s=arc-20240605; b=MCtXrpElqMh0SU9ebYvO28da32x+ucGb7VXOYhOFx0NjBakHgCJHcZYFOK3ID3Kwda V5k9zBBItGdTce64cLBdPteBtTOZAKjNPybPFuS3yURsXA++E62V9RbCDCeh9ZTgx1t4 szL68OBVeEqVxlkKABVg11iJ9LOllcf1no5BBF0B6zDccmm0DwBAiNoHVesmAVAtdKbV GxnvyErXBJUMCvXdw1gJ6zDLetWORtUiyfLBHxykR343iBkVxnbyKFHU+niugnSpQn/O me39mwjhnvqkA0lAZS2JImKZmO11RhYBWLjym09I+SVKiCe1kLgxim1JfFZqPhvjpGCX IwBg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:content-transfer-encoding:cc :subject:message-id:date:from:in-reply-to:references:mime-version :sender:dkim-signature; bh=8RUkAldoPd+ataU7WrmH7tTqTsbO52M6ga8CkfrYETc=; fh=VsAl+ITokLjtGyowAJROFZVdgqzMuAaSctbQ380J598=; b=PDsxLL9aOxegZ2YgIlqjOp8PEH4MddvJEEXIKxzuCUJY/xOuiIBBmLi6tJuf5N90R5 CROUfCjluWrJfNzfW8iJYb1ZwrVMTU++biDrifEdMb4bU3Ir0QYmYjkyRev3x6OH39t9 j2fdRFB3gQdgh809XSAUzzfhijZGs1ayGxifKghSQ0lwxq31ApEGiw9dhNvZ1cpR6iaM +prsrC05Cj95LGTlqS8gvcpInnxBZkUN5OGqtuTQDuCCMPd5TltyQvF4CuaAo+veHcJM rZJCHnTIEVYKCFaxBoIqgOJ2Khw3RVhjILZE2C39I4w+vyF9Urgig7kMGPddYYGuEd11 5KIQ==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@woobling.org header.s=google header.b=BA+0AVhx; spf=none (google.com: nothingmuch@woobling.org does not designate permitted sender hosts) smtp.mailfrom=nothingmuch@woobling.org; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1738677997; x=1739282797; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:content-transfer-encoding:cc:subject:message-id :date:from:in-reply-to:references:mime-version:sender:from:to:cc :subject:date:message-id:reply-to; bh=8RUkAldoPd+ataU7WrmH7tTqTsbO52M6ga8CkfrYETc=; b=CfrQowbKQZbpHSSb3ATlBuGZsb6jb3k28XNei2Sfepa8c+fnxvJ3eBaJBHlz/Kj0Lh KHnUkhJWiKdglXWjGBpj0iAovLmu3eVIDfCyNuKGDIddLv/V1Qci3+COTIkDcaZnMbyY qCIRW3O1BwbLQZhuD2kvz5tPIiPzMoF3q32vIlo4peVkw2ZabWDVnCa97v8j/X7QkAA9 P0nULsckPx9FM+H2h+P4/xBCYiBb7PsRkGMfqlsLk8pyE0zN500JhhzAf2A/XuA1ahEe U0LrP9khIPcapt8E2i0JAkNF8mFuM+lHOixmupMeLUNbXSHj1G58+qpVpL4heQYwnoav aYjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1738677997; x=1739282797; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:content-transfer-encoding:cc:subject:message-id :date:from:in-reply-to:references:mime-version:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=8RUkAldoPd+ataU7WrmH7tTqTsbO52M6ga8CkfrYETc=; b=ivrkSwLC5L8Zz4yiaWL5jdF1rGMo7IA/0mabZo86wzVef56flnxe4q5UVIwAJ7dErU cjOtyLcEEM1VceTRsvencQYh4zoFOOEy0qFW4kgDSD1LT2NRDe1cdNU7DdF9H9x3NS0x o6jWisFsd9VnBxcpvlQt6GeVDiRK4BizNhTCZGcOANlqbw8ONqOBeymNbPZfKmnGTsuI /vlbV5cxf+6e2Gk7hdPay0NMqXqYZAeM7rDBZtCIlIe+YGGCRhY3RBYc6zp1H2PJRM5z AHsVLTQZYBMk3mfF0eLuSD987v3nQPydVuwdWK9xc5FqtSfs9zn0v3ZxRbxp0Uk0EyZa 6vqg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCWA041y0XOCTO5wBRLn0vTWv/ZhTuzRO0GJIrxMN3tATx+NBV9b1VTnnCW6Zi2q0KrhQkRycZeZClDe@gnusha.org X-Gm-Message-State: AOJu0Yw0xnZfxIFqvxjI4hzyJ/diudlfUfoTSn202D+6D7TRgQEYX7/U 9y7uHjMmjrtlWpqHhJwvW8MGo9DnJnk9+/azQEan66kHB/p3O1sO X-Google-Smtp-Source: AGHT+IFQTF0E3p0QRhqX1V7eh3wnNMT2oArQfGvvX9SEIBDtZ24jKdd6buvwdTLuEqWjFD7DRP7B1Q== X-Received: by 2002:ac8:5994:0:b0:467:5f32:3204 with SMTP id d75a77b69052e-46fd0b89c01mr285191561cf.45.1738677996684; Tue, 04 Feb 2025 06:06:36 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:ac8:40c9:0:b0:466:b34c:880d with SMTP id d75a77b69052e-46fdceb2440ls47590411cf.0.-pod-prod-03-us; Tue, 04 Feb 2025 06:06:32 -0800 (PST) X-Received: by 2002:a05:620a:1912:b0:7b6:e8d4:9b86 with SMTP id af79cd13be357-7bffcd9ffe6mr3933327885a.57.1738677992433; Tue, 04 Feb 2025 06:06:32 -0800 (PST) Received: by 2002:a05:620a:1da6:b0:7b6:dcc4:6708 with SMTP id af79cd13be357-7c02f67a624ms85a; Tue, 4 Feb 2025 06:02:22 -0800 (PST) X-Received: by 2002:a05:6402:e96:b0:5dc:74f1:8a32 with SMTP id 4fb4d7f45d1cf-5dc74f18bebmr22242056a12.28.1738677736650; Tue, 04 Feb 2025 06:02:16 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1738677736; cv=none; d=google.com; s=arc-20240605; b=Nxtt3+mJs/VZf4olY3aHmqFvCXmqT79jIZVLALwWBJNReMl+OJQD0fBQWSti4Pgk/I /cm/QL9yK0TQKxNnkN3of9wY0BeLF11kMEu1k1KuJJThGkfRoZ+u/4nMS4f9oLniq9GQ 9du4m6cUaHK6rqCCQOfpvQHu3zJWKFYu5IYZyRDUjgVzOQqdP3UOxOSEVzqdjRCqFHXm viLbU8s58NrVruKXMhFai4N+da9wtVki/m1E3bqZXL2OafpJX25YHpugvOYvmUtarIe/ S7WzJGxhld4e2KnfdIrGQAVhNRXchq0V+5rWacWCTViUm2MPe6x05Z6ymf7UzKJ5shyx G/PA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=content-transfer-encoding:cc:subject:message-id:date:from :in-reply-to:references:mime-version:dkim-signature; bh=xeCiAYs5GUkdsDEiYjFseR+v7letHQbLlVlL/mgkPHc=; fh=KToalNYOLOY5OcEN8k1qap7GE/GrsMpo+YpfFP5+Yok=; b=Q85ptzjAYEHFLKchqMQ+xS4tCXWmJbaxP94Sr9+5k+JDxp3yfzSQqxD7HSSXFDPW/v xOtQhAN03WNJ3mvtCdGk3G5DOm8AV0LAMELg4P4kucPqNIFks4uqHLQh86EOvNV36Vro tK250aO/uRQhs3073DohvT1+SIfHgdZhqbXD6hfgerbOl2U0fcYcs/0aUfI2dOeMIB1S 8oaWYA1vjNrPydscARev9/QsARUiT2jFiycxH0frX0I2s5Q8vDIVA2j2ESUcgxUnWrQz zGcOkDFKpQ1o641SW8XhrdJKKH88n+fVSbldn5dmo/8prUELM9vCQeto37dzMSjIT0zz aY2w==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@woobling.org header.s=google header.b=BA+0AVhx; spf=none (google.com: nothingmuch@woobling.org does not designate permitted sender hosts) smtp.mailfrom=nothingmuch@woobling.org; dara=pass header.i=@googlegroups.com Received: from mail-lj1-x22a.google.com (mail-lj1-x22a.google.com. [2a00:1450:4864:20::22a]) by gmr-mx.google.com with ESMTPS id 4fb4d7f45d1cf-5dc723efbfbsi285336a12.2.2025.02.04.06.02.16 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 04 Feb 2025 06:02:16 -0800 (PST) Received-SPF: none (google.com: nothingmuch@woobling.org does not designate permitted sender hosts) client-ip=2a00:1450:4864:20::22a; Received: by mail-lj1-x22a.google.com with SMTP id 38308e7fff4ca-307bc125e2eso22331681fa.3 for ; Tue, 04 Feb 2025 06:02:16 -0800 (PST) X-Gm-Gg: ASbGncuZqlp0+H2f9zqEAgK6evrHWCm0OfbAxKnG6e+rzKwa1u652IsiPa0XsTesDhp bX48c/2j721NB/caOcNaB2yooCrfQcxuAWT43ZzU+Cl8f/wemnCuvcClGF2AlYU+5iLG5jIS5 X-Received: by 2002:a2e:b88b:0:b0:302:264e:29ec with SMTP id 38308e7fff4ca-307968cb5admr101651881fa.11.1738677732775; Tue, 04 Feb 2025 06:02:12 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Yuval Kogman Date: Tue, 4 Feb 2025 15:02:01 +0100 X-Gm-Features: AWEUYZkT6Tg8lLEU-g_uVye_UcvujjRu4yR8ry5cNV5yBAnrjR-cpQebmIa4hMM Message-ID: Subject: Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks Cc: Bitcoin Development Mailing List Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Original-Sender: nothingmuch@woobling.org X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@woobling.org header.s=google header.b=BA+0AVhx; spf=none (google.com: nothingmuch@woobling.org does not designate permitted sender hosts) smtp.mailfrom=nothingmuch@woobling.org; dara=pass header.i=@googlegroups.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: 0.2 (/) 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: 1. Your proposed mitigation for the tagging attack is inadequate and is redundant when P2TR inputs are spent. 2. 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. 3. Your account of sybil resistance ignores important nuances, but at any rate that isn't really relevant to the subject. 4. You neglect to disclose a relevant conflict of interest which is relevant context re (2). Note: At the request of the moderators I have edited out some of the additional context I initially provided, as it is not directly related to the technica= l matter at hand. While I understand why this forum is perhaps not the appropriate one to bring that up, I stand by what I said and personally sti= ll feel that *is* relevant, due to misinformation about the services and softw= are offered by for profit privacy vendors. If anyone is interested in the full message, I have posted it publicly. Feel free to reply off list if you'd li= ke to read it and are having trouble finding it. On Thu, 23 Jan 2025 at 17:25, Peter Todd 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. 1. 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. 2. 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. 3. 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. 4. 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. 5. 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/d8d792d339d3e467ea36eedd4= 5f392de5ea716df/WalletWasabi/WebClients/Wasabi/WasabiHttpClientFactory.cs#L= 130 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/b49e69d48e6f599235cc3c518= c2cf8e3e9206571/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. - https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eed= d45f392de5ea716df/WalletWasabi/WabiSabi/Client/CoinJoin/Client/CoinJoinClie= nt.cs#L179-L181 - https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eed= d45f392de5ea716df/WalletWasabi/WabiSabi/Client/CoinJoin/Client/CoinJoinCoin= Selector.cs#L50-L303 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/1552= 86/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/d8d792d339d3e467ea36eedd4= 5f392de5ea716df/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 https://github.com/WalletWasabi/WabiSabi/issues/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: 1. redundant queries of round information over isolated tor circuits 2. best effort validation of ownership proofs under SPV assumptions 3. deterministic shuffling of transaction data seeded by transcript hash 4. 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/w= asabi2-0-released/#:~:text=3Dthat%20implements%20trustless%20WabiSabi%20coi= njoin%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=3D5482818.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/d8d792d339d3e467ea36eedd4= 5f392de5ea716df/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 expo= se >> 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 https://github.com/WalletWasabi/WalletWasabi/issues/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: - https://archive.is/dtPd9 - https://archive.is/8xtLW - https://archive.is/pyyuu - https://archive.is/rpRIo 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/d8d792d339d3e467ea36eedd4= 5f392de5ea716df/WalletWasabi/WabiSabi/Backend/Rounds/Arena.Partial.cs#L345C= 33-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 su= bject >> 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=3DBT6zfxdhqE= PBQ8rjDfWtA@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-trustc= om-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: https://github.com/WalletWasabi/WalletWasabi/issues/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 ownersh= ip >> proofs trivially, with spend status validation as well, but light client= s >> 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 sti= ll >> 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: https://github.com/WalletWasabi/WalletWasabi/pull/5994#issuecomment-9241057= 39 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=C2=B9 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. https://github.com/WalletWasabi/WalletWasabi/pull/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 https://github.com/WalletWasabi/WalletWasabi/pull/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) https://github.com/WalletWasabi/WalletWasabi/issues/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). # Conflict of Interest 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: - https://archive.is/cbffL - https://archive.is/BJCNG Kruw has described his service as "free" and "trustless", despite earning revenues and despite the issues described here. Supporting evidence for this is in the unedited version of this reply. --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= CAAQdECC0FG7xhxygAPEL0XD4umU%2BzH84rK-P-UDKMLaZhr1HBw%40mail.gmail.com.