path: root/46/7f865359cdfac8eb67843ff6a34db9ca614651

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 85DB4ACB
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu,  9 Nov 2017 23:44:22 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f51.google.com (mail-wm0-f51.google.com [74.125.82.51])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D95E0E3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu,  9 Nov 2017 23:44:20 +0000 (UTC)
Received: by mail-wm0-f51.google.com with SMTP id r68so20966335wmr.3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 09 Nov 2017 15:44:20 -0800 (PST)
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=z5LHpgu4hwG5bP5of4RhyYWDyj+LzZNQl2P8v0ezgQ8=;
	b=M03WqPhTjkrFkWmKc/KxKT6BiJUmfDtDwR1MgpDX01pRCPtsRJD6yX+PKh6xnqvugC
	2DoajgJt3egKuIfTgeuH2MP83sk2Ycfybyk0kK6R5dSzc2gfG+GvGX+cquXgDWWxh5nj
	lmccE7WzW4Zaa+9DAsVUqpIMtI71zNgywA44bRzDs5yZQ6UyA8VRq/8x4hC2SIr3kbNS
	/0KBs4oTKG54gDB39/iEjWaD7huYWPL+cvGy8sTlJtYKTr6s/RX+31rdGYIo/hEOo7Jg
	hmYmY9U6gEfubLpOGC9mrlFXdLFdyIogFDJt7qk8I/o+VAAPCg2NWU67RLGturIReqY8
	TE2w==
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=z5LHpgu4hwG5bP5of4RhyYWDyj+LzZNQl2P8v0ezgQ8=;
	b=TCYUeNOctU20i+GMw9TLKir/jciVxm26kQHm4JqVsL0iVDW5rSPR2rAUuVgp2OI3Y0
	2qROHfmp+QrQpJVvPQaW12Cz3Rpha81rhLTMMSrpdOO79dDbxavbc3BYENF77RP8CZGR
	0294XCWq5ijwi9CEQMihq6B+7fP+xrAJctFsG8fLgB3sr9jaNZPNRoTdNuajRzN8WVzN
	VieD2gcHhEmVRFIyGwVKmmpPUQeKzRCPwLozuoCgSJG8W5ffeqUlOWhaXVakQZJaNgE3
	TugLGKYhzvYTOxmZVA1BZovdm07p5wEzHK8G3nFr17gziVnxYsPwbWY9XhOIPZsBk2P7
	f7fw==
X-Gm-Message-State: AJaThX6KTqPBQUu2TOyIAMaxfsNL257hG0pgmcACDAgzWgNYSB4gjpbf
	x/zMzFy5YfVlZyeQh/OKVJXdntY60W1sEz8o03m0Ig==
X-Google-Smtp-Source: ABhQp+TbbPqstfSaKw5XMY9sP8nS+37bUeQmUeWbiVvYC0M/1qPHVbRl7fdCM4Zw03sB1j+56rLFlm/Ee8f/EuifuOU=
X-Received: by 10.80.147.93 with SMTP id n29mr168531eda.237.1510271059023;
	Thu, 09 Nov 2017 15:44:19 -0800 (PST)
MIME-Version: 1.0
References: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
	<CAO3Pvs-nNQR_53_wjS4rPU8W20kePnrSdBvCXMwpaOG7gpUNJQ@mail.gmail.com>
	<CAO3Pvs8-GAwUNZ9Fc7DAb9ZCwP4p5Wh0sD1O0n5NSLVcY2nJtg@mail.gmail.com>
In-Reply-To: <CAO3Pvs8-GAwUNZ9Fc7DAb9ZCwP4p5Wh0sD1O0n5NSLVcY2nJtg@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Thu, 09 Nov 2017 23:44:07 +0000
Message-ID: <CAO3Pvs8r_Ftha7RKUDtrVqd6SzqODH0PC5o8tUH1EH2UqMMecw@mail.gmail.com>
To: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev
	<bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="94eb2c1a8c0efcdd59055d9561a5"
X-Spam-Status: No, score=0.2 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,HTML_MESSAGE,
	RCVD_IN_DNSWL_NONE autolearn=disabled 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: Thu, 09 Nov 2017 23:44:22 -0000

--94eb2c1a8c0efcdd59055d9561a5
Content-Type: text/plain; charset="UTF-8"

Hi y'all,

Since my last email we've made a number of changes to the BIP. The changes
made
were driven by the feedback we've received so far in this thread, and also
as a
result of real-world testing using this new proposal as the basis for our
light
weight LN node which powers the demo Lightning desktop application we
recently
released.

