path: root/81/189a5ccf77ad747fe44e40f2780ea69b5204c6

Return-Path: <jim.posen@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 8ED3D92EE
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  4 Feb 2019 20:18:22 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qt1-f170.google.com (mail-qt1-f170.google.com
	[209.85.160.170])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 657BE87D
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon,  4 Feb 2019 20:18:21 +0000 (UTC)
Received: by mail-qt1-f170.google.com with SMTP id 2so1428467qtb.5
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 04 Feb 2019 12:18:21 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to
	:cc; bh=hVnprkP1IITWKhB8ToUgEX0GkMgEmPMFS49/Gw2ioIs=;
	b=LTfsq8iO8vViZAWGabWSEDpjH95i+qzeTTv27Sj3lOsiT8aO9ekOoI0nV+Pl5YfTwL
	+20b5ZLqQfk2QGGRC/bJ6hgJvDCh1gbKurxf3zZzj+HYvfvtBJBWBtl3QZ8WKLKUEh4j
	aQ1IM0Vp9GZixNzP432kqMmmFaAsaymi+c345B9T2xlzqU3Yin3sf1tRwQiSpuUp5Ogf
	vkAG/AOm2WcDxpuuDT0+OHHJP8hT9Cw0Ego+al0IJx8VuXzf7C5cWbrkuBTtaBu3DE56
	3709TZmVLatrHtYdVUlRcbhMqsSGsGCR+RYBTVnwlhQLYsjs5B1Im3n1SUt0VkyJUtwu
	s3ew==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:references:in-reply-to:from:date
	:message-id:subject:to:cc;
	bh=hVnprkP1IITWKhB8ToUgEX0GkMgEmPMFS49/Gw2ioIs=;
	b=WW+xM7z5/dqT9h1X0USs2w3BjKiHtx8UDeHfj0VHi0d397rZQf/tjVQXENLMfSqnFx
	ODdnCPHO4kh0ceF2xXsusFSnEVhJZIEHnArA5/ILB4TbFJBIHP+K7Ko45korxVRpI1yq
	z2g4SNetH5EjT0MdQrl5NqWApbJhu6ZGOSO8XhJ7WyxUtbuqqLDEWfCwHEaIFJZKv/1S
	n5FgRV0XWKgKVbtuPFZzK+0dv4fF+dJ67lu+3Tf5oK8qUePpNh6P/dlTqFTG4cCnJzC3
	4XaHVIqGeKfKnXLYfWdGOQHXbYva0StSfhnjsRTCaVvAfI1ECJBSyaeqrgHVd9AxfH4r
	Lv1g==
X-Gm-Message-State: AHQUAuboXG+VF0jnmEV9XuYXJufQ8QmiLBiLmatka1Pii5X6rHMb6WEt
	XQfyNaeWb/gOev5ZCgGNUL1ifDa2wn7qxKwekd0=
X-Google-Smtp-Source: AHgI3IZlCG/QdEdLGLzFcqQli4M4ODYXX/dwqul+39nTuV1MHRdPKI/Y7XsLnIi8NANfCL2eRufcXosCWCV4B2AFhjg=
X-Received: by 2002:a0c:80a8:: with SMTP id 37mr936698qvb.191.1549311500273;
	Mon, 04 Feb 2019 12:18:20 -0800 (PST)
MIME-Version: 1.0
References: <6D57649F-0236-4FBA-8376-4815F5F39E8A@gmail.com>
In-Reply-To: <6D57649F-0236-4FBA-8376-4815F5F39E8A@gmail.com>
From: Jim Posen <jim.posen@gmail.com>
Date: Mon, 4 Feb 2019 12:18:08 -0800
Message-ID: <CADZtCSgKu1LvjePNPT=0C0UYQvb47Ca0YN+B_AfgVNTpcOno4w@mail.gmail.com>
To: Tamas Blummer <tamas.blummer@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000009ecea1058117314f"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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: Mon, 04 Feb 2019 22:27:12 +0000
Cc: Jim Posen <jimpo@coinbase.com>
Subject: Re: [bitcoin-dev] Interrogating a BIP157 server,
	BIP158 change proposal
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: Mon, 04 Feb 2019 20:18:22 -0000

