Fungi

Fungi is a protocol for collaborative transactions designed to make using Bitcoin more private. Participants can also pay each other interactively in these transactions, which helps not just privacy but also blockspace efficiency.

A software development kit (SDK) is in development. This repository contains the specifications and the analysis behind them.

Note

Work in progress: most chapters are drafts under review. See the open pull requests for material being drafted.

Chapters, sections or paragraphs marked with 🤖 are LLM output. They have been partly verified but have not yet been edited or rewritten as necessary, and should be considered a working draft.

Background

Censorship resistance and fungibility are among Bitcoin’s foundational properties. Without privacy, both can be undermined largely outside the protocol’s rules, whether by targeting specific individuals or through chilling effects.

Bitcoin transactions are public data, and they are connected in a graph structure. Chain analysis is the application of heuristics to this graph to infer which coins share an owner. While no heuristic is perfect, their effectiveness has been shown in numerous studies. Several heuristics can be combined for a more accurate analysis. Analysis might also draw on auxiliary information not recorded on the blockchain, such as which coins an exchange sent to which customer.

CoinJoin transactions seek to undermine some of the heuristics used to cluster coins across the transaction graph. They combine several users’ inputs and outputs in one transaction in order to obscure ownership links within it. Several CoinJoin implementations exist with different approaches to their transaction structure.

Problem statement

Unfortunately, CoinJoin privacy is often stated in terms of the number of indistinguishable outputs in a transaction. This tacitly ignores the fact that those coins will go on to be spent. The information revealed by the spending transactions, which are themselves related to other transactions, can dramatically affect privacy, in some cases making the CoinJoin inputs linkable to the outputs.

Recurring relationships give rise to patterns too. Transacting with the same employers, shops and friends leaves a structure in the transaction graph, even if techniques like PayJoin might hide the individual amounts and confound some of the clustering heuristics. Obscuring this structure necessitates transacting with unrelated users, chosen at random, so users who don’t know or trust each other need a way to find each other and agree on a transaction. Random selection must additionally be Sybil resistant, so that the cost of an $n-1$ deanonymization attack, where the adversary controls all of the other (apparent) participants, is a sufficient deterrent.

In general, deanonymizing a single user always makes it easier to deanonymize the other users. But sometimes the adversary might progress not just by process of elimination, but more like divide and conquer. This happens when deanonymizing that one user splits the problem of deanonymizing the rest into several smaller problems, as opposed to merely making it incrementally smaller.

The problem definition chapter discusses these on-chain privacy leaks in depth, and describes a particular transaction graph structure that resists deanonymization more robustly.

How Fungi works

A user first tells their wallet which payments they intend to make, and the wallet keeps these in a queue. Intents can vary in their time, privacy or cost sensitivity. Making a payment quickly, cheaply and privately is a balancing act, and improving one usually means compromising on another. The wallet’s job is to construct transactions that make the queued payments, balancing these goals in line with the user’s preferences.

The wallet schedules and batches payments, negotiating with other participants to find terms that suit the user’s priorities. The more flexible a payment’s timing, the more cost-effective it can be, because there is more time for compatible proposals to be combined, so that its cost can be shared with more participants. The protocol and the strategy are designed together, and the SDK implements both.

Avoiding links between coins is central to the strategy. The input and output amounts can imply such links if there aren’t enough possibilities for how to group inputs and outputs so their totals match. But as mentioned above, a partition of a transaction’s coins can also be evaluated based on the surrounding context in the transaction graph, not just the amounts associated with that transaction. So the strategy must consider not just whether the transaction’s internal structure is sufficiently ambiguous, but also how a transaction sits in the wider transaction graph.

In Fungi, a co-spend proposal sets out the terms for spending a set of coins together. Proposals are made automatically according to the privacy optimization strategy. The transaction-wide terms of a co-spend proposal are public, constraining things like the range of acceptable feerates or whether or not non-SegWit inputs can be used. Proposals can also include fees, which are kept confidential. A proposal involving three or more parties additionally hides which of them made the proposal. Once accepted by all parties, co-spend proposals are publicly broadcast.

Any participant can collect fully accepted co-spend proposals from multiple parties, and then make a coalition formation proposal which aggregates them together, so long as the terms are compatible. If everyone accepts the coalition formation proposal, then a coalition has been formed, and the parties can proceed with collaborative transaction construction. Privacy is brittle in small transactions. A critical mass of participants is therefore necessary for privacy to be robust and cost-effective, and coalition formation is designed to facilitate such a critical mass forming.

During collaborative transaction construction, participants add their intended inputs and outputs anonymously. This preserves the unlinkability of inputs and outputs so long as it isn’t undermined in some other way (for example by reusing an output address). Interactive payments additionally provide privacy against the payment counterparty. In addition to hiding the payment amount from third parties, the sender and receiver do not learn about each other’s coins. Since many interactive payments can be settled in one collaborative transaction, this creates the opportunity for blockspace savings.

