[bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Transaction Propagation

[Andrew Miller <soc1024@illinois.edu>]

Dear bitcoin-dev,
   We've put together a preliminary implementation and BIP for
Dandelion, and would love to get your feedback on it. Dandelion is a
privacy-enhancing modification to Bitcoin's transaction propagation
mechanism. Its goal is to obscure the original source IP of each
transaction.

  https://github.com/gfanti/bips/blob/master/bip-dandelion.mediawiki
  https://github.com/gfanti/bitcoin/tree/dandelion

   The main idea is that transaction propagation proceeds in two
phases: first the “stem” phase, and then “fluff” phase. During the
stem phase, each node relays the transaction to a *single* peer. After
a random number of hops along the stem, the transaction enters the
fluff phase, which behaves just like ordinary transaction
flooding/diffusion. Even when an attacker can identify the location of
the fluff phase, it is much more difficult to identify the source of
the stem. Our approach and some preliminary evaluation are explained
in more detail in the BIP. The research paper originally introducing
this idea was recently presented at SIGMETRICS'17.
https://arxiv.org/pdf/1701.04439.pdf

  Compared to the original paper, our current proposal includes
several new design ideas, especially:
 - Stronger attacker model: we defend against an attacker that
actively tries to learn which nodes were involved in the stem phase.
Our approach is called "Mempool Embargo", meaning a node that receives
a "stem phase" transaction behaves as though it never heard of it,
until it receives it again from someone else (or until a random timer
elapses).
 - Robustness. We think the privacy benefit shouldn't come at the
expense of propagation quality. Our implementation is designed so that
if some node drops the transaction (or when Dandelion is adopted only
partially), then the fallback behavior is ordinary Bitcoin
propagation.

  We'd especially like feedback on the implementation details related
to the two points above. The mempool embargo mechanism is tricky,
since it hard to rule out indirect behavior that reveals if a
transaction is in mempool. In the BIP we explain one counterexample,
but at least it requires the attacker to get its connections banned.
Are there other ways we haven't thought of? We think the alternative
approach (bypassing mempool entirely) seems even harder to get right,
and foregoes existing DoS protection.

  We're currently running in-situ benchmark experiments with this code
on testnet and will report on those in this thread if there's
interest.

  Some prior discussion can be found here:
  - https://botbot.me/freenode/bitcoin-wizards/2017-03-29/?msg=83181866&page=2
  - https://botbot.me/freenode/bitcoin-wizards/2017-01-18/?msg=79578754&page=2
  - https://github.com/sbaks0820/bitcoin-dandelion/issues/1 (notes
from gmaxwell that we've mostly incorporated in the current proposal)

Thanks!
-----
Giulia Fanti <gfanti@andrew.cmu.edu>
Andrew Miller <soc1024@illinois.edu>
Surya Bakshi <sbakshi3@illinois.edu>
Shaileshh Bojja Venkatakrishnan <bjjvnkt2@illinois.edu>
Pramod Viswanath <pramodv@illinois.edu>