The Many Faces of CoinJoins

Written by Spiral’s Bitcoin Wizard not_nothingmuch.
What even is a “CoinJoin?” The long answer is: “it depends.” The tl;dr is: it means any kind of multiparty transaction, which technically makes Lightning a kind of CoinJoin. ;-)

In 2013, Greg Maxwell posted the following in the Bitcoin Forum:https://bitcointalk.org/index.php?topic=279249.0 Although this wasn’t the first account of breaking the common input ownership heuristic using theft-resistant multiparty transactions¹, as far as I know it’s the first concrete description of multiparty transactions where the output values are the same²:
"To use this to increase privacy, the N users would agree on a uniform output size and provide inputs amounting to at least that size. The transaction would have N outputs of that size and potentially N more change outputs if some of the users provided input in excess of the target. All would sign the transaction, and then the transaction could be transmitted. No risk of theft at any point."
A diagram was also included, and although the original URL is now broken a copy still exists on the related Bitcoin wiki article:

Note that the address 1A1 is used twice, strongly implying that the same entity owns the first and last inputs of Transaction 2. The post continues:
"In the illustration 'transaction 2' has inputs from 1A1 and 1C3. Say we believe [sic] 1A1 is an address used for Alice and 1C3 is an address used for Charlie. Which of Alice and Charlie owns which of the 1D and 1E outputs?"
The symmetry of this transaction structure makes every permutation of the same valued outputs equally plausible, at least when looking only at the transaction. If a single transaction is seen as a “data release” in the sense of the literature on k-anonymity, then assuming all of the attributes (the amount and the script type) are the same for k of the outputs, then this satisfies the definition of k-anonymity. Unfortunately, as discussed in the previous post, this does not adequately account for privacy leaks from multiple transactions, how they are related.
k-anonymity might be a reasonable model for CoinJoin privacy in principle, if the entire blockchain were seen as a continually appended data release. Unfortunately because transactions are connected in a graph structure the attribute set must also describe how every coin relates to every other coin in this graph, e.g. is one an ancestor of the other? This is a potentially quadratic growth in the number of attributes, but much worse, the number of possible quasi identifiers grows exponentially in the number of attributes. It is impossible to make rigorous claims about the k-anonymity of a particular coin meeting some threshold without accounting for the context in which the coin was created and the context in which it has been or will be spent. Showing that k is greater than some threshold, even with this proliferation of relevant quasi-identifiers, is possible in some specific transaction graph structures. Still, in general, this theory is intractable for any meaningful threshold.

Maxwell’s post is explicitly more general than just this highly symmetric approach. Another example in the post was that of collaborating to make batch transactions by aggregating several independent payments, or sub-transactions:
"The idea can also be used more casually. When you want to make a payment, find someone else who also wants to make a payment and make a joint payment together. Doing so doesn't increase privacy much, but it actually makes your transaction smaller and thus easier on the network (and lower in fees); the extra privacy is a perk."
This was implemented more or less literally in SharedCoin, which indeed didn’t increase privacy much, as demonstrated by Kristov Atlas. The basic idea behind this analysis was that even if the inputs and outputs of a transaction were shuffled, related inputs and outputs can often still be uniquely partitioned just by assuming that the input and output values in each sub-transaction must be more or less balanced. The common input ownership heuristic can be seen as a degenerate special case of this theory, where the partitioning only contains one sub-transaction, implying that everything is linked to everything else.
LaurentMT used a probabilistic approach in Boltzmann, which accounted for when there was more than one unique partition satisfying the balance requirement. By enumerating and counting the different possibilities, and then normalizing these counts to a probability, this makes an estimate of how likely it is that inputs or outputs might be linked to one another. Sub-transactions are allowed to be only approximately balanced, considering things like JoinMarket’s maker fees.
Later work by Maurer et al introduced a double counting correction, distinguishing between so-called derived and non-derived sub-transaction mappings (their term for the partitioning as a whole), and only counting the latter. This work neglects to account for fees entirely, working in a more idealized setting.
Although the total number of partitions of a set of size n—which is given by the nth Bell number—grows very rapidly, the subset of those partitions that satisfy this condition that the amounts are balanced may be very sparse within it. It is tempting, but incorrect to conclude from the rapid growth of the space that the complexity of finding some sparse set of solutions in such a vast search space is enough to protect privacy.
The reason this misconception is tempting is that the closely related problem of subset sum is NP-complete, which means that it’s possible to construct a specific subset sum instance where finding a solution is not just as difficult as, but equivalent to, just as an example, finding a SHA256 preimage for a specific hash. However, what NP-completeness does not guarantee is that all or even most subset sum problem instances are hard. This is why the Merkle–Hellman knapsack cryptosystem was broken, and other Knapsack cryptosystems rely on hard special cases of subset sum. Linear programming is often practical for enumerating sub-transaction mappings of bitcoin transactions, even those of considerable size.
What can provide a meaningful assurance is knowing that solving for the sub-transaction mapping is underdetermined, i.e. that there is more than some threshold of seemingly valid, non-derived sub-transaction mapping, or more precisely, that every input or output co-occurs with many other inputs and outputs in a varied collection of equally plausible but dissimilar sub-transactions across the range of sub-transaction mappings.

In a PayJoin transaction, which the Bitcoin Wiki describes as a “special type of CoinJoin,” the sender and receiver of a payment both contribute inputs.
Although the following excerpt from Maxwell’s post is overly optimistic in relation to multiparty batching, PayJoins attempts to realize the described indistinguishability property:
"Such a transaction is externally indistinguishable from a transaction created through conventional use. Because of this, if these transactions become widespread they improve the privacy even of people who do not use them, because no longer will input co-joining be strong evidence of common control."
For this to hold, the so-called “unnecessary input heuristics”[1, 2] must also hold within the transaction. For example a transaction that spends two coins, say a 10 and a 4 to create two outputs worth an 8 and a 6, that raises the question of why it shouldn’t just use the 10 to create either an 8 and a 2, or a 6 and a 4, presuming either 8 or 6 is the intended payment amount. Although there are exceptions, such a transaction is somewhat unusual considering the distribution of transactions most wallets would construct, which would typically avoid unnecessarily using the second input as that would result in higher fees.
This type of analysis can be extended beyond just the values. As briefly mentioned in the post before last, wallet fingerprinting is not as well studied in the context of wallet clustering as perhaps it should be. Although it remains an open question, it appears likely that this can be used to attack PayJoin’s privacy, but it’s also possible to mitigate this concern. This is something we’re looking into as part of PayJoin Dev Kit, so if you’re interested in this kind of thing, please join our Discord!
Another way of describing this steganographic property of PayJoins is that interpreting these transactions using the sub-transaction model will almost certainly assign both the sender and the receiver’s inputs and outputs to the same sub-transaction. This is because a significant net transfer between them upsets the balance invariant, the definition of a sub-transaction mapping case excludes what actually happened.
Breaking the sub-transaction invariant aids privacy even if we assume a hypothetical PayJoin aggregation mechanism that allows multiple senders and receivers to collaboratively construct a single transaction, something that would certainly not be distributed like “conventional use”. Although such multiparty PayJoin transactions could no longer be described as steganographic, seeing as they stand out, the missing information about the payments between participants makes clustering significantly harder. The more interconnected this activity, the more naive application of the theory of sub-transactions would lead to cluster collapse.

In the opening paragraph I framed it as a joke, and although I’ve previously mentioned it, let’s consider this angle a bit more seriously and fully here, because it does emphasize some aspects of Lightning that aren’t very widely discussed, and which aren’t as obvious when using a more sensible mental model to think about how Lightning works.
A Lightning channel is a multisig UTXO owned by two parties sharing a channel. The transaction that creates it is its funding transaction. Some channels are funded by only one party, but some are dual-funded, meaning both parties contributed to the channel’s initial balance. The Lightning protocol ensures that at every point in time, either party to the channel can close it unilaterally (without depending on the counterparty’s cooperation). Closing means the UTXO gets spent into a transaction that fairly distributes the channel funds between them, according to a balance they both agreed to. Payment channels are valuable because this balance can be securely updated if both parties agree, and this update happens off-chain, without needing to spend the shared UTXO, which means that it’s a cheap and instant way of transferring bitcoin. Lightning channels in particular are even more valuable, because they also allow payments to be routed: channels are edges of a graph, linking together pairs of nodes, and payments can flow along a path of edges, between nodes that aren’t directly connected by sharing a channel.
If everything goes smoothly, channels are closed cooperatively. In this scenario the channel UTXO is just spent into a transaction that settles the balance by creating two outputs. Unilateral closes also do this, but reveal more information and have a different on-chain footprint. We’ll ignore that here. Let’s also assume for a moment that the adversary we’re concerned with has no visibility into what happens off-chain, all routed payments have perfect privacy against this adversary. If all this adversary can see is the transactions that eventually confirm on-chain, then it would see a funding transaction that spends one or more coins to create a multisig coin (and maybe some change outputs). Then this multisig coin will be spent, creating two outputs, likely different amounts than what went into the funding transaction, each belonging to a different wallet. If it weren’t for the intermediate multisig coin, that all would sound a bit like a “conventional” payment transaction, or if the channel was dual funded, a PayJoin.
In reality any adversary would be able to collect Lightning gossip data as well. For payments to be routed, nodes must have a view of the channel graph, which is what this gossip data makes possible. Publicly announced channels overtly and publicly link a pair of nodes. Although the clustering of multisigs is more nuanced than we’ve previously discussed, you might say that a Lightning node’s ID being linked to its channel (U)TXOs is a form of address reuse, and it wouldn’t be stretching the truth by that much. For the two outputs of a channel closure, there are two clusters related to the node IDs. Deciding which of the two clusters to assign each output to is relatively easy, since other channel openings and closures would be linked to each node, as well as any the preceding or succeeding transactions to which each cluster might extend.
In other words, if we insist on thinking of Lightning as a strange form of CoinJoin or PayJoin, then its privacy guarantees are not very strong from a wallet clustering perspective. Please do not misread the previous sentence, it says nothing about the privacy of Lightning payments, which is by all accounts better than that of on-chain payments. Nor should the last sentence imply Lightning privacy is perfect. Anyway, the specific concern highlighted by thinking of Lightning channels as a weird 2 party CoinJoin is only to do with the on-chain footprint related to node opening and closing public channels, and the degree to which those funds can be clustered due to the non channel TXOs. This is also a good example of when clustering relevant information that isn’t recorded directly in the blockchain is still publicly available.

