Minimizing the redundancy in Golomb Coded Sets

Hi all,

I spent some time working out the optimal parameter selection for the Golomb Coded Sets that are proposed in BIP158: https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845

TL;DR: if we really want an FP rate of exactly 1 in 2^20, the Rice parameter should be 19, not 20. If we don't, we should pick an FP rate of 1 in a 1.4971*2^B. So for example M=784931 B=19 or M=1569861 B=20.

Cheers,

On Fri, May 25, 2018 at 5:54 PM, Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:

> Hi all,
>
> I spent some time working out the optimal parameter selection for the
> Golomb Coded Sets that are proposed in BIP158:
> https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845
>
> TL;DR: if we really want an FP rate of exactly 1 in 2^20, the Rice
> parameter should be 19, not 20. If we don't, we should pick an FP rate
> of 1 in a 1.4971*2^B. So for example M=784931 B=19 or M=1569861 B=20.

I did a rough analysis using Pieter's approximations on what parameters minimizes the total communications for a lite wallet scanning the chain and fetching a witnessless block whenever they get a filter hit. For a wallet with 1000 keys and blocks of 1MB if the number of entries in the is at least 5096 then M=784931 results in a lower total data rate rate (FP blocks + filters) than M=1569861. M=392465 (the optimal value for the rice parameter 18) is communications is better if at least 10192 entries are set, and M=196233 (optimal FP for rice 17) is better if at least 20384 entries are set.

The prior filter set proposal is setting roughly 13300 entries per full block, and I guestimate that the in+out scripts only ones are setting about 7500 entries (if that actual number was in any of the recent posts I missed it, I'm guessing based on jimpo's sizes graph).

The breakpoints are obviously different if the client is monitoring for, say, 10,000 keys instead of 1000 but I think it generally makes more sense to optimize for lower key counts since bigger users are more likely to tolerate the additional bandwidth usage.

So I think that assuming that all-scripts inputs and outputs (but no txids) are used and that my guess of 7500 bits set for that configuration is roughly right, then M=1569861 and rice parameter 19 should be used.

The actual optimal FP rate for total data transferred won't be one that gets the optimal rice coding efficiency, but since different clients will be monitoring for different numbers of keys, it probably makes sense to pick a parameter with optimal compression rather than optimal-data-transfer-for-a-specific-key-count-- at least then we're spending the least amount of filter bits per false positive rate, whatever that rate is... if we can't be optimal at least we can be efficient. :)

On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell <greg@xiph•org> wrote:

> configuration is roughly right, then M=1569861 and rice parameter 19
> should be used.

That should have been M=784931 B=19 ... paste error.

This is a really cool finding, thanks Pieter!

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:

filter_size(N, B) + block_size * false_positive_probability(C, N, B)

N is the number of filter elements per block B is the Golomb-Rice coding parameter C is the number of filter elements watched by the client

The main result is that:

For C = 10, B = 13 is optimal For C = 100, B = 16 is optimal For C = 1,000, B = 20 is optimal For C = 10,000, B = 23 is optimal

So any value of B in the range 16 to 20 seems reasonable, with M = 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.

I attached some of the results, and would be happy to share the CSV and raw notebook if people are interested.

On Fri, May 25, 2018 at 2:14 PM Gregory Maxwell via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:

> On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell <greg@xiph•org> wrote:
> > configuration is roughly right, then M=1569861 and rice parameter 19
> > should be used.
>
> That should have been M=784931 B=19  ... paste error.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

Hi Jim,

Yes please, could you share CSV? We are developing a Wallet that uses Golomb-Rice filters it would help a lot for determine the best P value depending on the estimated number of elements the client needs to watch.

2018-05-29 19:38 GMT-03:00 Jim Posen via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org>:

> This is a really cool finding, thanks Pieter!
>
> 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:
>
> filter_size(N, B) + block_size * false_positive_probability(C, N, B)
>
> N is the number of filter elements per block
> B is the Golomb-Rice coding parameter
> C is the number of filter elements watched by the client
>
> The main result is that:
>
> For C = 10, B = 13 is optimal
> For C = 100, B = 16 is optimal
> For C = 1,000, B = 20 is optimal
> For C = 10,000, B = 23 is optimal
>
> So any value of B in the range 16 to 20 seems reasonable, with M = 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.
>
> I attached some of the results, and would be happy to share the CSV and
> raw notebook if people are interested.
>
>
> On Fri, May 25, 2018 at 2:14 PM Gregory Maxwell via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation•org> wrote:
>
>> On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell <greg@xiph•org> wrote:
>> > configuration is roughly right, then M=1569861 and rice parameter 19
>> > should be used.
>>
>> That should have been M=784931 B=19  ... paste error.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists•linuxfoundation•org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>