path: root/0d/9f7bbe31312867a36e6de00afa0ce781f89e28

Return-Path: <adam.ficsor73@gmail.com>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 63BA3C013E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 22 Feb 2020 18:01:27 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by fraxinus.osuosl.org (Postfix) with ESMTP id 5238E855D7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 22 Feb 2020 18:01:27 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from fraxinus.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id hGCJxVDDjcdS
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 22 Feb 2020 18:01:26 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-ot1-f52.google.com (mail-ot1-f52.google.com
 [209.85.210.52])
 by fraxinus.osuosl.org (Postfix) with ESMTPS id 2891A855CF
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 22 Feb 2020 18:01:26 +0000 (UTC)
Received: by mail-ot1-f52.google.com with SMTP id r27so5052624otc.8
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 22 Feb 2020 10:01:26 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=y2+b8imI4vorGBJGRyIQ5ao6iDtfPBQBwJCBb3JvCUE=;
 b=QMrd8g8nVy0WygxoRHd3GW7zB2yIuooqYuVIPUgyoXk/IlqdK4hYiVgpUdT1OGGdWL
 jT2aMMZXbhmMFzuuBX152YX5YRsIcXnA5HBi4ilfeqvTPKLeu7yOp6IkDZsYytkhQGB7
 2C9jNCsBa3hQ/1WDkR1ibV2KF2aEbUfA01SzyPu+lfLcjo5+QbiYKtPsQRGkAotzyXo1
 9/nuX2SdsF0N2lCiOVf/Zj+XakQw2V9LRBdtOq20lt2nt02c+n/H5NGTzI4gf4qix7Dy
 4SySOMheiZP9TKaldoc6DN+5Eo4IbElqfpyaNRojYWqbjk19cJ2xKYIffUaWd9NicS4y
 dE3g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=y2+b8imI4vorGBJGRyIQ5ao6iDtfPBQBwJCBb3JvCUE=;
 b=fpoYZFEueg90AK3Me+rjzBI9beo7COzb5DzaZLL/C+nL97FJWGlhsT/fywbbCovm0p
 lc/5LlnBGoZ24cryQ8au60bUXcrCxqXAyX9fduMY9yxECCl0lHzXIkYwpRKvQLXmpSQP
 ito2gkXWXG6HUC6ccss/bizhfoxHEk3EmY2YXpi2RTfmVP+tPWCRo9oqwWGXTdYb61j7
 tyWZ/Ht5T6HB6INs4migPJmBmg82KAIKbIXRDAmeLGEPQRRw6pQnQY0AZSel/GPveb8j
 JWxCbQ01f4oIbWYQT2PUnMLaqAc/iotxX9cVtScb4y7MpGmdI8AXcT3Ji7sJI6Fxc0Lu
 ub0w==
X-Gm-Message-State: APjAAAV1QB1JdD+sC7E6++ABdnpjBf4PYOjT9I0CZT7yc3JKUxN2+Jrq
 Hy3WNsfTM6uKEI84gPvCJd4c7utDJ7JQLwbiPMw=
X-Google-Smtp-Source: APXvYqw8dNYdUHEvWPAS2dtDQ8uxPcfZhV7PaxM3uki8PbJ7sELHPqZf8rFw2Z6LqbkbpR4OkofMNTUyyqAcKaLkQpk=
X-Received: by 2002:a05:6830:13da:: with SMTP id
 e26mr31478707otq.97.1582394485319; 
 Sat, 22 Feb 2020 10:01:25 -0800 (PST)
MIME-Version: 1.0
References: <CAEPKjgdtgDbyLoj6FV+cjY1Djca_FBtd9Kt_eB4zWU+at=wfYQ@mail.gmail.com>
 <zlmDLPI5ns68UtpmU4KnIQff7O1V7sqI3-nzQ2i1axQXiyUsX0IhW5F7TAjoRAfIak1vw7LYaxhSCAHoi0r--DI6RFz7FhYGVQ_lBXi5L9M=@protonmail.com>