In order to ensure funds are secure throughout, every participant retains control at all times and therefore signs their own inputs. Unfortunately, this means that as the number of participants grows, reliability will necessarily degrade. Even if the probability of any one participant causing a fault is low, that compounds when considering the probability that none of them will. Transaction construction is designed to be fault-tolerant, so that even when a valid transaction has not successfully been produced, participants have a basis to refine the coalition structure. Fault tolerance includes malicious disruption.

Compared to JoinMarket

Fungi could be described as a spiritual successor to JoinMarket (as implemented by JoinMarket and JoinMarket-NG). Like JoinMarket, it is peer-to-peer and market-based, with no centralized coordinator, but differs substantially in how it approaches the order book mechanism as well as transaction construction.

JoinMarket distinguishes two roles: in each transaction, a user in the role of the taker selects several makers from the order book. Makers advertise their willingness to participate in CoinJoin transactions. Generally, the taker will pay the on-chain fees as well as any maker fees. The taker learns which coins belong to the makers it pays, so makers get no privacy from the taker. And because there is a single taker, a transaction can only include as many participants as one taker is willing to pay for.

Fungi makes no distinction between the taker and maker roles. Instead, a participant can both send and accept proposals, and proposals involving multiple users can be aggregated, allowing a single transaction to be negotiated more as a group buy of blockspace. As the number of participants grows, the privacy benefits compound for everyone, which means each individual user needs to pay for proportionately less blockspace in order to meet their individual privacy requirements. Finally, the proposed transaction structure aims to address several deanonymization attacks that were not yet understood at the time JoinMarket’s design was put in place.

Contents

Problem Statement

• Collaborative transaction privacy - Challenges for privacy in multiparty transaction settings, from PayJoin to CoinJoin.

Protocol Suite

• Overview - Collaborative transaction construction, privacy, fault tolerance and coalition formation.
• Abstract transport interfaces - Send, receive and bidirectional channels, the kinds of messaging the protocol needs, and broadcast built from peer to peer channels.
• 🤖 Peer and broadcast channels - Broadcast to a group or to the world, built by gossip over peer to peer channels.
• Contacts and payment messaging - What interactive payments need from peer to peer messaging between payer and payee.
• Market-based coalition formation - Bilateral negotiation and aggregation of co-spend proposals into a unanimously accepted coalition formation proposal.
• Transaction construction - Content and state synchronization, the phases, the optimistic and recovery tracks, and what the validity proofs enforce.
  • Block DAG - The validator blocks both tracks share, with their objects, nonce commitments and equivocation evidence, genesis, causal order and frontiers.
  • 🤖 Optimistic track: blocks and phase states - Unanimity and phase closure on the optimistic track, phase by phase.
  • Recovery track - How a stalled phase of the optimistic track turns into a recovery coalition formation proposal. Draft.
• 🤖 Peer set reconciliation - Requesting hash preimages, naive reconciliation, unordered sets, and range and rateless reconciliation as optimizations.
• 🤖 Protocol messages - The messages peers exchange, who sends them, when, and what each requires of its channel.
• 🤖 Validity proofs - Selected design: proving outputs are covered by inputs through anonymous allocation registration.

Privacy Optimization Strategy

• Optimization framework for Bitcoin wallets - Objective costs, privacy liabilities and payment utility as the basis for automated wallet decisions.
• 🤖 Pure Strategy Evaluation - How the cost of a pure strategy is evaluated: the structure of the cost function, its privacy liability terms, and the privacy metrics they take as input.
  • 🤖 Cost function structure - The structure shared by the family of cost functions that evaluate pure strategies: time dependence, linear combination of terms and bracketing.
  • 🤖 Privacy liability terms - The privacy objectives assessed by each liability term and how the terms interact.
    • Randomized selection - Selection preferences that randomize which coins are co-spent, and a lower bound on the size of the order book they were selected from.
    • 🤖 Sybil resistance - Observed resource requirements and sampled cost estimates assessed against the user’s threat model.
    • 🤖 Subset sum ambiguity - Outline of a concrete cost function term for the subset sum ambiguity of input and output values.
    • 🤖 Consolidation penalty - Outline of a concrete cost function term penalizing consolidation unless the subset sums are very dense and the coins are impervious to intersections.
    • 🤖 Sibling output penalty - Outline of a concrete cost function term penalizing spending sibling outputs together.
  • 🤖 Privacy metrics - Measures computed from public data that the privacy liability terms take as input.
    • 🤖 Order book size estimation - A relatively conservative estimate of a lower bound on the number of candidate coins a transaction’s inputs were selected from, and how to find the block hash they were selected with.
    • 🤖 Subset sum density - How many subsets of a multiset of effective values sum into a target interval, a quantity the subset sum ambiguity and consolidation terms reuse, how it’s estimated, and how co-spend proposals and the aggregator optimize it.
    • 🤖 Counterfactual paths - Outline of how to count disjoint counterfactual paths with one max flow, and how to estimate the count.
