summaryrefslogtreecommitdiff
path: root/45/71975e3040f6c3a576a85d6097302be8454b8e
blob: 99be642c15ef04cf1abc3861ef3da6cfc84f2267 (plain)
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
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
Return-Path: <gfanti@andrew.cmu.edu>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 8D308CAF
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun,  8 Jul 2018 12:51:21 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f41.google.com (mail-oi0-f41.google.com
	[209.85.218.41])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 12E13334
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun,  8 Jul 2018 12:51:20 +0000 (UTC)
Received: by mail-oi0-f41.google.com with SMTP id c6-v6so31290629oiy.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 08 Jul 2018 05:51:19 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=andrew-cmu-edu.20150623.gappssmtp.com; s=20150623;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to; 
	bh=XTV+NCf47jgYj8zk9IkU1SKTXGbsWNkJtW8xn1/a2LM=;
	b=h9cI0iqMye8yFe486QnVUSGHiuNd7L1MeXbNzisbqyAiPvOdzAo85zbNfIGDeT9QFR
	xMfLsxQ/845/JNWa/q7zA45eYs/i6zeVx5aCNpcEE7AQ3rDgZ+1Exuj9eHxO8cjfLa6t
	N5B2moaPn42BvwdFR1dciXbp5MjxeUHh5iAMObgwDH8AfXCNtUGrSEGP2sjSdJGuOMq8
	TH1IxTA8SwLramduOOWEtscL4Ttyi5zDAn9gFMqUBfnpT8lnQ8ne2Y5wvTcVdjYZ8x+5
	QMPj6en2gCVaOCW8LxLsffwFtfc7xDePg0Jo+QNUUImbE3c5IlDWKeag5aiYoGgPt8ha
	/8CA==
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=XTV+NCf47jgYj8zk9IkU1SKTXGbsWNkJtW8xn1/a2LM=;
	b=d0PCXXO/P8je1TuR2xYQOOLFlin3RhZFN/HGv4teEy9dSTPo2E2+Z7OX/cMoQF2XgI
	9XuTfIJVUYC7L+/JEYinjq1WT92wdOI8+e1KipAWzAZlcreZQJWLHZ4gdImaB7yMnXt4
	8FG1/6Bcn3kNlrtLjT2cXPH7PLCiNKCp5llAr+q0Npx+jr0dDe8xUPjGPCBVHxJPYHMr
	58ucojny/juzTyy+aoq0ieZcfX67E5Ka3dCcVZwuv/5P4rUsVRYOxMtXOVbP+xQt1J6D
	OkUwzCjx39NJrgZTjyFQyqU44Garmrgl1nMtnKkCvnFXQsmFXwykoqGX1TYOFsxOidhz
	s6nw==
X-Gm-Message-State: APt69E2CTqF7Z0U9qy5U86JfJ1ZKtyN3demAiGFnMRrK/iH3VqnVbnZw
	yxHiIge0MF9IEh7SrTmZalYG79Mq1HA5CCnOYQXzF6yq
X-Google-Smtp-Source: AAOMgpdOsuBg6CaWubBmoqB6oHNFp66sAzVki34ynHRgSxNUkoLT6YTlLshSr6JNMQiAhnX6QTsZylE6UUr6y882h38=
X-Received: by 2002:aca:2ec9:: with SMTP id
	u192-v6mr13675885oiu.17.1531054279092; 
	Sun, 08 Jul 2018 05:51:19 -0700 (PDT)