--0000000000009ecea1058117314f
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Please see the thread "BIP 158 Flexibility and Filter Size" from 2018
regarding the decision to remove outpoints from the filter [1].

Thanks for bringing this up though, because more discussion is needed on
the client protocol given that clients cannot reliably determine the
integrity of a block filter in a bandwidth-efficient manner (due to the
inclusion of input scripts).

I see three possibilities:
1) Introduce a new P2P message to retrieve all prev-outputs for a given
block (essentially the undo data in Core), and verify the scripts against
the block by executing them. While this permits some forms of input script
malleability (and thus cannot discriminate between all valid and invalid
filters), it restricts what an attacker can do. This was proposed by Laolu
AFAIK, and I believe this is how btcd is proceeding.
2) Clients track multiple possible filter header chains and essentially
consider the union of their matches. So if any filter received for a
particular block header matches, the client downloads the block. The client
can ban a peer if they 1) ever return a filter omitting some data that is
observed in the downloaded block, 2) repeatedly serve filters that trigger
false positive block downloads where such a number of false positives is
statistically unlikely, or 3) repeatedly serves filters that are
significantly larger than the expected size (essentially padding the actual
filters with garbage to waste bandwidth). I have not done the analysis yet,
but we should be able to come up with some fairly simple banning heuristics
using Chernoff bounds. The main downside is that the client logic to track
multiple possible filter chains and filters per block is more complex and
bandwidth increases if connected to a malicious server. I first heard about
this idea from David Harding.
3) Rush straight to committing the filters into the chain (via witness
reserved value or coinbase OP_RETURN) and give up on the pre-softfork BIP
157 P2P mode.

I'm in favor of option #2 despite the downsides since it requires the
smallest number of changes and is supported by the BIP 157 P2P protocol as
currently written. (Though the recommended client protocol in the BIP needs
to be updated to account for this). Another benefit of it is that it
removes some synchronicity assumptions where a peer with the correct
filters keeps timing out and is assumed to be dishonest, while the
dishonest peer is assumed to be OK because it is responsive.

If anyone has other ideas, I'd love to hear them.

-jimpo