In-Reply-To: <zlmDLPI5ns68UtpmU4KnIQff7O1V7sqI3-nzQ2i1axQXiyUsX0IhW5F7TAjoRAfIak1vw7LYaxhSCAHoi0r--DI6RFz7FhYGVQ_lBXi5L9M=@protonmail.com>
From: nopara73 <adam.ficsor73@gmail.com>
Date: Sat, 22 Feb 2020 19:01:14 +0100
Message-ID: <CAEPKjgcGaPPeNo7afiMdpUm+JTdqjxMLEvYUAaW5vHes7PJrrA@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000312cf4059f2ded21"
X-Mailman-Approved-At: Sun, 23 Feb 2020 01:34:24 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Non-equal value CoinJoins. Opinions.
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 22 Feb 2020 18:01:27 -0000

--000000000000312cf4059f2ded21
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

>  It seems to me that most users will not have nearly the same output of
"around 1 BTC"

While that would be true out of context, it depends on how you interpret it
and they interpret it really broadly: " One input might be 0.03771049 BCH;
the next might be 0.24881232 BCH, etc. "

> anyway if you deploy this on a real live mainnet, and if your math
requires that you have "around 1 BTC" outputs per user. you might as well
just use equal-valued CoinJoins, where the equal-valued outputs at least
are completely unlinked from the inputs.
>  e.g. if you have a CashFusion transaction with outputs 1.0, 1.1, 0.99,
you could transform that to a CoinJoin with 0.99, 0.99, 0.99, 0.01, 0.11
outputs.

Equal valued coinjoins (1) waste more blockspace as your example
illustrates and (2) prevent arbitrary amounts, so you cannot send in
coinjoins.

> Indeed, the change outputs of an equal-valued CoinJoin would have similar
analyses to CashFusion, since the same analysis "around 1 BTC" can be
performed with the CoinJoin change outputs "around 0 BTC".

I've been wondering about this too. I think it cannot be applied to
existing CoinJoin schemes, as coin selection heuristics are quite a help
and that could be a reason why the changes can be deanonymized (I assume.)
For example if I want to analyze a Wasabi CJ, then I assume every input
that have > 0.1 BTC value to be THE valid input partition and I will only
look for the valid matching partition on the output side. I won't try to
find all the partitions and look at all the possible subset sums. (
https://github.com/nopara73/Notes/blob/master/BellNumber.md,
https://github.com/nopara73/Notes/blob/master/SubSetSum.md)

At the very least coin selection for equal value coinjoins can be relaxed
to remove such assumptions and make the above math applicable for the
change. (If works.)



On Sun, Dec 29, 2019 at 12:25 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Adam,
>
> > 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 b=
e
> 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-trust=
com-coinjoin.pdf
>  )
> >
> >
> https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#avoiding-am=
ount-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 firs=
t
> output might be 0.91128495, the next could be 1.79783710, etc.
> >
> > Now, there are 100!/(10!)^10 ~=3D 10^92 ways to partition the inputs in=
to
> 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 produc=
e
> 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.000000=
01
> 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=3D10^72 possible distinct sites, one site which is our actual ou=
tput
> 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. No=
t
> only can players bring many inputs, they can also have multiple outputs.
> >
> > ---------END QUOTE ---------
> > --
>
>
> It seems to me that most users will not have nearly the same output of
> "around 1 BTC" anyway if you deploy this on a real live mainnet, and if
> your math requires that you have "around 1 BTC" outputs per user. you mig=
ht
> as well just use equal-valued CoinJoins, where the equal-valued outputs a=
t
> least are completely unlinked from the inputs.
>
> Indeed, the change outputs of an equal-valued CoinJoin would have similar
> analyses to CashFusion, since the same analysis "around 1 BTC" can be
> performed with the CoinJoin change outputs "around 0 BTC".
>
> * You can always transform a CashFusion transaction whose outputs are
> "around 1 BTC" to a CoinJoin transaction with equal-valued outputs and so=
me
> change outputs, with the equal-valued outputs having equal value to the
> smallest CashFusion output.
>  * e.g. if you have a CashFusion transaction with outputs 1.0, 1.1, 0.99,
> you could transform that to a CoinJoin with 0.99, 0.99, 0.99, 0.01, 0.11
> outputs.
> * Conversely, you can transform an equal-valued CoinJoin transaction to a
> CashFusion transaction using the same technique.
> * That implies that the change outputs of an equal-valued CoinJoin have
> the same linkability as the outputs of the equivalent CashFusion
> transaction.
> * At least with equal-valued CoinJoin, the equal-valued outputs have 0
> linkability with inputs (at least with only that transaction in isolation=
).
>   The same cannot be said of CashFusion, because the value involved is
> just in a single UTXO.
>
> Regards,
> ZmnSCPxj
>


