public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
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.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
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