BIP proposal - Dandelion: Privacy Preserving Transaction Propagation

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 <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>

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>
>

On Thu, May 10, 2018 at 5:59 AM, Bradley Denby via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:

> Hi all,
>
> ...
>
> 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

Hi Bradley,

thank you for working on this and going as far as implementing the entire protocol. It looks like a very well-worked out idea already, and its semantics can probably be adopted pretty much as-is. It would be very exciting to bring these kinds of privacy improvements to Bitcoin's P2P protocol.

I do have a number of comments on the specification and suggested implementation in Bitcoin Core. I'm dumping my thoughts here, though at this stage the specification is probably more important. The implementation can be discussed more thoroughly when there is a PR open.

Specification

* Overall, I think it would be worthwhile to describe the intended node behavior in the BIP, at a higher level than Bitcoin Core patchsets, but more detailed than what is in the BIP now. The patch-based descriptions are both hard to read for developers working on different systems who are unfamiliar with the Core codebase, and don't make it clear to what extent implementation decisions are local policy (which can be changed without network coordination), and which follow from security or privacy arguments for the protocol.

* Interaction with feefilter (BIP 133) and Bloom filter (BIP 37). When peers have given us filters on what transactions they will accept, should Dandelion transactions be subject to the same? Should it influence the choice of route? One simple possibility is perhaps to avoid choosing BIP37 peers as Dandelion routes, and treat transactions that do not pass the feefilter for its would-be-outgoing-Dandelion-route as an automatic fluff - justified by noting that relaying a transaction close to what fee is acceptable to the network's mempools is already less likely to get good privacy due to reduced chances of propagation.

* Mempool dependant transactions. It looks like the current implementation accepts Dandelion transactions which are dependant on other Dandelion (stempool) transactions and on confirmed blockchain transactions, but not ones that are dependant on other unconfirmed normal mempool transactions. Is this intentional, or resulting from a difficulty in implementing this? Should the correct behaviour be specified, or left free for nodes to decide?

* Orphan transactions. It looks like the current implementation assumes no orphan transactions, but in a dynamic network (especially with occasionally shuffling of Dandelion routes), I expect that sometimes a dependent transaction will go on a different route than its parent. Do you have any thoughts about that (even if not addressed in a very implementation). Could we have a Dandelion-orphan-pool of transactions, similar to the normal mempool has a set of orphan transactions?

* Preferred connections. Should we bias the outgoing connection peer selection code to prefer Dandelion-capable peers when the number is too low?

Implementation

* How do we control the size of the stempool? Should acceptance of a transaction to the normal mempool and/or blockchain result in eviction of it (and conflicts) from the stempool? The existing code intentionally has an upper bound on the size of the mempool to assure predictable resource usage - the introduction of the stempool shouldn't change that.

* I don't think you need to fully materialize all the routes. Instead, you can just maintain a vector of 2 selected Dandelion-supporting peers (and if one disconnects, replace just that one with another one). To map incoming peers to an index in that list of peers, you can use deterministic randomness (see SipHasher in the source code) with the incoming node_id as data and a single global secret nonce (chosen at startup, and reset on reshuffle).

* setDandelionInventoryKnown looks like it can grow unboundedly. A rolling Bloom filter (like used for filterInventoryKnown) is perhaps easier to guarantee predictable memory usage for.

* Use a scheduler job instead of a separate thread for shuffling the routes (extra threads use unnecessarily large amounts of memory).

* (nit) coding style: doc/developer-notes.md has a number of guidelines on coding style you may want to check out.

Cheers,

Thanks for the comments Pieter!

We can make descriptions for the intended node behaviors more clear in the BIP.

Regarding interaction with BIPs 37 and 133, we have found that if Dandelion routing decisions are based on self-reported features, malicious nodes can often exploit that to launch serious deanonymization attacks. As a result, we recommend not allowing fee filters from peers to influence the choice of route. Your suggestion of automatically fluffing is a good solution. Another (similar) option would be to apply fee filters in the stempool. This would prevent the tx from propagating in stem phase, so eventually an embargo timer on the stem will expire and the transaction will fluff. This is slower than auto-fluffing, but requires (slightly) less code.

