path: root/3f/200f0cd1483058a9182af9855c05d7c6aaaa28

Return-Path: <lucasontivero@gmail.com>
Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 46415C077D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 30 Dec 2019 01:14:33 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by whitealder.osuosl.org (Postfix) with ESMTP id 2DC7B82405
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 30 Dec 2019 01:14:33 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from whitealder.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id p5mtWBQG3dp4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 30 Dec 2019 01:14:31 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-il1-f172.google.com (mail-il1-f172.google.com
 [209.85.166.172])
 by whitealder.osuosl.org (Postfix) with ESMTPS id C6A1182146
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 30 Dec 2019 01:14:31 +0000 (UTC)
Received: by mail-il1-f172.google.com with SMTP id v69so26699299ili.10
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 29 Dec 2019 17:14:31 -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;
 bh=qAD8BTdZIZUMWAJdbLTJt+QFPzfTk3l9BMAKwGMbT2E=;
 b=nPHEncZwomXMt5ybfnwGs5WUXE8lCCbWzRYhmsv3+pG++4XcqbfJ9VgwR1CtyNZvRx
 X1NIT1F+nG+B1VsYp4nrL62xT6hXzVmPdpijRn47p4BLCDUZIJjnuyj7vkp0bFGgwb3p
 nvgbfc2i9xNGBQNXcBQmvtSOtw8rpXUcrsN+CB/MMX5Iv+lEErQ+eWNbT3Nt+8Bnv9nP
 pHFHQZb8B4MS6KyAdprZ/v6A2uQ/8CLf1wvXVVhSVJrumtPy+RLeSaCbOxr/vzfLANJA
 9bhjQfDPYEPZMHPQ2eKxHNAhUMNa+hEzL3811EyYfrcxsA9kzBgQQDm0J5hn6vy3IW0a
 WseQ==
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;
 bh=qAD8BTdZIZUMWAJdbLTJt+QFPzfTk3l9BMAKwGMbT2E=;
 b=n/pQ6smF+rQkQqwG/TLEK2XGJlldCM4CwsLpRMQwlLJHBxFXUdOUqeme4DzVm+N2vb
 +YXEjuoMH1uuMItXt5SvUkCvr4pg+5M+CZavjR0EOjvZq+To81JdhmsgR6SeGUbsaJ+l
 EaYglMcpAyRLWwuqDTNiYH8EyPBH2K6rXckCvJhgI6DfSQjiHUblZKI5OA/Nr2jyNN4R
 PxbJQM/JJDagsnD0bIqiZBHbRKu+ZRX9WnBmLyhbTjbkkeitofQ1NNAufid/uAoOABvp
 4fWGBpb3i33iCvioYkHX9+vzhHvbERFfUjxAD7bOjI96J/00UdLufgxwADlp0M5UuQAi
 DalQ==
X-Gm-Message-State: APjAAAXaRDLIR+dqNRfaBAyiKoHhLk0FYQ6D32a2e0bjNLLhzdj5AsUX
 6mSWQ5U42HGczFHG3xPXyBaB/lYGNmwPIpuwzho=
X-Google-Smtp-Source: APXvYqzXvy7jJO7xpW9JSRMJIdv+AR8hX3/nBHM08QzyxgBVnABP5xCdjspsnla8ZUCV0SpT6e/kmgYCrUahpDGjp6Y=
X-Received: by 2002:a92:c747:: with SMTP id y7mr29530181ilp.60.1577668471088; 
 Sun, 29 Dec 2019 17:14:31 -0800 (PST)
MIME-Version: 1.0
References: <CAEPKjgdtgDbyLoj6FV+cjY1Djca_FBtd9Kt_eB4zWU+at=wfYQ@mail.gmail.com>
In-Reply-To: <CAEPKjgdtgDbyLoj6FV+cjY1Djca_FBtd9Kt_eB4zWU+at=wfYQ@mail.gmail.com>
From: Lucas Ontivero <lucasontivero@gmail.com>
Date: Sun, 29 Dec 2019 22:14:19 -0300
Message-ID: <CALHvQn06DSPnxWYDEoi_28s9ukaC0Be1sCf0cvv44f2cz0f5hA@mail.gmail.com>
To: nopara73 <adam.ficsor73@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000caec8a059ae190e2"
X-Mailman-Approved-At: Mon, 30 Dec 2019 01:32:12 +0000
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: Mon, 30 Dec 2019 01:14:33 -0000

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

