Adam Gibson, the expert at CoinJoin anonymization method for bitcoin transactions, outlined the operating principles of the enhanced CoinJoinXT system during Build on Bitcoin conference that took place on July 3-4 in Lisbon, Portugal.
There is a general perspective that bitcoin is perfectly traceable. The entire history of a coin is not entirely traceable but people think it’s traceable. There is an intrinsic fungibility of bitcoin. Imagine gold jewelry – if you have several pieces of gold jewlery, it’s melted down, and it’s a bunch of gold atoms, and they are all the same and perfectly fungible, but then when you recast that gold into new pieces of jewelery, then you can’t tell which output or which piece of gold jewelry corresponds to which original piece.
In bitcoin transactions, if you have multiple inputs and outputs, you can’t say that bitcoins from output one corresponds to bitcoins in output two. It’s not just difficulty of calculation, it’s simply that no such correlation exists.
I want to straight away talk about CoinJoin and how it’s used today. This is an example of how CoinJoin is used today– it’s an example of a JoinMarket CoinJoin transaction. If you have good eyesight, you will be able to see that there are several exactly-equal sized outputs. The idea of CoinJoin as it’s been used so far, or in earlier wallets like dark and so on… the idea was to use same-size outputs so that it’s not possible to distinguish any of the exactly equal-sized outputs at least at the level of the transaction. There’s no analysis you can do on the transaction to distinguish those outputs because they are exactly the same amount. That’s how we use CoinJoin today.
What I want to do in this talk is to distinguish between that approach to using what fungibility exists in bitcoin and amplifying it with that method… and distinguishing that with deniability, which means… here, what we have is a fixed pattern where it’s easy to identify that these transactions are of a certain type, there’s been work by guys at Princeton in blocksci to write an algorithm to identify CoinJoin transactions on the blockchain.
The idea is that you sign the last transaction first. Segwit is the foundation of this technique. We have transaction ID malleability fixed. We can prepare a transaction, such as a funding transaction, and then instead of signing it or broadcasting it, we can get its TXID and use that to construct refunds, locktimes, or proposed transaction graphs (PTGs). We can prepare all of these sets of transactions and not broadcast them. We need to both have some control over transactions in the set. We only sign the funding transaction at the end, making the whole thing atomic. The entire set of transactions will only occur if we both agree, or you can do things like “if at least one of us wants them to go through then they will all go through”.
This construction is limited because it all starts with a single transaction up here. It could be a tree, rather than a chain, but it’s still got one unique entry point on to the blockchain. If we’re trying to make life more difficult for blockchain analysis, then that’s a limited model.
Promise UTXOs and unilaterally-controlled coins to improve the proposed transaction graph
We can extend this model where we add a promise. This is a promise UTXO here. The idea is that instead of only having one entry point into the graph of transactions here (which are co-controlled and pre-signed by the two parties), we can have other entry points, where Alice adds another UTXO from her own wallet, of whatever size, and we call that a promise UTXO. In a sense, it breaks the atomicity of the structure. If Alice and Bob agree to broadcast the transaction and Alice double spends A1 before we reach TX3, then it may not go through… so we’ve broken the atomicity if we allow unilaterally-controlled UTXOs to enter into the graph at some point in the middle. We need to use a refund transaction with a timelock before that transaction goes through. It’s a tradeoff. By adding these promise UTXOs, you’re able to add many origins to the graph.
We can make these graphs in any structure we like. So we have two different promise UTXOs here, and there’s a huge design space we could be exploring here. There are some dual-control UTXOs. Every time there’s a promise, there has to be a backout transaction that is timelocked on the previous transaction.
Other features to bear in mind – we have been looking at Alice and Bob but this works just as well for n-of-m and 2-of-2.
The other thing to observe is that I gave Alice some equal-sized outputs. There’s another kind of variable in the design space here, if you choose to use equal-sized outputs, you get that intrinsic fungibility but you lose deniability a little bit because you can no longer pretend this isn’t mixing activity going on. It’s possible for equal-sized outputs to not be CoinJoined, but people might say generally they are.
The other thing I will mention before I move on, what about practicality of this? I want you to understand that while it looks complex, it’s actually not more interactive than simple CoinJoin. The interaction between the two parties is simple – they are just sending keys and so on, but they are only agreeing upfront on the template of the graph. It doesn’t require more interactivity. CoinJoin is interactive, but not cross-block interactive where you wait for confirmations. So, that’s still true here, even though it might seem more complex.
These dual-control UTXOs, like 2-of-2 multisig between Alice and Bob on some of those coins… At the moment, if we use those, it’s a negative for deniability in that they are identifiable as that particular kind of pay-to-witness scripthash or 2-of-2 multisig or whatever… But we hope that there’s a Schnorr multisig option that might hide n-of-m keys into 1-of-1 key with the same anonymity set. And there’s also ECDSA multisig stuff that some guys have gone into recently.
There’s quite significant problems with using this approach if your intention is “deniability”. If you want to make structure of transactions that don’t look like CoinJoins but are CoinJoins, then you might still suffer from amount correlation. In one of the early versions of Joinmarket, you could work out a set of inputs corresponding to a certain set of the outputs, due to the way that the output amounts were determined. If we avoid using equal sized outputs, then Alice’s outputs added up are going to add up to Alice’s inputs. This is not payment – it’s her mixing coins with Bob in theory. It doesn’t work well if you can do subset sum analysis and look at the sums to find out who owns what. If you look at subset sum, theoretically it’s exponential time, but in the weeds, subset sum is practically realistic in general. Maybe it would be difficult in this case because the boundaries aren’t clear to the attacker so maybe the blockchain analyst is bad at finding the correct set of transactions, but maybe he’s able to find that correct subgraph of the blockchain with subset sum analysis.
You can tweak this and use Lightning to make subset sum analysis not work. We still have a set of transactions we negotiate upfront. And then we sign the funding transaction. Well, Alice has 2 inputs, Bob has 2 inputs, they each got 1 output, and there’s a third output, which is a dual-funded lightning channel. The usual thing would be to look at sets of inputs and try to add them up, but they are trying to figure out if this input or whatever belongs to Alice or Bob, and he has to figure out the lightning funding transaction as well… He wouldn’t initially know that it’s lightning, but maybe after it’s closed he would. He doesn’t actually know the initial channel balance between the two parties. So he can’t make a subset that corresponds to any of the inputs elsewhere. Subset sum analysis doesn’t work in this situation. Once the lightning channel closes, then these two numbers are exposed on to the blockchain with the closing balances. If the closing balances are the same as the starting balances and you never used the lightning channel, then subset sum analysis can work again, and the transaction analyst can do their analysis with the blockchain again and find the subgraph. But the whole point of Lightning Network is that you can make payments to other parties. If you leave the channel open for a while and use it, then your balances can significantly change, and then it would be such that there’s never any case where subset sum can work. This is a way of trying to get the Lightning Network’s inherit privacy by HTLC paths and so on, to get that to bleed back int othe main chain.
This has limitations, obviously, like the amount of bitcoin you can send on Lightning channels. If you look at the inputs and find the amounts are much larger than Lightning can handle, then you are asymptotically falling back into the CoinJoin analysis model. For large amounts of money, Lightning is a dubious security model, so maybe we can use equal-sized intrinsic fungibility CoinJoins. Moving between large and small, maybe CoinJoinXT with Lightning could be interesting. There’s a large design space here.