Regarding mempool-dependent transactions, the reference implementation adds any mempool transactions to the stempool but not vice-versa so that the stempool becomes a superset of the mempool. In other words, information is free to flow from the mempool to the stempool. Information does not flow from the stempool to the mempool except when a transaction fluffs. As a result, a node's stempool should accept and propagate Dandelion transactions that depend on other unconfirmed normal mempool transactions. The behavior you described is not intended; if you have any tests demonstrating this behavior, would you mind sharing them?

Orphans: stem orphans can occur when a node on the stem shuffles its route between sending dependent transactions. One way to deal with this issue would be to re-broadcast all previous Dandelion transactions that have not been fluffed after Dandelion route shuffling. This could add a fair amount of data and logic. This re-broadcast method also telegraphs the fact that a Dandelion shuffle has taken place and can result in bursts of transactions depending on traffic patterns. A second option (which we used in the reference implementation) is to wait for the fluff phase to begin, at which point the orphans will be resolved. This should happen within 15 seconds for most transactions. Do you have any thoughts on which option would be more palatable? Or if there are other options we have missed?

Regarding preferred connections, we have found that making Dandelion routing decisions based on claims made by peer nodes can cause problems and therefore would recommend against biasing the peer selection code.

On the implementation side:

* We apply the same logic to the stempool as the mempool in the reference implementation. The stempool should remain a superset of the mempool to allow for proper handling of mempool-dependent transactions.

* We'll take a look at setDandelionInventoryKnown.

* We will look into using scheduler jobs instead of a separate thread--could you point us towards somewhere else in the code that uses a scheduler job?

Based on the feedback we have received so far, we are planning to prioritize writing up a clearer spec for node behavior in the BIP. Does that seem reasonable, or are there other issues that are more pressing at this point?

Cheers

On Wed, Jun 6, 2018 at 12:01 AM, Pieter Wuille <pieter.wuille@gmail•com> wrote:

> On Thu, May 10, 2018 at 5:59 AM, Bradley Denby via bitcoin-dev
> <bitcoin-dev@lists•linuxfoundation•org> wrote:
> > Hi all,
> >
> > ...
> >
> > 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
>
> Hi Bradley,
>
> thank you for working on this and going as far as implementing the
> entire protocol. It looks like a very well-worked out idea already,
> and its semantics can probably be adopted pretty much as-is. It would
> be very exciting to bring these kinds of privacy improvements to
> Bitcoin's P2P protocol.
>
> I do have a number of comments on the specification and suggested
> implementation in Bitcoin Core. I'm dumping my thoughts here, though
> at this stage the specification is probably more important. The
> implementation can be discussed more thoroughly when there is a PR
> open.
>
> Specification
>
> * Overall, I think it would be worthwhile to describe the intended
> node behavior in the BIP, at a higher level than Bitcoin Core
> patchsets, but more detailed than what is in the BIP now. The
> patch-based descriptions are both hard to read for developers working
> on different systems who are unfamiliar with the Core codebase, and
> don't make it clear to what extent implementation decisions are local
> policy (which can be changed without network coordination), and which
> follow from security or privacy arguments for the protocol.
>
> * Interaction with feefilter (BIP 133) and Bloom filter (BIP 37). When
> peers have given us filters on what transactions they will accept,
> should Dandelion transactions be subject to the same? Should it
> influence the choice of route? One simple possibility is perhaps to
> avoid choosing BIP37 peers as Dandelion routes, and treat transactions
> that do not pass the feefilter for its
> would-be-outgoing-Dandelion-route as an automatic fluff - justified by
> noting that relaying a transaction close to what fee is acceptable to
> the network's mempools is already less likely to get good privacy due
> to reduced chances of propagation.
>
> * Mempool dependant transactions. It looks like the current
> implementation accepts Dandelion transactions which are dependant on
> other Dandelion (stempool) transactions and on confirmed blockchain
> transactions, but not ones that are dependant on other unconfirmed
> normal mempool transactions. Is this intentional, or resulting from a
> difficulty in implementing this? Should the correct behaviour be
> specified, or left free for nodes to decide?
>
> * Orphan transactions. It looks like the current implementation
> assumes no orphan transactions, but in a dynamic network (especially
> with occasionally shuffling of Dandelion routes), I expect that
> sometimes a dependent transaction will go on a different route than
> its parent. Do you have any thoughts about that (even if not addressed
> in a very implementation). Could we have a Dandelion-orphan-pool of
> transactions, similar to the normal mempool has a set of orphan
> transactions?
>
> * Preferred connections. Should we bias the outgoing connection peer
> selection code to prefer Dandelion-capable peers when the number is
> too low?
>
> Implementation
>
> * How do we control the size of the stempool? Should acceptance of a
> transaction to the normal mempool and/or blockchain result in eviction
> of it (and conflicts) from the stempool? The existing code
> intentionally has an upper bound on the size of the mempool to assure
> predictable resource usage - the introduction of the stempool
> shouldn't change that.
>
> * I don't think you need to fully materialize all the routes. Instead,
> you can just maintain a vector of 2 selected Dandelion-supporting
> peers (and if one disconnects, replace just that one with another
> one). To map incoming peers to an index in that list of peers, you can
> use deterministic randomness (see SipHasher in the source code) with
> the incoming node_id as data and a single global secret nonce (chosen
> at startup, and reset on reshuffle).
>
> * setDandelionInventoryKnown looks like it can grow unboundedly. A
> rolling Bloom filter (like used for filterInventoryKnown) is perhaps
> easier to guarantee predictable memory usage for.
>
> * Use a scheduler job instead of a separate thread for shuffling the
> routes (extra threads use unnecessarily large amounts of memory).
>
> * (nit) coding style: doc/developer-notes.md has a number of
> guidelines on coding style you may want to check out.
>
> Cheers,
>
> --
> Pieter
>

