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

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

[Bradley Denby]

[-- Attachment #1: Type: text/plain, Size: 3561 bytes --]

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>

[-- Attachment #2: Type: text/html, Size: 6872 bytes --]

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

[Bradley Denby]

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

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

[Pieter Wuille]

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

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

[Bradley Denby]

[-- Attachment #1: Type: text/plain, Size: 7958 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 9205 bytes --]

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

[Pieter Wuille]

[-- Attachment #1: Type: text/plain, Size: 4892 bytes --]

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,

-- 
Pieter

[-- Attachment #2: Type: text/html, Size: 6886 bytes --]

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

[Bradley Denby]

[-- Attachment #1: Type: text/plain, Size: 6409 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 10398 bytes --]

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

[Gregory Maxwell]

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

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

[Neudecker, Till (TM)]

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>

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

[Giulia Fanti]

[-- Attachment #1: Type: text/plain, Size: 9128 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 11630 bytes --]

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

[Giulia Fanti]

[-- Attachment #1: Type: text/plain, Size: 22144 bytes --]

Greetings bitcoin-dev,

  We’re returning to this thread to give an update on the Dandelion project
after several months of additional work. (Dandelion is a new
privacy-preserving transaction propagation method, which we are proposing
as a BIP. See the original post in this thread
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-June/014571.html
for more background) The feedback on our initial BIP from Greg Maxwell in
this thread touched on several important issues affecting the protocol
design, which it has taken us until now to adequately address.

The focus of this update is a new variant of the Dandelion++ mechanism
presented earlier. The new variant is called “Per-Incoming-Edge” routing.
In a nutshell, while the earlier Dandelion++ variant calls for routing
*each* stem transaction through a randomly chosen path, Per-Incoming Edge
routing causes each transaction from the same source to traverse the same
pseudorandom path. The most important benefit of Per-Incoming-Edge is that
it prevents “intersection attacks” that result if a client broadcasts
multiple transactions over a short period of time. We validate this new
variant with new analysis and simulation as explained below.

Today’s update also includes an outline of our next development plans. We
have not yet completed a reference implementation, so this update does not
include a new BIP. Instead we’re just outlining the steps we plan to take
before an updated BIP. The new approach also  impacts our implementation
approach. Since Per-Incoming Edge routing simplifies the handling of orphan
transactions, we’re now planning on adopting Greg Maxwell’s suggestion to
bypass the txMempool for dandelion stem transactions.

======

The feedback on Dandelion from Greg Maxwell touched on a few important
issues: (1) robustness to observations over time, aka “intersection
attacks”, (2) protocol- or implementation-level data leaks, and (3) graph
learning.

(1) With time, the adversary may be able to observe many message
trajectories, thereby eventually learning the underlying graph structure
and/or improving its deanonymization estimate for a given estimate of the
graph structure. In our original Dandelion BIP, we addressed this by
changing the anonymity graph topology from a directed line to a directed
4-regular graph. (In short, instead of a single outgoing edge for Dandelion
transactions, each node selects from  *two* such edges). This topology
provides robustness to adversaries who are able to learn the graph, but
those results still assume that each node generates only one transaction in
each “epoch” (time between reshuffling the anonymity graph). Hence a big
remaining question is to understand the effect of intersection attacks--an
adversary observing multiple dependent transactions--on deanonymization
precision and recall.

(2) The second issue is protocol- or implementation-level behavior that
would allow an adversary to actively probe Dandelion to learn more
information than before. As you correctly note, we want to avoid the
adversary using conflicting transactions to infer which nodes are in the
stem. This issue is related to issue (1), in that our mechanism for
addressing intersection attacks will determine what data structures we need
in the implementation.

(3) The third issue is that an adversary may be able to infer the structure
of the graph by observing network traffic. We want to prevent this.

----------

Intersection Attacks

----------


An adversary’s ability to launch intersection attacks depends on the
internal Dandelion routing policy. Two natural ways to approach routing are
the following:

 1. Per-Hop: For each incoming stem transaction, make an independent random
decision of (a) whether to transition to “fluff” phase, and (b) if “stem”,
then which node should we relay to. This means that two transactions, even
starting from the same source, take independent random walks through the
anonymity graph. This is what our current implementation does.

 2. Per-Inbound-Edge: For each inbound edge e, randomly select one outbound
edge g, and relay all transactions arriving on edge e to edge g (assuming
the transaction remains in stem phase). Each node uses this relay mapping
for an entire epoch, which lasts about 10 min. Each source also randomly
chooses one outbound edge g’ for its own transactions; so if a node
generates 5 transactions, they will all get propagated over edge g’. This
approach has the property that during an epoch, all transactions from a
single source will take the same path through the stem graph.

We have simulated and analyzed these two routing protocols, and find that
per-inbound-edge routing seems to be more robust to intersection attacks.
For our simulations we consider the “first-spy” estimator --- this means
the rule where the attacker simply guesses that the first peer to relay a
transaction to a spy node is the real source. Figure 1 (link below)
illustrates the first-spy precision for per-incoming-edge routing and
per-transaction routing when each node has *one* transaction. Higher
precision means worse anonymity. For comparison, this figure includes
diffusion, which is the spreading mechanism currently used. Here ‘p’
denotes the fraction of nodes in the network that are spies. (Recall that
in our model, we treat the attacker has having control over some fraction
of random nodes). The turquoise curve (labelled ‘p’) is shown for
reference---it does not represent any routing protocol.

https://github.com/gfanti/bips/blob/master/per-edge-vs-per-tx.jpg

First, note that the first-spy estimator is thought to be significantly
suboptimal for diffusion (red line). Prior literature has shown that on
certain classes of graphs, there exist estimators that can detect diffusion
sources with much higher probability than the first-spy estimator. While
it’s unclear how to apply those algorithms to Bitcoin’s graph, it is likely
that strong algorithms exist. Hence the first-spy estimator serves as a
lower bound on precision for diffusion. On the other hand, we can show
theoretically that the first-spy precision for per-tx and per-incoming-edge
routing is within a small constant factor of the optimal precision for
per-incoming-edge routing. Thus, we expect that the green (per-edge) and
blue (per-tx) lines reflect the near-optimal attack, whereas the red line
(diffusion) could be much higher in practice.

The second issue to note is that the blue line (per-tx forwarding) has the
lowest precision of the three protocols for one tx per node. The green line
(per-edge forwarding) has higher precision than per-tx forwarding when
there are very few spies, but approaches per-tx forwarding as p increases.
Moreover, it has lower precision than diffusion for p>=0.05.

However, the real benefits of per-edge forwarding emerge as nodes start to
transmit multiple transactions. Under per-edge forwarding, even if nodes
transmit multiple transactions each, those transactions will traverse the
same path in the anonymity graph, thereby preventing the adversary from
learning any new information from later transactions. Meanwhile, under
per-tx routing, we find empirically that as nodes generate an increasing
number of transactions, each source generates a unique signature of
spy-node-observations (we are currently working on a more detailed
exploration of this question). We expect that such signatures can be used
to exactly deanonymize users in cases where the adversary learns the
graph. Hence
per-tx forwarding is actually quite fragile to adversaries learning the
graph, whereas per-incoming-edge is robust to intersection attacks. This is
one key reason for adopting per-incoming-edge forwarding.

Adopting per-incoming-edge forwarding has another important implication: it
becomes easy to enforce the condition that child transactions never enter
fluff mode before parent transactions. This significantly simplifies orphan
handling, and means that adversaries cannot infer that a preceding
transaction is still in stem mode just by passively listening to network
traffic. We revisit this issue in the next section.

----------

Implementation-Level Metadata Leaks

----------

tl;dr: concept ACK for gmaxwell’s suggestion on a new per-peer data
structure instead of mempool

Regardless of which routing policy we choose, it is important that
implementations do not leak more information about transactions than they
do in our model. It’s especially important that spies do not get an
“off-path” view of the nodes involved in the stem of a transaction. This
practically means that implementations must be careful not to expose
whether or not a stem transaction was received, to any node except the two
randomly chosen ones. (i.e., not to supernodes that may make inbound
connections to thousands of nodes).

We are currently developing a reference implementation for Dandelion++, as
a patch against Bitcoin Core. It requires thoughtful integration to make
this patch, and the choice of routing policy informs our approach. We have
so far considered two main integration approaches, whose main difference is
whether or not they reuse the existing *txMempool* data structure to store
stem mode transactions.

A. Mempool embargo:

This how is our current implementation works. Stem transactions are only
relayed if they are accepted to mempool. Stem transactions are “embargoed”
by suppressing them from MEMPOOL and INV messages sent from the node. This
was the easiest to implement while preserving all of Bitcoin’s existing DoS
prevention. In particular, it simplifies the handling of orphan
transactions, because the AcceptToMempool routine already handles orphan
transactions. However, this approach comes with a risk of indirect leakage,
especially if some edge case is missed in implementation.

B. Avoid modifying mempool (or any global structure) for stem transactions:

This is the approach preferred by Greg Maxwell. The main benefit is that it
is much more clear that there is no indirect leakage, although it makes it
harder to argue there is no additional DoS concern. We have already taken a
couple of steps towards implementing this here:
https://github.com/gfanti/bitcoin/commits/dandelion-nomempool The main idea
is to avoid duplicating the rules for whether a transaction would be
accepted into mempool or not, by adding a “dry run” option to the
AcceptToMempool function. Our implementation of this approach is not yet
finished; it still remains to develop the per-peer data structure.

Orphan transactions are important for per-tx routing, because with per-tx
routing, the child and the parent might travel along different stems. A
burst of transactions from a single sender would have to be queued so they
enter fluff mode sequentially. A lot of our testing (with the included test
framework) involved ensuring such transactions were handled effectively.
This was also the deciding factor for our choice of using Option B “Mempool
Embargo” above. With Per-incoming Edge routing, however, orphan transaction
handling can be simplified, since out-of-order transactions would not be
sent along stems.

We therefore plan to re-engineer a much of our reference implementation to:

1) use per-incoming edge routing,

2) simplify handling of orphan transactions,

3) adopt the proposed approach of avoiding the mempool data structure for
stem transactions.

We’ll give an update soon on our development progress before updating the
BIP.

----------

Graph Learning

----------


Greg Maxwell also asked:

```

Has any work been given to the fact that dandelion propagation
potentially making to measure properties of the inter-node connection
graph?  e.g.  Say I wish to partition node X by disconnecting all of
its outbound connections, to do that it would be useful to learn whom
is connected to X.  I forward a transaction to X, observe the first
node to fluff it,  then DOS attack that node to take it offline.  Will
I need to DOS attack fewer or more nodes  to get all of X's outbounds
if X supports rapid stem forwarding?

```

In terms of graph learning, there are two graphs to consider: the anonymity
graph (i.e., the stem set of each node), and the main P2P graph. Dandelion
has at least as good graph-hiding properties as diffusion for a natural
class of attacks (which include the attack described in the comment above).


Consider the task of learning the main P2P graph in today’s network (under
diffusion spreading). Suppose a supernode is connected to all nodes, and
wants to learn the 1-hop neighbors of a given target node. The eavesdropper
passes a transaction to the target, and waits to hear which nodes relay the
transaction first. If the target has 8 outbound neighbors, then in each
experiment, the supernode will receive 8 independent relay timestamps from
the target’s 1-hop neighbors. By repeating this many times, the adversary
can infer the 1-hop neighbors as the nodes who relay the transaction with
the appropriate mean delay (taking into account the appropriate exponential
parameters). Eventually, this set will be learned with high certainty.

Now consider the same task if the target is a Dandelion node. Note that the
supernode’s probe tx must be relayed as a Dandelion message to observe any
difference with the prior experiment. First of all, the target will only
pass the tx to one node in its stem set. Hence, in each experiment, the
supernode can learn at most one timestamp from a relevant node, whereas
previously it learned eight per experiment. This inherently reduces the
adversary’s learning rate. Second, if the target’s relay is a Dandelion
node and chooses to extend the stem, then the supernode will not receive any
relevant timestamp (i.e. a timestamp from a 1-hop neighbor) unless the
supernode lies in the relay’s stem set. This happens with a probability
that depends on the level of deployment and the number of (seemingly)
distinct nodes being run by the supernode, but is strictly smaller than 1.

   _ Hence, the rate at which an attacker can learn the main P2P graph is
strictly higher under diffusion (as in Bitcoin Core today) compared to
using Dandelion. _

A similar argument can be made for the anonymity graph, which we currently
implement as an overlay to the main P2P graph.

=====

Responses to Other Miscellaneous Comments

====

```

An alternative construction would be that when a stem transaction goes
out there is a random chance that the stem flag is not set (with
suitable adjustment to keep the same expected path length)

For some reason I believe this would be a superior construction, but I
am only able to articulate one clear benefit:  It allows non-dandelion
capable nodes to take on the role of the last stem hop, which I
believe would improve the anonymity set during the transition phase.

```

Agreed, this is actually what we have implemented.


---------

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>



Date: Tue, 13 Jun 2017 01:00:50 +0000
> From: Gregory Maxwell <greg@xiph.org>
> To: Andrew Miller <soc1024@illinois.edu>
> Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
> Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy
>         Preserving Transaction Propagation
> Message-ID:
>         <CAAS2fgRAnGMMxKPCaj1SL=z3O2wuGS8nyPrgtGhSpuGgAoVtKg@mail.
> gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> On Mon, Jun 12, 2017 at 2:46 PM, Andrew Miller via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > 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.
>
> I'm glad to see this out now, so I'm not longer invading the git repo
> uninvited. :)
>
> >  - 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
> > elapsess).
>
>
> The description in the BIP appears inadequate:
>
>
> > That is, Alice will not include the embargoed transaction when
> responding to MEMPOOL requests, and will not respond to GETDATA requests
> from another node (Bob) unless Alice previously sent an INV to Bob. The
> embargo period ends as soon as Alice receives an INV advertising the
> transaction as being in fluff mode.
>
> For example, it's not clear if I can query for the existence of a
> transaction by sending a conflict.  If this doesn't seem problematic,
> consider the case where I, communicating with you over some private
> channel, send you a payment inside a payment protocol message. You
> announce it to the network and I concurrently send a double spend.
> Only nodes that were part of the stem will reject my double spend, so
> I just learned a lot about your network location.
>
> It's also appears clear that I can query by sending an inv and
> noticing that no getdata arrives.  An example attack in the latter is
> that when I get a stem transaction I rapidly INV interrogate the
> entire network and by observing who does and doesn't getdata I will
> likely learn the entire stem path upto permutation.
>
> The extra network capacity used by getdata-ing a transaction you
> already saw via dandelion would be pretty insignificant.
>
> I believe the text should be simplified and clarified so just say:
>
> "With the exception of her behavior towards the peer sending in the
> stem transaction and the peer sending out the transaction Alice's
> behavior should be indistinguishable from a node which has not seen
> the transaction at all until she receives it via ordinary forwarding
> or until after the timeout." -- then its up to the implementation to
> achieve indistinguishably regardless of what other protocol features
> it uses.
>
> > 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.
>
> I think avoiding the is the most sensible way; and from a software
> maintenance perspective I expect that anything less will end up
> continually suffering from serious information leaks which are hard to
> avoid accidentally introducing via other changes.
>
> The primary functionality should be straightforward to implement,
> needing just a flag to determine if a transaction would be accepted to
> the mempool but for the flag, but which skips actually adding it.
>
> Handling chains of unconfirmed stem transactions is made more
> complicated by this and this deserves careful consideration. I'm not
> sure if its possible to forward stem children of stem transactions
> except via the same stem path as the parent without leaking
> information, it seems unlikely.
>
> This approach would mostly take additional complexity from the need to
> limit the amplification of double spends. I believe this can be
> resolved by maintaining a per-peer map of the not yet expired vin's
> consumed by stem fowards sent out via that peer. E.g. vin->{timeout,
> feerate}.  Then any new forward via that stem-peer is tested against
> that map and suppressed if it it spends a non-timed-out input and
> doesn't meet the feerate epsilon for replacement.
>
> Use of the orphan map is not indistinguishable as it is used for block
> propagation, and itself also a maintenance burden to make sure
> unrelated code is not inadvertently leaking the stem transactions.
>
> > After a random number of hops along the stem, the transaction enters the
> fluff phase,
>
> The BIP is a bit under-specified on this transition, I think-- but I
> know how it works from reading the prior implementation (I have not
> yet read the new implementation).
>
> The way it works (assuming I'm not confused and it hasn't changed) is
> that when a new stem transaction comes in there is a chance that it is
> treated as coming in as a normal transaction.
>
> An alternative construction would be that when a stem transaction goes
> out there is a random chance that the stem flag is not set (with
> suitable adjustment to keep the same expected path length)
>
> For some reason I believe this would be a superior construction, but I
> am only able to articulate one clear benefit:  It allows non-dandelion
> capable nodes to take on the role of the last stem hop, which I
> believe would improve the anonymity set during the transition phase.
>
> Unrelated:
>
> Has any work been given to the fact that dandelion propagation
> potentially making to measure properties of the inter-node connection
> graph?  e.g.  Say I wish to partition node X by disconnecting all of
> its outbound connections, to do that it would be useful to learn whom
> is connected to X.  I forward a transaction to X, observe the first
> node to fluff it,  then DOS attack that node to take it offline.  Will
> I need to DOS attack fewer or more nodes  to get all of X's outbounds
> if X supports rapid stem forwarding?
>
>
> ------------------------------
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 41168 bytes --]

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

[Gregory Maxwell]

On Mon, Jun 12, 2017 at 2:46 PM, Andrew Miller via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> 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.

I'm glad to see this out now, so I'm not longer invading the git repo
uninvited. :)

>  - 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
> elapsess).


