path: root/9e/44af31165e5ca77d424cb9f3e5953b56056f34

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 7472F2C
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  2 Jun 2017 04:49:29 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yw0-f178.google.com (mail-yw0-f178.google.com
	[209.85.161.178])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 6CD9213B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  2 Jun 2017 04:49:28 +0000 (UTC)
Received: by mail-yw0-f178.google.com with SMTP id b68so28705555ywe.3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 01 Jun 2017 21:49:28 -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=QEQvtY3q9rR76eMn2tDVxKiuwhmScobWAZrnjpdB434=;
	b=nkVaX4kQ2JCfedD/GWmHXzM+y0CFRejqRKewbRxDYWTyd900r9A8wlwuCuPW6LrTB5
	LRIjw5nq6iYt212xfMU0H0ArFt6sX1gbIwZkdVXAUpfJ1GATlPpCEAluRFUL7RNgGSpl
	755ONuAqRHR9j/cSJtlQjVzKVvQ2LBga87SlQDZz76sRaDKeP3ANN/DDVC5CEdPkCOj8
	6/1zZ4Gqc91NfHBJs4ixS7UWhS+UnofcYxO496WujPu4zxxELdEDpFuHzOYqx5XxfKwW
	jJ9G+lki4meu7yc7eWhHyM7HBwB/bixGT/v9q4mDbB01VN0885R4/g4t1c1f+cWgfbsQ
	Wscg==
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=QEQvtY3q9rR76eMn2tDVxKiuwhmScobWAZrnjpdB434=;
	b=iGeHQhn6hM98org5lFR5N2akcmUO0zJwbyGpwjohFJANtbkQxdj+TK2NgKWLPevIpr
	1ACx43EbkMT9GmhCks+zCi+XrhNAIIMpXFOxmMxf2xonsvjOE2QB9RK2AQEpj5u4CVYQ
	eLXL9BZKWgL+Z9uahwETvlIH+oPZZNVcOQWPIP93w7bk1pAjSRv3ITe4HKROTVOmB3nT
	1c+tZ3WeUc32YWKY8Yj++A0AA6llNVg7mGU2DDGggiwCDaINCuk0/eVLL/Xwg5DX0XSB
	FGWhc4dZByKV3AbS+2G2z+QxlU662+AOshJB+yysCyG0bmnUsMaqeIL+DtnJvpMR+K8r
	RgWQ==
X-Gm-Message-State: AODbwcCgl/LVP9QOqzqUE/lVym+c7XU+/SZ27YDvXFxub+jNKn68+YbK
	kWqA5sXqEe2qCwWxaDyimZkj9FGI1ge+
X-Received: by 10.129.88.84 with SMTP id m81mr4319648ywb.22.1496378967406;
	Thu, 01 Jun 2017 21:49:27 -0700 (PDT)
MIME-Version: 1.0
References: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
In-Reply-To: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Fri, 02 Jun 2017 04:49:16 +0000
Message-ID: <CAO3Pvs-nNQR_53_wjS4rPU8W20kePnrSdBvCXMwpaOG7gpUNJQ@mail.gmail.com>
To: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev
	<bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="001a11492ff2cd5d460550f2e089"
X-Spam-Status: No, score=-1.2 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,
	RCVD_IN_SORBS_SPAM 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 Proposal: Compact Client Side Filtering for
	Light Clients
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: Fri, 02 Jun 2017 04:49:29 -0000

--001a11492ff2cd5d460550f2e089
Content-Type: text/plain; charset="UTF-8"

> 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
>
>

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

<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>Oops, realiz=
ed I made a mistake. These are the stats for Feb 2016 until about a</div><d=
iv>month ago (since height 400k iirc).</div><div><br></div><div>-- Laolu</d=
iv><div><br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu, J=
un 1, 2017 at 12:01 PM Olaoluwa Osuntokun &lt;<a href=3D"mailto:laolu32@gma=
il.com">laolu32@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmai=
l_quote" style=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>Al=
ex Akselrod and I would like to propose a new light client BIP for</div><di=
v>consideration:=C2=A0</div><div>=C2=A0 =C2=A0* <a href=3D"https://github.c=
om/Roasbeef/bips/blob/master/gcs_light_client.mediawiki" target=3D"_blank">=
https://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki</a>=
</div><div><br></div><div>This BIP proposal describes a concrete specificat=
ion (along with a</div><div>reference implementations[1][2][3]) for the muc=
h discussed client-side</div><div>filtering reversal of BIP-37. The precise=
 details are described in the</div><div>BIP, but as a summary: we&#39;ve im=
plemented 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 addi=
tional index of the chain, and serve this compact filter</div><div>(the ind=
ex) to light clients which request them. Light clients then fetch</div><div=
>these filters, 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 primar=
y motivation</div><div>for this work was enabling a light client mode for l=
nd[4] in order to</div><div>support a more light-weight back end paving the=
 way for the usage of</div><div>Lightning on mobile phones and other device=
