path: root/b0/bed6d847905dd8eeac50756ae7e64cdb998680

Return-Path: <dustinpaystaxes@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id C1318C000D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  3 Oct 2021 09:53:15 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 9BDC540547
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  3 Oct 2021 09:53:15 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.199
X-Spam-Level: 
X-Spam-Status: No, score=-0.199 tagged_above=-999 required=5
 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 4GDA47-QhZPw
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  3 Oct 2021 09:53:14 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-lf1-x130.google.com (mail-lf1-x130.google.com
 [IPv6:2a00:1450:4864:20::130])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 9FBCC4017A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun,  3 Oct 2021 09:53:13 +0000 (UTC)
Received: by mail-lf1-x130.google.com with SMTP id x27so58402155lfu.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 03 Oct 2021 02:53:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=j7G1HrYjQL9evI/SORqh2ikPSWAvukDkHoO5dhYesgI=;
 b=Z6FpQD0yLNto5hVrJ79lvRk2W2nqb5uVJD7py27fgI9V7jOb0neMqUEr3n0565scYT
 DFUnsu7djQOFiBcNDe7tWsFXL8EokFQHVVGLih0JMFjVFsLWS1fd35oVuMiU49kKzGMA
 G2196/P9bLGqyeXO0rqurbCihBEDpAOe7YbmJh4HUNcIWVkGQxkuwciTLIiz77q1YRy0
 J7ExYkbP2L5XxcUc6dkeNmba2d0Gd6q6wqhrNUmBCXRYPzv7pW7vGUIXXNr5FMrAVf5f
 3Dv3UG5bESvObXSQsPpkvWw3hN4vb1c8tTA73PXhu/pCIhQbEbYqhUs3Lubnwiwtm7ws
 /waA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=j7G1HrYjQL9evI/SORqh2ikPSWAvukDkHoO5dhYesgI=;
 b=bw6aFw8BJsKzV1hFsOCB/eVkUDbFNQRZr0W1nsFfOP2VRl9hM7cJACWKHQMJECmmDS
 M6SaB8QptRUM+URxp3fZ1ownqwxKPBjEPh4GIIhd65TQysWWK98iq61RyX1isPtVCNAJ
 uLOUpGuAZf0vbJjtlguZotcT3wCQetQShrKKy9i8s7OhTdSsZyGCAvQV8KX/wrmnRaLU
 Mstp3wHgvwjvrDzd8qqScpT7hh72O8YXN0FETGkPY97EIKF6FLajBGUkBQS/m5SZ5CbV
 d0HIgyfMxsabgVFsPm7RX2Au97ieUlFPxgG9F6+uBFvsCSs8GTPZ+zB/eHl5DVP2yTIm
 Ouog==
X-Gm-Message-State: AOAM532GTaEUW7/DhZ5w0PDcS6LGhYC1UsHTXN+T2xf7YqHjsft6b1uo
 F4d+6+9xaYWxsxWqypQhdWQ46VcO5eGGUUM0i6j4c5Is
X-Google-Smtp-Source: ABdhPJxuLJM5ZYNOjp2JgnprLx0XzLKxXlhTUHS0rk/vCMBBZE5H90ehZn/QTTI+gJ0fjGU4gSvKS/cCvrRYHiub9LM=
X-Received: by 2002:a05:6512:224f:: with SMTP id
 i15mr8139553lfu.547.1633254791107; 
 Sun, 03 Oct 2021 02:53:11 -0700 (PDT)
MIME-Version: 1.0
References: <6D57649F-0236-4FBA-8376-4815F5F39E8A@gmail.com>
 <CADZtCSgKu1LvjePNPT=0C0UYQvb47Ca0YN+B_AfgVNTpcOno4w@mail.gmail.com>
In-Reply-To: <CADZtCSgKu1LvjePNPT=0C0UYQvb47Ca0YN+B_AfgVNTpcOno4w@mail.gmail.com>
From: Dustin Dettmer <dustinpaystaxes@gmail.com>
Date: Sun, 3 Oct 2021 02:53:00 -0700
Message-ID: <CABLeJxSrR84bA4OXk9wRG54agF=o8-svOyM55+xF3+-QB7jY_g@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 Jim Posen <jim.posen@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000a6d91e05cd6fc307"
X-Mailman-Approved-At: Sun, 03 Oct 2021 15:08:45 +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.15
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: Sun, 03 Oct 2021 09:53:15 -0000

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

Jim Posen,

A few years ago you mentioned roastbeef=E2=80=99s proposal of a P2P message=
 to
retrieve all prev-outputs for a given block:

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 scrip=
t
> malleability (and thus cannot discriminate between all valid and invalid
> filters), it restricts what an attacker can do. This was proposed by Laol=
u
> AFAIK, and I believe this is how btcd is proceeding.
>

I=E2=80=99m trying to find the follow up on this. Was there discussion abou=
t it
under another name (thread, PR, bip etc)? Apologies if I=E2=80=99m being ob=
tuse and
it=E2=80=99s easily found but for the life of me I can=E2=80=99t find any r=
eferences.
Bip157 seems to not make any mention of it.

Thanks!
Dustin

>


If anyone has other ideas, I'd love to hear them.
>
> -jimpo
>
> [1]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.=
html
>
>
>
> 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
>> earlier and is now offered an alternate reality by a newly connected BIP=
157
>> server.
>>
>> The client notices the alternate reality by routinely asking for filter
>> chain checkpoints after connecting to a new BIP157 server. A divergence =
at
>> 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 n=
ot match
>> previous assumption, and request that filter from the server.
>>
>> The client downloads the corresponding block, checks that its header fit=
s
>> 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 s=
ee
>> if every output script of every transaction is contained in there, if no=
t
>> 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 =
are
>> 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 =
by
>> 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 cha=
in
>> must offer a match for every spent output of the block with the divergen=
t
>> 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, =
in 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
>> contains created scripts and spent outpoints. It appears to me that this
>> would serve 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 =
as
>> 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 th=
e
>> block can be checked entirely against the contents of the same block. Th=
e
>> decision on filter correctness does not require more bandwith then downl=
oad
>> of a block at the mismatching checkpoint. The client could only be force=
d
>> at max. to download 1/1000 th of the blockchain in addition to the filte=
r
>> 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_RET=
URN
>> output scripts.
>>
>> Tamas Blummer
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"auto">Jim Posen,</div><div dir=3D"auto"><br></div><div dir=3D"a=
uto">A few years ago you mentioned roastbeef=E2=80=99s proposal of a P2P me=
ssage to retrieve all prev-outputs for a given block:</div><div><br><div cl=
ass=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding-left:1ex=
;border-left-color:rgb(204,204,204)"><div dir=3D"ltr"><div>1) Introduce a n=
ew 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 executi=
ng them. While this permits some forms of input script malleability (and th=
us cannot discriminate between all valid and invalid filters), it restricts=
 what an attacker can do. This was proposed by Laolu AFAIK, and I believe t=
his is how btcd is proceeding.</div></div></blockquote><div dir=3D"auto"><b=
r></div><div dir=3D"auto">I=E2=80=99m trying to find the follow up on this.=
 Was there discussion about it under another name (thread, PR, bip etc)? Ap=
ologies if I=E2=80=99m being obtuse and it=E2=80=99s easily found but for t=
he life of me I can=E2=80=99t find any references. Bip157 seems to not make=
 any mention of it.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Than=
ks!</div><div dir=3D"auto">Dustin</div><blockquote class=3D"gmail_quote" st=
yle=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:sol=
id;padding-left:1ex;border-left-color:rgb(204,204,204)"><div dir=3D"ltr"><d=
iv></div></div></blockquote><div dir=3D"auto"><br></div><div dir=3D"auto"><=
br></div><div dir=3D"auto"><br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid=
;padding-left:1ex;border-left-color:rgb(204,204,204)"><div dir=3D"ltr"><div=
>If anyone has other ideas, I&#39;d love to hear them.<br></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-June/016057.html" tar=
get=3D"_blank">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018=
-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" target=3D"_blank">bit=
coin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;b=
order-left-style:solid;padding-left:1ex;border-left-color:rgb(204,204,204)"=
>TLDR: a change to BIP158 would allow decision on which filter chain is cor=
rect 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>
_______________________________________________<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></div>

--000000000000a6d91e05cd6fc307--