• 🤖 Mixed strategy - How to compose a mixed strategy from the cost of pure strategies: randomization, time dependence, internalization and the decision loop.
• Tactics - Generating the decision tree bottom up, with coin selection and change decomposition, and when to re-evaluate it.
  • Bottom-up construction - Building the decision tree from the leaves: partitions of the intent queue, coin selection, change construction, order book coins, action sequences, and bracketing.
  • Radix CoinJoin Denominations - Why small Hamming weight denominations suit CoinJoin outputs, and how closely sums of a few of them approximate arbitrary amounts.

BIP Drafts

• PSBT Scrubber - Which PSBT fields can be shared with trusted and untrusted parties such that privacy is preserved.
• Concurrent PSBT Construction - PSBT fields and rules for combining partial transactions and terminating concurrent construction.

Collaborative transaction privacy

This document examines some challenges for privacy in a variety of multiparty transaction settings, from PayJoin to CoinJoin.

The Bitcoin transaction graph

The Bitcoin transaction graph is a trace of the movement of funds between different users.

The flows themselves can also be modeled as a graph where vertices represent users, and edges represent the relationships between the users, that is to say the edges describe how funds tend to flow between the users. Borrowing from the first study to describe this, we’ll refer to it as the user network, and define it more precisely below. Deanonymization of Bitcoin transactions roughly corresponds to recovering (parts of) this underlying structure from the transaction graph recorded on-chain.

Neither the user network nor the transaction graph is random. But they both have some randomness in them. The user network is a kind of social graph, specifically an economic network. An extensive literature on complex networks characterizes such graphs.¹ These networks behave very differently from random graphs, certain properties of these graphs can be predicted reliably. In the transaction graph, some of the details are obscured, primarily due to Bitcoin’s reliance on the UTXO model (rather than say the account model) for transfers. However, because the transaction graph is a trace of transfers through the user network, and because the user network is highly structured, so is the transaction graph. And while the user network is not directly observable, it is one of the defining properties of Bitcoin that the complete transaction graph is observable by anyone.

For the transaction graph to be privacy preserving, it must robustly obscure patterns originating from the user network. This is challenging because the user network constrains how the transaction graph is constructed. There are different ways of accomplishing this goal, but the approach assumed here is that of an overtly ambiguous graph, where the individual users’ actions are sufficiently and randomly intertwined, necessitating additional information to disentangle. The central claim made here is that such a graph must be carefully and deliberately constructed. It does not emerge spontaneously, nor by naive attempts. But it can be constructed, even efficiently, and the guarantees it provides are relatively straightforward to understand and even to quantify.

Unfortunately, common misconceptions about how on-chain privacy works and what attackers are capable of paint a much rosier picture than what the published literature has shown is actually possible. None of the attacks described here are novel, but some of the cited results of the privacy literature originated in a different setting than Bitcoin privacy.

This document isn’t concerned with providing empirical proof of the viability of different attacks, partly because some of the structures whose weaknesses are examined are still hypothetical, but mostly because of the lack of novelty; the cited works are generally supported by evidence and most are peer reviewed. It is on proponents of privacy to show why their technology can resist such attacks, rather than on critics to demonstrate how it can be broken for the same reasons as in cryptography but even more so because many of these attacks are substantially amplified by an adversary’s access to auxiliary information such as labeling originating from KYC processes.

Unlike in cryptography, where the burden of proof is both high and generally belongs to those making claims of security, in Bitcoin privacy various apologists and interested parties often promote the notion that the burden of proof is reversed, or that addressing these problems is trivial. That framing is misleading in minimizing the consequences. Misinformed users are needlessly exposed to risks to which they might not have given informed consent.

This document is concerned with defining specific failure modes. Vendors of privacy-enhancing technologies, as is the norm in other industries, should be expected to address these widely understood attacks and argue for how their product maintains privacy in the face of adversaries that aren’t assumed to be unreasonably weak. Specifically this document defines the problems that the Fungi protocol suite aims to address. And by extension a minimum bar for evaluating any claims about the on-chain privacy guarantees it tries to provide.

In other words, the problem is that due to the economic network at the heart of Bitcoin, not only is it unreasonable to expect privacy or fungibility automatically, but the privacy guarantees that are currently available themselves often rely on unreasonable assumptions. By understanding these challenges we can describe the properties a transaction graph requires so that its resistance to analysis does not rest on fragile or unrealistic assumptions.

Unilateral transaction privacy

Unilateral transactions are highly susceptible to deanonymization using clustering techniques. After address reuse, the most obvious way to cluster, or link a user’s coins, is the common-input-ownership heuristic (CIOH): A transaction that spends several inputs is evidence that one entity owns all of them, since at the protocol level signing for all of them normally requires all of their keys.^{2 3}

CIOH links the inputs of each transaction, and change identification links the two transactions: All five blue coins merge into a single cluster.

Practical clustering combines heuristics beyond CIOH to build a wallet cluster: a set of addresses and coins inferred to share one owner.^{4 5 6 7 8 9 10}