On Mon, Jun 11, 2018, 07:37 Bradley Denby via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:

> Thanks for the comments Pieter!
>
> We can make descriptions for the intended node behaviors more clear in the
> BIP.
>
> Regarding interaction with BIPs 37 and 133, we have found that if
> Dandelion routing decisions are based on self-reported features, malicious
> nodes can often exploit that to launch serious deanonymization attacks. As
> a result, we recommend not allowing fee filters from peers to influence the
> choice of route. Your suggestion of automatically fluffing is a good
> solution. Another (similar) option would be to apply fee filters in the
> stempool. This would prevent the tx from propagating in stem phase, so
> eventually an embargo timer on the stem will expire and the transaction
> will fluff. This is slower than auto-fluffing, but requires (slightly) less
> code.
>

I understand the argument about not making routing decisions based on self-reported features, but I would expect it to only matter if done selectively? Allowing a node to opt out of Dandelion entirely should always be possible regardless - as they can always indicate not supporting it.

The reason for my suggestion was that most full nodes on the network use feefilter, while only (from the perspective of Dandelion uninteresting) light nodes and blocksonly nodes generally use Bloom filters.

Just dropping stem transactions that would otherwise be sent to a Dandelion peer which fails its filter, and relying on embargo seems fine. But perhaps this option is something to describe in the BIP ("Nodes MAY choose to either drop stem transactions or immediately start diffusion when a transaction would otherwise be sent to a Dandelion node whose filter is not satisfied for that transaction. A node SHOULD NOT make any routing decisions based on the transaction itself, and thus SHOULD NOT try to find an alternative Dandelion node to forward to" for example).

Regarding mempool-dependent transactions, the reference implementation adds

> any mempool transactions to the stempool but not vice-versa so that the
> stempool becomes a superset of the mempool. In other words, information is
> free to flow from the mempool to the stempool. Information does not flow
> from the stempool to the mempool except when a transaction fluffs. As a
> result, a node's stempool should accept and propagate Dandelion
> transactions that depend on other unconfirmed normal mempool transactions.
> The behavior you described is not intended; if you have any tests
> demonstrating this behavior, would you mind sharing them?
>

Oh, I see! I was just judging based on the spec code you published, but I must have missed this. Yes, that makes perfect sense. There may be some issues with this having a significant impact on stempool memory usage, but let's discuss this later on implementation.

Orphans: stem orphans can occur when a node on the stem shuffles its route

> between sending dependent transactions. One way to deal with this issue
> would be to re-broadcast all previous Dandelion transactions that have not
> been fluffed after Dandelion route shuffling. This could add a fair amount
> of data and logic. This re-broadcast method also telegraphs the fact that a
> Dandelion shuffle has taken place and can result in bursts of transactions
> depending on traffic patterns. A second option (which we used in the
> reference implementation) is to wait for the fluff phase to begin, at which
> point the orphans will be resolved. This should happen within 15 seconds
> for most transactions. Do you have any thoughts on which option would be
> more palatable? Or if there are other options we have missed?
>