This idea is not similar to the one in the knapsack paper because this one
is based only in the computational complexity of finding partitions that
match the outputs. However, and except in rare cases, there is only one
valid partition (solution) for each output, it doesn't introduce any
ambiguity. Knapsack, on the other hand, splits the original outputs in such
a way that there are many partitions (solutions) that match the a selected
group of outputs. For example, imagine 7 people decide to participate in a
coinjoin transaction with an arbitrary number of inputs (no more than 7
inputs each), imagine this is not a pay to yourself cj tx but a pay to
someone else cjtx instead such that there are at most 2 outputs for
participants (payment output and change output) in this case, configuring
the partitions search algorithm to restrict the search space to sets of 7
inputs maximum and 4 outputs maximum it found 14,599 valid transactions in
42mins 18secs
https://raw.githubusercontent.com/lontivero/Knapsack/master/data/knapsack-7=
-participants.txt

The same simulation with 8 participants under the same conditions found
35,781 valid transactions in about 4 hours. Finally, with 9 participants I
let it running all the day and it didn't finished. The point is that the
number of valid transactions grows so incredible fast that with 100
participants even if you find a way to find all the partitions that matches
a set of outputs (something near to impossible), there are no way to know
which of those are the real ones.

Also, the attacks on this mechanism look so simple that generate doubts.
Finally, I think the numbers in this proposal look weird because the
example is using 10 inputs and the amounts are in the "neighborhood of
~0.1btc" (what the heck does that mean?) and the sum of those are around
1btc. That means that it could work in a very specific scenario. Knapsack
is a general solution with good math behind and backtested against
historical data extracted from the bitcoin's blockchain.

In summary, in unequal inputs/outputs coinjoins knapsack is the best we
have at the moment (btw, it is not as effective as equal-outputs
transactions). This proposal is imo inferior and it is not supported by
good math.


El vie., 27 dic. 2019 a las 22:29, nopara73 via bitcoin-dev (<
bitcoin-dev@lists.linuxfoundation.org>) escribi=C3=B3:

> 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 into=
 a
> list of 10 sets of 10 inputs, but only a tiny fraction of these partition=
s
> will produce the precise output list. So, how many ways produce this exac=
t
> 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, an=
d
> the last will be constrained by the others. So, the 10^92 possibilies wil=
l
> land somewhere within a 9-dimensional grid that cointains (10^8)^9=3D10^7=
2
> 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 site=
s,
> 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 ---------
> --
> Best,
> =C3=81d=C3=A1m
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div><div><div>This idea is not similar to the one in the =
knapsack paper because this one is based only in the computational complexi=
ty of finding partitions that match the outputs. However, and except in rar=
e cases, there is only one valid partition (solution) for each output, it d=
oesn&#39;t introduce any ambiguity. Knapsack, on the other hand, splits the=
 original outputs in such a way that there are many partitions (solutions) =
that match the a selected group of outputs. For example, imagine 7 people d=
ecide to participate in a coinjoin transaction with an arbitrary number of =
inputs (no more than 7 inputs each), imagine this is not a pay to yourself =
cj tx but a pay to someone else cjtx instead such that there are at most 2 =
outputs for participants (payment output and change output) in this case, c=
onfiguring the partitions search algorithm to restrict the search space to =
sets of 7 inputs maximum and 4 outputs maximum it found 14,599 valid transa=
ctions in 42mins 18secs <a href=3D"https://raw.githubusercontent.com/lontiv=
ero/Knapsack/master/data/knapsack-7-participants.txt">https://raw.githubuse=
rcontent.com/lontivero/Knapsack/master/data/knapsack-7-participants.txt</a>=
<br><br></div>The same simulation with 8 participants under the same condit=
ions found 35,781 valid transactions in about 4 hours. Finally, with 9 part=
icipants I let it running all the day and it didn&#39;t finished. The point=
 is that the number of valid transactions grows so incredible fast that wit=
h 100 participants even if you find a way to find all the partitions that m=
atches a set of outputs (something near to impossible), there are no way to=
 know which of those are the real ones.<br><br></div>Also, the attacks on t=
