MIME-Version: 1.0
References: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
	<CAO3Pvs-nNQR_53_wjS4rPU8W20kePnrSdBvCXMwpaOG7gpUNJQ@mail.gmail.com>
In-Reply-To: <CAO3Pvs-nNQR_53_wjS4rPU8W20kePnrSdBvCXMwpaOG7gpUNJQ@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Fri, 09 Jun 2017 03:59:17 +0000
Message-ID: <CAO3Pvs8-GAwUNZ9Fc7DAb9ZCwP4p5Wh0sD1O0n5NSLVcY2nJtg@mail.gmail.com>
To: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev
	<bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="089e0822ef74eabbc705517efe44"
Subject: Re: [bitcoin-dev] BIP Proposal: Compact Client Side Filtering for
	Light Clients
Precedence: list

--089e0822ef74eabbc705517efe44
Content-Type: text/plain; charset="UTF-8"

Hi y'all,

Thanks for all the comments so far!

I've pushed a series of updates to the text of the BIP repo linked in the
OP.
The fixes include: typos, components of the specification which were
incorrect
(N is the total number of items, NOT the number of txns in the block), and a
few sections have been clarified.

The latest version also includes a set of test vectors (as CSV files), which
for a series of fp rates (1/2 to 1/2^32) includes (for 6 testnet blocks,
one of
which generates a "null" filter):

   * The block height
   * The block hash
   * The raw block itself
   * The previous basic+extended filter header
   * The basic+extended filter header for the block
   * The basic+extended filter for the block

The size of the test vectors was too large to include in-line within the
document, so we put them temporarily in a distinct folder [1]. The code
used to
generate the test vectors has also been included.

-- Laolu

[1]: https://github.com/Roasbeef/bips/tree/master/gcs_light_client


On Thu, Jun 1, 2017 at 9:49 PM Olaoluwa Osuntokun <laolu32@gmail.com> wrote:

> > In order to consider the average+median filter sizes in a world worth
> larger
> > blocks, I also ran the index for testnet:
> >
> >     * total size:  2753238530
> >     * total avg:  5918.95736054141
> >     * total median:  60202
> >     * total max:  74983
> >     * regular size:  1165148878
> >     * regular avg:  2504.856172982827
> >     * regular median:  24812
> >     * regular max:  64554
> >     * extended size:  1588089652
> >     * extended avg:  3414.1011875585823
> >     * extended median:  35260
> >     * extended max:  41731
> >
>
> Oops, realized I made a mistake. These are the stats for Feb 2016 until
> about a
> month ago (since height 400k iirc).
>
> -- Laolu
>
>
> On Thu, Jun 1, 2017 at 12:01 PM Olaoluwa Osuntokun <laolu32@gmail.com>
> wrote:
>
>> Hi y'all,
>>
>> Alex Akselrod and I would like to propose a new light client BIP for
>> consideration:
>>    *
>> https://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki
>>
>> This BIP proposal describes a concrete specification (along with a
>> reference implementations[1][2][3]) for the much discussed client-side
>> filtering reversal of BIP-37. The precise details are described in the
>> BIP, but as a summary: we've implemented a new light-client mode that uses
>> client-side filtering based off of Golomb-Rice coded sets. Full-nodes
>> maintain an additional index of the chain, and serve this compact filter
>> (the index) to light clients which request them. Light clients then fetch
>> these filters, query the locally and _maybe_ fetch the block if a relevant
>> item matches. The cool part is that blocks can be fetched from _any_
>> source, once the light client deems it necessary. Our primary motivation
>> for this work was enabling a light client mode for lnd[4] in order to
>> support a more light-weight back end paving the way for the usage of
>> Lightning on mobile phones and other devices. We've integrated neutrino
>> as a back end for lnd, and will be making the updated code public very
>> soon.
>>
>> One specific area we'd like feedback on is the parameter selection. Unlike
>> BIP-37 which allows clients to dynamically tune their false positive rate,
>> our proposal uses a _fixed_ false-positive. Within the document, it's
>> currently specified as P = 1/2^20. We've done a bit of analysis and
>> optimization attempting to optimize the following sum:
>> filter_download_bandwidth + expected_block_false_positive_bandwidth. Alex
>> has made a JS calculator that allows y'all to explore the affect of
>> tweaking the false positive rate in addition to the following variables:
>> the number of items the wallet is scanning for, the size of the blocks,
>> number of blocks fetched, and the size of the filters themselves. The
>> calculator calculates the expected bandwidth utilization using the CDF of
>> the Geometric Distribution. The calculator can be found here:
>> https://aakselrod.github.io/gcs_calc.html. Alex also has an empirical
>> script he's been running on actual data, and the results seem to match up
>> rather nicely.
>>
>> We we're excited to see that Karl Johan Alm (kallewoof) has done some
>> (rather extensive!) analysis of his own, focusing on a distinct encoding
>> type [5]. I haven't had the time yet to dig into his report yet, but I
>> think I've read enough to extract the key difference in our encodings: his
>> filters use a binomial encoding _directly_ on the filter contents, will we
>> instead create a Golomb-Coded set with the contents being _hashes_ (we use
>> siphash) of the filter items.
>>
>> Using a fixed fp=20, I have some stats detailing the total index size, as
>> well as averages for both mainnet and testnet. For mainnet, using the
>> filter contents as currently described in the BIP (basic + extended), the
>> total size of the index comes out to 6.9GB. The break down is as follows:
>>
>>     * total size:  6976047156
>>     * total avg:  14997.220622758816
>>     * total median:  3801
>>     * total max:  79155
>>     * regular size:  3117183743
>>     * regular avg:  6701.372750217131
>>     * regular median:  1734
>>     * regular max:  67533
>>     * extended size:  3858863413 <(385)%20886-3413>
>>     * extended avg:  8295.847872541684
>>     * extended median:  2041
>>     * extended max:  52508
>>
>> In order to consider the average+median filter sizes in a world worth
>> larger blocks, I also ran the index for testnet:
>>
>>     * total size:  2753238530
>>     * total avg:  5918.95736054141
>>     * total median:  60202
>>     * total max:  74983
>>     * regular size:  1165148878
>>     * regular avg:  2504.856172982827
>>     * regular median:  24812
>>     * regular max:  64554
>>     * extended size:  1588089652
>>     * extended avg:  3414.1011875585823
>>     * extended median:  35260
>>     * extended max:  41731
>>
>> Finally, here are the testnet stats which take into account the increase
>> in the maximum filter size due to segwit's block-size increase. The max
>> filter sizes are a bit larger due to some of the habitual blocks I
>> created last year when testing segwit (transactions with 30k inputs, 30k
>> outputs, etc).
>>
>>      * total size:  585087597
>>      * total avg:  520.8839608674402
>>      * total median:  20
>>      * total max:  164598
>>      * regular size:  299325029
>>      * regular avg:  266.4790836307566
>>      * regular median:  13
>>      * regular max:  164583
>>      * extended size:  285762568
>>      * extended avg:  254.4048772366836
>>      * extended median:  7
>>      * extended max:  127631
>>
>> For those that are interested in the raw data, I've uploaded a CSV file
>> of raw data for each block (mainnet + testnet), which can be found here:
>>      * mainnet: (14MB):
>> https://www.dropbox.com/s/4yk2u8dj06njbuv/mainnet-gcs-stats.csv?dl=0
>>      * testnet: (25MB):
>> https://www.dropbox.com/s/w7dmmcbocnmjfbo/gcs-stats-testnet.csv?dl=0
>>
>>
>> We look forward to getting feedback from all of y'all!
>>
>> -- Laolu
>>
>>
>> [1]: https://github.com/lightninglabs/neutrino
>> [2]: https://github.com/Roasbeef/btcd/tree/segwit-cbf
>> [3]: https://github.com/Roasbeef/btcutil/tree/gcs/gcs
>> [4]: https://github.com/lightningnetwork/lnd/
>>
>> -- Laolu
>>
>>

--089e0822ef74eabbc705517efe44
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><div>Hi y&#39;all,=C2=A0</div><div><br></div><div>Tha=
nks for all the comments so far!</div><div><br></div><div>I&#39;ve pushed a=
 series of updates to the text of the BIP repo linked in the OP.</div><div>=