The description in the BIP appears inadequate:


> That is, Alice will not include the embargoed transaction when responding to MEMPOOL requests, and will not respond to GETDATA requests from another node (Bob) unless Alice previously sent an INV to Bob. The embargo period ends as soon as Alice receives an INV advertising the transaction as being in fluff mode.

For example, it's not clear if I can query for the existence of a
transaction by sending a conflict.  If this doesn't seem problematic,
consider the case where I, communicating with you over some private
channel, send you a payment inside a payment protocol message. You
announce it to the network and I concurrently send a double spend.
Only nodes that were part of the stem will reject my double spend, so
I just learned a lot about your network location.

It's also appears clear that I can query by sending an inv and
noticing that no getdata arrives.  An example attack in the latter is
that when I get a stem transaction I rapidly INV interrogate the
entire network and by observing who does and doesn't getdata I will
likely learn the entire stem path upto permutation.

The extra network capacity used by getdata-ing a transaction you
already saw via dandelion would be pretty insignificant.

I believe the text should be simplified and clarified so just say:

"With the exception of her behavior towards the peer sending in the
stem transaction and the peer sending out the transaction Alice's
behavior should be indistinguishable from a node which has not seen
the transaction at all until she receives it via ordinary forwarding
or until after the timeout." -- then its up to the implementation to
achieve indistinguishably regardless of what other protocol features
it uses.

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

