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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
|
Return-Path: <bdenby@andrew.cmu.edu>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 6E173A80
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 10 May 2018 12:59:16 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lf0-f42.google.com (mail-lf0-f42.google.com
[209.85.215.42])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8AB716A1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 10 May 2018 12:59:14 +0000 (UTC)
Received: by mail-lf0-f42.google.com with SMTP id t129-v6so2847786lff.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 10 May 2018 05:59:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=cmu-edu.20150623.gappssmtp.com; s=20150623;
h=mime-version:from:date:message-id:subject:to;
bh=sylOE5IJVXBfb8IB4wrD+jY+EHl2xQ4M7Yt6AqvkAvY=;
b=f6NpJUH9v0N2jQ0IRC6YzYYOOBdr17hof8tTw6c7PLFtFZOxQ8ukApb6iNszSiVSMP
B02B7FQzMAG9la2MNbZuiYwZxqjgxdBtP3Xy+EUaMUoFJVll4rFoCnDPCcnxwbyYiyPq
GsMD6tdPXF80qxriUmJquqKPqS+oz7zUcYSseTcRYtH2/Tl7Z3Y7d3e96ign/3iiGAUt
CfzxlADaLYYx/GxMYUtaNvCf2mUJEUXEhECYKrYMv8TGnE68EXVQL7K4QxSYzXsvaM7I
N2jXNfVboYR1A5pW6X4epS8IUHqBe4iMMjLefgr/NRShxyTKQvPHD1L0bzf9HssFXU7s
q2Xg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=sylOE5IJVXBfb8IB4wrD+jY+EHl2xQ4M7Yt6AqvkAvY=;
b=lRWFqAi+t9w5/JlQUJI0YHeu7eyVrlv2Q4r3gFOhuKUqtzGEMKZlO6003bVmu+sjFE
q55cqVcr2Zh8AEgqaKbH1ez+ruFnyOJRCKz5UK4582xWcKs7NC+aNw15I1gkWMOeMCD5
thCkxNz33Y1lyi+d9uW1+IdQOr+5PuPQ558YEOPyu1piEqtdHW6jl6OxcEFjEL4etYd1
x+EQnSVwCGaOGtMiliNd1nJJoupVR9sEEnsfTyhcGsG3oHnsx+UZ0vf8tkKcFvFInnZT
8zbF+pta47X5mEDe43os9LmU51Wnw2SGJ8BXkAOxD3tpImh95ZOrlL7dJqEAFQnx3lXj
XK+A==
X-Gm-Message-State: ALKqPwdG/tgCaKOW/l4jPEyUMUyJYvyKLAySn6fQM6oWF6Vnnfhb71Vp
no18rzQmr/xdSro/6yz6RJIsZ0UcPTTfAsPzq1AHTWc=
X-Google-Smtp-Source: AB8JxZp3LGuDr4NbgSNuO6ZURMsyOLxgAEdY2B3l2TmMclZsGv1roFUDiBvNc34JsbRtBMTr+ZOkJDiJ5FN0enkJgqQ=
X-Received: by 2002:a19:7b11:: with SMTP id
w17-v6mr924299lfc.103.1525957152647;
Thu, 10 May 2018 05:59:12 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.46.144.204 with HTTP; Thu, 10 May 2018 05:59:12 -0700 (PDT)
From: Bradley Denby <bdenby@cmu.edu>
Date: Thu, 10 May 2018 08:59:12 -0400
Message-ID: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="00000000000006c8e7056bd99630"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Thu, 10 May 2018 13:01:19 +0000
Subject: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving
Transaction Propagation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Thu, 10 May 2018 12:59:16 -0000
--00000000000006c8e7056bd99630
Content-Type: text/plain; charset="UTF-8"
Hi all,
We're writing with an update on the Dandelion project. As a reminder,
Dandelion
is a practical, lightweight privacy solution that provides Bitcoin users
formal
anonymity guarantees. While other privacy solutions aim to protect
individual
users, Dandelion protects privacy by limiting the capability of adversaries
to
deanonymize the entire network.
Bitcoin's transaction spreading protocol is vulnerable to deanonymization
attacks. When a node generates a transaction without Dandelion, it transmits
that transaction to its peers with independent, exponential delays. This
approach, known as diffusion in academia, allows network adversaries to link
transactions to IP addresses.
Dandelion prevents this class of attacks by sending transactions over a
randomly
selected path before diffusion. Transactions travel along this path during
the
"stem phase" and are then diffused during the "fluff phase" (hence the name
Dandelion). We have shown that this routing protocol provides near-optimal
anonymity guarantees among schemes that do not introduce additional
encryption
mechanisms.
Since the last time we contacted the list, we have:
- Completed additional theoretical analysis and simulations
- Built a working prototype
(https://github.com/mablem8/bitcoin/tree/dandelion)
- Built a test suite for the prototype
(https://github.com/mablem8/bitcoin/blob/dandelion/test/
functional/p2p_dandelion.py)
- Written detailed documentation for the new implementation
(https://github.com/mablem8/bips/blob/master/bip-
dandelion/dandelion-reference-documentation.pdf)
Among other things, one question we've addressed in our additional analysis
is
how to route messages during the stem phase. For example, if two Dandelion
transactions arrive at a node from different inbound peers, to which
Dandelion
destination(s) should these transactions be sent? We have found that some
choices are much better than others.
Consider the case in which each Dandelion transaction is forwarded to a
Dandelion destination selected uniformly at random. We have shown that this
approach results in a fingerprint attack allowing network-level botnet
adversaries to achieve total deanonymization of the P2P network after
observing
less than ten transactions per node.
To avoid this issue, we suggest "per-inbound-edge" routing. Each inbound
peer is
assigned a particular Dandelion destination. Each Dandelion transaction that
arrives via this peer is forwarded to the same Dandelion destination.
Per-inbound-edge routing breaks the described attack by blocking an
adversary's
ability to construct useful fingerprints.
This iteration of Dandelion has been tested on our own small network, and we
would like to get the implementation in front of a wider audience. An
updated
BIP document with further details on motivation, specification,
compatibility,
and implementation is located here:
https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki
We would like to thank the Bitcoin Core developers and Gregory Maxwell in
particular for their insightful comments, which helped to inform this
implementation and some of the follow-up work we conducted. We would also
like
to thank the Mimblewimble development community for coining the term
"stempool,"
which we happily adopted for this implementation.
All the best,
Brad Denby <bdenby@cmu.edu>
Andrew Miller <soc1024@illinois.edu>
Giulia Fanti <gfanti@andrew.cmu.edu>
Surya Bakshi <sbakshi3@illinois.edu>
Shaileshh Bojja Venkatakrishnan <shaileshh.bv@gmail.com>
Pramod Viswanath <pramodv@illinois.edu>
--00000000000006c8e7056bd99630
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div style=3D"font-size:12.8px">Hi all,</div><div style=3D=
"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">We're writ=
ing with an update on the Dandelion project. As a reminder, Dandelion</div>=
<div style=3D"font-size:12.8px">is a practical, lightweight privacy solutio=
n that provides Bitcoin users formal</div><div style=3D"font-size:12.8px">a=
nonymity guarantees. While other privacy solutions aim to protect individua=
l</div><div style=3D"font-size:12.8px">users, Dandelion protects privacy by=
limiting the capability of adversaries to</div><div style=3D"font-size:12.=
8px">deanonymize the entire network.</div><div style=3D"font-size:12.8px"><=
br></div><div style=3D"font-size:12.8px">Bitcoin's transaction spreadin=
g protocol is vulnerable to deanonymization</div><div style=3D"font-size:12=
.8px">attacks. When a node generates a transaction without Dandelion, it tr=
ansmits</div><div style=3D"font-size:12.8px">that transaction to its peers =
with independent, exponential delays. This</div><div style=3D"font-size:12.=
8px">approach, known as diffusion in academia, allows network adversaries t=
o link</div><div style=3D"font-size:12.8px">transactions to IP addresses.</=
div><div style=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8p=
x">Dandelion prevents this class of attacks by sending transactions over a =
randomly</div><div style=3D"font-size:12.8px">selected path before diffusio=
n. Transactions travel along this path during the</div><div style=3D"font-s=
ize:12.8px">"stem phase" and are then diffused during the "f=
luff phase" (hence the name</div><div style=3D"font-size:12.8px">Dande=
lion). We have shown that this routing protocol provides near-optimal</div>=
<div style=3D"font-size:12.8px">anonymity guarantees among schemes that do =
not introduce additional encryption</div><div style=3D"font-size:12.8px">me=
chanisms.</div><div style=3D"font-size:12.8px"><br></div><div style=3D"font=
-size:12.8px">Since the last time we contacted the list, we have:</div><div=
style=3D"font-size:12.8px">=C2=A0- Completed additional theoretical analys=
is and simulations</div><div style=3D"font-size:12.8px">=C2=A0- Built a wor=
king prototype</div><div style=3D"font-size:12.8px">=C2=A0 =C2=A0(<a href=
=3D"https://github.com/mablem8/bitcoin/tree/dandelion" target=3D"_blank">ht=
tps://github.com/mablem8/<wbr>bitcoin/tree/dandelion</a>)</div><div style=
=3D"font-size:12.8px">=C2=A0- Built a test suite for the prototype</div><di=
v style=3D"font-size:12.8px">=C2=A0 =C2=A0(<a href=3D"https://github.com/ma=
blem8/bitcoin/blob/dandelion/test/functional/p2p_dandelion.py" target=3D"_b=
lank">https://github.com/mablem8/<wbr>bitcoin/blob/dandelion/test/<wbr>func=
tional/p2p_dandelion.py</a>)</div><div style=3D"font-size:12.8px">=C2=A0- W=
ritten detailed documentation for the new implementation</div><div style=3D=
"font-size:12.8px">=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bips=
/blob/master/bip-dandelion/dandelion-reference-documentation.pdf" target=3D=
"_blank">https://github.com/mablem8/<wbr>bips/blob/master/bip-<wbr>dandelio=
n/dandelion-reference-<wbr>documentation.pdf</a>)</div><div style=3D"font-s=
ize:12.8px"><br></div><div style=3D"font-size:12.8px">Among other things, o=
ne question we've addressed in our additional analysis is</div><div sty=
le=3D"font-size:12.8px">how to route messages during the stem phase. For ex=
ample, if two Dandelion</div><div style=3D"font-size:12.8px">transactions a=
rrive at a node from different inbound peers, to which Dandelion</div><div =
style=3D"font-size:12.8px">destination(s) should these transactions be sent=
? We have found that some</div><div style=3D"font-size:12.8px">choices are =
much better than others.</div><div style=3D"font-size:12.8px"><br></div><di=
v style=3D"font-size:12.8px">Consider the case in which each Dandelion tran=
saction is forwarded to a</div><div style=3D"font-size:12.8px">Dandelion de=
stination selected uniformly at random. We have shown that this</div><div s=
tyle=3D"font-size:12.8px">approach results in a fingerprint attack allowing=
network-level botnet</div><div style=3D"font-size:12.8px">adversaries to a=
chieve total deanonymization of the P2P network after observing</div><div s=
tyle=3D"font-size:12.8px">less than ten transactions per node.</div><div st=
yle=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">To avoid=
this issue, we suggest "per-inbound-edge" routing. Each inbound =
peer is</div><div style=3D"font-size:12.8px">assigned a particular Dandelio=
n destination. Each Dandelion transaction that</div><div style=3D"font-size=
:12.8px">arrives via this peer is forwarded to the same Dandelion destinati=
on.</div><div style=3D"font-size:12.8px">Per-inbound-edge routing breaks th=
e described attack by blocking an adversary's</div><div style=3D"font-s=
ize:12.8px">ability to construct useful fingerprints.</div><div style=3D"fo=
nt-size:12.8px"><br></div><div style=3D"font-size:12.8px">This iteration of=
Dandelion has been tested on our own small network, and we</div><div style=
=3D"font-size:12.8px">would like to get the implementation in front of a wi=
der audience. An updated</div><div style=3D"font-size:12.8px">BIP document =
with further details on motivation, specification, compatibility,</div><div=
style=3D"font-size:12.8px">and implementation is located here:</div><div s=
tyle=3D"font-size:12.8px"><a href=3D"https://github.com/mablem8/bips/blob/m=
aster/bip-dandelion.mediawiki" target=3D"_blank">https://github.com/mablem8=
/<wbr>bips/blob/master/bip-<wbr>dandelion.mediawiki</a></div><div style=3D"=
font-size:12.8px"><br></div><div style=3D"font-size:12.8px">We would like t=
o thank the Bitcoin Core developers and Gregory Maxwell in</div><div style=
=3D"font-size:12.8px">particular for their insightful comments, which helpe=
d to inform this</div><div style=3D"font-size:12.8px">implementation and so=
me of the follow-up work we conducted. We would also like</div><div style=
=3D"font-size:12.8px">to thank the Mimblewimble development community for c=
oining the term "stempool,"</div><div style=3D"font-size:12.8px">=
which we happily adopted for this implementation.</div><div style=3D"font-s=
ize:12.8px"><br></div><div style=3D"font-size:12.8px">All the best,</div><d=
iv style=3D"font-size:12.8px">Brad Denby <<a href=3D"mailto:bdenby@cmu.e=
du" target=3D"_blank">bdenby@cmu.edu</a>></div><div style=3D"font-size:1=
2.8px">Andrew Miller <<a href=3D"mailto:soc1024@illinois.edu" target=3D"=
_blank">soc1024@illinois.edu</a>></div><div style=3D"font-size:12.8px">G=
iulia Fanti <<a href=3D"mailto:gfanti@andrew.cmu.edu" target=3D"_blank">=
gfanti@andrew.cmu.edu</a>></div><div style=3D"font-size:12.8px">Surya Ba=
kshi <<a href=3D"mailto:sbakshi3@illinois.edu" target=3D"_blank">sbakshi=
3@illinois.edu</a>></div><div style=3D"font-size:12.8px">Shaileshh Bojja=
Venkatakrishnan <<a href=3D"mailto:shaileshh.bv@gmail.com" target=3D"_b=
lank">shaileshh.bv@gmail.com</a>></div><div style=3D"font-size:12.8px">P=
ramod Viswanath <<a href=3D"mailto:pramodv@illinois.edu" target=3D"_blan=
k">pramodv@illinois.edu</a>></div></div>
--00000000000006c8e7056bd99630--
|