Collaborative transactions

A transaction that spends inputs owned by more than one user falsifies CIOH by construction. Starting with just two parties, the observable structure can have (at least) two forms.¹¹ The on-chain transaction must be compatible with the actual allocation of inputs, outputs, and payments among the participants, but it might not reveal that allocation in its entirety.

The first two-party form is a batched transaction, or a CoinJoin: two independent sub-transactions, both of which are balanced, aggregated into a single transaction.

Here, a sub-transaction means some, but not all, of a transaction’s inputs and outputs attributed to one participant’s action. A more precise, probabilistic notion will be discussed below. Informally, a balanced sub-transaction is one whose balance, the difference of the sum of input values and the sum of the output values, is approximately zero.

A batch: two independent spends aggregated, SharedCoin style. Each sub-transaction balances on its own (0.9 = 0.5 + 0.4 and 0.3 = 0.2 + 0.1).

In the example above, although CIOH is falsified, the amounts strongly suggest one way of partitioning the transaction, and CIOH still applies within each sub-transaction separately. We’ll return to this form of collaborative transaction and its variations, as well as how the sub-transaction model generalizes CIOH, in later sections.

Two-party PayJoin

The other main form a two-party transaction can take is a PayJoin.^{12 13 14 15} Unlike the independent, balanced sub-transactions in the preceding example, the sender’s sub-transaction has a positive balance (a surplus) that covers the receiver’s negative balance (a deficit). This imbalance between the two sub-transactions is the payment.

The following illustrates a single payment from Alice to Bob, but Bob also contributes one of his own inputs alongside Alice’s:

Here, Alice pays Bob 0.5: Bob’s 0.6 input grows into a 1.1 output. The payment amount appears nowhere on-chain, and the ownership coloring is of course not part of the on-chain data either.

For privacy, a somewhat teleological but more general definition of PayJoin is a collaborative transaction that should be indistinguishable from an ordinary single-party transaction. The unnecessary-input heuristics flag an input when the remaining inputs could already fund the outputs and fees; such an input may reveal that another participant contributed it.^{16 17} If collaborative transactions were sufficiently common, naive application of CIOH would quickly lead to cluster collapse, forcing a more nuanced approach to clustering.

CIOH, seeing two inputs, would wrongly attribute them to a single owner. There’s no single unambiguous interpretation: Looking at a transaction like the example in isolation, an analyst cannot be sure which inputs are Alice’s, which output is the real payment, or even that a PayJoin occurred at all rather than an ordinary two-input spend.

With only two parties, there are only a few interpretations, namely the different ways of assigning inputs and outputs to sub-transactions attributed to Alice and Bob separately. The typical uncertainty is therefore on the order of a few bits to an external observer, even when looking only at the transaction in isolation and ignoring its context.¹⁸

The next few sections discuss extensions to two-party PayJoin, but bear in mind that as they’re more difficult to analyze, the same concerns apply even more to the two-party case. Additionally, a two-party PayJoin inherently cannot provide privacy from the counterparty. Each participant can eliminate their own inputs and outputs from consideration, which entails that everything else is attributable to the only other party. Privacy within a transaction requires three or more parties.

Many senders, one receiver (NS1R)

A natural generalization is from one sender to many.¹⁹ Several senders each contribute inputs to a single transaction that pays one common receiver, so it resembles an ordinary batched payout the receiver might have made by consolidating funds:

The payment graph, which isn’t observable on-chain.

Alice, Bob and Carol pay 0.2, 0.3 and 0.7 respectively; Dave consolidates the payments with a 0.4 input of his own. None of the payment amounts appear on-chain.

This allows more payments to be consolidated into a single receiver output, so it’s cheaper than paying separately.

Counterparty privacy depends on how the transaction is constructed. In the experimental NS1R implementation,¹⁹ each sender supplied a pre-signed transaction to the receiver, revealing which inputs and change outputs belonged to that sender. If transaction construction conceals attribution, the receiver can still use its knowledge of each sender’s payment amount to test possible input and change-output assignments. This can narrow the possibilities, and may identify a sender’s change output, but does not by itself guarantee a unique assignment.

This structure can’t really hide much more than that: The change outputs will likely still link, and as the number of senders grows, the receiver must consolidate more aggressively to leverage the savings — which is itself a detectable fingerprint. Avoiding it means forgoing the fee savings and splitting the received funds into several outputs of a smaller magnitude to better match the distribution of the change outputs. Splitting the receiver’s funds creates another hazard: Later spending those sibling outputs together, even in a multiparty transaction, is wasteful and potentially more indicative of common ownership than spending non-sibling outputs together. Two independent users participating in one transaction and then independently spending their respective outputs in the same subsequent transaction would arguably require more coincidences.²⁰

Many senders, many receivers (NSNR)

The two sides can instead be made symmetric. Let $n=2m$ be the number of participants, half spending and half receiving. The transaction consists of $m$ payments between the $n$ sub-transactions, pairing sub-transactions uniquely.

