path: root/aa/561d4603479cba95c7a2956c8f942c0e8a95d3

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 5B615D29
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  4 Jun 2018 20:29:54 +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 D269B6F2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  4 Jun 2018 20:29:52 +0000 (UTC)
Received: by mail-lf0-f42.google.com with SMTP id i83-v6so15120408lfh.5
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 04 Jun 2018 13:29:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=cmu-edu.20150623.gappssmtp.com; s=20150623;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=b7xgsYHcYSGK8XM+pufP39V01Bh+3fUsWCrwpOr1bII=;
	b=SCLA1EJJ06y8XZ7yrB6QtrtMa0/0+EUsVVxUkHYssC5RibDgDPxyXinrlR4cR7LOAQ
	nkyMqMb2uoe17UsuQZjuoIseHOC6paiXYyL564f34Yi5ZmRhqxBZZIeE4eHUGKZinGZD
	H55ruGoyiRVpLL1QJO8i8eFflQMRjroaIm8J2n0v4YXSP/1FAzKrFo+daAIFG/qmhgyW
	Y3ghSyfKSNSvZ9bTUnR2szZXmevFn3X0MhKRn/0mRG3A8PkN7eZqydUqz/BFQsIcw51P
	x9ZeGDKlgGCeT1s5wiIzbREE0G+valXeNsGEcVfK0OCPqZbABHmglCBJ8GjRXFNOFQCr
	Mtqw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to;
	bh=b7xgsYHcYSGK8XM+pufP39V01Bh+3fUsWCrwpOr1bII=;
	b=VFFFinWH02S80Gg/CBtbS3njzoay+MiBViTbsKLmm5ba6NuG+0ohBV9UW4y2isXgbv
	EbgnF327D4YLm1lCdtst26zpLkJa3WoDqDFCjRPzQmEEj6Y4LSPH7kq1Qa7Rn3Q2ElMY
	KQg8N9ecB7ra4tqHql7lOYEZLUs1iHOWEcXEF2/yg7/zE5gOJtoQwl6CJ+sNfH2zaMwd
	kteh/NXbrvMx3kW7iaTcAx51liXozgocKcCeVVTVBFtiAwDaBIF1Z1Ch/P5YuLSEwZXD
	2FsQl9FpLwB5RzqHx9vQaeQg2aDNdVI4tbj4a3ZUulbUFFzZD4R7WrWy1eREIrWFlhOY
	d1mg==
X-Gm-Message-State: ALKqPwezicL0mAfWZOM0l0JRA+R3zfVmy51yjlevVzYk2cLoBhK7Q+Ps
	V+5z5pUJkm0A6qAtNnGJ40pXa/5qeaLjaCvK46oXu/A=
X-Google-Smtp-Source: ADUXVKKqZfUgJqNCwvihrX0Lp2LwZ/EpjGPZFB5UuxRitDzxVhYJ6h5b9z0tyYPEN44YfLazR4PqKTIYHmHaLMjc1PQ=
X-Received: by 2002:a19:1647:: with SMTP id
	m68-v6mr14346308lfi.131.1528144190914; 
	Mon, 04 Jun 2018 13:29:50 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a2e:5046:0:0:0:0:0 with HTTP;
	Mon, 4 Jun 2018 13:29:50 -0700 (PDT)
In-Reply-To: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
References: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
From: Bradley Denby <bdenby@cmu.edu>
Date: Mon, 4 Jun 2018 16:29:50 -0400
Message-ID: <CAGq_bNJmnKjvK_zL6_drVRmYqqBJOb0tULDHWSf58VSJs-DbAA@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="000000000000aa4f77056dd6cb5a"
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: Mon, 04 Jun 2018 20:31:42 +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: Mon, 04 Jun 2018 20:29:54 -0000

--000000000000aa4f77056dd6cb5a
Content-Type: text/plain; charset="UTF-8"

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/fun
> ctional/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>
>

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

<div dir=3D"ltr"><div>Hello all,</div><div><br></div><div>We now have an ar=
Xiv preprint of our latest findings available, which provides additional de=
tails regarding Dandelion: <a href=3D"https://arxiv.org/pdf/1805.11060.pdf"=
>https://arxiv.org/pdf/1805.11060.pdf</a></div><div><br></div><div>Note tha=
t Dandelion&#39;s precision guarantees are at the population level, while t=
he recall guarantees can be interpreted as individual guarantees. Expected =
recall is equivalent to the probability of an adversary associating a singl=
e transaction with a given source.</div><div><br></div><div>Since these gua=
rantees are probabilistic, a node cannot be sure whether all of its peers a=
re monitoring it. Dandelion does not protect against these adversaries, and=
 individuals who are worried about targeted deanonymization should still us=
e Tor.</div><div><br></div><div>One way to conceptualize Dandelion is as a =
&quot;public health&quot; fix or an &quot;anonymity vaccination.&quot; High=
er adoption leads to greater benefits, even for those who are not using Tor=
. Individuals who adopt Dandelion benefit because their transactions make a=
t least one hop before diffusing (or more as adoption increases).</div><div=
><br></div><div>Nevertheless, the probabilistic nature of the guarantees me=
ans 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.</div><div><br></div><div>Thank you to Eric Voskuil, Pieter Wuil=
le, Suhas Daftuar, Christian Decker, and Tim Ruffing for the recent feedbac=
k!</div></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On =
Thu, May 10, 2018 at 8:59 AM, Bradley Denby <span dir=3D"ltr">&lt;<a href=
=3D"mailto:bdenby@cmu.edu" target=3D"_blank">bdenby@cmu.edu</a>&gt;</span> =
wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div style=3D"fon=
t-size:12.8px">Hi all,</div><div style=3D"font-size:12.8px"><br></div><div =
style=3D"font-size:12.8px">We&#39;re writing with an update on the Dandelio=
n project. As a reminder, Dandelion</div><div style=3D"font-size:12.8px">is=
 a practical, lightweight privacy solution that provides Bitcoin users form=
al</div><div style=3D"font-size:12.8px">anonymity guarantees. While other p=
rivacy solutions aim to protect individual</div><div style=3D"font-size:12.=
8px">users, Dandelion protects privacy by limiting the capability of advers=
aries to</div><div style=3D"font-size:12.8px">deanonymize the entire networ=
k.</div><div style=3D"font-size:12.8px"><br></div><div style=3D"font-size:1=
2.8px">Bitcoin&#39;s transaction spreading protocol is vulnerable to deanon=
ymization</div><div style=3D"font-size:12.8px">attacks. When a node generat=
es a transaction without Dandelion, it transmits</div><div style=3D"font-si=
ze:12.8px">that transaction to its peers with independent, exponential dela=
ys. This</div><div style=3D"font-size:12.8px">approach, known as diffusion =
in academia, allows network adversaries to link</div><div style=3D"font-siz=
e:12.8px">transactions to IP addresses.</div><div style=3D"font-size:12.8px=
"><br></div><div style=3D"font-size:12.8px">Dandelion prevents this class o=
f attacks by sending transactions over a randomly</div><div style=3D"font-s=
ize:12.8px">selected path before diffusion. Transactions travel along this =
path during the</div><div style=3D"font-size:12.8px">&quot;stem phase&quot;=
 and are then diffused during the &quot;fluff phase&quot; (hence the name</=
div><div style=3D"font-size:12.8px">Dandelion). We have shown that this rou=
ting protocol provides near-optimal</div><div style=3D"font-size:12.8px">an=
onymity guarantees among schemes that do not introduce additional encryptio=
n</div><div style=3D"font-size:12.8px">mechanisms.</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 analysis and simulations</div><div style=
=3D"font-size:12.8px">=C2=A0- Built a working prototype</div><div style=3D"=
font-size:12.8px">=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bitco=
in/tree/dandelion" target=3D"_blank">https://github.com/mablem8/b<wbr>itcoi=
n/tree/dandelion</a>)</div><div style=3D"font-size:12.8px">=C2=A0- Built a =
test suite for the prototype</div><div style=3D"font-size:12.8px">=C2=A0 =
=C2=A0(<a href=3D"https://github.com/mablem8/bitcoin/blob/dandelion/test/fu=
nctional/p2p_dandelion.py" target=3D"_blank">https://github.com/mablem8/b<w=
br>itcoin/blob/dandelion/test/fun<wbr>ctional/p2p_dandelion.py</a>)</div><d=
iv style=3D"font-size:12.8px">=C2=A0- Written detailed documentation for th=
e 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/=
b<wbr>ips/blob/master/bip-dandelion/<wbr>dandelion-reference-documentat<wbr=
>ion.pdf</a>)</div><div style=3D"font-size:12.8px"><br></div><div style=3D"=
font-size:12.8px">Among other things, one question we&#39;ve addressed in o=
ur additional analysis is</div><div style=3D"font-size:12.8px">how to route=
 messages during the stem phase. For example, if two Dandelion</div><div st=
yle=3D"font-size:12.8px">transactions arrive at a node from different inbou=
nd peers, to which Dandelion</div><div style=3D"font-size:12.8px">destinati=
on(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 s=
tyle=3D"font-size:12.8px"><br></div><div style=3D"font-size:12.8px">Conside=
r the case in which each Dandelion transaction is forwarded to a</div><div =
style=3D"font-size:12.8px">Dandelion destination selected uniformly at rand=
om. We have shown that this</div><div style=3D"font-size:12.8px">approach r=
esults in a fingerprint attack allowing network-level botnet</div><div styl=
e=3D"font-size:12.8px">adversaries to achieve total deanonymization of the =
P2P network after observing</div><div style=3D"font-size:12.8px">less than =
ten transactions per node.</div><div style=3D"font-size:12.8px"><br></div><=
div style=3D"font-size:12.8px">To avoid this issue, we suggest &quot;per-in=
bound-edge&quot; routing. Each inbound peer is</div><div style=3D"font-size=
:12.8px">assigned a particular Dandelion destination. Each Dandelion transa=
ction that</div><div style=3D"font-size:12.8px">arrives via this peer is fo=
rwarded to the same Dandelion destination.</div><div style=3D"font-size:12.=
8px">Per-inbound-edge routing breaks the described attack by blocking an ad=
versary&#39;s</div><div style=3D"font-size:12.8px">ability to construct use=
ful fingerprints.</div><div style=3D"font-size:12.8px"><br></div><div style=
=3D"font-size:12.8px">This iteration of Dandelion has been tested on our ow=
n small network, and we</div><div style=3D"font-size:12.8px">would like to =
get the implementation in front of a wider audience. An updated</div><div s=
tyle=3D"font-size:12.8px">BIP document with further details on motivation, =
specification, compatibility,</div><div style=3D"font-size:12.8px">and impl=
ementation is located here:</div><div style=3D"font-size:12.8px"><a href=3D=
"https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki" targe=
t=3D"_blank">https://github.com/mablem8/bip<wbr>s/blob/master/bip-dandelion=
.<wbr>mediawiki</a></div><div style=3D"font-size:12.8px"><br></div><div sty=
le=3D"font-size:12.8px">We would like to thank the Bitcoin Core developers =
and Gregory Maxwell in</div><div style=3D"font-size:12.8px">particular for =
their insightful comments, which helped to inform this</div><div style=3D"f=
ont-size:12.8px">implementation and some of the follow-up work we conducted=
. We would also like</div><div style=3D"font-size:12.8px">to thank the Mimb=
lewimble development community for coining the term &quot;stempool,&quot;</=
div><div style=3D"font-size:12.8px">which we happily adopted for this imple=
mentation.</div><div style=3D"font-size:12.8px"><br></div><div style=3D"fon=
t-size:12.8px">All the best,</div><div style=3D"font-size:12.8px">Brad Denb=
y &lt;<a href=3D"mailto:bdenby@cmu.edu" target=3D"_blank">bdenby@cmu.edu</a=
>&gt;</div><div style=3D"font-size:12.8px">Andrew Miller &lt;<a href=3D"mai=
lto:soc1024@illinois.edu" target=3D"_blank">soc1024@illinois.edu</a>&gt;</d=
iv><div style=3D"font-size:12.8px">Giulia Fanti &lt;<a href=3D"mailto:gfant=
i@andrew.cmu.edu" target=3D"_blank">gfanti@andrew.cmu.edu</a>&gt;</div><div=
 style=3D"font-size:12.8px">Surya Bakshi &lt;<a href=3D"mailto:sbakshi3@ill=
inois.edu" target=3D"_blank">sbakshi3@illinois.edu</a>&gt;</div><div style=
=3D"font-size:12.8px">Shaileshh Bojja Venkatakrishnan &lt;<a href=3D"mailto=
:shaileshh.bv@gmail.com" target=3D"_blank">shaileshh.bv@gmail.com</a>&gt;</=
div><div style=3D"font-size:12.8px">Pramod Viswanath &lt;<a href=3D"mailto:=
pramodv@illinois.edu" target=3D"_blank">pramodv@illinois.edu</a>&gt;</div><=
/div>
</blockquote></div><br></div>

--000000000000aa4f77056dd6cb5a--