[bitcoin-dev] CoinJoin Jigsaw

[Ryan Perkins <riperk@protonmail.com>]

Earlier today ZmnSCPxj posted to the mailing list with an interesting post about payjoin. In it he mentioned:

> Any non-equal-value coinjoin is easily solvable via [value sudoku](https://www.coinjoinsudoku.com/advisory/).

Which doesn't seem right to me.

I came up with something I call a "CoinJoin Jigsaw". A "CoinJoin Jigsaw" is send-to-self coinjoin transaction in which every input is ambiguously associated with an output (i.e. every transaction input must belong to at least one subset of every output amount).


For simplicity I've used minizinc to model this. To make it clean, I decided to model as two users (affectionately called 'A' and 'B') who trust a common party to orchestrate the CoinJoin Jigsaw for them. A and B don't trust each other, so they want to get all their money atomically in this one transaction. We also want the "CoinJoin Jigsaw" to have exactly 2 outputs. One for A, and one for B. That way at first approximation it looks like a pretty standard bitcoin payment. (Of course the problem is substantially easier to solve if we allow A and B to have N outputs, but that creates an ugly transaction).

We also need to make sure that both A and B are paying a fee proportional to the amount of inputs they added, and the total transaction fee is satisfactory.

So I've modelled it as A and B provide their utxo to the orchestrater. The orchestrater will pick the largest subset of A's and B's utxo and such that satisfies our CoinJoin Jigsaw properties. I ended up copy-and-pasting a lot more than I'd like:

https://gist.github.com/riperk/7be6698f291e865ad5c930d0edb0cd5a

I'm not sure it has much practical utility, but it's kind of cool. Maybe.