The fixes include: typos, components of the specification which were incorr=
ect</div><div>(N is the total number of items, NOT the number of txns in th=
e block), and a</div><div>few sections have been clarified.</div><div><br><=
/div><div>The latest version also includes a set of test vectors (as CSV fi=
les), which</div><div>for a series of fp rates (1/2 to 1/2^32) includes (fo=
r 6 testnet blocks, one of</div><div>which generates a &quot;null&quot; fil=
ter):=C2=A0</div><div><br></div><div>=C2=A0 =C2=A0* The block height</div><=
div>=C2=A0 =C2=A0* The block hash</div><div>=C2=A0 =C2=A0* The raw block it=
self</div><div>=C2=A0 =C2=A0* The previous basic+extended filter header=C2=
=A0</div><div>=C2=A0 =C2=A0* The basic+extended filter header for the block=
</div><div>=C2=A0 =C2=A0* The basic+extended filter for the block</div><div=
><br></div><div>The size of the test vectors was too large to include in-li=
ne within the</div><div>document, so we put them temporarily in a distinct =
folder [1]. The code used to</div><div>generate the test vectors has also b=
een included.</div><div><br></div><div>-- Laolu</div><div><br></div><div>[1=
]: <a href=3D"https://github.com/Roasbeef/bips/tree/master/gcs_light_client=
">https://github.com/Roasbeef/bips/tree/master/gcs_light_client</a></div><d=
iv><br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu, Jun 1,=
 2017 at 9:49 PM Olaoluwa Osuntokun &lt;<a href=3D"mailto:laolu32@gmail.com=
">laolu32@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">=
<div dir=3D"ltr"><div>&gt; In order to consider the average+median filter s=
izes in a world worth larger</div><div>&gt; blocks, I also ran the index fo=
r testnet:</div><div>&gt;=C2=A0</div><div>&gt; =C2=A0 =C2=A0 * total size: =
=C2=A02753238530</div><div>&gt; =C2=A0 =C2=A0 * total avg: =C2=A05918.95736=
054141</div><div>&gt; =C2=A0 =C2=A0 * total median: =C2=A060202</div><div>&=
gt; =C2=A0 =C2=A0 * total max: =C2=A074983</div><div>&gt; =C2=A0 =C2=A0 * r=
egular size: =C2=A01165148878</div><div>&gt; =C2=A0 =C2=A0 * regular avg: =
=C2=A02504.856172982827</div><div>&gt; =C2=A0 =C2=A0 * regular median: =C2=
=A024812</div><div>&gt; =C2=A0 =C2=A0 * regular max: =C2=A064554</div><div>=
&gt; =C2=A0 =C2=A0 * extended size: =C2=A01588089652</div><div>&gt; =C2=A0 =
=C2=A0 * extended avg: =C2=A03414.1011875585823</div><div>&gt; =C2=A0 =C2=
=A0 * extended median: =C2=A035260</div><div>&gt; =C2=A0 =C2=A0 * extended =
max: =C2=A041731</div><div>&gt;=C2=A0</div><div><br></div></div><div dir=3D=
"ltr"><div>Oops, realized I made a mistake. These are the stats for Feb 201=
6 until about a</div><div>month ago (since height 400k iirc).</div><div><br=
></div><div>-- Laolu</div></div><div dir=3D"ltr"><div><br></div><br><div cl=
ass=3D"gmail_quote"><div dir=3D"ltr">On Thu, Jun 1, 2017 at 12:01 PM Olaolu=
wa Osuntokun &lt;<a href=3D"mailto:laolu32@gmail.com" target=3D"_blank">lao=
lu32@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" st=
yle=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div =
dir=3D"ltr"><div>Hi y&#39;all,=C2=A0</div><div><br></div><div>Alex Akselrod=
 and I would like to propose a new light client BIP for</div><div>considera=
tion:=C2=A0</div><div>=C2=A0 =C2=A0* <a href=3D"https://github.com/Roasbeef=
/bips/blob/master/gcs_light_client.mediawiki" target=3D"_blank">https://git=
hub.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki</a></div><div>=
<br></div><div>This BIP proposal describes a concrete specification (along =
with a</div><div>reference implementations[1][2][3]) for the much discussed=
 client-side</div><div>filtering reversal of BIP-37. The precise details ar=
e described in the</div><div>BIP, but as a summary: we&#39;ve implemented a=
 new light-client mode that uses</div><div>client-side filtering based off =
