MIME-Version: 1.0
References: <mailman.3774.1530901879.19027.bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <mailman.3774.1530901879.19027.bitcoin-dev@lists.linuxfoundation.org>
From: Giulia Fanti <gfanti@andrew.cmu.edu>
Date: Sun, 8 Jul 2018 08:50:43 -0400
Message-ID: <CAB6Q0ym7uqtJembXuib+VbWHbUGYTQRtP-taJH_ns780a2jDWQ@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary="0000000000006ff6e705707c5af9"
Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving
 Transaction Propagation
Precedence: list

--0000000000006ff6e705707c5af9
Content-Type: text/plain; charset="UTF-8"

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

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

<div dir=3D"ltr"><div class=3D"gmail_quote"><div>=C2=A0Hi Till,=C2=A0</div>=
<div><br></div><div>Thank you for the comments! Responses are inline:</div>=
<div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex=
;border-left:1px #ccc solid;padding-left:1ex">
* Could you elaborate on the reasoning behind choosing the periodic route s=
huffling interval to be around 10 minutes? I guess that there is some trade=
off between making intersection attacks possible by choosing a too small in=
terval, and making graph-learning attacks possible by choosing a too large =
interval. Intuitively, this interval should depend on the number of forward=
ed Dandelion transactions, because these are the events that leak informati=
on, and not the absolute elapsed time. On the other hand, making the interv=
al dependent on the number of processed transactions would allow an active =
adversary to trigger route shuffling by sending Dandelion transaction to sp=
ecific peers, which could enable intersection attacks...<br></blockquote><d=
iv>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; inters=
ection attacks can be really devastating (with recall tending to 1), wherea=
s graph learning attacks still have limited recall and precision. If we dec=
ide to allow graph learning in order to prevent intersection attacks, the n=
atural conclusion would be to use as long a time interval as possible. We a=
re open to changing this time interval; 10 minutes was just a heuristic we =
proposed at the time of writing.=C2=A0</div><div>=C2=A0</div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;p=
adding-left:1ex">
* Speaking of active adversaries: Adversaries could send a large number of =
transactions to selected peers - either by creating the transactions on the=
ir own, or by relaying (Dandelion) transactions observed by the adversary?s=
 peers to the selected peer. Could this allow the adversary to launch finge=