--=20
Best,
=C3=81d=C3=A1m

--000000000000312cf4059f2ded21
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">&gt;=C2=A0

It seems to me that most users will not have nearly the same output of &quo=
t;around 1 BTC&quot;<div><br></div><div>While that would be true out of con=
text, it depends on how you interpret it and they interpret it really broad=
ly: &quot;

<span style=3D"color:rgb(80,0,80)">One input might be 0.03771049 BCH; the n=
ext might be 0.24881232 BCH, etc.</span>=C2=A0&quot;=C2=A0<br><br>&gt; anyw=
ay if you deploy this on a real live mainnet, and if your math requires tha=
t you have &quot;around 1 BTC&quot; outputs per user. you might as well jus=
t use equal-valued CoinJoins, where the equal-valued outputs at least are c=
ompletely unlinked from the inputs.<br>&gt;=C2=A0

e.g. if you have a CashFusion transaction with outputs 1.0, 1.1, 0.99, you =
could transform that to a CoinJoin with 0.99, 0.99, 0.99, 0.01, 0.11 output=
s.=C2=A0=C2=A0<br><br>Equal valued coinjoins (1) waste more blockspace as y=
our example illustrates and (2) prevent arbitrary amounts, so you cannot se=
nd in coinjoins.<br><br>&gt; Indeed, the change outputs of an equal-valued =
CoinJoin would have similar analyses to CashFusion, since the same analysis=
 &quot;around 1 BTC&quot; can be performed with the CoinJoin change outputs=
 &quot;around 0 BTC&quot;.<br><br>I&#39;ve been wondering about this too. I=
 think it cannot be applied to existing CoinJoin schemes, as coin selection=
 heuristics are quite a help and that could be a reason why the changes can=
 be deanonymized (I assume.) For example if I want to analyze a Wasabi CJ, =