of Golomb-Rice coded sets. Full-nodes</div><div>maintain an additional inde=
x of the chain, and serve this compact filter</div><div>(the index) to ligh=
t clients which request them. Light clients then fetch</div><div>these filt=
ers, query the locally and _maybe_ fetch the block if a relevant</div><div>=
item matches. The cool part is that blocks can be fetched from _any_</div><=
div>source, once the light client deems it necessary. Our primary motivatio=
n</div><div>for this work was enabling a light client mode for lnd[4] in or=
der to</div><div>support a more light-weight back end paving the way for th=
e usage of</div><div>Lightning on mobile phones and other devices. We&#39;v=
e integrated neutrino</div><div>as a back end for lnd, and will be making t=
he updated code public very</div><div>soon.</div><div><br></div><div>One sp=
ecific area we&#39;d like feedback on is the parameter selection. Unlike</d=
iv><div>BIP-37 which allows clients to dynamically tune their false positiv=
e rate,</div><div>our proposal uses a _fixed_ false-positive. Within the do=
cument, it&#39;s</div><div>currently specified as P =3D 1/2^20. We&#39;ve d=
one a bit of analysis and</div><div>optimization attempting to optimize the=
 following sum:</div><div>filter_download_bandwidth + expected_block_false_=
positive_bandwidth. Alex</div><div>has made a JS calculator that allows y&#=
39;all to explore the affect of</div><div>tweaking the false positive rate =
in addition to the following variables:</div><div>the number of items the w=
allet is scanning for, the size of the blocks,</div><div>number of blocks f=
etched, and the size of the filters themselves. The</div><div>calculator ca=
lculates the expected bandwidth utilization using the CDF of</div><div>the =
Geometric Distribution. The calculator can be found here:</div><div><a href=
=3D"https://aakselrod.github.io/gcs_calc.html" target=3D"_blank">https://aa=
kselrod.github.io/gcs_calc.html</a>. Alex also has an empirical</div><div>s=
cript he&#39;s been running on actual data, and the results seem to match u=
p</div><div>rather nicely.</div><div><br></div><div>We we&#39;re excited to=
 see that Karl Johan Alm (kallewoof) has done some</div><div>(rather extens=
ive!) analysis of his own, focusing on a distinct encoding</div><div>type [=
5]. I haven&#39;t had the time yet to dig into his report yet, but I</div><=
div>think I&#39;ve read enough to extract the key difference in our encodin=
gs: his</div><div>filters use a binomial encoding _directly_ on the filter =
contents, will we</div><div>instead create a Golomb-Coded set with the cont=
ents being _hashes_ (we use</div><div>siphash) of the filter items.</div><d=
iv><br></div><div>Using a fixed fp=3D20, I have some stats detailing the to=
tal index size, as</div><div>well as averages for both mainnet and testnet.=
 For mainnet, using the</div><div>filter contents as currently described in=
 the BIP (basic + extended), the</div><div>total size of the index comes ou=
t to 6.9GB. The break down is as follows:</div><div><br></div><div>=C2=A0 =
=C2=A0 * total size: =C2=A06976047156</div><div>=C2=A0 =C2=A0 * total avg: =
=C2=A014997.220622758816</div><div>=C2=A0 =C2=A0 * total median: =C2=A03801=
</div><div>=C2=A0 =C2=A0 * total max: =C2=A079155</div><div>=C2=A0 =C2=A0 *=
 regular size: =C2=A03117183743</div><div>=C2=A0 =C2=A0 * regular avg: =C2=
=A06701.372750217131</div><div>=C2=A0 =C2=A0 * regular median: =C2=A01734</=
div><div>=C2=A0 =C2=A0 * regular max: =C2=A067533</div><div>=C2=A0 =C2=A0 *=
 extended size: =C2=A0<a href=3D"tel:(385)%20886-3413" value=3D"+1385886341=
3" target=3D"_blank">3858863413</a></div><div>=C2=A0 =C2=A0 * extended avg:=
 =C2=A08295.847872541684</div><div>=C2=A0 =C2=A0 * extended median: =C2=A02=
