<div dir="ltr">This is a really cool finding, thanks Pieter!<div><br></div><div>I did some more analysis on selecting a good P value to reduce total data downloaded considering both filters themselves and blocks in the case of false positive matches, using data from mainnet. The quantity it minimizes is:</div><div><br></div><div>filter_size(N, B) + block_size * false_positive_probability(C, N, B)</div><div><br></div><div>N is the number of filter elements per block</div><div>B is the Golomb-Rice coding parameter</div><div>C is the number of filter elements watched by the client</div><div><br></div><div>The main result is that:</div><div><br></div><div>For C = 10, B = 13 is optimal</div><div>For C = 100, B = 16 is optimal</div><div>For C = 1,000, B = 20 is optimal</div><div>For C = 10,000, B = 23 is optimal</div><div><br></div><div>So any value of B in the range 16 to 20 seems reasonable, with M = <span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">1.4971 * 2^B for optimal compression, as Pieter derived. The selection of the parameter depends on the target number of elements that a client may watch.</span></div><div><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><br></span></div><div><span style="color:rgb(34,34,34);font-family:sans-serif;font-size:13px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">I attached some of the results, and would be happy to share the CSV and raw notebook if people are interested.</span></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Fri, May 25, 2018 at 2:14 PM Gregory Maxwell via bitcoin-dev <<a href="mailto:bitcoin-dev@lists.linuxfoundation.org" target="_blank">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell <<a href="mailto:greg@xiph.org" target="_blank">greg@xiph.org</a>> wrote:<br>
> configuration is roughly right, then M=1569861 and rice parameter 19<br>
> should be used.<br>
<br>
That should have been M=784931 B=19 ... paste error.<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href="mailto:bitcoin-dev@lists.linuxfoundation.org" target="_blank">bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br>
</blockquote></div>