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"
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
Precedence: list

--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>&gt; I believe (1) could be ski=
pped entirely - there is almost no reason why</div><div>&gt; you&#39;d not =
be able to filter for, eg, the set of output scripts in a</div><div>&gt; 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&#39;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&#39;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>&gt; (2) and (3) may want to be split out - many wall=
ets may wish to just find</div><div>&gt; transactions paying to them, as tr=
ansactions spending from their outputs</div><div>&gt; should generally be t=
hings they&#39;ve created.</div><div><br></div><div>FWIW, in the &quot;resc=
an after importing by seed phrase&quot; 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>&gt; In general, I&#39;m concerned about t=
he size of the filters making existing SPV</div><div>&gt; clients less will=
ing to adopt BIP 158 instead of the existing bloom filter</div><div>&gt; ga=
rbage and would like to see a further exploration of ways to split out</div=
><div>&gt; 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 &quot;popular&quot=
; BIP 37 wallets I&#39;m aware of</div><div>(Breadwallet, and Andreas Schil=
dbach&#39;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 &quot;pivot=
ed&quot;</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&#39;t think they&#39;d adopt the protocol.</div><div><br></div><div>&g=
t; Some further ideas we should probably play with before finalizing moving=
</div><div>&gt; forward is providing filters for certain script templates, =
eg being able to</div><div>&gt; 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&#39=
;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 &quot;query</div><div>time&quot;, but then this counters the benefit of=
 simply slinging the filters</div><div>from disk (or a memory map or w/e). =
IMO, it&#39;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&#39;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 &lt;<a href=3D"mai=
lto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundatio=
n.org</a>&gt; 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 &quot;basic&quot; 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&#39;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&#39;ve created.<br>
<br>
In general, I&#39;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--