041</div><div>=C2=A0 =C2=A0 * extended max: =C2=A052508</div><div><br></div=
><div>In order to consider the average+median filter sizes in a world worth=
</div><div>larger blocks, I also ran the index for testnet:=C2=A0</div><div=
><br></div><div>=C2=A0 =C2=A0 * total size: =C2=A02753238530</div><div>=C2=
=A0 =C2=A0 * total avg: =C2=A05918.95736054141</div><div>=C2=A0 =C2=A0 * to=
tal median: =C2=A060202</div><div>=C2=A0 =C2=A0 * total max: =C2=A074983</d=
iv><div>=C2=A0 =C2=A0 * regular size: =C2=A01165148878</div><div>=C2=A0 =C2=
=A0 * regular avg: =C2=A02504.856172982827</div><div>=C2=A0 =C2=A0 * regula=
r median: =C2=A024812</div><div>=C2=A0 =C2=A0 * regular max: =C2=A064554</d=
iv><div>=C2=A0 =C2=A0 * extended size: =C2=A01588089652</div><div>=C2=A0 =
=C2=A0 * extended avg: =C2=A03414.1011875585823</div><div>=C2=A0 =C2=A0 * e=
xtended median: =C2=A035260</div><div>=C2=A0 =C2=A0 * extended max: =C2=A04=
1731</div><div><br></div><div>Finally, here are the testnet stats which tak=
e into account the increase</div><div>in the maximum filter size due to seg=
wit&#39;s block-size increase. The max</div><div>filter sizes are a bit lar=
ger due to some of the habitual blocks I</div><div>created last year when t=
esting segwit (transactions with 30k inputs, 30k</div><div>outputs, etc).</=
div><div><br></div><div>=C2=A0 =C2=A0 =C2=A0* total size: =C2=A0585087597</=
div><div>=C2=A0 =C2=A0 =C2=A0* total avg: =C2=A0520.8839608674402</div><div=
>=C2=A0 =C2=A0 =C2=A0* total median: =C2=A020</div><div>=C2=A0 =C2=A0 =C2=
=A0* total max: =C2=A0164598</div><div>=C2=A0 =C2=A0 =C2=A0* regular size: =
=C2=A0299325029</div><div>=C2=A0 =C2=A0 =C2=A0* regular avg: =C2=A0266.4790=
836307566</div><div>=C2=A0 =C2=A0 =C2=A0* regular median: =C2=A013</div><di=
v>=C2=A0 =C2=A0 =C2=A0* regular max: =C2=A0164583</div><div>=C2=A0 =C2=A0 =
=C2=A0* extended size: =C2=A0285762568</div><div>=C2=A0 =C2=A0 =C2=A0* exte=
nded avg: =C2=A0254.4048772366836</div><div>=C2=A0 =C2=A0 =C2=A0* extended =
median: =C2=A07</div><div>=C2=A0 =C2=A0 =C2=A0* extended max: =C2=A0127631<=
/div><div><br></div><div>For those that are interested in the raw data, I&#=
39;ve uploaded a CSV file</div><div>of raw data for each block (mainnet + t=
estnet), which can be found here:</div><div>=C2=A0 =C2=A0 =C2=A0* mainnet: =
(14MB): <a href=3D"https://www.dropbox.com/s/4yk2u8dj06njbuv/mainnet-gcs-st=
ats.csv?dl=3D0" target=3D"_blank">https://www.dropbox.com/s/4yk2u8dj06njbuv=
/mainnet-gcs-stats.csv?dl=3D0</a></div><div>=C2=A0 =C2=A0 =C2=A0* testnet: =
(25MB): <a href=3D"https://www.dropbox.com/s/w7dmmcbocnmjfbo/gcs-stats-test=
net.csv?dl=3D0" target=3D"_blank">https://www.dropbox.com/s/w7dmmcbocnmjfbo=
/gcs-stats-testnet.csv?dl=3D0</a></div><div><br></div><div><br></div><div>W=
e look forward to getting feedback from all of y&#39;all!</div><div><br></d=
iv><div>-- Laolu</div><div><br></div><div><br></div><div>[1]: <a href=3D"ht=
tps://github.com/lightninglabs/neutrino" target=3D"_blank">https://github.c=
om/lightninglabs/neutrino</a></div><div>[2]: <a href=3D"https://github.com/=
Roasbeef/btcd/tree/segwit-cbf" target=3D"_blank">https://github.com/Roasbee=
f/btcd/tree/segwit-cbf</a></div><div>[3]: <a href=3D"https://github.com/Roa=
sbeef/btcutil/tree/gcs/gcs" target=3D"_blank">https://github.com/Roasbeef/b=
tcutil/tree/gcs/gcs</a></div><div>[4]: <a href=3D"https://github.com/lightn=
ingnetwork/lnd/" target=3D"_blank">https://github.com/lightningnetwork/lnd/=
</a></div><div><br></div><div>-- Laolu</div><div><br></div></div></blockquo=
te></div></div></blockquote></div></div></div>

--089e0822ef74eabbc705517efe44--