A multiparty PayJoin transaction with three payments between six participants, with one input and one output per party.

The underlying payment graph, which isn’t observable on-chain.

A different interpretation of the same transaction might swap the candidate ownership of Alice’s 0.4 change and Erin’s 0.85 output:

Under this alternative assignment, Alice’s 0.9 input leaves 0.85 in change, implying a payment of only 0.05 to Erin.

Because each participant only participates in exactly one payment, each hidden sub-transaction is related to only one payment of one amount. The amounts therefore still carry information. In the example above, the alternative 0.05 payment may seem less plausible than the original 0.5 payment if its magnitude is atypical relative to prior on-chain payments and auxiliary context such as exchange rates, timing, fees, and wallet fingerprints. This is essentially the same logic as the unnecessary input heuristics.^{16 17} And if the adversary happens to know that Alice’s cluster contains a smaller UTXO than the 0.9 one which still suffices for a payment of 0.05, that would be rather strong evidence in favor of the payment amount being 0.5.

Net settlement with cycles

Net settlement is the most general form of multiparty PayJoin. Where NSNR fixed $\frac{n}{2}$ payments among $n$ participants, net settlement allows odd $n$ and up to $\frac{n(n-1)}{2}$ net payments to be aggregated: Any participant may pay any other.

Participants settle an arbitrary set of mutual obligations in a single transaction, including cycles (e.g. Alice pays Bob, Bob pays Carol, Carol pays Alice). A participant may both pay and receive payments in the same settlement. The number of participants $n$ is in general not observable from the transaction (though in some cases it can be statistically or directly inferred from its structure).

A single settlement transaction. Under the ownership assignment shown, the balances are Alice +0.1, Bob −0.2, and Carol +0.1: inputs minus outputs, including fees. None of the individual obligation amounts appear on-chain.

Three mutual obligations, including a cycle.

Once cycles are allowed, a participant’s inferred balance can combine several payments sent and received, as well as their miner fee contribution. It is still a single amount, but its magnitude need not resemble that of any individual payment: Large payments in opposite directions can leave a small balance, including near zero. This weakens the amount-based analysis used in the preceding NSNR example. A small balance is no longer evidence of an implausibly small payment, because it may instead reflect the settlement of several larger obligations.

Since net settlement is strictly more general, if it’s supported in implementations, then every multiparty batch could in principle be a net settlement transaction, even if that’s not actually the case. Conversely, if the only thing actually deployed is the restricted NSNR above, users are forced back into that weaker regime where amounts still leak. The strength of the defense depends on the general form being the norm, not the exception.

Unfortunately, this isn’t enough for privacy, because the resulting graph still has community structure. The adversary doesn’t see only a single transaction; it sees the transaction graph and some clustering of it (which may be based just on the graph structure, or be based on blockchain-external information too). A settlement among counterparties is a slice of an economic network, and economic networks aren’t featureless: They have recurring relationships, and the behaviors can often follow predictable patterns.

Sparse datasets

Deanonymization of networks with exactly this kind of structure is a well studied problem. In 2008, Narayanan and Shmatikov showed that real-world high dimensional datasets are typically sparse — most records have no close neighbors in the feature space — and this sparseness makes deanonymization feasible with only a little auxiliary information, even when that information is noisy.^{21 22}

Any observable pattern in a cluster is potentially useful for such an analysis. These divide into statistical features (fee-rate habits, activity timing and time zone, value distributions) and topological features (the shape a cluster carves through the graph and its links to other clusters). “Topological” is used to refer to the graph structure in order to distinguish it from the structure of transactions, which are more to do with wallet fingerprints.

Wallet (software) fingerprints are a special case of the statistical kind: Signature grinding, fee-rate selection, script and address types, and nSequence and nLockTime conventions each vary from one wallet implementation to the next. While some wallets randomize these, and specific entities may use more than one piece of software, fingerprint-based clustering — both more generally^{23 24}, and also specifically in the context of PayJoin²⁵ — has thus far proven to be extremely powerful. This problem is pretty widespread. In principle, it can be mitigated by the Sisyphean task of making all wallets draw their observable behavior from similar enough distributions to render them indistinguishable. Note that these distributions need not be uniform, nor must every transaction look identical.

Fortunately wallet fingerprints on their own do not have high enough dimensionality to satisfy the sparseness condition: while the software used to create certain transactions might be determined even with low uncertainty, that on its own does not distinguish one user of the software from another. It can nevertheless narrow the population within which other statistical and topological features distinguish a cluster.

Unfortunately, that doesn’t invalidate the general approach. And while minimizing fingerprint leaks is necessary for clustering resistance in a diverse wallet ecosystem, even if it comprehensively fixed that would not be sufficient for addressing these concerns they currently raise, since wallet fingerprints aren’t the only dimensions along which clusters can be compared, and they remain useful when considering a model where sparseness does hold.

Social graphs

