public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: nopara73 <adam.ficsor73@gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
Date: Fri, 27 Dec 2019 14:03:49 -0400	[thread overview]
Message-ID: <CAEPKjgdtgDbyLoj6FV+cjY1Djca_FBtd9Kt_eB4zWU+at=wfYQ@mail.gmail.com> (raw)

[-- Attachment #1: Type: text/plain, Size: 2434 bytes --]

The CashFusion research came out of the Bitcoin Cash camp, thus this
probably went under the radar of many of you. I would like to ask your
opinions on the research's claim that, if non-equal value coinjoins can be
really relied on for privacy or not.

(Btw, there were also similar ideas in the Knapsack paper in 2017:
https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf
 )

https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#avoiding-amount-linkages-through-combinatorics


I copy the most relevant paragraphs here:

  ---------BEGIN QUOTE ---------


Consider a transaction where 10 people have each brought 10 inputs of
arbitary amounts in the neighborhood of ~0.1 BCH. One input might be
0.03771049 BCH; the next might be 0.24881232 BCH, etc. All parties have
chosen to consolidate their coins, so the transaction has 10 outputs of
around 1 BCH. So the transaction has 100 inputs, and 10 outputs. The first
output might be 0.91128495, the next could be 1.79783710, etc.

Now, there are 100!/(10!)^10 ~= 10^92 ways to partition the inputs into a
list of 10 sets of 10 inputs, but only a tiny fraction of these partitions
will produce the precise output list. So, how many ways produce this exact
output list? We can estimate with some napkin math. First, recognize that
for each partitioning, each output will typically land in a range of ~10^8
discrete possibilities (around 1 BCH wide, with a 0.00000001 BCH
resolution). The first 9 outputs all have this range of possibilities, and
the last will be constrained by the others. So, the 10^92 possibilies will
land somewhere within a 9-dimensional grid that cointains (10^8)^9=10^72
possible distinct sites, one site which is our actual output list. Since we
are stuffing 10^92 possibilties into a grid that contains only 10^72 sites,
then this means on average, each site will have 10^20 possibilities.

Based on the example above, we can see that not only are there a huge
number of partitions, but that even with a fast algorithm that could find
matching partitions, it would produce around 10^20 possible valid
configurations. With 10^20 possibilities, there is essentially no linkage.
The Cash Fusion scheme actually extends this obfuscation even further. Not
only can players bring many inputs, they can also have multiple outputs.
---------END QUOTE ---------
-- 
Best,
Ádám

[-- Attachment #2: Type: text/html, Size: 3716 bytes --]

             reply	other threads:[~2019-12-27 18:04 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-12-27 18:03 nopara73 [this message]
2019-12-28 17:38 ` [bitcoin-dev] Non-equal value CoinJoins. Opinions Ethan Heilman
2019-12-28 23:25 ` ZmnSCPxj
2020-02-22 18:01   ` nopara73
2019-12-29  3:31 ` Yuval Kogman
2019-12-29  9:57   ` Yuval Kogman
2019-12-29 10:23   ` ZmnSCPxj
2019-12-29 17:48     ` Yuval Kogman
2019-12-30  1:14 ` Lucas Ontivero

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='CAEPKjgdtgDbyLoj6FV+cjY1Djca_FBtd9Kt_eB4zWU+at=wfYQ@mail.gmail.com' \
    --to=adam.ficsor73@gmail.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