MIME-Version: 1.0
In-Reply-To: <CAPg+sBjdTmZ4m5c92CQK5DsU18M=GKgTM-OZZzwgjpE3hqe6=w@mail.gmail.com>
References: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
	<CAPg+sBjdTmZ4m5c92CQK5DsU18M=GKgTM-OZZzwgjpE3hqe6=w@mail.gmail.com>
From: Bradley Denby <bdenby@cmu.edu>
Date: Mon, 11 Jun 2018 10:31:09 -0400
Message-ID: <CAGq_bNKj4rA9pzk7CPA0r099PXOy3naNfZsr=MSPpYh08OZ6TQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000d3e6c7056e5e995b"
Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving
 Transaction Propagation
Precedence: list

--000000000000d3e6c7056e5e995b
Content-Type: text/plain; charset="UTF-8"

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
>

--000000000000d3e6c7056e5e995b
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Thanks for the comments Pieter!</div><div><br></div><=
div>We can make descriptions for the intended node behaviors more clear in =
the BIP.</div><div><br></div><div>Regarding interaction with BIPs 37 and 13=
3, we have found that if Dandelion routing decisions are based on self-repo=
rted features, malicious nodes can often exploit that to launch serious dea=
nonymization attacks. As a result, we recommend not allowing fee filters fr=
om peers to influence the choice of route. Your suggestion of automatically=
 fluffing is a good solution. Another (similar) option would be to apply fe=
e filters in the stempool. This would prevent the tx from propagating in st=
em phase, so eventually an embargo timer on the stem will expire and the tr=
ansaction will fluff. This is slower than auto-fluffing, but requires (slig=
htly) less code.=C2=A0</div><div><br></div><div>Regarding mempool-dependent=
 transactions, the reference implementation adds any mempool transactions t=
o the stempool but not vice-versa so that the stempool becomes a superset o=
f 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 mempoo=
l except when a transaction fluffs. As a result, a node&#39;s stempool shou=
ld accept and propagate Dandelion transactions that depend on other unconfi=
rmed normal mempool transactions. The behavior you described is not intende=
d; if you have any tests demonstrating this behavior, would you mind sharin=
g them?</div><div><br></div><div>Orphans: stem orphans can occur when a nod=
e on the stem shuffles its route between sending dependent transactions. On=
e way to deal with this issue would be to re-broadcast all previous Dandeli=
on transactions that have not been fluffed after Dandelion route shuffling.=
 This could add a fair amount of data and logic. This re-broadcast method a=