Another option (just brainstorming, I may be missing something here), is to remember which peer each stempool transaction was forwarded to. When a dependent stem transaction arrives, it is always sent to (one of?) the peers its dependencies were sent to, even if a reshuffle happened in between.

Thinking more about it, relying on embargo is probably fine - it'll just result in slightly lowered average stem length, and perhaps multiple simultaneous fluffs starting?

Regarding preferred connections, we have found that making Dandelion

> routing decisions based on claims made by peer nodes can cause problems and
> therefore would recommend against biasing the peer selection code.
>

Oh, I don't mean routing decisions, but connections in general.

On the implementation side:

>

Let's discuss these later.

> Based on the feedback we have received so far, we are planning to
> prioritize writing up a clearer spec for node behavior in the BIP. Does
> that seem reasonable, or are there other issues that are more pressing at
> this point?
>

I think that's the primary thing to focus on at this point, but perhaps others on this list feel different.

Cheers,

On Mon, Jun 11, 2018 at 9:05 PM, Pieter Wuille <pieter.wuille@gmail•com> wrote:

> On Mon, Jun 11, 2018, 07:37 Bradley Denby via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation•org> wrote:
>
>> Thanks for the comments Pieter!
>>
>> We can make descriptions for the intended node behaviors more clear in
>> the BIP.
>>
>> Regarding interaction with BIPs 37 and 133, we have found that if
>> Dandelion routing decisions are based on self-reported features, malicious
>> nodes can often exploit that to launch serious deanonymization attacks. As
>> a result, we recommend not allowing fee filters from peers to influence the
>> choice of route. Your suggestion of automatically fluffing is a good
>> solution. Another (similar) option would be to apply fee filters in the
>> stempool. This would prevent the tx from propagating in stem phase, so
>> eventually an embargo timer on the stem will expire and the transaction
>> will fluff. This is slower than auto-fluffing, but requires (slightly) less
>> code.
>>
>
> I understand the argument about not making routing decisions based on
> self-reported features, but I would expect it to only matter if done
> selectively? Allowing a node to opt out of Dandelion entirely should always
> be possible regardless - as they can always indicate not supporting it.
>

That's right, the idea is to choose Dandelion relays independently from whether they support Dandelion. If the chosen nodes do not support Dandelion, then the transactions are fluffed. Otherwise, the transactions are relayed along a stem.

