Walletwasabi: [RESEARCH] coin selection for receiving PayJoin

[MaxHillebrand]

This is an issue to discuss and research on coin selection for the receiver of a PayJoin transaction. I find this an interesting exercise, regardless if #3582 gets merged or not.

With PayJoin, the receiver of a transaction takes some of his coins [at least one] and adds them in the input. The receiving output is increased in value by the sum of the values of the inputs. So basically, the receiver consolidates some of his coins and the potential receiving coin into one single UTXO.

Due to the nature of PayJoin, it is inherently non-trivial to fingerprint that this transaction in fact is a PayJoin. Thus, it confused the common ownership input heuristic and is a net privacy benefit for the whole ecosystem [even non-PayJoin users]. I think that it is good to try to avoid the detection/fingerprinting of PayJoin, and this should be kept in mind for coin selection.

Wasabi "solves" coin selection for the sender, by having labeled addresses, and thus building clusters of the observers of a specific coin. The sender should try to keep this cluster small, and not grow it unnecessarily. For example, if the sender has a coin observed by Alice, and now he pays her, then he should use the coin that Alice already knows about.

With PayJoin however, the receiver, too, should consider which coin to use in the input of the PayJoin transaction. I think there are several options with different trade-offs. But I do think that this should be done automated, and not with manual coin selection as currently when sending in Wasabi - simply to not clutter UX even more...

Stay in same cluster

Like the example above, if the receiver has a coin that is already known by the sender, then he can use this coin in the PayJoin. This means that the sender does not gain any additional information about the wallet of the receiver.

However, if this coin is of a previous PayJoin between the same sender and receiver, then this is a chain of PayJoins that snowball to an ever larger value.

Previous PayJoin output

The receiver can use a coin that of a previous PayJoin output, regardless is from the same sender or not. "This" coin will get ever larger with every PayJoin transaction. The benefit is, that eventually it might be large enough to meet the minimum denomination of Wasabi CoinJoins. The downside is, that it might be fingerprinted that the graph with this coin is doin PayJoin, and then the payment output + change can be identified again.

Anonset CoinJoin output

The receiver can use an anonset Coinjoin output, here the sender does not gain any knowledge of the pre-mix history of the receiver. The receiving output however now has a cluster of the sender. This might be considered bad, as the receiver used to have a "perfectly private" coin, that is now again in a cluster of the sender.

This gets interesting however if the sender also uses an anonset CoinJoin output - as this would again indicate common input ownership / participation in two different CoinJoin rounds - but of course it is not.

CoinJoin change output

For CoinJoin change outputs, an attacker can do subset sum analysis to link them to the input - thus they should not be considered private. So, when the receiver adds a CoinJoin change to the PayJoin, then the naive common ownership heuristic would say that the the change belongs actually to the sender too. So, even when an attacker breaks the subset sum analysis, he might get confused by this PayJoin transaction.

I'm not sure, but I think that using change coins for PayJoin is a great way of handling them!

[lontivero]

This is a very real thing to have in mind during the development of a payjoin receiver. I faced this problem while coding the wasabi payjoin server PoC.

As @MaxHillebrand says, the sender should learn as less as possible and there are many possible non-mutually-exclusive solutions with their pros and cons but I would separate them in two big categories: automatic selection and manual selection.

Automatic selection

• Automatic selection: the idea is to make the receiver as smart as possible by selecting those coins that reveal less information to the sender about the receiver's wallet.
• Automatic selection (with help): the idea is to use the generated address label to help the coins selector to choose the best coin (one already known by the sender)

According to these ideas, coins should be selected in the following order:

1. Coins already known by the payee,
2. Coins used in payjoins with the same participants,
3. Coins with high level of privacy. (good, some, few)
4. Other aspects are important too, height, amount, confirmed, banned, ect.

Manual selection

• Manual selection for payment: the idea is to associate a coin to the payment uri (eg: bitcoin:bc1q4p.....?pj=http://i34h7swq8...onion/<token-identifing-the-coin. In that case the uri depends on the selected coin. Another alternative that I would prefer is a different onion address for each coin.
• Manual pre-selection: the user could _mark_ in some way which coins he wants to use for payjoins. This is probably the worse alternative but it could be use together with Automatic selection (help to improve the selection). The good part is that given in payjoin the transaction has to be signed automatically without user interaction, coins in password-protected wallets, hardware wallets and watch-only wallets cannot be used. Having a wallet without password for this could be good.

Other even more controversial selections

• use dust coins for payjoin. In case we have a dust coins comming from a kyc service or with a big history (many observers in the cluster), we could use them. The payer can learn the history of that coin and the amount (we lose privacy here) but on the other hand we are fooling the old observers (we gain some privacy too).
• Coinjoin change is also a possibility.