<div dir="ltr"><div>Hi y&#39;all, </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 thread, and also as a</div><div>result of real-world testing using this new proposal as the basis for our light</div><div>weight LN node which powers the 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>  * We&#39;ve removed the modulus operation in the inner loop when constructing</div><div>    filters. This has been replaced with an alternative, more efficient</div><div>    mapping[1] as suggested by gmaxwell and sipa. In our implementation, we</div><div>    perform the operation in a piece-wise fashion by hand. Alternative</div><div>    implementations can take advantage of 128-bit arithmetic extensions on</div><div>    supporting CPU&#39;s.</div><div> </div><div>  * The txid has been moved from the extended filter to the regular filter.</div><div>    During out testing of the new light client with our LN node implementation,</div><div>    we found that we were able to reduce network traffic as we only need the</div><div>    extended filter for rare on-chain events.</div><div><br></div><div>  * We now use the 6th service bit. We realized that the bit we had chosen</div><div>    prior was already being used to signal support of x-thin block syncing. To</div><div>    select this bit number, we ran a scanner on the addrman of our nodes and</div><div>    also the network to fin da bit that wasn&#39;t used widely.</div><div>  </div><div>  * An error in the BIP that didn&#39;t include the public key script of coinbase</div><div>    transactions in the filter has been fixed.</div><div><br></div><div>  * An error in the BIP when constructing the initial &quot;genesis&quot; filter has been</div><div>    fixed.</div><div><br></div><div>  * We no longer use the ProtocolVersion field in the getcfheaders message or</div><div>    its response. </div><div><br></div><div>  * The specification of several newly defined messages were incorrect and have</div><div>    been fixed.</div><div><br></div><div>  * A number of typos spotted by several reviewers have been fixed.</div><div><br></div><div>The full commit history of the BIP draft can be found here:</div><div><a href="https://github.com/Roasbeef/bips/commits/gcs-bip-draft">https://github.com/Roasbeef/bips/commits/gcs-bip-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="https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/">https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/</a></div><div><br></div><div>-- Laolu</div><div><br></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Jun 8, 2017 at 8:59 PM Olaoluwa Osuntokun &lt;<a href="mailto:laolu32@gmail.com">laolu32@gmail.com</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>Hi y&#39;all, </div><div><br></div><div>Thanks 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 incorrect</div><div>(N is the 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 version 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, one of</div><div>which generates a &quot;null&quot; filter): </div><div><br></div><div>   * The block height</div><div>   * The block hash</div><div>   * The raw block itself</div><div>   * The previous basic+extended filter header </div><div>   * The basic+extended filter header for the block</div><div>   * The basic+extended filter for the block</div><div><br></div><div>The size of the test vectors was too large to include in-line 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 been included.</div><div><br></div><div>-- Laolu</div><div><br></div><div>[1]: <a href="https://github.com/Roasbeef/bips/tree/master/gcs_light_client" target="_blank">https://github.com/Roasbeef/bips/tree/master/gcs_light_client</a></div></div></div><div dir="ltr"><div><div><br></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Jun 1, 2017 at 9:49 PM Olaoluwa Osuntokun &lt;<a href="mailto:laolu32@gmail.com" target="_blank">laolu32@gmail.com</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>&gt; In order to consider the average+median filter sizes in a world worth larger</div><div>&gt; blocks, I also ran the index for testnet:</div><div>&gt; </div><div>&gt;     * total size:  2753238530</div><div>&gt;     * total avg:  5918.95736054141</div><div>&gt;     * total median:  60202</div><div>&gt;     * total max:  74983</div><div>&gt;     * regular size:  1165148878</div><div>&gt;     * regular avg:  2504.856172982827</div><div>&gt;     * regular median:  24812</div><div>&gt;     * regular max:  64554</div><div>&gt;     * extended size:  1588089652</div><div>&gt;     * extended avg:  3414.1011875585823</div><div>&gt;     * extended median:  35260</div><div>&gt;     * extended max:  41731</div><div>&gt; </div><div><br></div></div><div dir="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="ltr"><div><br></div><br><div class="gmail_quote"><div dir="ltr">On Thu, Jun 1, 2017 at 12:01 PM Olaoluwa Osuntokun &lt;<a href="mailto:laolu32@gmail.com" target="_blank">laolu32@gmail.com</a>&gt; wrote:<br></div><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/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 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_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/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:  <a href="tel:(385)%20886-3413" value="+13858863413" target="_blank">3858863413</a></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/4yk2u8dj06njbuv/mainnet-gcs-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/w7dmmcbocnmjfbo/gcs-stats-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/lightninglabs/neutrino</a></div><div>[2]: <a href="https://github.com/Roasbeef/btcd/tree/segwit-cbf" target="_blank">https://github.com/Roasbeef/btcd/tree/segwit-cbf</a></div><div>[3]: <a href="https://github.com/Roasbeef/btcutil/tree/gcs/gcs" target="_blank">https://github.com/Roasbeef/btcutil/tree/gcs/gcs</a></div><div>[4]: <a href="https://github.com/lightningnetwork/lnd/" target="_blank">https://github.com/lightningnetwork/lnd/</a></div><div><br></div><div>-- Laolu</div><div><br></div></div></blockquote></div></div></blockquote></div></div></div></blockquote></div></div>