s. We&#39;ve integrated neutrino</div><div>as a back end for lnd, and will =
be making the updated code public very</div><div>soon.</div><div><br></div>=
<div>One specific area we&#39;d like feedback on is the parameter selection=
. Unlike</div><div>BIP-37 which allows clients to dynamically tune their fa=
lse positive rate,</div><div>our proposal uses a _fixed_ false-positive. Wi=
thin the document, it&#39;s</div><div>currently specified as P =3D 1/2^20. =
We&#39;ve done a bit of analysis and</div><div>optimization attempting to o=
ptimize the following sum:</div><div>filter_download_bandwidth + expected_b=
lock_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 pos=
itive rate in addition to the following variables:</div><div>the number of =
items the wallet is scanning for, the size of the blocks,</div><div>number =
of blocks fetched, and the size of the filters themselves. The</div><div>ca=
lculator calculates the expected bandwidth utilization using the CDF of</di=
v><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://aakselrod.github.io/gcs_calc.html</a>. Alex also has an empirical<=
/div><div>script he&#39;s been running on actual data, and the results seem=
 to match up</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>(ra=
ther extensive!) 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, b=
ut I</div><div>think I&#39;ve read enough to extract the key difference in =
our encodings: his</div><div>filters use a binomial encoding _directly_ on =
the filter contents, will we</div><div>instead create a Golomb-Coded set wi=
th the contents being _hashes_ (we use</div><div>siphash) of the filter ite=
ms.</div><div><br></div><div>Using a fixed fp=3D20, I have some stats detai=
ling the total index size, as</div><div>well as averages for both mainnet a=
nd testnet. For mainnet, using the</div><div>filter contents as currently d=
escribed in the BIP (basic + extended), the</div><div>total size of the ind=
ex comes out to 6.9GB. The break down is as follows:</div><div><br></div><d=
iv>=C2=A0 =C2=A0 * total size: =C2=A06976047156</div><div>=C2=A0 =C2=A0 * t=
otal 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 * regul=
ar 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=
"+13858863413" target=3D"_blank">3858863413</a></div><div>=C2=A0 =C2=A0 * e=
xtended avg: =C2=A08295.847872541684</div><div>=C2=A0 =C2=A0 * extended med=
ian: =C2=A02041</div><div>=C2=A0 =C2=A0 * extended max: =C2=A052508</div><d=
iv><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 * total median: =C2=A060202</div><div>=C2=A0 =C2=A0 * total max: =
=C2=A074983</div><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 * regular median: =C2=A024812</div><div>=C2=A0 =C2=A0 * regular max:=
 =C2=A064554</div><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 * extended median: =C2=A035260</div><div>=C2=A0 =C2=A0 * extende=
d max: =C2=A041731</div><div><br></div><div>Finally, here are the testnet s=
tats which take into account the increase</div><div>in the maximum filter s=
ize due to segwit&#39;s block-size increase. The max</div><div>filter sizes=
 are a bit larger due to some of the habitual blocks I</div><div>created la=
st year when testing segwit (transactions with 30k inputs, 30k</div><div>ou=
tputs, 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.883960867=
4402</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.4790836307566</div><div>=C2=A0 =C2=A0 =C2=A0* regular median: =C2=
=A013</div><div>=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* extended 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 m=
ax: =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 b=
lock (mainnet + testnet), which can be found here:</div><div>=C2=A0 =C2=A0 =
=C2=A0* mainnet: (14MB): <a href=3D"https://www.dropbox.com/s/4yk2u8dj06njb=
uv/mainnet-gcs-stats.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/w7dmmcbocnmjf=
bo/gcs-stats-testnet.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>We look forward to getting feedback from all of y&#39;all!<=
/div><div><br></div><div>-- Laolu</div><div><br></div><div><br></div><div>[=
1]: <a href=3D"https://github.com/lightninglabs/neutrino" target=3D"_blank"=
>https://github.com/lightninglabs/neutrino</a></div><div>[2]: <a href=3D"ht=
tps://github.com/Roasbeef/btcd/tree/segwit-cbf" target=3D"_blank">https://g=
ithub.com/Roasbeef/btcd/tree/segwit-cbf</a></div><div>[3]: <a href=3D"https=
://github.com/Roasbeef/btcutil/tree/gcs/gcs" target=3D"_blank">https://gith=
ub.com/Roasbeef/btcutil/tree/gcs/gcs</a></div><div>[4]: <a href=3D"https://=
github.com/lightningnetwork/lnd/" target=3D"_blank">https://github.com/ligh=
tningnetwork/lnd/</a></div><div><br></div><div>-- Laolu</div><div><br></div=
></div></blockquote></div></div>

--001a11492ff2cd5d460550f2e089--