Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id C1318C000D for ; 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 ; 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 ; 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 ; Sun, 3 Oct 2021 09:53:13 +0000 (UTC) Received: by mail-lf1-x130.google.com with SMTP id x27so58402155lfu.5 for ; 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> In-Reply-To: From: Dustin Dettmer Date: Sun, 3 Oct 2021 02:53:00 -0700 Message-ID: To: Bitcoin Protocol Discussion , Jim Posen Content-Type: multipart/alternative; boundary="000000000000a6d91e05cd6fc307" X-Mailman-Approved-At: Sun, 03 Oct 2021 15:08:45 +0000 Cc: Jim Posen 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Jim Posen,

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:

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

Than= ks!
Dustin

<= br>

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

On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev <bit= coin-dev@lists.linuxfoundation.org> wrote:
TLDR: a change to BIP158 would allow decision on which filter chain is cor= rect 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 BIP157 server.=

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

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.

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.

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.

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.

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 wall= et already knows outpoints of its previously received coins, so it can quer= y the filters for them.

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.

Therefore I suggest to change BIP158 to have a base filter, defined as:

A basic filter MUST contain exactly the following items for each transactio= n in a block:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =E2=80=A2 Spent outpoints
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =E2=80=A2 The scriptPubKey of each output, asid= e from all OP_RETURN output scripts.

Tamas Blummer
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000a6d91e05cd6fc307--