Use an SMT solver to make better CoinJoins

[csH7KmCC9]

Please see this proof-of-concept. This sets up an example CoinJoin, encodes the CoinJoin constraints into a satisfiability modulo theories problem, and uses PySMT with an off-the-shelf SMT solver e.g. from Microsoft.

The key advantages of this approach are:

• There is no more guessing and fuzziness about tx fees
• We can use it to put more outputs (i.e. change outputs) into a non-singleton anonymity set, potentially improving the privacy of makers

Consider the default CoinJoin example from my repo. We have four inputs from three parties, in amounts 1BTC (from the taker who is doing a sweep), 1.3BTC (from the second party), and two inputs totaling 1.4BTC (from the third party). In the current implementation, we might get CoinJoin outputs like (party, amount): [(1, 99997329), (2, 99997329), (3, 99997329), (2, 30002682), (3, 40002676)], which includes two outputs that are uniquely identifiable.

In contrast, here is the solution found by the SMT-based approach: [(1, 99997329), (2, 99997329), (3, 99997329), (2, 9999994), (3, 9999994), (3, 9999994), (2, 20002688), (3, 20002688)], which includes zero outputs that are uniquely identifiable. Of course, subsequent behavior of the maker could reveal the association between outputs, but a similar approach can be taken to use an SMT solver to choose the least-revealing set of UTXOs for a maker to use for a given offer.

Note that this is just a proof-of-concept, and the final implementation probably should not take the extreme of trying to minimize unique outputs at all costs, as the extra outputs primarily cost the taker but give privacy benefits to the makers. Of course there will need to be some protocol tweaks, too, to enable the communication to the taker of more than one change address per maker.

[undeath]

I think it's a really interesting idea. It would need some sensible upper limit for change addresses, maybe 4 or 5. Where it becomes tricky is when thinking about the target mixdepth.

1. Should all change output, even the non-identifiable, go back into the same mixdepth?
2. Should they go into the next mixdepth and potentially be combined with the "main" coinjoin output later? Would that have implications regarding the privacy of their originating coinjoin transaction?
3. Should the non-identifiable change output go into different mixdepths each? To me, this would seem like the best separation. However, it blurs the borders of the mixdepths and privacy level of the funds in a mixdepth.

And, as you already noted, the implementation requires a protocol update. How would takers/makers ideally communicate the maximum number of acceptable change addresses and the addresses itself? One possible solution would be for makers to supply X change addresses, where X is the upper limit of change addresses. This would mean they probably "burn" a lot of addresses that are never used and cannot be used later, just like with any transactions that are not broadcasted.

[csH7KmCC9]

One possible solution would be for makers to supply X change addresses, where X is the upper limit of change addresses. This would mean they probably "burn" a lot of addresses that are never used and cannot be used later, just like with any transactions that are not broadcasted.

From my experiments, maximum 2 change outputs per party seems to work OK, but there is lots of room for further experimentation. Too many outputs increase transaction costs, make a more difficult SMT problem, and fragment UTXOs so I think this should not be too high. And yes, this will burn more addresses, but that's not really a problem, right?

I think the change outputs should all go in the same mixdepth, but:

• The UTXO selection algorithm should be updated to encode linkability constraints into a SAT problem and choose UTXOs that do not violate those constraints. One effective but perhaps over-conservative linkability constraint is for a party's UTXOs from the same CoinJoin never to be spent together. In fact this approach can be extended to also encode UTXO mixdepth and eliminate the need for fancy wallet architecture, or even supersede the concept of mixdepths entirely. Instead the wallet would store Just a Bunch of UTXOs (like a regular HD wallet) but treat each UTXO as the special snowflake that it is, with its own set of spending constraints that help to enforce mixdepth (and/or anonymity set cardinality) constraints and limit information leakage.
• The transaction signing code should be updated to verify that those linkability constraints are not violated (this is extremely fast vs. solving the problem in the first place), warn the user that they are compromising their privacy, and require manual override to continue.

Linkability constraints can be stored in the wallet file and in fact be recovered from the blockchain and wallet history, as long as the blockchain is rescanned from the first wallet transaction.

[chris-belcher]

As you say this idea has a problem of incentives, because the taker pays but the maker benefits. (even if in many ways privacy is an externality, and nobody is private unless many people are private).

Perhaps a way to fix the incentive problem is to somehow use coinjoin fees? Maybe have takers pay less coinjoin fees to the maker if they create more coinjoin outputs. Or something (I'm brainstorming here)