path: root/81/bc0135f700f7d63fa6419631e49e5526435d21

Return-Path: <bdenby@andrew.cmu.edu>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 283C8D02
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 26 Jun 2018 00:12:07 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lf0-f45.google.com (mail-lf0-f45.google.com
	[209.85.215.45])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8BEED784
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 26 Jun 2018 00:12:05 +0000 (UTC)
Received: by mail-lf0-f45.google.com with SMTP id a4-v6so5215724lff.5
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 25 Jun 2018 17:12:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=cmu-edu.20150623.gappssmtp.com; s=20150623;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to
	:cc; bh=DVnvnToIs0Fk5WQXrFAGs7ZdGQp8hbzL85MJk4b3xwU=;
	b=A2XdW17tCmDPl96/YlPuBXiRtY0PaAnkFnYgXhyKZUSlEd8Rro9S2mGpJD+h7MEdF5
	svnlMjJL0DvVhiT808qpljbU2G4/Fxos+hRymluLQTxeyxflFfho8Yw9XlwjGJmXz5W4
	rQBxnnQLe9pMbbTYnhyXFNiVLDlJeokmVt5uZha5eO01YjGb/h/N1Hg7CDV0Qhku9WV1
	KVu2Wq+t+2qKsQH3pRmHkv0dT1VBnMJq7mUe/+jXHrKNNsW0aG8kUjvRyKg9Y2bLNl43
	rTrP5/O8DVl4HG/MPM8GAhewLrBMpWboYCMYensHbkiawX/ihe7mNnYuPVuHeQAZudsd
	nRYg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to:cc;
	bh=DVnvnToIs0Fk5WQXrFAGs7ZdGQp8hbzL85MJk4b3xwU=;
	b=fgxYWMykcP+4Ms/GLrsf9cUo4Ggf/YUZkIP0EiglapsSaShv3SrjH3xjRvez4FjmiP
	8eslaChv38lby8DNvF5taaBgFIWwwEj39kCS4rkBn5tGopcmjlvd4HJQk0kWhTpGw5SM
	3T56S31sRqo5TvGcT5S7H5fadG2o4bqqJe1Rn2jIwAy86U72f6SQjVwFd+uQXsdkJ/VE
	jUJzvUPDhI50mw8wOiLWQA/GwV/iWOsUrjUWFQxAbA5Eb88SKmZm99jXhnyTbFucHXPf
	E/3zyfqY49iDCZTcMrenmBUYtaYRvZXIN2QO5HiSYTBncH98gZygeGgIYwJY98rn4tF0
	Oc0w==
X-Gm-Message-State: APt69E1S9W2Ke1S1qIvDfZJbK4L6tVjMhwtaqnWyCLBA1kQ2uZCn2Jg+
	0FLYpNqWbkGhVHWO+WsZ74eWSW05V29IMWXl8AHB
X-Google-Smtp-Source: ADUXVKKvs/i6s5JAgsbPXcvwJN4DJGHUiniaZlAPM7P1HLZIE4HAgcqmUbQMRRIC9JQhEwtfH4G+nwtkIwUABKiZBgw=
X-Received: by 2002:a19:ce51:: with SMTP id
	e78-v6mr6057655lfg.99.1529971923454; 
	Mon, 25 Jun 2018 17:12:03 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a2e:2c03:0:0:0:0:0 with HTTP; Mon, 25 Jun 2018 17:12:02
	-0700 (PDT)
In-Reply-To: <CAPg+sBj7HoR8ptaZw9UeJYDegk2q6y0w9s8tOg6mc2bzNw4zVw@mail.gmail.com>
References: <CAGq_bNLvnZcOGU7c-8i7OL-OGAp4N2bX9T5SEROm59YBGL5yzw@mail.gmail.com>
	<CAPg+sBjdTmZ4m5c92CQK5DsU18M=GKgTM-OZZzwgjpE3hqe6=w@mail.gmail.com>
	<CAGq_bNKj4rA9pzk7CPA0r099PXOy3naNfZsr=MSPpYh08OZ6TQ@mail.gmail.com>
	<CAPg+sBj7HoR8ptaZw9UeJYDegk2q6y0w9s8tOg6mc2bzNw4zVw@mail.gmail.com>
