diff options
| author | Olaoluwa Osuntokun <laolu32@gmail.com> | 2018-05-21 18:16:52 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-05-22 01:17:07 +0000 |
| commit | b904b198a3cf996179a011ff214a21e39d408ede (patch) | |
| tree | 48a33cb0b87f274df03ecb326941bab464a28a52 | |
| parent | 4f1fe37a370e86044ea6cf7561946b002e9b89e6 (diff) | |
| download | pi-bitcoindev-b904b198a3cf996179a011ff214a21e39d408ede.tar.gz pi-bitcoindev-b904b198a3cf996179a011ff214a21e39d408ede.zip | |
Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
| -rw-r--r-- | 23/fb5b6d468d2061992d198805288ebf6149ebb8 | 279 |
1 files changed, 279 insertions, 0 deletions
diff --git a/23/fb5b6d468d2061992d198805288ebf6149ebb8 b/23/fb5b6d468d2061992d198805288ebf6149ebb8 new file mode 100644 index 000000000..c4457d4bc --- /dev/null +++ b/23/fb5b6d468d2061992d198805288ebf6149ebb8 @@ -0,0 +1,279 @@ +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 98CF1D0A + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 22 May 2018 01:17:07 +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 5D035F3 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 22 May 2018 01:17:05 +0000 (UTC) +Received: by mail-wm0-f65.google.com with SMTP id x12-v6so14039581wmc.0 + for <bitcoin-dev@lists.linuxfoundation.org>; + Mon, 21 May 2018 18:17:05 -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 + :cc; bh=cifVcp8iVLNyTFBMIw4vG8BbfDyatTpibI4P5ELqLoQ=; + b=twCxahCiZ1TGoU+n9kN0rezvYaAAfajjOPg3ucqrlDWX0sd/PBf/8H0Q1ch+7jumvS + hA9RDNsDQdje1PKtCLzdSWiQEkjKCWwi/pU8Xipisun0MHhn2LO0rE05RUBPfq5qq4z9 + IVG3gJ6uBCm8ZIgnv91EgpEtFmA9w4iLX9uGe8UiGQlAVdoCLpREPC6RkbcBE/ME9swb + BO9CNotxgLnTbqSdprz+4Z81oQUHV3pwX9mJBsfHpEYrlcwpqGMVTG9OTTJ+q1GHU0oo + HUPdeaYy9iQu1qrtLlNWjwifMkOygkr41f+l8EL3QETJ+YxjlSGob71lYADDO0nUrctV + BZKw== +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=cifVcp8iVLNyTFBMIw4vG8BbfDyatTpibI4P5ELqLoQ=; + b=Gs/XxKOdU4udBbH/ehUwRoYkEOg84tjYkTe6h/AF94e8tmqgDGIWdDQFio7Zfjm8W3 + RKfH5Za9rWDe31YcvomG92aAeasUZzexZp+oP14dJJEBbATtOz0/GbcLzfkJFCE4tHJZ + Ev45WWan29czZOwNQRhoRWe5sykqEYI0I+f9WdtwTXejjY6GewBrCwHIAohn0BnoHD5O + xRBIFqKglaUruJ0EoQd8+VvAQYBfCaeZejhX4UKYwKfsK8sW2vHImHDgvLjcEUOnsvWe + qnofSURbCHVm5/bA4FXBtYAZsHkeb9zTCgwyjybJKxLfa3hTFaiWKCUwqRzUDyU0pVk7 + LGjQ== +X-Gm-Message-State: ALKqPwcf+uMXMQLWL7qnji2v6Sx88LVcyzqKlIsXyg5yk9zgYR6IAkoM + 79kHXKXQ22syOhkHZBb8bfUwhJ0iKadZv6KxGnA= +X-Google-Smtp-Source: AB8JxZpCHIwC7lLQSeU3tPa6UejuTCL3rWi50Nsd4QsCElSDlQhssVixcaVALgZngA6qzjiB0iCw8Y1IDn+dLcp3VdE= +X-Received: by 2002:aa7:c60a:: with SMTP id + h10-v6mr25969614edq.151.1526951824003; + Mon, 21 May 2018 18:17:04 -0700 (PDT) +MIME-Version: 1.0 +References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com> + <CAAS2fgRF-MhOvpFY6c_qAPzNMo3GQ28RExdSbOV6Q6Oy2iWn1A@mail.gmail.com> + <22d375c7-a032-8691-98dc-0e6ee87a4b08@mattcorallo.com> + <CAAS2fgR3QRHeHEjjOS1ckEkL-h7=Na56G12hYW9Bmy9WEMduvg@mail.gmail.com> + <CADZtCShLmH_k-UssNWahUNHgHvWQQ1y638LwaOfnJEipwjbiYg@mail.gmail.com> + <CAAS2fgQLCN_cuZ-3QPjCLfYOtHfEk=SenTn5=y9LfGzJxLPR3Q@mail.gmail.com> + <CADZtCSjYr6VMBVQ=rx44SgRWcFSXhVXUZJB=rHMh4X78Z2eY1A@mail.gmail.com> + <CAO3Pvs9K3n=OzVQ06XGQvzNC+Aqp9S60kWM9VRPA8hWTJ3u9BQ@mail.gmail.com> + <c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com> +In-Reply-To: <c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com> +From: Olaoluwa Osuntokun <laolu32@gmail.com> +Date: Mon, 21 May 2018 18:16:52 -0700 +Message-ID: <CAO3Pvs_MA4TtgCCu1NgCBjK2bZRN+rKnGQJN6m4yTrViBXRiPA@mail.gmail.com> +To: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com> +Content-Type: multipart/alternative; boundary="0000000000000f1609056cc12d60" +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 +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.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: Tue, 22 May 2018 01:17:07 -0000 + +--0000000000000f1609056cc12d60 +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +> What if instead of trying to decide up front which subset of elements wil= +l +> be most useful to include in the filters, and the size tradeoff, we let +the +> full-node decide which subsets of elements it serves filters for? + +This is already the case. The current "track" is to add new service bits +(while we're in the uncommitted phase) to introduce new fitler types. Light +clients can then filter out nodes before even connecting to them. + +-- Laolu + +On Mon, May 21, 2018 at 1:35 AM Johan Tor=C3=A5s Halseth <johanth@gmail.com= +> +wrote: + +> Hi all, +> +> Most light wallets will want to download the minimum amount of data +> required to operate, which means they would ideally download the smallest +> possible filters containing the subset of elements they need. +> +> What if instead of trying to decide up front which subset of elements wil= +l +> be most useful to include in the filters, and the size tradeoff, we let t= +he +> full-node decide which subsets of elements it serves filters for? +> +> For instance, a full node would advertise that it could serve filters for +> the subsets 110 (txid+script+outpoint), 100 (txid only), 011 (script+outp= +oint) +> etc. A light client could then choose to download the minimal filter type +> covering its needs. +> +> The obvious benefit of this would be minimal bandwidth usage for the ligh= +t +> client, but there are also some less obvious ones. We wouldn=E2=80=99t ha= +ve to +> decide up front what each filter type should contain, only the possible +> elements a filter can contain (more can be added later without breaking +> existing clients). This, I think, would let the most served filter types +> grow organically, with full-node implementations coming with sane default= +s +> for served filter types (maybe even all possible types as long as the +> number of elements is small), letting their operator add/remove types at +> will. +> +> The main disadvantage of this as I see it, is that there=E2=80=99s an exp= +onential +> blowup in the number of possible filter types in the number of element +> types. However, this would let us start out small with only the elements = +we +> need, and in the worst case the node operators just choose to serve the +> subsets corresponding to what now is called =E2=80=9Cregular=E2=80=9D + = +=E2=80=9Cextended=E2=80=9D filters +> anyway, requiring no more resources. +> +> This would also give us some data on what is the most widely used filter +> types, which could be useful in making the decision on what should be par= +t +> of filters to eventually commit to in blocks. +> +> - Johan +> On Sat, May 19, 2018 at 5:12, Olaoluwa Osuntokun via bitcoin-dev < +> bitcoin-dev@lists.linuxfoundation.org> wrote: +> +> On Thu, May 17, 2018 at 2:44 PM Jim Posen via bitcoin-dev <bitcoin- +> +>> Monitoring inputs by scriptPubkey vs input-txid also has a massive +>>> advantage for parallel filtering: You can usually known your pubkeys +>>> well in advance, but if you have to change what you're watching block +>>> N+1 for based on the txids that paid you in N you can't filter them +>>> in parallel. +>>> +>> +>> Yes, I'll grant that this is a benefit of your suggestion. +>> +> +> Yeah parallel filtering would be pretty nice. We've implemented a serial +> filtering for btcwallet [1] for the use-case of rescanning after a seed +> phrase import. Parallel filtering would help here, but also we don't yet +> take advantage of batch querying for the filters themselves. This would +> speed up the scanning by quite a bit. +> +> I really like the filtering model though, it really simplifies the code, +> and we can leverage identical logic for btcd (which has RPCs to fetch the +> filters) as well. +> +> [1]: +> https://github.com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180 +> +> _______________________________________________ bitcoin-dev mailing list +> bitcoin-dev@lists.linuxfoundation.org +> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev +> +> + +--0000000000000f1609056cc12d60 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr"><div>> What if instead of trying to decide up front whi= +ch subset of elements will</div><div>> be most useful to include in the = +filters, and the size tradeoff, we let the</div><div>> full-node decide = +which subsets of elements it serves filters for?</div><div><br></div><div>T= +his is already the case. The current "track" is to add new servic= +e bits</div><div>(while we're in the uncommitted phase) to introduce ne= +w fitler types. Light</div><div>clients can then filter out nodes before ev= +en connecting to them.</div><div><br></div><div>-- Laolu</div><div><br></di= +v><div class=3D"gmail_quote"><div dir=3D"ltr">On Mon, May 21, 2018 at 1:35 = +AM Johan Tor=C3=A5s Halseth <<a href=3D"mailto:johanth@gmail.com">johant= +h@gmail.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style= +=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><img cla= +ss=3D"m_-8850601494583743300cloudmagic-smart-beacon" src=3D"https://tr.clou= +dmagic.com/h/v6/emailtag/tag/2.0/1526891728/b33cfe15f93c4412b9d3504fec67269= +7/2/b53988f48cda345112c1586d420d31cf/076962fa5a1f7737d8541e3d8681273b/903bb= +174d9946b90a95b4da487a91d69/newton.gif" style=3D"border:0;width:10px;height= +:10px" width=3D"10" height=3D"10" align=3D"right"><div dir=3D"auto"><span>H= +i all,</span><div><span><br></span></div><div><span>Most light wallets will= + want to download the minimum amount of data required to operate, which mea= +ns they would ideally download the smallest possible filters containing the= + subset of elements they need.=C2=A0</span></div><div><span><br></span></di= +v><div><span>What if instead of trying to decide up front which subset of e= +lements will be most useful to include in the filters, and the size tradeof= +f, we let the full-node decide which subsets of elements it serves filters = +for?<br></span><span><br>For instance, a full node would advertise that it = +could serve filters for the subsets 110 (txid+script+outpoint), 100 (txid o= +nly), 011 (</span>script+outpoint) etc. A light client could then choose to= + download the minimal filter type covering its needs.=C2=A0</div><div><br><= +/div><div>The obvious benefit of this would be minimal bandwidth usage for = +the light client, but there are also some less obvious ones. We wouldn=E2= +=80=99t have to decide up front what each filter type should contain, only = +the possible elements a filter can contain (more can be added later without= + breaking existing clients). This, I think, would let the most served filte= +r types grow organically, with full-node implementations coming with sane d= +efaults for served filter types (maybe even all possible types as long as t= +he number of elements is small), letting their operator add/remove types at= + will.</div><div><br></div><div>The main disadvantage of this as I see it, = +is that there=E2=80=99s an exponential blowup in the number of possible fil= +ter types in the number of element types. However, this would let us start = +out small with only the elements we need, and in the worst case the node op= +erators just choose to serve the subsets corresponding to what now is calle= +d =E2=80=9Cregular=E2=80=9D + =E2=80=9Cextended=E2=80=9D filters anyway, re= +quiring no more resources.</div><div><br></div><div>This would also give us= + some data on what is the most widely used filter types, which could be use= +ful in making the decision on what should be part of filters to eventually = +commit to in blocks.</div></div><div dir=3D"auto"><div><br></div><div>- Joh= +an</div></div><div dir=3D"auto"><div><div id=3D"m_-8850601494583743300cm_re= +plymail_content_wrap"><div class=3D"m_-8850601494583743300cm_replymail_cont= +ent_1526889092_wrapper">On Sat, May 19, 2018 at 5:12, Olaoluwa Osuntokun vi= +a bitcoin-dev <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" = +target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br><= +/div></div></div></div><div dir=3D"auto"><div><div id=3D"m_-885060149458374= +3300cm_replymail_content_wrap"><div class=3D"m_-8850601494583743300cm_reply= +mail_content_1526889092_wrapper"><div id=3D"m_-8850601494583743300cm_replym= +ail_content_1526889092" style=3D"overflow:visible"><blockquote style=3D"mar= +gin:0;border-left:#d6d6d6 1px solid;padding-left:10px"><div dir=3D"ltr"><di= +v class=3D"gmail_quote"><div dir=3D"ltr">On Thu, May 17, 2018 at 2:44 PM Ji= +m Posen via bitcoin-dev <bitcoin- </div><blockquote class=3D"gmail_quote= +" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><= +div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><bloc= +kquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #cc= +c solid;padding-left:1ex">Monitoring inputs by scriptPubkey vs input-txid a= +lso has a massive<br> +advantage for parallel filtering: You can usually known your pubkeys<br> +well in advance, but if you have to change what you're watching block<b= +r> + N+1 for based on the txids that paid you in N you can't filter them<br= +> +in parallel.<br></blockquote><div><br></div></div></div></div><div dir=3D"l= +tr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div>Yes, I'l= +l grant that this is a benefit of your suggestion.</div></div></div></div><= +/blockquote><div><br></div><div>Yeah parallel filtering would be pretty nic= +e. We've implemented a serial filtering for btcwallet [1] for the use-c= +ase of rescanning after a seed phrase import. Parallel filtering would help= + here, but also we don't yet take advantage of batch querying for the f= +ilters themselves. This would speed up the scanning by quite a bit. </div><= +div><br></div><div>I really like the filtering model though, it really simp= +lifies the code, and we can leverage identical logic for btcd (which has RP= +Cs to fetch the filters) as well. </div><div><br></div><div>[1]: <a href=3D= +"https://github.com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180" = +target=3D"_blank">https://github.com/Roasbeef/btcwallet/blob/master/chain/n= +eutrino.go#L180</a> </div></div></div> +<br></blockquote></div></div></div></div></div><div dir=3D"auto"><div><div = +id=3D"m_-8850601494583743300cm_replymail_content_wrap"><div class=3D"m_-885= +0601494583743300cm_replymail_content_1526889092_wrapper"><div id=3D"m_-8850= +601494583743300cm_replymail_content_1526889092" style=3D"overflow:visible">= +<blockquote style=3D"margin:0;border-left:#d6d6d6 1px solid;padding-left:10= +px">_______________________________________________ +bitcoin-dev mailing list +<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">= +bitcoin-dev@lists.linuxfoundation.org</a> +<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = +target=3D"_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoi= +n-dev</a> +</blockquote></div></div></div></div></div></blockquote></div></div> + +--0000000000000f1609056cc12d60-- + |