Turning to the topological features, in subsequent work,²⁶ the same authors showed that the vertices of two social graphs can be matched iteratively, starting from a relatively small seed matching, which matches some of the vertices of one graph with those of the other.

This builds on the sparseness assumption exploited by the previous work. Here, a “dimension” can be thought of roughly as whether some target vertex is related to some other specific vertex. In a social graph, most nodes will be readily identifiable based on the identities of their neighbors. The actual result in the paper is significantly stronger, requiring only a seed of relatively few matched nodes to iteratively propagate the matching along the graphs. Later work by Narayanan et al. generalized this further to link prediction on incomplete graphs.²⁷

The adversary holds two overlapping social graphs — one identified, one anonymized. The yellow correspondence edges mark the seed of confidently matched pairs, identifying their anonymous endpoints.

The only unidentified vertex adjacent to both seeds must be Carol’s, so it’s matched first.

Each match extends the frontier: Dave’s vertex is the remaining neighbor of Bob’s, and Erin’s is the remaining neighbor of Carol’s. The graphs don’t need to agree exactly — the vertex with no counterpart in the auxiliary graph simply remains unmatched.

Suppose the adversary starts with an incomplete clustering of Bitcoin transaction outputs. While the clusters do link together some outputs, because it’s incomplete, there may be several clusters per actual user. So long as the adversary still hasn’t collected enough evidence to conclude that several clusters belong to the same user, that user still enjoys pseudonymity.

This adversary doesn’t just apply CIOH blindly. When it’s first observed, a transaction suspected to be a PayJoin, for example, will have four or more related clusters. Each entity will be represented by at least one input-side cluster and at least one output-side cluster. Naive CIOH would compel merging of all of the input clusters, and change identification may additionally link it to one of the outputs. Subsequent transactions will in turn link to those. The ensuing cluster collapse will of course be avoided by any competent adversary.

Starting with the transaction graph, where coins are vertices, let clusters be represented by undirected edges connecting the linked coins. By edge contraction on these edges, a graph minor analogue²⁸ can be obtained from a given clustering, where all of the coins of a particular cluster are fused into just one vertex representing the cluster itself. The residual edges of this multigraph correspond to transfers of Bitcoin between clusters, so those relationships remain available for analysis.

Reid and Harrigan’s paper⁴, in its discussion of clustering, introduced the notion of a user network, where vertices are users and edges represent the flows of Bitcoin between them. If the clustering is complete, and each user can be identified with just one node on the contracted graph, that is the user network. Otherwise, when the clustering is incomplete, this cluster graph is better thought of as a pseudonym graph rather than a user network. This is a social network per Shmatikov and Narayanan’s definition.²⁹ The statistical feature distributions of clusters reduce to attributes on the vertices, and both those and the topological features can inform the edge attributes used in their algorithm.

Narayanan and Shmatikov’s propagation algorithm starts with two graph views and a seed correspondence between some of their vertices. Contracting the entire coin graph gives us only one view. To obtain several, we could first partition the cluster-annotated coin graph, for example into epochs, and then contract each subgraph separately. Each resulting graph minor analogue would then present a view of the pseudonym graph over a different period.

Existing clustering supplies the seed correspondence. If a coin in one epoch is already linked to a coin in another, their cluster vertices form a seed pair. Address reuse, heuristics applied to boundary transactions, or auxiliary information can supply such links.

The more active a user is, the more data they expose. Consistent economic relationships can also make their neighborhood recognizable across epochs. Where the views preserve enough of this structure and the adversary has suitable seeds, Shmatikov and Narayanan’s graph matching algorithm can propagate clustering information beyond local heuristics. A proliferation of pseudonyms may limit any one run of the propagation algorithm, but high-confidence matches can still inform other clustering heuristics, and the outputs of other clustering heuristics can be used as inputs to this algorithm.

Epochs are also only one way to partition the coin graph. Another approach would place the boundaries at high-ambiguity regions, where many clusters seemingly connect to many others, as CoinJoins tend to produce. Excluding those densely connected regions can leave components in which each cluster has relatively few neighbors. The adversary can then compare components from different partitions.

As a crude analogy, this is the “opposite” of expander decomposition, a technique that partitions a graph by making sparse cuts in order to decompose a graph into several components, while retaining strong connectivity within each component. Here, the adversary instead decomposes the graph along dense, high-ambiguity regions in order to obtain sparse components whose relationships are easier to match to one another.

Some clustering must already have been produced by another technique for this to work, hence the starting assumption that the clustering is partial. It both supplies the annotations that make contraction possible in the first place and provides the seed correspondence from which graph matching can propagate.

So, even when net settlements call amount-based analysis into question, and the number of parties complicates things further, the nature of social networks and of the transaction graph is that over time, a lot of structure will inevitably be revealed. There’s an expression that illustrates this; I think it goes something like “show [the adversary] who your friends are, and [the adversary] will [successfully deanonymize you].”

Equal amount CoinJoin among arbitrary peers

Every construction so far required its participants to be doing business with one another: a payment, a batch of payments, a settlement of mutual obligations.