lso telegraphs the fact that a Dandelion shuffle has taken place and can re=
sult in bursts of transactions depending on traffic patterns. A second opti=
on (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 h=
appen 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?=C2=A0</div><div><br></div><div>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 biasin=
g the peer selection code.</div><div><br></div><div>On the implementation s=
ide:</div><div><br></div><div>* We apply the same logic to the stempool as =
the mempool in the reference implementation. The stempool should remain a s=
uperset of the mempool to allow for proper handling of mempool-dependent tr=
ansactions.=C2=A0</div><div><br></div><div>* We&#39;ll take a look at setDa=
ndelionInventoryKnown.=C2=A0</div><div><br></div><div>* We will look into u=
sing scheduler jobs instead of a separate thread--could you point us toward=
s somewhere else in the code that uses a scheduler job?</div><div><br></div=
><div>Based on the feedback we have received so far, we are planning to pri=
oritize writing up a clearer spec for node behavior in the BIP. Does that s=
eem reasonable, or are there other issues that are more pressing at this po=
int?=C2=A0</div><div><br></div><div>Cheers</div></div><div class=3D"gmail_e=
xtra"><br><div class=3D"gmail_quote">On Wed, Jun 6, 2018 at 12:01 AM, Piete=
r Wuille <span dir=3D"ltr">&lt;<a href=3D"mailto:pieter.wuille@gmail.com" t=
arget=3D"_blank">pieter.wuille@gmail.com</a>&gt;</span> wrote:<br><blockquo=
te class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc so=
lid;padding-left:1ex">On Thu, May 10, 2018 at 5:59 AM, Bradley Denby via bi=
tcoin-dev<br>
&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@li=
sts.<wbr>linuxfoundation.org</a>&gt; wrote:<br>
&gt; Hi all,<br>
&gt;<br>
&gt; ...<br>
<span class=3D"">&gt;<br>
&gt; This iteration of Dandelion has been tested on our own small network, =
and we<br>
&gt; would like to get the implementation in front of a wider audience. An<=
br>
&gt; updated<br>
&gt; BIP document with further details on motivation, specification,<br>
&gt; compatibility,<br>
&gt; and implementation is located here:<br>
&gt; <a href=3D"https://github.com/mablem8/bips/blob/master/bip-dandelion.m=
ediawiki" rel=3D"noreferrer" target=3D"_blank">https://github.com/mablem8/<=
wbr>bips/blob/master/bip-<wbr>dandelion.mediawiki</a><br>
<br>
</span>Hi Bradley,<br>
<br>
thank you for working on this and going as far as implementing the<br>
entire protocol. It looks like a very well-worked out idea already,<br>
and its semantics can probably be adopted pretty much as-is. It would<br>
be very exciting to bring these kinds of privacy improvements to<br>
Bitcoin&#39;s P2P protocol.<br>
<br>
I do have a number of comments on the specification and suggested<br>
implementation in Bitcoin Core. I&#39;m dumping my thoughts here, though<br=
>
at this stage the specification is probably more important. The<br>
implementation can be discussed more thoroughly when there is a PR<br>
open.<br>
<br>
Specification<br>
<br>
* Overall, I think it would be worthwhile to describe the intended<br>
node behavior in the BIP, at a higher level than Bitcoin Core<br>
patchsets, but more detailed than what is in the BIP now. The<br>
patch-based descriptions are both hard to read for developers working<br>
on different systems who are unfamiliar with the Core codebase, and<br>
don&#39;t make it clear to what extent implementation decisions are local<b=
r>
policy (which can be changed without network coordination), and which<br>
follow from security or privacy arguments for the protocol.<br>
<br>
* Interaction with feefilter (BIP 133) and Bloom filter (BIP 37). When<br>
peers have given us filters on what transactions they will accept,<br>
should Dandelion transactions be subject to the same? Should it<br>
influence the choice of route? One simple possibility is perhaps to<br>
avoid choosing BIP37 peers as Dandelion routes, and treat transactions<br>
that do not pass the feefilter for its<br>
would-be-outgoing-Dandelion-<wbr>route as an automatic fluff - justified by=
<br>
noting that relaying a transaction close to what fee is acceptable to<br>
the network&#39;s mempools is already less likely to get good privacy due<b=
r>
to reduced chances of propagation.<br>
<br>
* Mempool dependant transactions. It looks like the current<br>
implementation accepts Dandelion transactions which are dependant on<br>
other Dandelion (stempool) transactions and on confirmed blockchain<br>
transactions, but not ones that are dependant on other unconfirmed<br>
normal mempool transactions. Is this intentional, or resulting from a<br>
difficulty in implementing this? Should the correct behaviour be<br>
specified, or left free for nodes to decide?<br>
<br>
* Orphan transactions. It looks like the current implementation<br>
assumes no orphan transactions, but in a dynamic network (especially<br>
with occasionally shuffling of Dandelion routes), I expect that<br>
sometimes a dependent transaction will go on a different route than<br>
its parent. Do you have any thoughts about that (even if not addressed<br>
in a very implementation). Could we have a Dandelion-orphan-pool of<br>
transactions, similar to the normal mempool has a set of orphan<br>
transactions?<br>
<br>
* Preferred connections. Should we bias the outgoing connection peer<br>
selection code to prefer Dandelion-capable peers when the number is<br>
too low?<br>
<br>
Implementation<br>
<br>
* How do we control the size of the stempool? Should acceptance of a<br>
transaction to the normal mempool and/or blockchain result in eviction<br>
of it (and conflicts) from the stempool? The existing code<br>
intentionally has an upper bound on the size of the mempool to assure<br>
predictable resource usage - the introduction of the stempool<br>
shouldn&#39;t change that.<br>
<br>
* I don&#39;t think you need to fully materialize all the routes. Instead,<=
br>
you can just maintain a vector of 2 selected Dandelion-supporting<br>
peers (and if one disconnects, replace just that one with another<br>
one). To map incoming peers to an index in that list of peers, you can<br>
use deterministic randomness (see SipHasher in the source code) with<br>
the incoming node_id as data and a single global secret nonce (chosen<br>
at startup, and reset on reshuffle).<br>
<br>
* setDandelionInventoryKnown looks like it can grow unboundedly. A<br>
rolling Bloom filter (like used for filterInventoryKnown) is perhaps<br>
easier to guarantee predictable memory usage for.<br>
<br>
* Use a scheduler job instead of a separate thread for shuffling the<br>
routes (extra threads use unnecessarily large amounts of memory).<br>
<br>
* (nit) coding style: doc/developer-notes.md has a number of<br>
guidelines on coding style you may want to check out.<br>
<br>
Cheers,<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
-- <br>
Pieter<br>
</font></span></blockquote></div><br></div>

--000000000000d3e6c7056e5e995b--