rprinting attacks on the selected peer by comparing the observed propagatio=
n of the transactions relayed through the peer to other transactions observ=
ed?<br></blockquote><div>Yes, this is one of the main ways we envision adve=
rsaries potentially learning the graph in practice.=C2=A0=C2=A0</div><div>=
=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex">
* If an adversary performs a black-hole attack (i.e., drops Dandelion trans=
actions), and if the adversary is able to identify the diffusion source, re=
construction of parts of the anonymity graph (i.e., the part between the di=
ffusion 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 th=
e anonymity graph, but it nonetheless helps the adversary.<br></blockquote>=
<div>This is also true. Using a small shuffle time interval=C2=A0 would hel=
p prevent this, but if we go with a longer interval, this approach could ce=
rtainly help with graph learning.</div><div>=C2=A0</div><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex">
* 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 ad=
versary?s precision and recall regarding imperfect topology knowledge?<br><=
/blockquote><div>We only studied what happens when the adversary has full k=
nowledge of the graph and local knowledge (i.e. the spy nodes know their ow=
n neighbors, but nothing else). We did not study what happens when the adve=
rsary has partial graph knowledge, but that would be an interesting and use=
ful question to look at.</div><div>=C2=A0</div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1e=
x">
<br>
--Till<br>
<br>
<br>
From: <a href=3D"mailto:bitcoin-dev-bounces@lists.linuxfoundation.org" targ=
et=3D"_blank">bitcoin-dev-bounces@lists.linuxfoundation.org</a> [mailto:<a =
href=3D"mailto:bitcoin-dev-bounces@lists.linuxfoundation.org" target=3D"_bl=
ank">bitcoin-dev-bounces@lists.linuxfoundation.org</a>] On Behalf Of Bradle=
y Denby via bitcoin-dev<br>
Sent: Monday, June 4, 2018 10:30 PM<br>
To: <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a><br>
Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Tra=
nsaction Propagation<br>
<br>
Hello all,<br>
<br>
We now have an arXiv preprint of our latest findings available, which provi=
des additional details regarding Dandelion: <a href=3D"https://arxiv.org/pd=
f/1805.11060.pdf" rel=3D"noreferrer" target=3D"_blank">https://arxiv.org/pd=
f/1805.11060.pdf</a><br>
<br>
Note that Dandelion&#39;s precision guarantees are at the population level,=
 while the recall guarantees can be interpreted as individual guarantees. E=
xpected recall is equivalent to the probability of an adversary associating=
 a single transaction with a given source.<br>
<br>
Since these guarantees are probabilistic, a node cannot be sure whether all=
 of its peers are monitoring it. Dandelion does not protect against these a=
dversaries, and individuals who are worried about targeted deanonymization =
should still use Tor.<br>
<br>
One way to conceptualize Dandelion is as a &quot;public health&quot; fix or=
 an &quot;anonymity vaccination.&quot; Higher adoption leads to greater ben=
efits, even for those who are not using Tor. Individuals who adopt Dandelio=
n benefit because their transactions make at least one hop before diffusing=
 (or more as adoption increases).<br>
<br>
Nevertheless, the probabilistic nature of the guarantees means that they ar=
e not absolute. We have shown that any solution based only on routing canno=
t be absolute due to fundamental lower bounds on precision and recall.<br>
<br>
Thank you to Eric Voskuil, Pieter Wuille, Suhas Daftuar, Christian Decker, =
and Tim Ruffing for the recent feedback!<br>
<br>
On Thu, May 10, 2018 at 8:59 AM, Bradley Denby &lt;<a href=3D"mailto:bdenby=
@cmu.edu" target=3D"_blank">bdenby@cmu.edu</a>&gt; wrote:<br>
Hi all,<br>
<br>
We&#39;re writing with an update on the Dandelion project. As a reminder, D=
andelion<br>
is a practical, lightweight privacy solution that provides Bitcoin users fo=
rmal<br>
anonymity guarantees. While other privacy solutions aim to protect individu=
al<br>
users, Dandelion protects privacy by limiting the capability of adversaries=
 to<br>
deanonymize the entire network.<br>
<br>
Bitcoin&#39;s transaction spreading protocol is vulnerable to deanonymizati=
on<br>
attacks. When a node generates a transaction without Dandelion, it transmit=
s<br>
that transaction to its peers with independent, exponential delays. This<br=
>
approach, known as diffusion in academia, allows network adversaries to lin=
k<br>
transactions to IP addresses.<br>
<br>
Dandelion prevents this class of attacks by sending transactions over a ran=
domly<br>
selected path before diffusion. Transactions travel along this path during =
the<br>
&quot;stem phase&quot; and are then diffused during the &quot;fluff phase&q=
uot; (hence the name<br>
Dandelion). We have shown that this routing protocol provides near-optimal<=
br>
anonymity guarantees among schemes that do not introduce additional encrypt=
ion<br>
mechanisms.<br>
<br>
Since the last time we contacted the list, we have:<br>
=C2=A0- Completed additional theoretical analysis and simulations<br>
=C2=A0- Built a working prototype<br>
=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bitcoin/tree/dandelion"=
 rel=3D"noreferrer" target=3D"_blank">https://github.com/mablem8/bitcoin/tr=
ee/dandelion</a>)<br>
=C2=A0- Built a test suite for the prototype<br>
=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bitcoin/blob/dandelion/=
test/functional/p2p_dandelion.py" rel=3D"noreferrer" target=3D"_blank">http=
s://github.com/mablem8/bitcoin/blob/dandelion/test/functional/p2p_dandelion=
.py</a>)<br>
=C2=A0- Written detailed documentation for the new implementation<br>
=C2=A0 =C2=A0(<a href=3D"https://github.com/mablem8/bips/blob/master/bip-da=
ndelion/dandelion-reference-documentation.pdf" rel=3D"noreferrer" target=3D=
"_blank">https://github.com/mablem8/bips/blob/master/bip-dandelion/dandelio=
n-reference-documentation.pdf</a>)<br>
<br>
Among other things, one question we&#39;ve addressed in our additional anal=
ysis is<br>
how to route messages during the stem phase. For example, if two Dandelion<=
br>
transactions arrive at a node from different inbound peers, to which Dandel=
ion<br>
destination(s) should these transactions be sent? We have found that some<b=
r>
choices are much better than others.<br>
<br>
Consider the case in which each Dandelion transaction is forwarded to a<br>
Dandelion destination selected uniformly at random. We have shown that this=
<br>
approach results in a fingerprint attack allowing network-level botnet<br>
adversaries to achieve total deanonymization of the P2P network after obser=
ving<br>
less than ten transactions per node.<br>
<br>
To avoid this issue, we suggest &quot;per-inbound-edge&quot; routing. Each =
inbound peer is<br>
assigned a particular Dandelion destination. Each Dandelion transaction tha=
t<br>
arrives via this peer is forwarded to the same Dandelion destination.<br>
Per-inbound-edge routing breaks the described attack by blocking an adversa=
ry&#39;s<br>
ability to construct useful fingerprints.<br>
<br>
This iteration of Dandelion has been tested on our own small network, and w=
e<br>
would like to get the implementation in front of a wider audience. An updat=
ed<br>
BIP document with further details on motivation, specification, compatibili=
ty,<br>
and implementation is located here:<br>
<a href=3D"https://github.com/mablem8/bips/blob/master/bip-dandelion.mediaw=
iki" rel=3D"noreferrer" target=3D"_blank">https://github.com/mablem8/bips/b=
lob/master/bip-dandelion.mediawiki</a><br>
<br>
We would like to thank the Bitcoin Core developers and Gregory Maxwell in<b=
r>
particular for their insightful comments, which helped to inform this<br>
implementation and some of the follow-up work we conducted. We would also l=
ike<br>
to thank the Mimblewimble development community for coining the term &quot;=
stempool,&quot;<br>
which we happily adopted for this implementation.<br>
<br>
All the best,<br>
Brad Denby &lt;<a href=3D"mailto:bdenby@cmu.edu" target=3D"_blank">bdenby@c=
mu.edu</a>&gt;<br>
Andrew Miller &lt;<a href=3D"mailto:soc1024@illinois.edu" target=3D"_blank"=
>soc1024@illinois.edu</a>&gt;<br>
Giulia Fanti &lt;<a href=3D"mailto:gfanti@andrew.cmu.edu" target=3D"_blank"=
>gfanti@andrew.cmu.edu</a>&gt;<br>
Surya Bakshi &lt;<a href=3D"mailto:sbakshi3@illinois.edu" target=3D"_blank"=
>sbakshi3@illinois.edu</a>&gt;<br>
Shaileshh Bojja Venkatakrishnan &lt;<a href=3D"mailto:shaileshh.bv@gmail.co=
m" target=3D"_blank">shaileshh.bv@gmail.com</a>&gt;<br>
Pramod Viswanath &lt;<a href=3D"mailto:pramodv@illinois.edu" target=3D"_bla=
nk">pramodv@illinois.edu</a>&gt;<br>
<br>
<br>
------------------------------<br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br>
<br>
End of bitcoin-dev Digest, Vol 38, Issue 8<br>
******************************************<br>
</blockquote></div></div>

--0000000000006ff6e705707c5af9--