A highlight of the changes made between this version and the last follows:

  * We've removed the modulus operation in the inner loop when constructing
    filters. This has been replaced with an alternative, more efficient
    mapping[1] as suggested by gmaxwell and sipa. In our implementation, we
    perform the operation in a piece-wise fashion by hand. Alternative
    implementations can take advantage of 128-bit arithmetic extensions on
    supporting CPU's.

  * The txid has been moved from the extended filter to the regular filter.
    During out testing of the new light client with our LN node
implementation,
    we found that we were able to reduce network traffic as we only need the
    extended filter for rare on-chain events.

  * We now use the 6th service bit. We realized that the bit we had chosen
    prior was already being used to signal support of x-thin block syncing.
To
    select this bit number, we ran a scanner on the addrman of our nodes and
    also the network to fin da bit that wasn't used widely.

  * An error in the BIP that didn't include the public key script of
coinbase
    transactions in the filter has been fixed.

  * An error in the BIP when constructing the initial "genesis" filter has
been
    fixed.

  * We no longer use the ProtocolVersion field in the getcfheaders message
or
    its response.

  * The specification of several newly defined messages were incorrect and
have
    been fixed.

  * A number of typos spotted by several reviewers have been fixed.

The full commit history of the BIP draft can be found here:
https://github.com/Roasbeef/bips/commits/gcs-bip-draft

At this point, we're ready to make a PR against the official BIP repo and to
request a number to be assigned to our proposal. Thanks to all those that
have
reviewed, and contributed to the proposal!

[1]:
https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

-- Laolu


On Thu, Jun 8, 2017 at 8:59 PM Olaoluwa Osuntokun <laolu32@gmail.com> wrote:

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

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

<div dir=3D"ltr"><div>Hi y&#39;all,=C2=A0</div><div><br></div><div>Since my=
 last email we&#39;ve made a number of changes to the BIP. The changes made=
</div><div>were driven by the feedback we&#39;ve received so far in this th=
read, and also as a</div><div>result of real-world testing using this new p=
roposal as the basis for our light</div><div>weight LN node which powers th=
e demo Lightning desktop application we recently</div><div>released.</div><=
div><br></div><div>A highlight of the changes made between this version and=
 the last follows:</div><div><br></div><div>=C2=A0 * We&#39;ve removed the =
modulus operation in the inner loop when constructing</div><div>=C2=A0 =C2=
=A0 filters. This has been replaced with an alternative, more efficient</di=
v><div>=C2=A0 =C2=A0 mapping[1] as suggested by gmaxwell and sipa. In our i=
mplementation, we</div><div>=C2=A0 =C2=A0 perform the operation in a piece-=
wise fashion by hand. Alternative</div><div>=C2=A0 =C2=A0 implementations c=
an take advantage of 128-bit arithmetic extensions on</div><div>=C2=A0 =C2=
=A0 supporting CPU&#39;s.</div><div>=C2=A0</div><div>=C2=A0 * The txid has =
been moved from the extended filter to the regular filter.</div><div>=C2=A0=
 =C2=A0 During out testing of the new light client with our LN node impleme=
ntation,</div><div>=C2=A0 =C2=A0 we found that we were able to reduce netwo=
rk traffic as we only need the</div><div>=C2=A0 =C2=A0 extended filter for =
rare on-chain events.</div><div><br></div><div>=C2=A0 * We now use the 6th =
service bit. We realized that the bit we had chosen</div><div>=C2=A0 =C2=A0=
 prior was already being used to signal support of x-thin block syncing. To=
</div><div>=C2=A0 =C2=A0 select this bit number, we ran a scanner on the ad=
drman of our nodes and</div><div>=C2=A0 =C2=A0 also the network to fin da b=
it that wasn&#39;t used widely.</div><div>=C2=A0=C2=A0</div><div>=C2=A0 * A=
n error in the BIP that didn&#39;t include the public key script of coinbas=
e</div><div>=C2=A0 =C2=A0 transactions in the filter has been fixed.</div><=
div><br></div><div>=C2=A0 * An error in the BIP when constructing the initi=
al &quot;genesis&quot; filter has been</div><div>=C2=A0 =C2=A0 fixed.</div>=
<div><br></div><div>=C2=A0 * We no longer use the ProtocolVersion field in =
the getcfheaders message or</div><div>=C2=A0 =C2=A0 its response.=C2=A0</di=
v><div><br></div><div>=C2=A0 * The specification of several newly defined m=
essages were incorrect and have</div><div>=C2=A0 =C2=A0 been fixed.</div><d=
iv><br></div><div>=C2=A0 * A number of typos spotted by several reviewers h=
ave been fixed.</div><div><br></div><div>The full commit history of the BIP=
 draft can be found here:</div><div><a href=3D"https://github.com/Roasbeef/=
