Content-Type: multipart/alternative;
	boundary="----sinikael-?=_1-15268917468760.3363917884416878"
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
To: Olaoluwa Osuntokun <laolu32@gmail.com>
In-Reply-To: <CAO3Pvs9K3n=OzVQ06XGQvzNC+Aqp9S60kWM9VRPA8hWTJ3u9BQ@mail.gmail.com>
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>
Message-Id: <c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com>
Date: Mon, 21 May 2018 10:35:28 +0200
MIME-Version: 1.0
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
Precedence: list

------sinikael-?=_1-15268917468760.3363917884416878
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

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 will =
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?

For instance, a full node would advertise that it could serve filters for =
the subsets 110 (txid+script+outpoint), 100 (txid only), 011 ( =
script+outpoint) 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 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 filter types grow organically, with full-node =
implementations coming with sane defaults 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 exponential 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 part =
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 [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
------sinikael-?=_1-15268917468760.3363917884416878
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

<img class=3D"cloudmagic-smart-beacon" src=3D"https://tr.cloudmagic.=
com/h/v6/emailtag/tag/2.0/1526891728/b33cfe15f93c4412b9d3504fec672697/2/b53=
988f48cda345112c1586d420d31cf/076962fa5a1f7737d8541e3d8681273b/0f75828a92f1=
cf543e26ab700e98c693/newton.gif" style=3D"border:0; width:10px; =
height:10px;" width=3D"10" height=3D"10" align=3D"right"><div =
dir=3D"auto"><span>Hi all,</span><div><span><br></span></div><div><span>Mos=
t 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.=
&nbsp;</span></div><div><span><br></span></div><div><span>What if instead =
of trying to decide up front which subset of elements will 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?=
<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 =
only), 011 (</span>script+outpoint) etc. A light client could then choose =
to download the minimal filter type covering its needs.=
&nbsp;</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 filter types grow organically, with full-node =
implementations coming with sane defaults 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.</div><div><br></div><div>T=
he main disadvantage of this as I see it, is that there=E2=80=99s an =
exponential 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.</div><div><br></div><div>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 part of filters to =
eventually commit to in blocks.</div><div><br></div><div>- =
Johan</div><div><div id=3D"cm_replymail_content_wrap"><div =
class=3D"cm_replymail_content_1526889092_wrapper">On Sat, May 19, 2018 at =
5:12, Olaoluwa Osuntokun via bitcoin-dev &lt;bitcoin-dev@lists.=
linuxfoundation.org&gt; wrote:<br><div id=3D"cm_replymail_content_152688909=
2" style=3D"overflow: visible;"><blockquote style=3D"margin:0;border-left: =
#D6D6D6 1px solid;padding-left: 10px;"><div dir=3D"ltr"><div =
class=3D"gmail_quote"><div dir=3D"ltr">On Thu, May 17, 2018 at 2:44 PM Jim =
Posen via bitcoin-dev &lt;bitcoin- </div><blockquote class=3D"gmail_quote" =
style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><di=
v dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><blockq=
uote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc =
solid;padding-left:1ex">Monitoring inputs by scriptPubkey vs input-txid =
also 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<br>
 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"ltr"><div class=3D"gmail_extra"><div =
class=3D"gmail_quote"><div>Yes, I'll grant that this is a benefit of your =
suggestion.</div></div></div></div></blockquote><div><br></div><div>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. </div><div><br></div><div>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. </div><div><br></div><div>[1]: <a href=3D"https://github.=
com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180">https://github.=
com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180</a> =
</div></div></div>
<br>_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
</blockquote></div></div></div></div></div>
------sinikael-?=_1-15268917468760.3363917884416878--