[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.ht=
ml



On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> TLDR: a change to BIP158 would allow decision on which filter chain is
> correct at lower bandwith use
>
> Assume there is a BIP157 client that learned a filter header chain earlie=
r
> and is now offered an alternate reality by a newly connected BIP157 serve=
r.
>
> The client notices the alternate reality by routinely asking for filter
> chain checkpoints after connecting to a new BIP157 server. A divergence a=
t
> a checkpoint means that the server disagrees the client's history at or
> before the first diverging checkpoint. The client would then request the
> filter headers between the last matching and first divergent checkpoint,
> and quickly figure which block=E2=80=99s filter is the first that does no=
t match
> previous assumption, and request that filter from the server.
>
> The client downloads the corresponding block, checks that its header fits
> the PoW secured best header chain, re-calculates merkle root of its
> transaction list to know that it is complete and queries the filter to se=
e
> if every output script of every transaction is contained in there, if not
> the server is lying, the case is closed, the server disconnected.
>
> Having all output scripts in the filter does not however guarantee that
> the filter is correct since it might omit input scripts. Inputs scripts a=
re
> not part of the downloaded block, but are in some blocks before that.
> Checking those are out of reach for lightweight client with tools given b=
y
> the current BIP.
>
> A remedy here would be an other filter chain on created and spent
> outpoints as is implemented currently by Murmel. The outpoint filter chai=
n
> must offer a match for every spent output of the block with the divergent
> filter, otherwise the interrogated server is lying since a PoW secured
> block can not spend coins out of nowhere. Doing this check would already
> force the client to download the outpoint filter history up-to the point =
of
> divergence. Then the client would have to download and PoW check every
> block that shows a match in outpoints until it figures that one of the
> spent outputs has a script that was not in the server=E2=80=99s filter, i=
n which
> case the server is lying. If everything checks out then the previous
> assumption on filter history was incorrect and should be replaced by the
> history offered by the interrogated server.
>
> As you see the interrogation works with this added filter but is highly
> ineffective. A really light client should not be forced to download lots =
of
> blocks just to uncover a lying filter server. This would actually be an
> easy DoS on light BIP157 clients.
>
> A better solution is a change to BIP158 such that the only filter contain=
s
> created scripts and spent outpoints. It appears to me that this would ser=
ve
> well both wallets and interrogation of filter servers well:
>
> Wallets would recognize payments to their addresses by the filter as
> output scripts are included, spends from the wallet would be recognized a=
s
> a wallet already knows outpoints of its previously received coins, so it
> can query the filters for them.
>
> Interrogation of a filter server also simplifies, since the filter of the
> block can be checked entirely against the contents of the same block. The
> decision on filter correctness does not require more bandwith then downlo=
ad
> of a block at the mismatching checkpoint. The client could only be forced
> at max. to download 1/1000 th of the blockchain in addition to the filter
> header history.
>
> Therefore I suggest to change BIP158 to have a base filter, defined as:
>
> A basic filter MUST contain exactly the following items for each
> transaction in a block:
>         =E2=80=A2 Spent outpoints
>         =E2=80=A2 The scriptPubKey of each output, aside from all OP_RETU=
RN output
> scripts.
>
> Tamas Blummer
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div dir=3D"ltr">Please see the thread &quot;BIP 158 Flexi=
bility and Filter Size&quot; from 2018 regarding the decision to remove out=
points from the filter [1].</div><div dir=3D"ltr"><br></div><div>Thanks for=
 bringing this up though, because more discussion is needed on the client p=
rotocol given that clients cannot reliably determine the integrity of a blo=
ck filter in a bandwidth-efficient manner (due to the inclusion of input sc=
ripts).</div><div><br></div><div>I see three possibilities:</div><div>1) In=
troduce a new P2P message to retrieve all prev-outputs for a given block (e=
ssentially the undo data in Core), and verify the scripts against the block=
 by executing them. While this permits some forms of input script malleabil=
ity (and thus cannot discriminate between all valid and invalid filters), i=
t restricts what an attacker can do. This was proposed by Laolu AFAIK, and =
I believe this is how btcd is proceeding.</div><div>2) Clients track multip=
le possible filter header chains and essentially consider the union of thei=
r matches. So if any filter received for a particular block header matches,=
 the client downloads the block. The client can ban a peer if they 1) ever =
return a filter omitting some data that is observed in the downloaded block=
, 2) repeatedly serve filters that trigger false positive block downloads w=
here such a number of false positives is statistically unlikely, or 3) repe=
atedly serves filters that are significantly larger than the expected size =
(essentially padding the actual filters with garbage to waste bandwidth). I=
 have not done the analysis yet, but we should be able to come up with some=
 fairly simple banning heuristics using Chernoff bounds. The main downside =
is that the client logic to track multiple possible filter chains and filte=
rs per block is more complex and bandwidth increases if connected to a mali=
cious server. I first heard about this idea from David Harding.</div><div>3=
) Rush straight to committing the filters into the chain (via witness reser=
ved value or coinbase OP_RETURN) and give up on the pre-softfork BIP 157 P2=
P mode.</div><div><br></div><div>I&#39;m in favor of option #2 despite the =
downsides since it requires the smallest number of changes and is supported=
 by the BIP 157 P2P protocol as currently written. (Though the recommended =
client protocol in the BIP needs to be updated to account for this). Anothe=
r benefit of it is that it removes some synchronicity assumptions where a p=
eer with the correct filters keeps timing out and is assumed to be dishones=
t, while the dishonest peer is assumed to be OK because it is responsive.</=
div><div><br></div><div>If anyone has other ideas, I&#39;d love to hear the=
m.</div><div><br></div><div>-jimpo</div><div><br></div><div dir=3D"ltr">[1]=
 <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Ju=