bips/commits/gcs-bip-draft">https://github.com/Roasbeef/bips/commits/gcs-bi=
p-draft</a></div><div><br></div><div>At this point, we&#39;re ready to make=
 a PR against the official BIP repo and to</div><div>request a number to be=
 assigned to our proposal. Thanks to all those that have</div><div>reviewed=
, and contributed to the proposal!</div><div><br></div><div>[1]: <a href=3D=
"https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reducti=
on/">https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-red=
uction/</a></div><div><br></div><div>-- Laolu</div><div><br></div><br><div =
class=3D"gmail_quote"><div dir=3D"ltr">On Thu, Jun 8, 2017 at 8:59 PM Olaol=
uwa Osuntokun &lt;<a href=3D"mailto:laolu32@gmail.com">laolu32@gmail.com</a=
>&gt; wrote:<br></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>=
<div>Hi y&#39;all,=C2=A0</div><div><br></div><div>Thanks for all the commen=
ts 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: typ=
os, components of the specification which were incorrect</div><div>(N is th=
e total number of items, NOT the number of txns in the block), and a</div><=
div>few sections have been clarified.</div><div><br></div><div>The latest v=
ersion also includes a set of test vectors (as CSV files), which</div><div>=
for a series of fp rates (1/2 to 1/2^32) includes (for 6 testnet blocks, on=
e of</div><div>which generates a &quot;null&quot; filter):=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 itself</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 s=
ize of the test vectors was too large to include in-line within the</div><d=
iv>document, so we put them temporarily in a distinct folder [1]. The code =
used to</div><div>generate the test vectors has also been included.</div><d=
iv><br></div><div>-- Laolu</div><div><br></div><div>[1]: <a href=3D"https:/=
/github.com/Roasbeef/bips/tree/master/gcs_light_client" target=3D"_blank">h=
ttps://github.com/Roasbeef/bips/tree/master/gcs_light_client</a></div></div=
></div><div dir=3D"ltr"><div><div><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 h=
ref=3D"mailto:laolu32@gmail.com" target=3D"_blank">laolu32@gmail.com</a>&gt=
; wrote:<br></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>&gt;=
 In order to consider the average+median filter sizes in a world worth larg=