Generalizing further, within each transaction we might consider the inputs and outputs being connected in a weighted, complete bipartite graph, or even a complete graph (i.e. also allowing input-input links and output-output links to be represented). The weights on the edges indicate how related coins are. Indeed, there is no reason to stop at the boundary of a single transaction: all coins may in principle be related to all other coins, a probabilistic generalization of wallet clustering and inter-transaction relatedness, not just of the sub-transaction model and intra-transaction relatedness.
The specific values assigned as these weights could be based on any other theory, such as the intersection attacks discussed in the previous post, external data sources like leaked xpubs,³ KYC information or proprietary clustering labels, or even something as trivial as address reuse.
And it can also go the other way. For example if it was widely accepted as true that transactions using CoinSwap⁴ are being created, even if it isn’t actually true, then anyone who knew this was widely believed and honestly attempts to assign weights in the linking graph would be compelled to account for that contingency and admit some degree of uncertainty, or argue to the contrary while bearing the burden of proof. An estimate of the upper limit of potential Coinswap usage for a more limited design was made in a 2017 paper by Malte Möser and Rainer Böhme. Chris Belcher’s CoinSwap design compels the analysis to cast a much wider net. That said, it has not yet been fully implemented. Hopefully P2TR MuSig2 and multiparty ECDSA support will be added at some point, because even if those script types don't get much use, the fungibility of coins of all types will improve as a result. The more it is true that for all anyone receiving a coin knows, it could have potentially originated from a CoinSwap (even if that’s not very likely), the weaker the theories of chain analysis become. Consider a scenario where a website breach leaks home addresses and bitcoin payments, and a large UTXO was used for one of these payments. A world in which it’s plausible that this UTXO belonged to a CoinSwap maker would be safer for this unfortunate customer, even if they never did a CoinSwap themselves. How much safer depends on how widely held a belief that is.
This extends even to nonsensical, dare I say religious theories of input and output relatedness which have been proposed, such as FIFO,⁵ or ordinal theory. The unfortunate consequence of meme magic is that such theories can in some sense become good theories merely by inhabiting people’s minds so that they end up shaping people’s actions, so that the trail of transactions that will be left behind can after the fact be correctly interpreted using the theory. Much like you shouldn’t take seriously anyone who tells you, without qualifying, that bitcoin is private, you also shouldn’t believe anyone who tells you bitcoin can’t be private. The outcome primarily depends on whether people who use bitcoin for commerce also use bitcoin in a privacy preserving manner. It may be unfortunate that this isn’t easy to do, at least with the current state of most wallets, especially not without deliberate effort, but I feel like the most embarrassing way to destroy Bitcoin privacy is if everyone “knows” it’s a lost cause because of some silly superstition.

In this post we’ve looked at the more theoretical side of CoinJoin privacy as it relates to different notions of the term, and then strayed a bit further than the CoinJoin sandwich alignment chart to see how these ideas can help make sense of Bitcoin privacy more broadly. The theory tends to emphasize the attackers’ perspective, since it’s often useful to reason about how hard it is to break privacy by understanding the attacker’s capabilities and finding the weaknesses. Although there is a lot more that could be said in theory, the next post will focus more on the defenders’ side, and discuss some of the practical challenges of designing a privacy preserving CoinJoin transaction structure.