I think avoiding the is the most sensible way; and from a software
maintenance perspective I expect that anything less will end up
continually suffering from serious information leaks which are hard to
avoid accidentally introducing via other changes.

The primary functionality should be straightforward to implement,
needing just a flag to determine if a transaction would be accepted to
the mempool but for the flag, but which skips actually adding it.

Handling chains of unconfirmed stem transactions is made more
complicated by this and this deserves careful consideration. I'm not
sure if its possible to forward stem children of stem transactions
except via the same stem path as the parent without leaking
information, it seems unlikely.

This approach would mostly take additional complexity from the need to
limit the amplification of double spends. I believe this can be
resolved by maintaining a per-peer map of the not yet expired vin's
consumed by stem fowards sent out via that peer. E.g. vin->{timeout,
feerate}.  Then any new forward via that stem-peer is tested against
that map and suppressed if it it spends a non-timed-out input and
doesn't meet the feerate epsilon for replacement.

Use of the orphan map is not indistinguishable as it is used for block
propagation, and itself also a maintenance burden to make sure
unrelated code is not inadvertently leaking the stem transactions.

> After a random number of hops along the stem, the transaction enters the fluff phase,

The BIP is a bit under-specified on this transition, I think-- but I
know how it works from reading the prior implementation (I have not
yet read the new implementation).

The way it works (assuming I'm not confused and it hasn't changed) is
that when a new stem transaction comes in there is a chance that it is
treated as coming in as a normal transaction.

An alternative construction would be that when a stem transaction goes
out there is a random chance that the stem flag is not set (with
suitable adjustment to keep the same expected path length)

For some reason I believe this would be a superior construction, but I
am only able to articulate one clear benefit:  It allows non-dandelion
capable nodes to take on the role of the last stem hop, which I
believe would improve the anonymity set during the transition phase.

Unrelated:

Has any work been given to the fact that dandelion propagation
potentially making to measure properties of the inter-node connection
graph?  e.g.  Say I wish to partition node X by disconnecting all of
its outbound connections, to do that it would be useful to learn whom
is connected to X.  I forward a transaction to X, observe the first
node to fluff it,  then DOS attack that node to take it offline.  Will
I need to DOS attack fewer or more nodes  to get all of X's outbounds
if X supports rapid stem forwarding?

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

[Andrew Miller]

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>