MIME-Version: 1.0
References: <mailman.3774.1530901879.19027.bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <mailman.3774.1530901879.19027.bitcoin-dev@lists.linuxfoundation.org>
From: Giulia Fanti <gfanti@andrew.cmu.edu>
Date: Sun, 8 Jul 2018 08:50:43 -0400
Message-ID: <CAB6Q0ym7uqtJembXuib+VbWHbUGYTQRtP-taJH_ns780a2jDWQ@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="0000000000006ff6e705707c5af9"
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: Sun, 08 Jul 2018 14:26:30 +0000
Subject: Re: [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: Sun, 08 Jul 2018 12:51:21 -0000

--0000000000006ff6e705707c5af9
Content-Type: text/plain; charset="UTF-8"

 Hi Till,

Thank you for the comments! Responses are inline:

* Could you elaborate on the reasoning behind choosing the periodic route
> shuffling interval to be around 10 minutes? I guess that there is some
> tradeoff between making intersection attacks possible by choosing a too
> small interval, and making graph-learning attacks possible by choosing a
> too large interval. Intuitively, this interval should depend on the number
> of forwarded Dandelion transactions, because these are the events that leak
> information, and not the absolute elapsed time. On the other hand, making
> the interval dependent on the number of processed transactions would allow
> an active adversary to trigger route shuffling by sending Dandelion
> transaction to specific peers, which could enable intersection attacks...
>
Your intuition is spot-on in the sense that shorter intervals help with
intersection attacks, whereas longer ones help with graph learning. On that
tradeoff curve, we would recommend favoring graph learning attacks;
intersection attacks can be really devastating (with recall tending to 1),
whereas graph learning attacks still have limited recall and precision. If
we decide to allow graph learning in order to prevent intersection attacks,
the natural conclusion would be to use as long a time interval as possible.
We are open to changing this time interval; 10 minutes was just a heuristic
we proposed at the time of writing.


> * Speaking of active adversaries: Adversaries could send a large number of
> transactions to selected peers - either by creating the transactions on
> their own, or by relaying (Dandelion) transactions observed by the
> adversary?s peers to the selected peer. Could this allow the adversary to
> launch fingerprinting attacks on the selected peer by comparing the
> observed propagation of the transactions relayed through the peer to other
> transactions observed?
>
Yes, this is one of the main ways we envision adversaries potentially
learning the graph in practice.


> * If an adversary performs a black-hole attack (i.e., drops Dandelion
> transactions), and if the adversary is able to identify the diffusion
> source, reconstruction of parts of the anonymity graph (i.e., the part
> between the diffusion source and the last peer before the black-hole) might
> be possible. I understand that the adversary does not gain much from the
> knowledge of the anonymity graph, but it nonetheless helps the adversary.
>
This is also true. Using a small shuffle time interval  would help prevent
this, but if we go with a longer interval, this approach could certainly
help with graph learning.


> * Out of personal interest: Inferring Bitcoin?s network topology is hard.
> I think it?s wise to assume a strong adversary that has perfect knowledge
> of the topology, but can you make any statements on the sensitivity of the
> adversary?s precision and recall regarding imperfect topology knowledge?
>
We only studied what happens when the adversary has full knowledge of the
graph and local knowledge (i.e. the spy nodes know their own neighbors, but
nothing else). We did not study what happens when the adversary has partial
graph knowledge, but that would be an interesting and useful question to
look at.


>
> --Till
>
>
> From: bitcoin-dev-bounces@lists.linuxfoundation.org [mailto:
> bitcoin-dev-bounces@lists.linuxfoundation.org] On Behalf Of Bradley Denby
> via bitcoin-dev
> Sent: Monday, June 4, 2018 10:30 PM
> To: bitcoin-dev@lists.linuxfoundation.org
> Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving
> Transaction Propagation
>
> Hello all,
>
> We now have an arXiv preprint of our latest findings available, which
> provides additional details regarding Dandelion:
> https://arxiv.org/pdf/1805.11060.pdf
>
> Note that Dandelion's precision guarantees are at the population level,
> while the recall guarantees can be interpreted as individual guarantees.
> Expected recall is equivalent to the probability of an adversary
> associating a single transaction with a given source.
>
> Since these guarantees are probabilistic, a node cannot be sure whether
> all of its peers are monitoring it. Dandelion does not protect against
> these adversaries, and individuals who are worried about targeted
> deanonymization should still use Tor.
>
> One way to conceptualize Dandelion is as a "public health" fix or an
> "anonymity vaccination." Higher adoption leads to greater benefits, even
> for those who are not using Tor. Individuals who adopt Dandelion benefit
> because their transactions make at least one hop before diffusing (or more
> as adoption increases).
>
> Nevertheless, the probabilistic nature of the guarantees means that they
> are not absolute. We have shown that any solution based only on routing
> cannot be absolute due to fundamental lower bounds on precision and recall.
>
> Thank you to Eric Voskuil, Pieter Wuille, Suhas Daftuar, Christian Decker,
> and Tim Ruffing for the recent feedback!
>
> On Thu, May 10, 2018 at 8:59 AM, Bradley Denby <bdenby@cmu.edu> wrote:
> 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>
>
>
> ------------------------------
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> End of bitcoin-dev Digest, Vol 38, Issue 8
> ******************************************
>

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

<div dir=3D"ltr"><div class=3D"gmail_quote"><div>=C2=A0Hi Till,=C2=A0</div>=
<div><br></div><div>Thank you for the comments! Responses are inline:</div>=
<div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex=
;border-left:1px #ccc solid;padding-left:1ex">
* Could you elaborate on the reasoning behind choosing the periodic route s=
huffling interval to be around 10 minutes? I guess that there is some trade=
off between making intersection attacks possible by choosing a too small in=
terval, and making graph-learning attacks possible by choosing a too large =
interval. Intuitively, this interval should depend on the number of forward=
ed Dandelion transactions, because these are the events that leak informati=
on, and not the absolute elapsed time. On the other hand, making the interv=
al dependent on the number of processed transactions would allow an active =
adversary to trigger route shuffling by sending Dandelion transaction to sp=
ecific peers, which could enable intersection attacks...<br></blockquote><d=
iv>Your intuition is spot-on in the sense that shorter intervals help with =
intersection attacks, whereas longer ones help with graph learning. On that=
 tradeoff curve, we would recommend favoring graph learning attacks; inters=
ection attacks can be really devastating (with recall tending to 1), wherea=
s graph learning attacks still have limited recall and precision. If we dec=
ide to allow graph learning in order to prevent intersection attacks, the n=
atural conclusion would be to use as long a time interval as possible. We a=
re open to changing this time interval; 10 minutes was just a heuristic we =
proposed at the time of writing.=C2=A0</div><div>=C2=A0</div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;p=
adding-left:1ex">
* Speaking of active adversaries: Adversaries could send a large number of =
transactions to selected peers - either by creating the transactions on the=
ir own, or by relaying (Dandelion) transactions observed by the adversary?s=
 peers to the selected peer. Could this allow the adversary to launch finge=
rprinting attacks on the selected peer by comparing the observed propagatio=
n of the transactions relayed through the peer to other transactions observ=
ed?<br></blockquote><div>Yes, this is one of the main ways we envision adve=
rsaries potentially learning the graph in practice.=C2=A0=C2=A0</div><div>=
=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex">
* If an adversary performs a black-hole attack (i.e., drops Dandelion trans=
actions), and if the adversary is able to identify the diffusion source, re=
construction of parts of the anonymity graph (i.e., the part between the di=
ffusion source and the last peer before the black-hole) might be possible. =
I understand that the adversary does not gain much from the knowledge of th=
e anonymity graph, but it nonetheless helps the adversary.<br></blockquote>=
<div>This is also true. Using a small shuffle time interval=C2=A0 would hel=
p prevent this, but if we go with a longer interval, this approach could ce=
rtainly help with graph learning.</div><div>=C2=A0</div><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex">
* Out of personal interest: Inferring Bitcoin?s network topology is hard. I=
 think it?s wise to assume a strong adversary that has perfect knowledge of=
 the topology, but can you make any statements on the sensitivity of the ad=
versary?s precision and recall regarding imperfect topology knowledge?<br><=
/blockquote><div>We only studied what happens when the adversary has full k=
nowledge of the graph and local knowledge (i.e. the spy nodes know their ow=
n neighbors, but nothing else). We did not study what happens when the adve=
rsary has partial graph knowledge, but that would be an interesting and use=
ful question to look at.</div><div>=C2=A0</div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1e=
x">
<br>
--Till<br>
<br>
<br>
From: <a href=3D"mailto:bitcoin-dev-bounces@lists.linuxfoundation.org" targ=
et=3D"_blank">bitcoin-dev-bounces@lists.linuxfoundation.org</a> [mailto:<a =
href=3D"mailto:bitcoin-dev-bounces@lists.linuxfoundation.org" target=3D"_bl=
ank">bitcoin-dev-bounces@lists.linuxfoundation.org</a>] On Behalf Of Bradle=
y Denby via bitcoin-dev<br>
Sent: Monday, June 4, 2018 10:30 PM<br>
To: <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a><br>
Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Tra=
nsaction Propagation<br>
<br>
Hello all,<br>
<br>
We now have an arXiv preprint of our latest findings available, which provi=
des additional details regarding Dandelion: <a href=3D"https://arxiv.org/pd=
f/1805.11060.pdf" rel=3D"noreferrer" target=3D"_blank">https://arxiv.org/pd=
f/1805.11060.pdf</a><br>
<br>
Note that Dandelion&#39;s precision guarantees are at the population level,=
 while the recall guarantees can be interpreted as individual guarantees. E=
xpected recall is equivalent to the probability of an adversary associating=
 a single transaction with a given source.<br>
<br>
Since these guarantees are probabilistic, a node cannot be sure whether all=
 of its peers are monitoring it. Dandelion does not protect against these a=
dversaries, and individuals who are worried about targeted deanonymization =
should still use Tor.<br>
<br>
One way to conceptualize Dandelion is as a &quot;public health&quot; fix or=
 an &quot;anonymity vaccination.&quot; Higher adoption leads to greater ben=
efits, even for those who are not using Tor. Individuals who adopt Dandelio=
n benefit because their transactions make at least one hop before diffusing=
 (or more as adoption increases).<br>
<br>
Nevertheless, the probabilistic nature of the guarantees means that they ar=
e not absolute. We have shown that any solution based only on routing canno=
t be absolute due to fundamental lower bounds on precision and recall.<br>
<br>
Thank you to Eric Voskuil, Pieter Wuille, Suhas Daftuar, Christian Decker, =
and Tim Ruffing for the recent feedback!<br>
<br>
On Thu, May 10, 2018 at 8:59 AM, Bradley Denby &lt;<a href=3D"mailto:bdenby=
@cmu.edu" target=3D"_blank">bdenby@cmu.edu</a>&gt; wrote:<br>
Hi all,<br>
<br>
We&#39;re writing with an update on the Dandelion project. As a reminder, D=
andelion<br>
is a practical, lightweight privacy solution that provides Bitcoin users fo=
rmal<br>
anonymity guarantees. While other privacy solutions aim to protect individu=
al<br>
users, Dandelion protects privacy by limiting the capability of adversaries=
 to<br>
deanonymize the entire network.<br>
<br>
Bitcoin&#39;s transaction spreading protocol is vulnerable to deanonymizati=
on<br>
attacks. When a node generates a transaction without Dandelion, it transmit=
s<br>
that transaction to its peers with independent, exponential delays. This<br=
>
approach, known as diffusion in academia, allows network adversaries to lin=
k<br>
transactions to IP addresses.<br>
<br>
Dandelion prevents this class of attacks by sending transactions over a ran=
domly<br>
selected path before diffusion. Transactions travel along this path during =
the<br>
&quot;stem phase&quot; and are then diffused during the &quot;fluff phase&q=
uot; (hence the name<br>
Dandelion). We have shown that this routing protocol provides near-optimal<=
br>
anonymity guarantees among schemes that do not introduce additional encrypt=
ion<br>
mechanisms.<br>
<br>
Since the last time we contacted the list, we have:<br>
=C2=A0- Completed additional theoretical analysis and simulations<br>
=C2=A0- Built a working prototype<br>
=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bitcoin/tree/dandelion"=
 rel=3D"noreferrer" target=3D"_blank">https://github.com/mablem8/bitcoin/tr=
ee/dandelion</a>)<br>
=C2=A0- Built a test suite for the prototype<br>
=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bitcoin/blob/dandelion/=
test/functional/p2p_dandelion.py" rel=3D"noreferrer" target=3D"_blank">http=
s://github.com/mablem8/bitcoin/blob/dandelion/test/functional/p2p_dandelion=
.py</a>)<br>
=C2=A0- Written detailed documentation for the new implementation<br>
=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bips/blob/master/bip-da=
ndelion/dandelion-reference-documentation.pdf" rel=3D"noreferrer" target=3D=
"_blank">https://github.com/mablem8/bips/blob/master/bip-dandelion/dandelio=
n-reference-documentation.pdf</a>)<br>
<br>
Among other things, one question we&#39;ve addressed in our additional anal=
ysis is<br>
how to route messages during the stem phase. For example, if two Dandelion<=
br>
transactions arrive at a node from different inbound peers, to which Dandel=
ion<br>
destination(s) should these transactions be sent? We have found that some<b=
r>
choices are much better than others.<br>
<br>
Consider the case in which each Dandelion transaction is forwarded to a<br>
Dandelion destination selected uniformly at random. We have shown that this=
<br>
approach results in a fingerprint attack allowing network-level botnet<br>
adversaries to achieve total deanonymization of the P2P network after obser=
ving<br>
less than ten transactions per node.<br>
<br>
To avoid this issue, we suggest &quot;per-inbound-edge&quot; routing. Each =
inbound peer is<br>
assigned a particular Dandelion destination. Each Dandelion transaction tha=
t<br>
arrives via this peer is forwarded to the same Dandelion destination.<br>
Per-inbound-edge routing breaks the described attack by blocking an adversa=
ry&#39;s<br>
ability to construct useful fingerprints.<br>
<br>
This iteration of Dandelion has been tested on our own small network, and w=
e<br>
would like to get the implementation in front of a wider audience. An updat=
ed<br>
BIP document with further details on motivation, specification, compatibili=
ty,<br>
and implementation is located here:<br>
<a href=3D"https://github.com/mablem8/bips/blob/master/bip-dandelion.mediaw=
iki" rel=3D"noreferrer" target=3D"_blank">https://github.com/mablem8/bips/b=
lob/master/bip-dandelion.mediawiki</a><br>
<br>
We would like to thank the Bitcoin Core developers and Gregory Maxwell in<b=
r>
particular for their insightful comments, which helped to inform this<br>
implementation and some of the follow-up work we conducted. We would also l=
ike<br>
to thank the Mimblewimble development community for coining the term &quot;=
stempool,&quot;<br>
which we happily adopted for this implementation.<br>
<br>
All the best,<br>
Brad Denby &lt;<a href=3D"mailto:bdenby@cmu.edu" target=3D"_blank">bdenby@c=
mu.edu</a>&gt;<br>
Andrew Miller &lt;<a href=3D"mailto:soc1024@illinois.edu" target=3D"_blank"=
>soc1024@illinois.edu</a>&gt;<br>
Giulia Fanti &lt;<a href=3D"mailto:gfanti@andrew.cmu.edu" target=3D"_blank"=
>gfanti@andrew.cmu.edu</a>&gt;<br>
Surya Bakshi &lt;<a href=3D"mailto:sbakshi3@illinois.edu" target=3D"_blank"=
>sbakshi3@illinois.edu</a>&gt;<br>
Shaileshh Bojja Venkatakrishnan &lt;<a href=3D"mailto:shaileshh.bv@gmail.co=
m" target=3D"_blank">shaileshh.bv@gmail.com</a>&gt;<br>
Pramod Viswanath &lt;<a href=3D"mailto:pramodv@illinois.edu" target=3D"_bla=
nk">pramodv@illinois.edu</a>&gt;<br>
<br>
<br>
------------------------------<br>
<br>
_______________________________________________<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>
<br>
<br>
End of bitcoin-dev Digest, Vol 38, Issue 8<br>
******************************************<br>
</blockquote></div></div>

--0000000000006ff6e705707c5af9--