ne/016057.html">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/201=
8-June/016057.html</a></div><div dir=3D"ltr"><br></div><div dir=3D"ltr"><br=
></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev &lt;<a=
 href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.li=
nuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex">TLDR: a change to BIP158 would allow decision on which fil=
ter chain is correct at lower bandwith use<br>
<br>
Assume there is a BIP157 client that learned a filter header chain earlier =
and is now offered an alternate reality by a newly connected BIP157 server.=
<br>
<br>
The client notices the alternate reality by routinely asking for filter cha=
in checkpoints after connecting to a new BIP157 server. A divergence at a c=
heckpoint means that the server disagrees the client&#39;s history at or be=
fore the first diverging checkpoint. The client would then request the filt=
er headers between the last matching and first divergent checkpoint, and qu=
ickly figure which block=E2=80=99s filter is the first that does not match =
previous assumption, and request that filter from the server.<br>
<br>
The client downloads the corresponding block, checks that its header fits t=
he PoW secured best header chain, re-calculates merkle root of its transact=
ion list to know that it is complete and queries the filter to see if every=
 output script of every transaction is contained in there, if not the serve=
r is lying, the case is closed, the server disconnected.<br>
<br>
Having all output scripts in the filter does not however guarantee that the=
 filter is correct since it might omit input scripts. Inputs scripts are no=
t part of the downloaded block, but are in some blocks before that. Checkin=
g those are out of reach for lightweight client with tools given by the cur=
rent BIP.<br>
<br>
A remedy here would be an other filter chain on created and spent outpoints=
 as is implemented currently by Murmel. The outpoint filter chain must offe=
r a match for every spent output of the block with the divergent filter, ot=
herwise the interrogated server is lying since a PoW secured block can not =
spend coins out of nowhere. Doing this check would already force the client=
 to download the outpoint filter history up-to the point of divergence. The=
n the client would have to download and PoW check every block that shows a =
match in outpoints until it figures that one of the spent outputs has a scr=
ipt that was not in the server=E2=80=99s filter, in which case the server i=
s lying. If everything checks out then the previous assumption on filter hi=
story was incorrect and should be replaced by the history offered by the in=
terrogated server. <br>
<br>
As you see the interrogation works with this added filter but is highly ine=
ffective. A really light client should not be forced to download lots of bl=
ocks just to uncover a lying filter server. This would actually be an easy =
DoS on light BIP157 clients.<br>
<br>
A better solution is a change to BIP158 such that the only filter contains =
created scripts and spent outpoints. It appears to me that this would serve=
 well both wallets and interrogation of filter servers well:<br>
<br>
Wallets would recognize payments to their addresses by the filter as output=
 scripts are included, spends from the wallet would be recognized as a wall=
et already knows outpoints of its previously received coins, so it can quer=
y the filters for them.<br>
<br>
Interrogation of a filter server also simplifies, since the filter of the b=
lock can be checked entirely against the contents of the same block. The de=
cision on filter correctness does not require more bandwith then download o=
f a block at the mismatching checkpoint. The client could only be forced at=
 max. to download 1/1000 th of the blockchain in addition to the filter hea=
der history.<br>
<br>
Therefore I suggest to change BIP158 to have a base filter, defined as:<br>
<br>
A basic filter MUST contain exactly the following items for each transactio=
n in a block:<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =E2=80=A2 Spent outpoints<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =E2=80=A2 The scriptPubKey of each output, asid=
e from all OP_RETURN output scripts.<br>
<br>
Tamas Blummer<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>
</blockquote></div>

--0000000000009ecea1058117314f--