From: Bradley Denby <bdenby@cmu.edu>
Date: Mon, 25 Jun 2018 20:12:02 -0400
Message-ID: <CAGq_bNJv6z5uTX-0feNMVFNxtDcFJSuzS14AE68hxnBu9WP=0g@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000039c03056f805976"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Tue, 26 Jun 2018 00:17:31 +0000
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving
 Transaction Propagation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 26 Jun 2018 00:12:07 -0000

--000000000000039c03056f805976
Content-Type: text/plain; charset="UTF-8"

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

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Mon, Jun 11, 2018 at 9:05 PM, Pieter Wuille <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:pieter.wuille@gmail.com" target=3D"_blank">pieter.wuille@gm=
ail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D=
"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;bor=
der-left-color:rgb(204,204,204);padding-left:1ex"><div dir=3D"auto"><span c=
lass=3D"gmail-"><div><div class=3D"gmail_quote"><div dir=3D"ltr">On Mon, Ju=
n 11, 2018, 07:37 Bradley Denby via bitcoin-dev &lt;<a href=3D"mailto:bitco=
in-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.<wbr>=
linuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-styl=
e:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir=3D"lt=
r"><div>Thanks for the comments Pieter!</div><div><br></div><div>We can mak=
e descriptions for the intended node behaviors more clear in the BIP.</div>=
<div><br></div><div>Regarding interaction with BIPs 37 and 133, we have fou=
nd that if Dandelion routing decisions are based on self-reported features,=
 malicious nodes can often exploit that to launch serious deanonymization a=
ttacks. As a result, we recommend not allowing fee filters from peers to in=
fluence the choice of route. Your suggestion of automatically fluffing is a=
 good solution. Another (similar) option would be to apply fee filters in t=
he stempool. This would prevent the tx from propagating in stem phase, so e=
ventually an embargo timer on the stem will expire and the transaction will=
 fluff. This is slower than auto-fluffing, but requires (slightly) less cod=
e.</div></div></blockquote></div></div><div dir=3D"auto"><br></div></span><=
div dir=3D"auto">I understand the argument about not making routing decisio=
ns 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.</div></div></blockquote><div><br></div><div>That&#39;s right, the idea =
is to choose=C2=A0Dandelion relays independently from whether=C2=A0they sup=
port Dandelion. If the chosen nodes do not support Dandelion, then the tran=
sactions are fluffed. Otherwise, the transactions are relayed along a stem.=
</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-c=
olor:rgb(204,204,204);padding-left:1ex"><div dir=3D"auto"><div dir=3D"auto"=
><br></div><div dir=3D"auto">The reason for my suggestion was that most ful=
l nodes on the network use feefilter, while only (from the perspective of D=
andelion uninteresting) light nodes and blocksonly nodes generally use Bloo=
m filters.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Just dropping=
 stem transactions that would otherwise be sent to a Dandelion peer which f=
ails its filter, and relying on embargo seems fine. But perhaps this option=
 is something to describe in the BIP (&quot;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 tha=
t transaction. A node SHOULD NOT make any routing decisions based on the tr=
ansaction itself, and thus SHOULD NOT try to find an alternative Dandelion =
node to forward to&quot; for example).</div></div></blockquote><div><br></d=
iv><div>Thanks for the suggestion, we&#39;ve updated the BIP with RFC 2119 =
language.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"=
margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;bord=
er-left-color:rgb(204,204,204);padding-left:1ex"><div dir=3D"auto"><span cl=
ass=3D"gmail-"><div dir=3D"auto"><br></div><div dir=3D"auto"><div class=3D"=
gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px =
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(2=
04,204,204);padding-left:1ex"><div dir=3D"ltr"><div>Regarding mempool-depen=
dent transactions, the reference implementation adds any mempool transactio=
ns to the stempool but not vice-versa so that the stempool becomes a supers=
et of the mempool. In other words, information is free to flow from the mem=
pool to the stempool. Information does not flow from the stempool to the me=
mpool except when a transaction fluffs. As a result, a node&#39;s stempool =
should accept and propagate Dandelion transactions that depend on other unc=
onfirmed normal mempool transactions. The behavior you described is not int=
ended; if you have any tests demonstrating this behavior, would you mind sh=
aring them?</div></div></blockquote></div></div><div dir=3D"auto"><br></div=
></span><div dir=3D"auto">Oh, I see! I was just judging based on the spec c=
ode you published, but I must have missed this. Yes, that makes perfect sen=
se. There may be some issues with this having a significant impact on stemp=
ool memory usage, but let&#39;s discuss this later on implementation.</div>=
<span class=3D"gmail-"><div dir=3D"auto"><br></div><div dir=3D"auto"><div c=
lass=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-col=
or:rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>Orphans: stem o=
rphans 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-bro=
adcast 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 traf=
fic patterns. A second option (which we used in the reference implementatio=
n) 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. D=
o you have any thoughts on which option would be more palatable? Or if ther=
e are other options we have missed?</div></div></blockquote></div></div><di=
v dir=3D"auto"><br></div></span><div dir=3D"auto">Another option (just brai=
nstorming, I may be missing something here), is to remember which peer each=
 stempool transaction was forwarded to. When a dependent stem transaction a=
