From: Bradley Denby <bdenby@cmu•edu>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Transaction Propagation
Date: Mon, 4 Jun 2018 16:29:50 -0400 [thread overview]
Message-ID: <CAGq_bNJmnKjvK_zL6_drVRmYqqBJOb0tULDHWSf58VSJs-DbAA@mail.gmail.com> (raw)
In-Reply-To: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 5139 bytes --]
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>
>
[-- Attachment #2: Type: text/html, Size: 8799 bytes --]
next prev parent reply other threads:[~2018-06-04 20:29 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-05-10 12:59 Bradley Denby
2018-06-04 20:29 ` Bradley Denby [this message]
2018-07-05 14:50 ` Neudecker, Till (TM)
2018-06-06 4:01 ` Pieter Wuille
2018-06-11 14:31 ` Bradley Denby
2018-06-12 1:05 ` Pieter Wuille
2018-06-26 0:12 ` Bradley Denby
2018-06-26 5:20 ` Gregory Maxwell
[not found] <mailman.3774.1530901879.19027.bitcoin-dev@lists.linuxfoundation.org>
2018-07-08 12:50 ` Giulia Fanti
-- strict thread matches above, loose matches on Subject: below --
2017-09-21 2:10 Giulia Fanti
2017-06-12 14:46 Andrew Miller
2017-06-13 1:00 ` Gregory Maxwell
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAGq_bNJmnKjvK_zL6_drVRmYqqBJOb0tULDHWSf58VSJs-DbAA@mail.gmail.com \
--to=bdenby@cmu$(echo .)edu \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox