From: Ryan Perkins <riperk@protonmail•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] CoinJoin Jigsaw
Date: Mon, 22 Apr 2019 19:22:52 +0000 [thread overview]
Message-ID: <kZwZOekiYq3oxv7wgNj57KJqpOP0a2lkwM-TXsROtIDW5M8VunVV7majgvia4uo_bF3LxJn-8IOYN3IHBy25gjEN-OmPt-T47068L6s5ycE=@protonmail.com> (raw)
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.
reply other threads:[~2019-04-22 19:23 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='kZwZOekiYq3oxv7wgNj57KJqpOP0a2lkwM-TXsROtIDW5M8VunVV7majgvia4uo_bF3LxJn-8IOYN3IHBy25gjEN-OmPt-T47068L6s5ycE=@protonmail.com' \
--to=riperk@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox