Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 5B615D29 for ; 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 ; Mon, 4 Jun 2018 20:29:52 +0000 (UTC) Received: by mail-lf0-f42.google.com with SMTP id i83-v6so15120408lfh.5 for ; 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: References: From: Bradley Denby Date: Mon, 4 Jun 2018 16:29:50 -0400 Message-ID: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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 > Andrew Miller > Giulia Fanti > Surya Bakshi > Shaileshh Bojja Venkatakrishnan > Pramod Viswanath > --000000000000aa4f77056dd6cb5a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hello all,

We now have an ar= Xiv preprint of our latest findings available, which provides additional de= tails regarding Dandelion: https://arxiv.org/pdf/1805.11060.pdf

Note tha= t Dandelion'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.

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.

One way to conceptualize Dandelion is as a = "public health" fix or an "anonymity vaccination." 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).

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.

Thank you to Eric Voskuil, Pieter Wuil= le, Suhas Daftuar, Christian Decker, and Tim Ruffing for the recent feedbac= k!

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 Dandelio= n project. As a reminder, Dandelion
is= a practical, lightweight privacy solution that provides Bitcoin users form= al
anonymity guarantees. While other p= rivacy solutions aim to protect individual
users, Dandelion protects privacy by limiting the capability of advers= aries to
deanonymize the entire networ= k.

Bitcoin's transaction spreading protocol is vulnerable to deanon= ymization
attacks. When a node generat= es a transaction without Dandelion, it transmits
that transaction to its peers with independent, exponential dela= ys. This
approach, known as diffusion = in academia, allows network adversaries to link
transactions to IP addresses.

Dandelion prevents this class o= f 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 rou= ting protocol provides near-optimal
an= onymity guarantees among schemes that do not introduce additional encryptio= n
mechanisms.

Since the last time = we contacted the list, we have:
=C2=A0= - Completed additional theoretical analysis and simulations
=C2=A0- Built a working prototype
=C2=A0- Built a = test suite for the prototype
=C2=A0- Written detailed documentation for th= e new implementation

Among other things, one question we've addressed in o= ur additional analysis is
how to route= messages during the stem phase. For example, if two Dandelion
transactions arrive at a node from different inbou= nd peers, to which Dandelion
destinati= on(s) should these transactions be sent? We have found that some
choices are much better than others.

Conside= r the case in which each Dandelion transaction is forwarded to a
Dandelion destination selected uniformly at rand= om. We have shown that this
approach r= esults 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.

<= div style=3D"font-size:12.8px">To avoid this issue, we suggest "per-in= bound-edge" routing. Each inbound peer is
assigned a particular Dandelion destination. Each Dandelion transa= ction that
arrives via this peer is fo= rwarded to the same Dandelion destination.
Per-inbound-edge routing breaks the described attack by blocking an ad= versary's
ability to construct use= ful fingerprints.

This iteration of Dandelion has been tested on our ow= n 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 impl= ementation is located here:

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 Mimb= lewimble development community for coining the term "stempool,"
which we happily adopted for this imple= mentation.

All the best,
Brad Denb= y <bdenby@cmu.edu>
Shaileshh Bojja Venkatakrishnan <shaileshh.bv@gmail.com>
Pramod Viswanath <pramodv@illinois.edu>
<= /div>

--000000000000aa4f77056dd6cb5a--