1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
Return-Path: <eth3rs@gmail.com>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id E8C06C0881
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 28 Dec 2019 17:38:48 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by fraxinus.osuosl.org (Postfix) with ESMTP id D26C88525D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 28 Dec 2019 17:38:48 +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 d5aSDvP19ou6
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 28 Dec 2019 17:38:48 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com
[209.85.214.173])
by fraxinus.osuosl.org (Postfix) with ESMTPS id 251D684E77
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 28 Dec 2019 17:38:48 +0000 (UTC)
Received: by mail-pl1-f173.google.com with SMTP id a6so12259578plm.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 28 Dec 2019 09:38:48 -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
:content-transfer-encoding;
bh=HkleBp1GzQMaDYql0yPi0i1NXhqpGgss0T/mg6aRxY0=;
b=VmtbWSOvD3yFBx+GZau6D9wHMNCLMxubsydsmHSfRB8Ic2Q7ofgq20Bnrf3pB81Ni9
W0JUbMIKvk8jj2W1KQjp/OCFmzEC/PlJvrHuRAfVkJuegKaN6R0RZZpHl90x/NUI46hG
mUezuWpPEHXtBs5y2b43h6nvfm/mvurzMt5A3jH4d+ffuYoqex58AC7kEHSfhiRC7k5a
2gwxIKR+RM2S9a1twQQRqo41/tdtySUfAaOiFlGhxt7PKRCzDnnW+FfKgvVrRakEptFO
gqg1ORiyWlRlqY8Hq7x2rllxtpor+rGeRAXCM6mQDG6wlLJanEs8pv0U8oU4d9vN4LeD
PZ3Q==
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:content-transfer-encoding;
bh=HkleBp1GzQMaDYql0yPi0i1NXhqpGgss0T/mg6aRxY0=;
b=eUoshVg0Nl0Mcn12MSoYaNaPoVGKMZfJRefHH8xR5TGoKrbblXbmkJcrRMy6ZMFC63
GlpUC68eY45SD7agGgBGSin3nWf4uG100102XxQZaBTWO7qC+TF1JHeH0aR9xmRsB8/o
t6zYk0btDtMJaRCbW1sdySBeplykAj+IT1ngsfc2guXRJ4kdJ8D1llGh4wrEeSjRRR31
sqWZn9QrGoMkMpzMfrf1K2ePVl+VIiez+QGkC8w/Qj106JiXcpjvdl99uwyz5Wsa4fN9
71KhX79lyUsh8KcqZ0OsvfnFcskzh3CwUEH6VHApHzwmPhlERDNzLvrBKFaAwStzVuFS
3VIA==
X-Gm-Message-State: APjAAAV05k/QKnIbArcKu4MXFpnmRaG3xZhPfLLK5TSf4km5DloA+sLI
btR4kaK459KaIpaCrioVY4DUtOu7RajGVovbdas=
X-Google-Smtp-Source: APXvYqzC2Fholnes/m2GFRLqTAWXY2PWgeGQXIQcJgz72wJLtD/AAuK7UkRGvvlAvfJ4XNWpN5NQosjvzmC5XJSPAHc=
X-Received: by 2002:a17:90a:fb4f:: with SMTP id
iq15mr34444119pjb.86.1577554727425;
Sat, 28 Dec 2019 09:38:47 -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: Ethan Heilman <eth3rs@gmail.com>
Date: Sat, 28 Dec 2019 12:38:11 -0500
Message-ID: <CAEM=y+XdaLLW+EBt8TnceHmpBhFDJnX3jYY=zs_PW6fy-QFRBA@mail.gmail.com>
To: nopara73 <adam.ficsor73@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
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, 28 Dec 2019 17:38:49 -0000
I'm only going to talk about cashfusion and not the knapsack paper.
The language they use to describe the cashfusion protocol is very
broad and could describe many things. Because it is hard so vague I
don't want to dismiss the cashfusion approach out of hand. For
instance they say: "inputs of arbitary amounts in the neighborhood of
~0.1 BCH" what exactly does this mean?
Attack 1:
If we assume arbitrary means any precision then a trivial attack is
possible. Consider the case where one of the inputs has more precision
than any other input. This allows an attacker to trivially break the
privacy of that input:
Lets look at a toy example that takes 12 inputs and creates 3 outputs
inputs:
0.1525
0.1225
0.1145
0.1443
0.1144111
0.1001
0.1124
0.1093
0.1113
0.1134
0.1029
0.1206
Outputs:
0.4648111
0.5185
0.4349
Clearly output output 0.4648111 contains input 0.1144111.
Attack 2:
Let's say you attempt to address this problem this by limiting the
precision of inputs to two decimal places i.e. 0.1X where 0<=3DX<=3D9.
Consider the case of 10 users where each user is always joining sets
of 10 inputs to create 1 output. Thus in total you would have 100
inputs and 10 outputs in the coinjoin. If one of those outputs is 2
then you know its inputs must all be 0.2. Using this method you can
start eliminate input output pairs far faster brute force. How much
faster is hard to say without adding additional assumptions for
instance are these inputs amounts drawn from a uniform distribution?
I want to be clear. I'm not saying cashfusion is broken or that this
more inputs than outputs technique is a dead end. However the
description given is vague and could be interpreted to describe a
broken protocol. Is this actively being used?
On Fri, Dec 27, 2019 at 8:29 PM nopara73 via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> The CashFusion research came out of the Bitcoin Cash camp, thus this prob=
ably 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 r=
elied 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-coin=
join.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 arb=
itary amounts in the neighborhood of ~0.1 BCH. One input might be 0.0377104=
9 BCH; the next might be 0.24881232 BCH, etc. All parties have chosen to co=
nsolidate their coins, so the transaction has 10 outputs of around 1 BCH. S=
o 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 ~=3D 10^92 ways to partition the inputs into=
a list of 10 sets of 10 inputs, but only a tiny fraction of these partitio=
ns will produce the precise output list. So, how many ways produce this exa=
ct output list? We can estimate with some napkin math. First, recognize tha=
t 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 resoluti=
on). 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 som=
ewhere 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 stu=
ffing 10^92 possibilties into a grid that contains only 10^72 sites, then t=
his 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 num=
ber of partitions, but that even with a fast algorithm that could find matc=
hing partitions, it would produce around 10^20 possible valid configuration=
s. With 10^20 possibilities, there is essentially no linkage. The Cash Fusi=
on scheme actually extends this obfuscation even further. Not only can play=
ers 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
|