A CoinJoin doesn’t have this limitation.³⁰ The participants of an equal amount CoinJoin transaction spend their inputs to produce outputs of the same amount and script type. Traditionally parties are assumed to not be related except in that they are participating in the same transaction, which implies there are no payments settled between them apart from any fees related to the transaction itself, which tend to be low.

The equal outputs are interchangeable, but the change outputs remain linked to the inputs by their amounts, and Bob’s two inputs are linked to each other by the consolidation forced by a minimum denomination requirement.

PayJoin transactions are made when one party intends to pay another, but in CoinJoin transactions no such relationship between the parties needs to exist. This means they can be chosen randomly from a broader population rather than be constrained by the structure of the real world user network and its economic relationships. While it may seem that this already confounds social-graph analysis, this type of CoinJoin is readily identifiable. A cautious adversary can decline to apply CIOH within it, leaving additional cluster pseudonyms, while still matching the implied user graphs on either side.²⁶ Observable flows between apparent clusters elsewhere in the graph can still expose recurring economic relationships and therefore community structure.

What it can do is introduce uncertainty about the origins of a coin, limiting the ability to perform input-side clustering for any subsequent transactions as well. This slows the rate at which certainty can be gained about clustering structures, but it isn’t a comprehensive or robust defense, and over time, such structures will generally be revealed.^{31 32}

Unfortunately, linking inputs to one another is practically inherent in the equal-amount approach.³³ Users generally cannot choose incoming payment amounts or outgoing-payment change to match a CoinJoin denomination, so reaching that denomination often requires combining inputs and almost always produces change. This change is also relatively easy to link to the input clusters, as discussed in the next section.

Turning to the equal amount outputs, their order is presumed to be meaningless, so as long as they’re unspent, they’re interchangeable. But this doesn’t last indefinitely. Any spending transactions of these outputs will reveal more information about an output’s ownership through its timing, fingerprints, and other information that can be incorporated into the adversary’s clustering model.

Furthermore, even though such a transaction only spends a single output, any change left from the payment will, in general, not be of a specific denomination either. To avoid harming the privacy of the payment transaction, this change shouldn’t be linkable to the spender’s other on-chain activity, but even if spent into a CoinJoin, the equal amount approach necessitates consolidating multiple such coins together, which potentially links many “anonymous” transactions to each other, and to subsequent transactions via the change from the CoinJoin.

For example, suppose Alice obtains two seemingly anonymous coins from two independent CoinJoins of the same denomination and spends each in its own payment:

Two mixed coins spent independently: Each payment is ambiguous, and nothing links the payments to the same user.

Later, wanting to CoinJoin again, she consolidates the two leftover change outputs:

The consolidating CoinJoin links the two change outputs, which links the two payments and retroactively identifies Alice’s outputs in both of the original CoinJoins.

In other words, attempting to CoinJoin to recover the change and make it usable for private payments not only fails to achieve that goal, but also undoes the privacy of the previous transactions.

Arbitrary amount CoinJoin

So strict adherence to the equal amount approach leaks information about linkage after the fact. Naive batching, which we glossed over, does too, even without considering the wider context of the graph.³⁴

The Boltzmann link probability matrix³⁵ and Maurer et al.’s sub-transaction model³⁶ are two similar models. They employ a combinatorial approach: Count all the ways the transaction could be partitioned, grouping together subsets of the inputs and outputs into sub-transactions, which are assumed to be the actions of a single party in a multiparty transaction.

What exactly makes a partition a valid sub-transaction mapping is whether or not the sub-transaction is deemed plausible. In Maurer et al., the values of the inputs and the outputs must exactly cancel out, which isn’t sufficiently general for real-world analyses. Boltzmann casts a wider net by allowing these to vary somewhat, accounting for fees (including JoinMarket maker fees).

A large number of possible partitions does not by itself imply much privacy: Most of the probability may be concentrated on just a few of them. Entropy quantifies the uncertainty in this distribution, measured in bits.^{37 38 39 40}

When a sub-transaction mapping is underdetermined, more than one assignment of inputs and outputs to separate sub-transactions remains possible. If several assignments have comparable probabilities, the adversary needs further information to distinguish them. The entropy of the distribution implies a lower bound on how much additional information is required. Output values can be deliberately chosen to create many possible assignments.⁴¹

Carelessly chosen values are no better than a naive batch: The only sub-transaction mapping consistent with the amounts is 0.1 + 0.3 = 0.4 and 2 + 5 = 7, so a subset sum analysis fully partitions the transaction.

With values chosen to be underdetermined, three distinct mappings balance: The 0.7 output can be funded by 0.3 + 0.4, by 0.2 + 0.5, or by 0.1 + 0.2 + 0.4, with the remaining inputs funding the 0.8 output. Across these readings — and the single-owner one — no input is linked to either output.

