Thanks for sending this proposal! I look forward to having a great discussion around this.<div><br></div><div>- Eric</div><div><br>On Thursday, June 1, 2017, Olaoluwa Osuntokun via bitcoin-dev &lt;<a href="mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hi y&#39;all, </div><div><br></div><div>Alex Akselrod and I would like to propose a new light client BIP for</div><div>consideration: </div><div>   * <a href="https://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki" target="_blank">https://github.com/Roasbeef/<wbr>bips/blob/master/gcs_light_<wbr>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 are 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 index of the chain, and serve this compact filter</div><div>(the index) 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 primary motivation</div><div>for this work was enabling a light client mode for lnd[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 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 like feedback on is the parameter selection. Unlike</div><div>BIP-37 which allows 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 = 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_<wbr>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 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>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="https://aakselrod.github.io/gcs_calc.html" target="_blank">https://aakselrod.github.io/<wbr>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>(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 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 with the contents being _hashes_ (we use</div><div>siphash) of the filter items.</div><div><br></div><div>Using a fixed fp=20, I have some stats detailing the total 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 out to 6.9GB. The break down is as follows:</div><div><br></div><div>    * total size:  6976047156</div><div>    * total avg:  14997.220622758816</div><div>    * total median:  3801</div><div>    * total max:  79155</div><div>    * regular size:  3117183743</div><div>    * regular avg:  6701.372750217131</div><div>    * regular median:  1734</div><div>    * regular max:  67533</div><div>    * extended size:  3858863413</div><div>    * extended avg:  8295.847872541684</div><div>    * extended median:  2041</div><div>    * extended max:  52508</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: </div><div><br></div><div>    * total size:  2753238530</div><div>    * total avg:  5918.95736054141</div><div>    * total median:  60202</div><div>    * total max:  74983</div><div>    * regular size:  1165148878</div><div>    * regular avg:  2504.856172982827</div><div>    * regular median:  24812</div><div>    * regular max:  64554</div><div>    * extended size:  1588089652</div><div>    * extended avg:  3414.1011875585823</div><div>    * extended median:  35260</div><div>    * extended max:  41731</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-size 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 (transactions with 30k inputs, 30k</div><div>outputs, etc).</div><div><br></div><div>     * total size:  585087597</div><div>     * total avg:  520.8839608674402</div><div>     * total median:  20</div><div>     * total max:  164598</div><div>     * regular size:  299325029</div><div>     * regular avg:  266.4790836307566</div><div>     * regular median:  13</div><div>     * regular max:  164583</div><div>     * extended size:  285762568</div><div>     * extended avg:  254.4048772366836</div><div>     * extended median:  7</div><div>     * extended max:  127631</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 be found here:</div><div>     * mainnet: (14MB): <a href="https://www.dropbox.com/s/4yk2u8dj06njbuv/mainnet-gcs-stats.csv?dl=0" target="_blank">https://www.dropbox.com/s/<wbr>4yk2u8dj06njbuv/mainnet-gcs-<wbr>stats.csv?dl=0</a></div><div>     * testnet: (25MB): <a href="https://www.dropbox.com/s/w7dmmcbocnmjfbo/gcs-stats-testnet.csv?dl=0" target="_blank">https://www.dropbox.com/s/<wbr>w7dmmcbocnmjfbo/gcs-stats-<wbr>testnet.csv?dl=0</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="https://github.com/lightninglabs/neutrino" target="_blank">https://github.com/<wbr>lightninglabs/neutrino</a></div><div>[2]: <a href="https://github.com/Roasbeef/btcd/tree/segwit-cbf" target="_blank">https://github.com/Roasbeef/<wbr>btcd/tree/segwit-cbf</a></div><div>[3]: <a href="https://github.com/Roasbeef/btcutil/tree/gcs/gcs" target="_blank">https://github.com/Roasbeef/<wbr>btcutil/tree/gcs/gcs</a></div><div>[4]: <a href="https://github.com/lightningnetwork/lnd/" target="_blank">https://github.com/<wbr>lightningnetwork/lnd/</a></div><div><br></div><div>-- Laolu</div><div><br></div></div>
</blockquote></div>