then I assume every input that have &gt; 0.1 BTC value to be THE valid inpu=
t partition and I will only look for the valid matching partition on the ou=
tput side. I won&#39;t try to find all the partitions and look at all the p=
ossible subset sums. (<a href=3D"https://github.com/nopara73/Notes/blob/mas=
ter/BellNumber.md">https://github.com/nopara73/Notes/blob/master/BellNumber=
.md</a>,=C2=A0<a href=3D"https://github.com/nopara73/Notes/blob/master/SubS=
etSum.md">https://github.com/nopara73/Notes/blob/master/SubSetSum.md</a>)=
=C2=A0<br><br>At the very least coin selection for equal value coinjoins ca=
n be relaxed to remove such assumptions and make the above math applicable =
for the change. (If works.)</div><div><br><br></div></div><br><div class=3D=
"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sun, Dec 29, 2019 at=
 12:25 AM ZmnSCPxj &lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@=
protonmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" st=
yle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padd=
ing-left:1ex">Good morning Adam,<br>
<br>
&gt; The CashFusion research came out of the Bitcoin Cash camp, thus this p=
robably went under the radar of many of you. I would like to ask your opini=
ons on the research&#39;s claim that, if non-equal value coinjoins can be r=
eally relied on for privacy or not.<br>
&gt;<br>
&gt; (Btw, there were also similar ideas in the Knapsack paper in 2017:=C2=
=A0<a href=3D"https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-=
maurer-trustcom-coinjoin.pdf" rel=3D"noreferrer" target=3D"_blank">https://=
www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjo=
in.pdf</a>=C2=A0)=C2=A0<br>
&gt;<br>
&gt; <a href=3D"https://github.com/cashshuffle/spec/blob/master/CASHFUSION.=
md#avoiding-amount-linkages-through-combinatorics" rel=3D"noreferrer" targe=
t=3D"_blank">https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#=
avoiding-amount-linkages-through-combinatorics</a>=C2=A0=C2=A0<br>
&gt;<br>
&gt; I copy the most relevant paragraphs here:<br>
&gt;<br>
&gt; =C2=A0 ---------BEGIN QUOTE ---------=C2=A0<br>
&gt; =C2=A0<br>
&gt;<br>
&gt; 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.0377=
1049 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.<br>
&gt;<br>
&gt; Now, there are 100!/(10!)^10 ~=3D 10^92 ways to partition the inputs i=
nto a list of 10 sets of 10 inputs, but only a tiny fraction of these parti=
tions 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 resol=
ution). The first 9 outputs all have this range of possibilities, and the l=
ast will be constrained by the others. So, the 10^92 possibilies will land =
somewhere within a 9-dimensional grid that cointains (10^8)^9=3D10^72 possi=
ble 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, the=
n this means on average, each site will have 10^20 possibilities.<br>
&gt;<br>
&gt; 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 m=
atching partitions, it would produce around 10^20 possible valid configurat=
ions. With 10^20 possibilities, there is essentially no linkage. The Cash F=
usion scheme actually extends this obfuscation even further. Not only can p=
layers bring many inputs, they can also have multiple outputs.<br>
&gt;<br>
&gt; ---------END QUOTE ---------<br>
&gt; --<br>
<br>
<br>
It seems to me that most users will not have nearly the same output of &quo=
t;around 1 BTC&quot; anyway if you deploy this on a real live mainnet, and =
if your math requires that you have &quot;around 1 BTC&quot; outputs per us=
er. you might as well just use equal-valued CoinJoins, where the equal-valu=
ed outputs at least are completely unlinked from the inputs.<br>
<br>
Indeed, the change outputs of an equal-valued CoinJoin would have similar a=
nalyses to CashFusion, since the same analysis &quot;around 1 BTC&quot; can=
 be performed with the CoinJoin change outputs &quot;around 0 BTC&quot;.<br=
>
<br>
* You can always transform a CashFusion transaction whose outputs are &quot=
;around 1 BTC&quot; to a CoinJoin transaction with equal-valued outputs and=
 some change outputs, with the equal-valued outputs having equal value to t=
he smallest CashFusion output.<br>
=C2=A0* e.g. if you have a CashFusion transaction with outputs 1.0, 1.1, 0.=
99, you could transform that to a CoinJoin with 0.99, 0.99, 0.99, 0.01, 0.1=
1 outputs.<br>
* Conversely, you can transform an equal-valued CoinJoin transaction to a C=
ashFusion transaction using the same technique.<br>
* That implies that the change outputs of an equal-valued CoinJoin have the=
 same linkability as the outputs of the equivalent CashFusion transaction.<=
br>
* At least with equal-valued CoinJoin, the equal-valued outputs have 0 link=
ability with inputs (at least with only that transaction in isolation).<br>
=C2=A0 The same cannot be said of CashFusion, because the value involved is=
 just in a single UTXO.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
 class=3D"gmail_signature"><div dir=3D"ltr"><div><div dir=3D"ltr"><div><div=
 dir=3D"ltr"><div><div><span style=3D"font-size:13.3333px">Best,<br>=C3=81d=
=C3=A1m</span></div></div></div></div></div></div></div></div>

--000000000000312cf4059f2ded21--