rrives, it is always sent to (one of?) the peers its dependencies were sent=
 to, even if a reshuffle happened in between.</div><div dir=3D"auto"><br></=
div><div dir=3D"auto">Thinking more about it, relying on embargo is probabl=
y fine - it&#39;ll just result in slightly lowered average stem length, and=
 perhaps multiple simultaneous fluffs starting?</div></div></blockquote><di=
v><br></div><div>That&#39;s right, the stem length=C2=A0would be slightly s=
horter because of the time spent waiting for the parent transaction, and yo=
u could get multiple simultaneous fluffs. If this is acceptable, it is prob=
ably the simplest solution.<br></div><div>=C2=A0</div><blockquote class=3D"=
gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border=
-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div=
 dir=3D"auto"><span class=3D"gmail-"><div dir=3D"auto"><br></div><div dir=
=3D"auto"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid=
;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div=
>Regarding preferred connections, we have found that making Dandelion routi=
ng decisions based on claims made by peer nodes can cause problems and ther=
efore would recommend against biasing the peer selection code.</div></div><=
/blockquote></div></div><div dir=3D"auto"><br></div></span><div dir=3D"auto=
">Oh, I don&#39;t mean routing decisions, but connections in general.</div>=
</div></blockquote><div><br></div><div>Ah ok. Even biasing a node&#39;s con=
nections to prefer Dandelion nodes could be problematic, especially in the =
early-deployment stage. For instance, a set of malicious nodes could run Da=
ndelion at the beginning; since there are few honest nodes running Dandelio=
n, the malicious nodes would draw a disproportionate fraction of peer conne=
ctions. This could have implications for anonymity as well as eclipsing att=
acks. So we would suggest not changing the peer connection strategy. In fac=
t, we found that even when there are very few nodes running Dandelion, this=
 Dandelion-agnostic connection strategy still provides some benefit over th=
e current mechanism.<br></div><div>=C2=A0</div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-s=
tyle:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir=3D=
"auto"><div dir=3D"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_qu=
ote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo=
rder-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,2=
04);padding-left:1ex"><div dir=3D"ltr"><div>On the implementation side:</di=
v><div></div></div></blockquote></div></div><div dir=3D"auto"><br></div><di=
v dir=3D"auto">Let&#39;s discuss these later.</div><span class=3D"gmail-"><=
div dir=3D"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_quote"><bl=
ockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-lef=
t-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padd=
ing-left:1ex"><div dir=3D"ltr"><div><br></div><div>Based on the feedback we=
 have received so far, we are planning to prioritize writing up a clearer s=
pec for node behavior in the BIP. Does that seem reasonable, or are there o=
ther issues that are more pressing at this point?=C2=A0</div></div></blockq=
uote></div></div><div dir=3D"auto"><br></div></span><div dir=3D"auto">I thi=
nk that&#39;s the primary thing to focus on at this point, but perhaps othe=
rs on this list feel different.</div></div></blockquote><div><br></div><div=
>We&#39;ve updated the BIP with RFC 2119 statements. Thanks for the feedbac=
k!</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left=
-color:rgb(204,204,204);padding-left:1ex"><div dir=3D"auto"><div dir=3D"aut=
o"><br></div><div dir=3D"auto">Cheers,</div><span class=3D"gmail-HOEnZb"><f=
ont color=3D"#888888"><div dir=3D"auto"><br></div><div dir=3D"auto">--=C2=
=A0</div><div dir=3D"auto">Pieter</div><div dir=3D"auto"><br></div></font><=
/span></div>
</blockquote></div><br></div></div>

--000000000000039c03056f805976--