his mechanism look so simple that generate doubts. Finally, I think the num=
bers in this proposal look weird because the example is using 10 inputs and=
 the amounts are in the &quot;neighborhood of ~0.1btc&quot; (what the heck =
does that mean?) and the sum of those are around 1btc. That means that it c=
ould work in a very specific scenario. Knapsack is a general solution with =
good math behind and backtested against historical data extracted from the =
bitcoin&#39;s blockchain.<br><br></div>In summary, in unequal inputs/output=
s coinjoins knapsack is the best we have at the moment (btw, it is not as e=
ffective as equal-outputs transactions). This proposal is imo inferior and =
it is not supported by good math.<br><div><div><div><div><br></div></div></=
div></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gm=
ail_attr">El vie., 27 dic. 2019 a las 22:29, nopara73 via bitcoin-dev (&lt;=
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
linuxfoundation.org</a>&gt;) escribi=C3=B3:<br></div><blockquote class=3D"g=
mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204=
,204,204);padding-left:1ex"><div dir=3D"ltr">The CashFusion research came o=
ut of the Bitcoin Cash camp, thus this probably went under the radar of man=
y of you. I would like to ask your opinions on the research&#39;s claim tha=
t, if non-equal value coinjoins can be really relied on for privacy or not.=
<br><br>(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/20=
17-maurer-trustcom-coinjoin.pdf" target=3D"_blank">https://www.comsys.rwth-=
aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf</a>=C2=A0=
)=C2=A0<br><br><a href=3D"https://github.com/cashshuffle/spec/blob/master/C=
ASHFUSION.md#avoiding-amount-linkages-through-combinatorics" target=3D"_bla=
nk">https://github.com/cashshuffle/spec/blob/master/CASHFUSION.md#avoiding-=
amount-linkages-through-combinatorics</a>=C2=A0=C2=A0<br><br>I copy the mos=
t relevant paragraphs here:<br clear=3D"all"><div><br>=C2=A0 ---------BEGIN=
 QUOTE

---------=C2=A0<br>=C2=A0<br><p style=3D"box-sizing:border-box;margin-top:0=
px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,BlinkMa=
cSystemFont,&quot;Segoe UI&quot;,Helvetica,Arial,sans-serif,&quot;Apple Col=
or Emoji&quot;,&quot;Segoe UI Emoji&quot;;font-size:16px">Consider a transa=
ction where 10 people have each brought 10 inputs of arbitary amounts in th=
e neighborhood of ~0.1 BCH. One input might be 0.03771049 BCH; the next mig=
ht be 0.24881232 BCH, etc. All parties have chosen to consolidate their coi=
ns, so the transaction has 10 outputs of around 1 BCH. So the transaction h=
as 100 inputs, and 10 outputs. The first output might be 0.91128495, the ne=
xt could be 1.79783710, etc.</p><p style=3D"box-sizing:border-box;margin-to=
p:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,Blin=
kMacSystemFont,&quot;Segoe UI&quot;,Helvetica,Arial,sans-serif,&quot;Apple =
Color Emoji&quot;,&quot;Segoe UI Emoji&quot;;font-size:16px">Now, there are=
 100!/(10!)^10 ~=3D 10^92 ways to partition the inputs into a list of 10 se=
ts 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 parti=
tioning, each output will typically land in a range of ~10^8 discrete possi=
bilities (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 constra=
ined 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 output list. Since we are stuffing 10^92 poss=
ibilties into a grid that contains only 10^72 sites, then this means on ave=
rage, each site will have 10^20 possibilities.</p><p style=3D"box-sizing:bo=
rder-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:=
-apple-system,BlinkMacSystemFont,&quot;Segoe UI&quot;,Helvetica,Arial,sans-=
serif,&quot;Apple Color Emoji&quot;,&quot;Segoe UI Emoji&quot;;font-size:16=
px">Based on the example above, we can see that not only are there a huge n=
umber of partitions, but that even with a fast algorithm that could find ma=
tching partitions, it would produce around 10^20 possible valid configurati=
ons. With 10^20 possibilities, there is essentially no linkage. The Cash Fu=
sion scheme actually extends this obfuscation even further. Not only can pl=
ayers bring many inputs, they can also have multiple outputs.</p>---------E=
ND QUOTE

---------

</div>-- <br><div dir=3D"ltr"><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></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000caec8a059ae190e2--