What is the tradeoff between privacy and implementation complexity of Dandelion (BIP156) Dandelion is a new relay protocol for transactions on cryptocurrency peer-to-peer networks. It has been heralded as a huge privacy improvement for cryptocurrencies at the networking level– I'm wondering what costs this comes at. 


Does Dandelion introduce more complexity into the code base? 
Are there possible attack vectors introduced with Dandelion?
What is the hold-up with implementing Dandelion in Bitcoin Core?
In my view, the main implementation detail to be worked out with Dandelion
is ensuring that there are no new DoS vectors introduced.

In the existing transaction relay model of Bitcoin Core, transactions that
do not make it into a node's mempool -- a proxy for what we expect to be
(eventually) mined -- do not get relayed to other nodes.

In the Dandelion protocol, transactions are relayed (in the stem phase) prior
to acceptance into a node's mempool.  As a result, there are potential DoS
vectors if transactions can be systematically relayed via Dandelion but
ultimately not be accepted to any node's mempool -- this could either introduce
a bandwidth DoS, where the Bitcoin network's bandwidth is used up or wasted
relaying ultimately useless data; or a CPU-exhaustion DoS, if
expensive-to-validate transactions can be relayed without ultimately being
mined.  [In general, the only way attackers "pay" for the network's resources
they consume when relaying is via the transaction fee in their transactions; if
attackers can generate transactions that do not ultimately get mined, then any
side effects of the relay -- such as validation cost and bandwidth used -- can
be achieved for free since those transaction fees are never actually paid,
which typically implies that the network's resources could be utilized entirely
(since it would be costless for an attacker to ramp up usage).]

It turns out that -- in a naive Dandelion implementation -- it would not be
very difficult to generate transactions that would propagate in the stem-phase
but never be accepted to the mempool (at very low cost).  This is largely a
consequence of the complexity around mempool acceptance logic, and seems
particularly unavoidable given the mempool's own anti-DoS limits.

The existing mempool acceptance logic attempts to prevent or limit the effect
of these kinds of DoS attacks.  Transactions don't have their signatures
checked until just before mempool acceptance, after all other transaction
policy rules have been met, to avoid CPU exhaustion attacks.  Preventing
bandwidth attacks is more involved:


transactions are only relayed after being accepted to our own mempool
if our mempool fills up (it is a memory-limited data structure), then we can
evict low feerate transactions to make room for new transactions, but new
transactions are subject to a higher minimum relay fee, designed to offset/pay 
the relay fee for transactions which were evicted from the
mempool (and will thus no longer be mined until they relay again).


In short, there's quite a bit of complexity in the mempool acceptance logic to
prevent DoS.  So in my view, the questions around a Dandelion implementation are:

(a) Do we need something as complex as the current mempool logic in order to
avoid DoS vectors with Dandelion, or can we do something simpler?

(b) Are there acceptable modifications to the Dandelion protocol that would
simplify the DoS analysis and allow for a simpler implementation while still
providing a significant privacy boost to the network?  As an example: would it
be acceptable to implement Dandelion in such a way that under DoS scenarios, we
just fall back to the current relay model?

(c) If we don't have simpler solutions that work, is it worth implementing
something akin to the current mempool logic (called a "stempool" in some of the
discussions) in order to introduce Dandelion into Bitcoin Core?  Is the code
complexity worth the privacy benefit that Dandelion would confer?  While
improving privacy on the network is obviously a good thing, the privacy
benefits of Dandelion are limited, so is this the kind of thing that's worth
spending a lot of energy to implement and maintain, or should we focus our
mental energy elsewhere?