diff options
| author | Olaoluwa Osuntokun <laolu32@gmail.com> | 2018-05-18 19:51:02 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-05-19 02:51:19 +0000 |
| commit | fc2860739d938ca143ec93bd10da9c24ab536d61 (patch) | |
| tree | be1e7a234f2980406be0c658cd03b258017f95b7 | |
| parent | 451cd6492722d7e05c526676f0e0d710f0de6b0d (diff) | |
| download | pi-bitcoindev-fc2860739d938ca143ec93bd10da9c24ab536d61.tar.gz pi-bitcoindev-fc2860739d938ca143ec93bd10da9c24ab536d61.zip | |
Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
| -rw-r--r-- | e5/31f88e4624fab193ecc8aee57145c2bbc65216 | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/e5/31f88e4624fab193ecc8aee57145c2bbc65216 b/e5/31f88e4624fab193ecc8aee57145c2bbc65216 new file mode 100644 index 000000000..f1bede648 --- /dev/null +++ b/e5/31f88e4624fab193ecc8aee57145c2bbc65216 @@ -0,0 +1,312 @@ +Return-Path: <laolu32@gmail.com> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 45FA2E4D + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 19 May 2018 02:51:19 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-wm0-f65.google.com (mail-wm0-f65.google.com [74.125.82.65]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 176A5B0 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 19 May 2018 02:51:18 +0000 (UTC) +Received: by mail-wm0-f65.google.com with SMTP id f8-v6so18229741wmc.4 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 18 May 2018 19:51:17 -0700 (PDT) +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; + bh=EP/poyr6jJxFayL3QKvwckUEb1mAVzJksnXmgtdUly0=; + b=rgUWRl0LRhssyIG/hd6WuDkGEuAoXS3YcTUm5kgLESKm3hFf9yNa11onnvgvclIkdA + YvuI5h6zQBPhfoZvvLpEo5J/8ZIgt/2DfSed8YzBwDLMqxMQTmaAeRljoQsykV1yX7XA + S+pXA/jdP8Xnbj78zNd4elo/LsVb+4XBtO7ik8KAKbCtJn0MZy3D8ODN5EXj50KzmYIU + mnuOT/J/+SqwTauztVgyzx/POw3jmJt3lz9kly3ogjnVtmAkbrlIz5BD+zUDRh0IMnEm + iRoJX/8e2I+/tMIY2AXl5+yNszq1bSeCpl3Ncj3ukXXtGdJ4NA7yOe1tZ1xnC4cRaLJ6 + UFgQ== +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; + bh=EP/poyr6jJxFayL3QKvwckUEb1mAVzJksnXmgtdUly0=; + b=IzniSCW8bwdsb8jIsdT+yyM2JXMZun7KlzFVdj1My05yRqEJAn4yq8bCA65eEVT39T + rdvXoLVKsvnyHceQBwjAcYWs16kNIUPVIoYE3GKofp0SM0H117bfsTOdMhh36FjRtdhS + 1G+AR+AGnZ8DDMXrjK7RPrwJR5Ixct1h1hA6iUvyMRsU1cNO5Ww8bUrDebW4ses3U5QG + umfemiyhMAAmfgBf+8wKG1HhWkUMw11Xo2ruHmxJMFEa/uPBrCXrRX5RvJy9JxKiy4Q7 + aYBeaU8f+ZANHKs/w/rK1Dg/N43vIjtVwbeifPfAoW8mUt/FI4tkPlbO/T49l3DNUZdZ + wnWQ== +X-Gm-Message-State: ALKqPwdNELMkFdAbEKXWQQZU7lDb4A56ZIVhun0r3mgsatS9Z+rjyMEm + lbijx8gAcI5/ozR45EMeYKZ65O8d1bin+gFX0o7w9g== +X-Google-Smtp-Source: AB8JxZporD0M7ei6tH8kJI4JJH66mWSzGcrLA1bxTEFCQj4a+4BoPY/rCGQfGcuzIUcjksm/7DijYK1nntEjP5Jl2qY= +X-Received: by 2002:aa7:c2d0:: with SMTP id + m16-v6mr14427761edp.171.1526698276507; + Fri, 18 May 2018 19:51:16 -0700 (PDT) +MIME-Version: 1.0 +References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com> +In-Reply-To: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com> +From: Olaoluwa Osuntokun <laolu32@gmail.com> +Date: Fri, 18 May 2018 19:51:02 -0700 +Message-ID: <CAO3Pvs8t6rNBkdCNBfqH+cyxLftBPCUMB9ZjDuHq--SXGmCvnA@mail.gmail.com> +To: Matt Corallo <lf-lists@mattcorallo.com>, + Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary="00000000000073544d056c862419" +X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, + DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM, + HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1 +X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on + smtp1.linux-foundation.org +Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size +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: Sat, 19 May 2018 02:51:19 -0000 + +--00000000000073544d056c862419 +Content-Type: text/plain; charset="UTF-8" + +Matt wrote: +> I believe (1) could be skipped entirely - there is almost no reason why +> you'd not be able to filter for, eg, the set of output scripts in a +> transaction you know about + +Depending on the use-case, the txid is more precise than searching for the +output script as it doesn't need to deal with duplicated output scripts. To +my knowledge, lnd is the only major project that currently utilizes BIP +157+158. At this point, we use the txid in the regular filter for +confirmations (channel confirmed, sweep tx confirmed, cltv confirmed, etc). +Switching to use output scripts instead wouldn't be _too_ invasive w.r.t +changes required in the codebase, only the need to deal with output script +duplication could be annoying. + +> (2) and (3) may want to be split out - many wallets may wish to just find +> transactions paying to them, as transactions spending from their outputs +> should generally be things they've created. + +FWIW, in the "rescan after importing by seed phrase" both are needed in +order to ensure the wallet ends up with the proper output set after the +scan. In lnd we actively use both (2) to detect deposits to the internal +wallet, and (3) to be notified when our channel outputs are spent on-chain +(and also generally when any of our special scripts are spent). + +> In general, I'm concerned about the size of the filters making existing +SPV +> clients less willing to adopt BIP 158 instead of the existing bloom filter +> garbage and would like to see a further exploration of ways to split out +> filters to make them less bandwidth intensive. + +Agreed that the current filter size may prevent adoption amongst wallets. +However, the other factor that will likely prevent adoption amongst current +BIP-37 mobile wallets is the lack of support for notifying _unconfirmed_ +transactions. When we drafted up the protocol last year and asked around, +this was one of the major points of contention amongst existing mobile +wallets that utilize BIP 37. + +On the other hand, the two "popular" BIP 37 wallets I'm aware of +(Breadwallet, and Andreas Schildbach's Bitcoin Wallet) have lagged massively +behind the existing set of wallet related protocol upgrades. For example, +neither of them have released versions of their applications that take +advantage of segwit in any manner. Breadwallet has more or less "pivoted" +(they did an ICO and have a token) and instead is prioritizing things like +adding random ICO tokens over catching up with the latest protocol updates. +Based on this behavior, even if the filter sizes were even _more_ bandwidth +efficient that BIP 37, I don't think they'd adopt the protocol. + +> Some further ideas we should probably play with before finalizing moving +> forward is providing filters for certain script templates, eg being able +to +> only get outputs that are segwit version X or other similar ideas. + +Why should this block active deployment of BIP 157+158 as is now? As +defined, the protocol already allows future updates to add additional filter +types. Before the filters are committed, each filter type requires a new +filter header. We could move to a single filter header that commits to the +hashes of _all_ filters, but that would mean that a node couldn't serve the +headers unless they had all currently defined features, defeating the +optionality offered. + +Additionally, more filters entails more disk utilization for nodes serving +these filters. Nodes have the option to instead create the filters at "query +time", but then this counters the benefit of simply slinging the filters +from disk (or a memory map or w/e). IMO, it's a desirable feature that +serving light clients no longer requires active CPU+I/O and instead just +passive I/O (nodes could even write the filters to disk in protocol msg +format). + +To get a feel for the current filter sizes, a txid-only filter size, and a +regular filter w/o txid's, I ran some stats on the last 10k blocks: + +regular size: 217107653 bytes +regular avg: 21710.7653 bytes +regular median: 22332 bytes +regular max: 61901 bytes + +txid-only size: 34518463 bytes +txid-only avg: 3451.8463 bytes +txid-only median: 3258 bytes +txid-only max: 10193 bytes + +reg-no-txid size: 182663961 bytes +reg-no-txid avg: 18266.3961 bytes +reg-no-txid median: 19198 bytes +reg-no-txid max: 60172 bytes + +So the median regular filter size over the past 10k blocks is 20KB. If we +extract the txid from the regular filter and add a txid-only filter, the +median size of that is 3.2KB. Finally, the median size of a modified regular +filter (no txid) is 19KB. + +-- Laolu + + +On Thu, May 17, 2018 at 8:33 AM Matt Corallo via bitcoin-dev < +bitcoin-dev@lists.linuxfoundation.org> wrote: + +> BIP 158 currently includes the following in the "basic" filter: 1) +> txids, 2) output scripts, 3) input prevouts. +> +> I believe (1) could be skipped entirely - there is almost no reason why +> you'd not be able to filter for, eg, the set of output scripts in a +> transaction you know about and (2) and (3) may want to be split out - +> many wallets may wish to just find transactions paying to them, as +> transactions spending from their outputs should generally be things +> they've created. +> +> In general, I'm concerned about the size of the filters making existing +> SPV clients less willing to adopt BIP 158 instead of the existing bloom +> filter garbage and would like to see a further exploration of ways to +> split out filters to make them less bandwidth intensive. Some further +> ideas we should probably play with before finalizing moving forward is +> providing filters for certain script templates, eg being able to only +> get outputs that are segwit version X or other similar ideas. +> +> Matt +> _______________________________________________ +> bitcoin-dev mailing list +> bitcoin-dev@lists.linuxfoundation.org +> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev +> + +--00000000000073544d056c862419 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr"><div>Matt wrote:</div><div>> I believe (1) could be ski= +pped entirely - there is almost no reason why</div><div>> you'd not = +be able to filter for, eg, the set of output scripts in a</div><div>> tr= +ansaction you know about</div><div><br></div><div>Depending on the use-case= +, the txid is more precise than searching for the</div><div>output script a= +s it doesn't need to deal with duplicated output scripts. To</div><div>= +my knowledge, lnd is the only major project that currently utilizes BIP</di= +v><div>157+158. At this point, we use the txid in the regular filter for</d= +iv><div>confirmations (channel confirmed, sweep tx confirmed, cltv confirme= +d, etc).</div><div>Switching to use output scripts instead wouldn't be = +_too_ invasive w.r.t</div><div>changes required in the codebase, only the n= +eed to deal with output script</div><div>duplication could be annoying.</di= +v><div><br></div><div>> (2) and (3) may want to be split out - many wall= +ets may wish to just find</div><div>> transactions paying to them, as tr= +ansactions spending from their outputs</div><div>> should generally be t= +hings they've created.</div><div><br></div><div>FWIW, in the "resc= +an after importing by seed phrase" both are needed in</div><div>order = +to ensure the wallet ends up with the proper output set after the</div><div= +>scan. In lnd we actively use both (2) to detect deposits to the internal</= +div><div>wallet, and (3) to be notified when our channel outputs are spent = +on-chain</div><div>(and also generally when any of our special scripts are = +spent).</div><div><br></div><div>> In general, I'm concerned about t= +he size of the filters making existing SPV</div><div>> clients less will= +ing to adopt BIP 158 instead of the existing bloom filter</div><div>> ga= +rbage and would like to see a further exploration of ways to split out</div= +><div>> filters to make them less bandwidth intensive.</div><div><br></d= +iv><div>Agreed that the current filter size may prevent adoption amongst wa= +llets.</div><div>However, the other factor that will likely prevent adoptio= +n amongst current</div><div>BIP-37 mobile wallets is the lack of support fo= +r notifying _unconfirmed_</div><div>transactions. When we drafted up the pr= +otocol last year and asked around,</div><div>this was one of the major poin= +ts of contention amongst existing mobile</div><div>wallets that utilize BIP= + 37.</div><div><br></div><div>On the other hand, the two "popular"= +; BIP 37 wallets I'm aware of</div><div>(Breadwallet, and Andreas Schil= +dbach's Bitcoin Wallet) have lagged massively</div><div>behind the exis= +ting set of wallet related protocol upgrades. For example,</div><div>neithe= +r of them have released versions of their applications that take</div><div>= +advantage of segwit in any manner. Breadwallet has more or less "pivot= +ed"</div><div>(they did an ICO and have a token) and instead is priori= +tizing things like</div><div>adding random ICO tokens over catching up with= + the latest protocol updates.</div><div>Based on this behavior, even if the= + filter sizes were even _more_ bandwidth</div><div>efficient that BIP 37, I= + don't think they'd adopt the protocol.</div><div><br></div><div>&g= +t; Some further ideas we should probably play with before finalizing moving= +</div><div>> forward is providing filters for certain script templates, = +eg being able to</div><div>> only get outputs that are segwit version X = +or other similar ideas.</div><div><br></div><div>Why should this block acti= +ve deployment of BIP 157+158 as is now? As</div><div>defined, the protocol = +already allows future updates to add additional filter</div><div>types. Bef= +ore the filters are committed, each filter type requires a new</div><div>fi= +lter header. We could move to a single filter header that commits to the</d= +iv><div>hashes of _all_ filters, but that would mean that a node couldn'= +;t serve the</div><div>headers unless they had all currently defined featur= +es, defeating the</div><div>optionality offered.</div><div><br></div><div>A= +dditionally, more filters entails more disk utilization for nodes serving</= +div><div>these filters. Nodes have the option to instead create the filters= + at "query</div><div>time", but then this counters the benefit of= + simply slinging the filters</div><div>from disk (or a memory map or w/e). = +IMO, it's a desirable feature that</div><div>serving light clients no l= +onger requires active CPU+I/O and instead just</div><div>passive I/O (nodes= + could even write the filters to disk in protocol msg</div><div>format).</d= +iv><div><br></div><div>To get a feel for the current filter sizes, a txid-o= +nly filter size, and a</div><div>regular filter w/o txid's, I ran some = +stats on the last 10k blocks:</div><div><br></div><div>regular size:=C2=A0 = +=C2=A0 217107653=C2=A0 bytes</div><div>regular avg:=C2=A0 =C2=A0 =C2=A02171= +0.7653 bytes</div><div>regular median:=C2=A0 22332=C2=A0 =C2=A0 =C2=A0 byte= +s</div><div>regular max:=C2=A0 =C2=A0 =C2=A061901=C2=A0 =C2=A0 =C2=A0 bytes= +</div><div><br></div><div>txid-only size:=C2=A0 =C2=A0 34518463=C2=A0 bytes= +</div><div>txid-only avg:=C2=A0 =C2=A0 =C2=A03451.8463 bytes</div><div>txid= +-only median:=C2=A0 3258=C2=A0 =C2=A0 =C2=A0 bytes</div><div>txid-only max:= +=C2=A0 =C2=A0 =C2=A010193=C2=A0 =C2=A0 =C2=A0bytes</div><div><br></div><div= +>reg-no-txid size:=C2=A0 =C2=A0 182663961=C2=A0 bytes</div><div>reg-no-txid= + avg:=C2=A0 =C2=A0 =C2=A018266.3961 bytes</div><div>reg-no-txid median:=C2= +=A0 19198=C2=A0 =C2=A0 =C2=A0 bytes</div><div>reg-no-txid max:=C2=A0 =C2=A0= + =C2=A060172=C2=A0 =C2=A0 =C2=A0 bytes</div><div><br></div><div>So the medi= +an regular filter size over the past 10k blocks is 20KB. If we</div><div>ex= +tract the txid from the regular filter and add a txid-only filter, the</div= +><div>median size of that is 3.2KB. Finally, the median size of a modified = +regular</div><div>filter (no txid) is 19KB.</div><div><br></div><div>-- Lao= +lu</div><div><br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On T= +hu, May 17, 2018 at 8:33 AM Matt Corallo via bitcoin-dev <<a href=3D"mai= +lto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundatio= +n.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"ma= +rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">BIP 158 curren= +tly includes the following in the "basic" filter: 1)<br> +txids, 2) output scripts, 3) input prevouts.<br> +<br> +I believe (1) could be skipped entirely - there is almost no reason why<br> +you'd not be able to filter for, eg, the set of output scripts in a<br> +transaction you know about and (2) and (3) may want to be split out -<br> +many wallets may wish to just find transactions paying to them, as<br> +transactions spending from their outputs should generally be things<br> +they've created.<br> +<br> +In general, I'm concerned about the size of the filters making existing= +<br> +SPV clients less willing to adopt BIP 158 instead of the existing bloom<br> +filter garbage and would like to see a further exploration of ways to<br> +split out filters to make them less bandwidth intensive. Some further<br> +ideas we should probably play with before finalizing moving forward is<br> +providing filters for certain script templates, eg being able to only<br> +get outputs that are segwit version X or other similar ideas.<br> +<br> +Matt<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></div> + +--00000000000073544d056c862419-- + |