er</div><div>&gt; blocks, I also ran the index for testnet:</div><div>&gt;=
=C2=A0</div><div>&gt; =C2=A0 =C2=A0 * total size: =C2=A02753238530</div><di=
v>&gt; =C2=A0 =C2=A0 * total avg: =C2=A05918.95736054141</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 * regular size: =C2=A0116514=
8878</div><div>&gt; =C2=A0 =C2=A0 * regular avg: =C2=A02504.856172982827</d=
iv><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 * extend=
ed 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 2016 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 class=3D"gmail_quote"><div d=
ir=3D"ltr">On Thu, Jun 1, 2017 at 12:01 PM Olaoluwa Osuntokun &lt;<a href=
=3D"mailto:laolu32@gmail.com" target=3D"_blank">laolu32@gmail.com</a>&gt; w=
rote:<br></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>Hi y&#3=
9;all,=C2=A0</div><div><br></div><div>Alex Akselrod and I would like to pro=
pose a new light client BIP for</div><div>consideration:=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://github.com/Roasbeef/bips/=
blob/master/gcs_light_client.mediawiki</a></div><div><br></div><div>This BI=
P proposal describes a concrete specification (along with a</div><div>refer=
ence implementations[1][2][3]) for the much discussed client-side</div><div=
>filtering reversal of BIP-37. The precise details are described in the</di=
v><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 s=
ets. Full-nodes</div><div>maintain an additional index of the chain, and se=
rve this compact filter</div><div>(the index) to light clients which reques=
t 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 l=
ight client deems it necessary. Our primary motivation</div><div>for this w=
ork was enabling a light client mode for lnd[4] in order to</div><div>suppo=
rt a more light-weight back end paving the way for the usage of</div><div>L=
ightning on mobile phones and other devices. 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 l=
ike feedback on is the parameter selection. Unlike</div><div>BIP-37 which a=
llows clients to dynamically tune their false positive rate,</div><div>our =
proposal uses a _fixed_ false-positive. Within 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 optimize the following sum:</div><=
div>filter_download_bandwidth + expected_block_false_positive_bandwidth. Al=
ex</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 fol=
lowing 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 o=
f the filters themselves. The</div><div>calculator calculates 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://aakselrod.github.io/gcs_=
calc.html</a>. Alex also has an empirical</div><div>script he&#39;s been ru=
nning on actual data, and the results seem to match up</div><div>rather nic=
ely.</div><div><br></div><div>We we&#39;re excited to see that Karl Johan A=
lm (kallewoof) has done some</div><div>(rather 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, but I</div><div>think I&#39;ve rea=
d enough to extract the key difference in our encodings: his</div><div>filt=
ers use a binomial encoding _directly_ on the filter contents, will we</div=
><div>instead create a Golomb-Coded set with the contents being _hashes_ (w=
e use</div><div>siphash) of the filter items.</div><div><br></div><div>Usin=
g a fixed fp=3D20, I have some stats detailing the total index size, as</di=
v><div>well as averages for both mainnet and testnet. For mainnet, using th=
e</div><div>filter contents as currently described in the BIP (basic + exte=
nded), the</div><div>total size of the index comes out 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.220622758=
816</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=A0=
3117183743</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"+13858863413" target=3D"_blank">3=
858863413</a></div><div>=C2=A0 =C2=A0 * extended avg: =C2=A08295.8478725416=
84</div><div>=C2=A0 =C2=A0 * extended median: =C2=A02041</div><div>=C2=A0 =
=C2=A0 * extended max: =C2=A052508</div><div><br></div><div>In order to con=
sider the average+median filter sizes in a world worth</div><div>larger blo=
cks, 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 a=
vg: =C2=A05918.95736054141</div><div>=C2=A0 =C2=A0 * total median: =C2=A060=
202</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=A024=
812</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 av=
g: =C2=A03414.1011875585823</div><div>=C2=A0 =C2=A0 * extended median: =C2=
=A035260</div><div>=C2=A0 =C2=A0 * extended max: =C2=A041731</div><div><br>=
</div><div>Finally, here are the testnet stats which take into account the =
increase</div><div>in the maximum filter size due to segwit&#39;s block-siz=
e increase. The max</div><div>filter sizes are a bit larger due to some of =
the habitual blocks I</div><div>created last year when testing segwit (tran=
sactions 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</di=
v><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 siz=
e: =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 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 + testnet), which can b=
e found here:</div><div>=C2=A0 =C2=A0 =C2=A0* mainnet: (14MB): <a href=3D"h=
ttps://www.dropbox.com/s/4yk2u8dj06njbuv/mainnet-gcs-stats.csv?dl=3D0" targ=
et=3D"_blank">https://www.dropbox.com/s/4yk2u8dj06njbuv/mainnet-gcs-stats.c=
sv?dl=3D0</a></div><div>=C2=A0 =C2=A0 =C2=A0* testnet: (25MB): <a href=3D"h=
ttps://www.dropbox.com/s/w7dmmcbocnmjfbo/gcs-stats-testnet.csv?dl=3D0" targ=
et=3D"_blank">https://www.dropbox.com/s/w7dmmcbocnmjfbo/gcs-stats-testnet.c=
sv?dl=3D0</a></div><div><br></div><div><br></div><div>We look forward to ge=
tting feedback from all of y&#39;all!</div><div><br></div><div>-- Laolu</di=
v><div><br></div><div><br></div><div>[1]: <a href=3D"https://github.com/lig=
htninglabs/neutrino" target=3D"_blank">https://github.com/lightninglabs/neu=
trino</a></div><div>[2]: <a href=3D"https://github.com/Roasbeef/btcd/tree/s=
egwit-cbf" target=3D"_blank">https://github.com/Roasbeef/btcd/tree/segwit-c=
bf</a></div><div>[3]: <a href=3D"https://github.com/Roasbeef/btcutil/tree/g=
cs/gcs" target=3D"_blank">https://github.com/Roasbeef/btcutil/tree/gcs/gcs<=
/a></div><div>[4]: <a href=3D"https://github.com/lightningnetwork/lnd/" tar=
get=3D"_blank">https://github.com/lightningnetwork/lnd/</a></div><div><br><=
/div><div>-- Laolu</div><div><br></div></div></blockquote></div></div></blo=
ckquote></div></div></div></blockquote></div></div>

--94eb2c1a8c0efcdd59055d9561a5--