Alternatively, the assumption that each participant’s sub-transaction is balanced (allowing for fees), can be invalidated. As discussed above, net settlement allows one participant’s surplus to cover another’s deficit while the transaction as a whole still balances. There’s no technical reason why economically related users couldn’t settle within a protocol that also admits strangers to the same transaction. This will also conceal their business relationships better than a purely net settlement transaction structure.

The adversary can also incorporate statistical features, topological features of the surrounding graph, and auxiliary information into its sub-transaction analysis. These can change the plausibility of a mapping which only accounts for the amounts. Neither variant of the model, as originally described, incorporates these additional observables. For this reason, neither net settlement nor overtly ambiguous CoinJoins can offer a comprehensive solution to these problems.

Taking provenance into account

Enumerating the possible points of origin of the funds of a particular coin is fairly intuitive based on the graph structure.⁴² The entropy of the probability distribution of this candidate set can grow fairly quickly by CoinJoining, especially if an effort is made to diversify peer selection.

However, it can also decay rather quickly. Suppose the adversary successfully deanonymizes some auxiliary user. This can have two very different outcomes:

• The coins of that user are eliminated as linking candidates when attempting to deanonymize the target user. This is an additive decay of privacy.
• In addition, the eliminated coins form the boundary between regions of the transaction graph, fracturing it. This is a multiplicative decay of privacy, and the adversary can make progress at an exponential rate when this is the case.

An entropy estimate based on on-chain observations measures uncertainty under the information available to that particular observer. It cannot represent the uncertainty remaining for an adversary with additional information, nor how quickly that uncertainty could shrink.

For example, a chain analysis vendor with KYC information may already be able to separate regions of a graph that still appears highly ambiguous to an outside observer. Users therefore need a safety margin chosen for the auxiliary information their threat model allows the adversary to have.

Robust connectivity

If the CoinJoin graph is robustly connected⁴³, then no small cut separates any output from the mass of its candidate origin coins. Stated differently, every output is connected to its candidate origins by multiple disjoint paths.

This redundancy forestalls the cliff of exponential decay, where privacy becomes much more brittle, extending the duration of the linear decay regime by requiring the adversary to deanonymize a much larger proportion of users before divide-and-conquer tactics start coming into play.

But when two post-CoinJoin outputs are linked, on-chain or otherwise, this makes intersection attacks^{44 40} possible. In such attacks, we take the candidate origins of these now-linked coins and check for any overlaps.

The adversary’s view while the CoinJoin outputs remain unspent: six outputs in two equivalence classes, each output ambiguous among its CoinJoin’s participants.

Alice’s spend links one output from each class. Tracing each input back — from spent output, through its creating CoinJoin, and to the pre-CoinJoin input clusters — gives the two antecessor sets, highlighted in yellow and red. These overlap only at Alice’s cluster, highlighted as the one node belonging to both: The intersection identifies her, and by elimination also narrows the remaining outputs’ candidate sets: CoinJoin 1’s to Bob or Carol, CoinJoin 2’s to Dave or Erin.

If each additional intersection reduces the remaining candidate set by a constant factor, its size falls exponentially with the number of observations. Starting from $n$ candidates, a process of elimination that rules out one candidate at a time will take $O(n)$ time to narrow down a single candidate, but if intersections are used to eliminate them then $O(\log n)$ observations may suffice for successful deanonymization.

This holds unless the size of the symmetric difference between antecessor sets is bounded by a constant — i.e. the antecessor sets of linked coins are very similar — because then the size of the intersection is similar to the size of the intersected sets. This attack is powerful because that similarity is rare in practice: The intersection will usually be significantly smaller than the sets themselves.

It’s also important to bear in mind that the candidate origins aren’t coins, but rather clusters, so the objects being intersected needn’t be connected on the transaction graph for the adversary to notice an overlap. This is particularly concerning because the clusters being intersected are the pre-CoinJoin ones, where — presumably — privacy is inherently weak. It’s also worth emphasizing that the change outputs of equal amount CoinJoins are part of these clusters as well.

Next, consider an adversary who is also a counterparty — for example, an ATM in some remote location that sells coins to a user in exchange for cash, and later receives funds from descendants of those coins. Such a counterparty knows, from its own records, exactly which coins it paid out and can observe when descendants of those coins are sold back to it. Connectivity to a crowd of strangers over the internet does little against this, because none of those strangers are likely to have transacted with the ATM, and the CoinJoin doesn’t sever the link from a coin to its past. By the same logic of intersection attacks, privacy loss arising from consolidation of more than one input doesn’t just add up; it compounds. This is known as the Eve-Alice-Eve threat model.

Own-origin robustness

The privileged counterparty knows one endpoint because it is the origin, so the property is stated relative to that origin. It demands that a coin have many plausible, counterfactual paths back to the user’s own antecedent coins.

Suppose Alice withdraws from that ATM, and that is her only means of obtaining Bitcoin. She then CoinJoins with Bob. If one of those coins is then returned to the ATM, its operator can conclude that it is likely Alice.

Taken in isolation, the deposited coin is ambiguous: It could be Alice’s or Bob’s.