Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 6E173A80 for ; 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 ; Thu, 10 May 2018 12:59:14 +0000 (UTC) Received: by mail-lf0-f42.google.com with SMTP id t129-v6so2847786lff.3 for ; 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 Date: Thu, 10 May 2018 08:59:12 -0400 Message-ID: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 Andrew Miller Giulia Fanti Surya Bakshi Shaileshh Bojja Venkatakrishnan Pramod Viswanath --00000000000006c8e7056bd99630 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi all,

We're writ= ing with an update on the Dandelion project. As a reminder, Dandelion
=
is a practical, lightweight privacy solutio= n that provides Bitcoin users formal
a= nonymity guarantees. While other privacy solutions aim to protect individua= l
users, Dandelion protects privacy by= limiting the capability of adversaries to
deanonymize the entire network.
<= br>
Bitcoin's transaction spreadin= g protocol is vulnerable to deanonymization
attacks. When a node generates a transaction without Dandelion, it tr= ansmits
that transaction to its peers = with independent, exponential delays. This
approach, known as diffusion in academia, allows network adversaries t= o link
transactions to IP addresses.

Dandelion prevents this class of attacks by sending transactions over a = randomly
selected path before diffusio= n. Transactions travel along this path during the
"stem phase" and are then diffused during the "f= luff phase" (hence the name
Dande= lion). We have shown that this routing protocol provides near-optimal
=
anonymity guarantees among schemes that do = not introduce additional encryption
me= chanisms.

Since the last time we contacted the list, we have:
=C2=A0- Completed additional theoretical analys= is and simulations
=C2=A0- Built a wor= king prototype
=C2=A0- Built a test suite for the prototype
=C2=A0 =C2=A0(https://github.com/mablem8/bitcoin/blob/dandelion/test/func= tional/p2p_dandelion.py)
=C2=A0- W= ritten detailed documentation for the new implementation

Among other things, o= ne question we've addressed in our additional analysis is
how to route messages during the stem phase. For ex= ample, if two Dandelion
transactions a= rrive 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 tran= saction is forwarded to a
Dandelion de= stination selected uniformly at random. We have shown that this
approach results in a fingerprint attack allowing= network-level botnet
adversaries to a= chieve 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 Dandelio= n destination. Each Dandelion transaction that
arrives via this peer is forwarded to the same Dandelion destinati= on.
Per-inbound-edge routing breaks th= e 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 wi= der audience. An updated
BIP document = with further details on motivation, specification, compatibility,
and implementation is located here:

We would like t= o thank the Bitcoin Core developers and Gregory Maxwell in
particular for their insightful comments, which helpe= d to inform this
implementation and so= me of the follow-up work we conducted. We would also like
to thank the Mimblewimble development community for c= oining the term "stempool,"
= which we happily adopted for this implementation.

All the best,
Brad Denby <bdenby@cmu.edu>
Andrew Miller <soc1024@illinois.edu>
G= iulia Fanti <= gfanti@andrew.cmu.edu>
Surya Ba= kshi <sbakshi= 3@illinois.edu>
Shaileshh Bojja= Venkatakrishnan <shaileshh.bv@gmail.com>
P= ramod Viswanath <pramodv@illinois.edu>
--00000000000006c8e7056bd99630--