>
> The reason for my suggestion was that most full nodes on the network use
> feefilter, while only (from the perspective of Dandelion uninteresting)
> light nodes and blocksonly nodes generally use Bloom filters.
>
> Just dropping stem transactions that would otherwise be sent to a
> Dandelion peer which fails its filter, and relying on embargo seems fine.
> But perhaps this option is something to describe in the BIP ("Nodes MAY
> choose to either drop stem transactions or immediately start diffusion when
> a transaction would otherwise be sent to a Dandelion node whose filter is
> not satisfied for that transaction. A node SHOULD NOT make any routing
> decisions based on the transaction itself, and thus SHOULD NOT try to find
> an alternative Dandelion node to forward to" for example).
>

Thanks for the suggestion, we've updated the BIP with RFC 2119 language.

>
> Regarding mempool-dependent transactions, the reference implementation
>> adds any mempool transactions to the stempool but not vice-versa so that
>> the stempool becomes a superset of the mempool. In other words, information
>> is free to flow from the mempool to the stempool. Information does not flow
>> from the stempool to the mempool except when a transaction fluffs. As a
>> result, a node's stempool should accept and propagate Dandelion
>> transactions that depend on other unconfirmed normal mempool transactions.
>> The behavior you described is not intended; if you have any tests
>> demonstrating this behavior, would you mind sharing them?
>>
>
> Oh, I see! I was just judging based on the spec code you published, but I
> must have missed this. Yes, that makes perfect sense. There may be some
> issues with this having a significant impact on stempool memory usage, but
> let's discuss this later on implementation.
>
> Orphans: stem orphans can occur when a node on the stem shuffles its route
>> between sending dependent transactions. One way to deal with this issue
>> would be to re-broadcast all previous Dandelion transactions that have not
>> been fluffed after Dandelion route shuffling. This could add a fair amount
>> of data and logic. This re-broadcast method also telegraphs the fact that a
>> Dandelion shuffle has taken place and can result in bursts of transactions
>> depending on traffic patterns. A second option (which we used in the
>> reference implementation) is to wait for the fluff phase to begin, at which
>> point the orphans will be resolved. This should happen within 15 seconds
>> for most transactions. Do you have any thoughts on which option would be
>> more palatable? Or if there are other options we have missed?
>>
>
> Another option (just brainstorming, I may be missing something here), is
> to remember which peer each stempool transaction was forwarded to. When a
> dependent stem transaction arrives, it is always sent to (one of?) the
> peers its dependencies were sent to, even if a reshuffle happened in
> between.
>
> Thinking more about it, relying on embargo is probably fine - it'll just
> result in slightly lowered average stem length, and perhaps multiple
> simultaneous fluffs starting?
>

That's right, the stem length would be slightly shorter because of the time spent waiting for the parent transaction, and you could get multiple simultaneous fluffs. If this is acceptable, it is probably the simplest solution.

>
> Regarding preferred connections, we have found that making Dandelion
>> routing decisions based on claims made by peer nodes can cause problems and
>> therefore would recommend against biasing the peer selection code.
>>
>
> Oh, I don't mean routing decisions, but connections in general.
>

Ah ok. Even biasing a node's connections to prefer Dandelion nodes could be problematic, especially in the early-deployment stage. For instance, a set of malicious nodes could run Dandelion at the beginning; since there are few honest nodes running Dandelion, the malicious nodes would draw a disproportionate fraction of peer connections. This could have implications for anonymity as well as eclipsing attacks. So we would suggest not changing the peer connection strategy. In fact, we found that even when there are very few nodes running Dandelion, this Dandelion-agnostic connection strategy still provides some benefit over the current mechanism.

>
> On the implementation side:
>>
>
> Let's discuss these later.
>
>
>> Based on the feedback we have received so far, we are planning to
>> prioritize writing up a clearer spec for node behavior in the BIP. Does
>> that seem reasonable, or are there other issues that are more pressing at
>> this point?
>>
>
> I think that's the primary thing to focus on at this point, but perhaps
> others on this list feel different.
>

We've updated the BIP with RFC 2119 statements. Thanks for the feedback!

>
> Cheers,
>
> --
> Pieter
>
>

On Tue, Jun 26, 2018 at 12:12 AM, Bradley Denby via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:

> That's right, the idea is to choose Dandelion relays independently from
> whether they support Dandelion. If the chosen nodes do not support
> Dandelion, then the transactions are fluffed. Otherwise, the transactions
> are relayed along a stem.

I don't see any problem with doing that... Although an additional countermeasure we're likely to take against attacks on partial deployment is that we'd likely make the wallet's use of stem forwarding be a configuration option which is initially hidden and set to off. In a subsistent release after dandelion propagation is widely deployed we'd unhide the option and default it to on. This way users don't begin using it until the deployment is relatively dense.

I believe this approach is a is sufficient such that it could always select out-peers that were dandelion capable without harm, but at the same time I also don't see a reason that we can't do both.

(in fact, for privacy reasons we might want to three-stage the deployment, with the use of dandelion by wallets having a setting of off, sometimes, or always so that attackers can't so easily correlate the use of dandelion with upgrades.)

Dear Bradley,

maybe I’m a little bit late to the discussion, but I’d also like to share some thoughts:

* Could you elaborate on the reasoning behind choosing the periodic route shuffling interval to be around 10 minutes? I guess that there is some tradeoff between making intersection attacks possible by choosing a too small interval, and making graph-learning attacks possible by choosing a too large interval. Intuitively, this interval should depend on the number of forwarded Dandelion transactions, because these are the events that leak information, and not the absolute elapsed time. On the other hand, making the interval dependent on the number of processed transactions would allow an active adversary to trigger route shuffling by sending Dandelion transaction to specific peers, which could enable intersection attacks...

* Speaking of active adversaries: Adversaries could send a large number of transactions to selected peers - either by creating the transactions on their own, or by relaying (Dandelion) transactions observed by the adversary’s peers to the selected peer. Could this allow the adversary to launch fingerprinting attacks on the selected peer by comparing the observed propagation of the transactions relayed through the peer to other transactions observed?

* If an adversary performs a black-hole attack (i.e., drops Dandelion transactions), and if the adversary is able to identify the diffusion source, reconstruction of parts of the anonymity graph (i.e., the part between the diffusion source and the last peer before the black-hole) might be possible. I understand that the adversary does not gain much from the knowledge of the anonymity graph, but it nonetheless helps the adversary.

* Out of personal interest: Inferring Bitcoin’s network topology is hard. I think it’s wise to assume a strong adversary that has perfect knowledge of the topology, but can you make any statements on the sensitivity of the adversary’s precision and recall regarding imperfect topology knowledge?

--Till

From: bitcoin-dev-bounces@lists•linuxfoundation•org [mailto:bitcoin-dev-bounces@lists.linuxfoundation.org] On Behalf Of Bradley Denby via bitcoin-dev Sent: Monday, June 4, 2018 10:30 PM To: bitcoin-dev@lists•linuxfoundation•org Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Transaction Propagation

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/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 <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>

Hi Till,

Thank you for the comments! Responses are inline:

* Could you elaborate on the reasoning behind choosing the periodic route

> shuffling interval to be around 10 minutes? I guess that there is some
> tradeoff between making intersection attacks possible by choosing a too
> small interval, and making graph-learning attacks possible by choosing a
> too large interval. Intuitively, this interval should depend on the number
> of forwarded Dandelion transactions, because these are the events that leak
> information, and not the absolute elapsed time. On the other hand, making
> the interval dependent on the number of processed transactions would allow
> an active adversary to trigger route shuffling by sending Dandelion
> transaction to specific peers, which could enable intersection attacks...
>

Your intuition is spot-on in the sense that shorter intervals help with intersection attacks, whereas longer ones help with graph learning. On that tradeoff curve, we would recommend favoring graph learning attacks; intersection attacks can be really devastating (with recall tending to 1), whereas graph learning attacks still have limited recall and precision. If we decide to allow graph learning in order to prevent intersection attacks, the natural conclusion would be to use as long a time interval as possible. We are open to changing this time interval; 10 minutes was just a heuristic we proposed at the time of writing.

> * Speaking of active adversaries: Adversaries could send a large number of
> transactions to selected peers - either by creating the transactions on
> their own, or by relaying (Dandelion) transactions observed by the
> adversary?s peers to the selected peer. Could this allow the adversary to
> launch fingerprinting attacks on the selected peer by comparing the
> observed propagation of the transactions relayed through the peer to other
> transactions observed?
>

Yes, this is one of the main ways we envision adversaries potentially learning the graph in practice.

> * If an adversary performs a black-hole attack (i.e., drops Dandelion
> transactions), and if the adversary is able to identify the diffusion
> source, reconstruction of parts of the anonymity graph (i.e., the part
> between the diffusion source and the last peer before the black-hole) might
> be possible. I understand that the adversary does not gain much from the
> knowledge of the anonymity graph, but it nonetheless helps the adversary.
>

This is also true. Using a small shuffle time interval would help prevent this, but if we go with a longer interval, this approach could certainly help with graph learning.

> * Out of personal interest: Inferring Bitcoin?s network topology is hard.
> I think it?s wise to assume a strong adversary that has perfect knowledge
> of the topology, but can you make any statements on the sensitivity of the
> adversary?s precision and recall regarding imperfect topology knowledge?
>

We only studied what happens when the adversary has full knowledge of the graph and local knowledge (i.e. the spy nodes know their own neighbors, but nothing else). We did not study what happens when the adversary has partial graph knowledge, but that would be an interesting and useful question to look at.

>
> --Till
>
>
> From: bitcoin-dev-bounces@lists•linuxfoundation•org [mailto:
> bitcoin-dev-bounces@lists•linuxfoundation•org] On Behalf Of Bradley Denby
> via bitcoin-dev
> Sent: Monday, June 4, 2018 10:30 PM
> To: bitcoin-dev@lists•linuxfoundation•org
> Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving
> Transaction Propagation
>
> 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/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 <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>
>
>
> ------------------------------
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> End of bitcoin-dev Digest, Vol 38, Issue 8
> ******************************************
>