7

The logs bloom filter in the block header has a size of 2048 bits. How many messages will it accommodate before the false positive rate is too high for it to be useful anymore? If a formula could be provided that would be excellent.

  • 1
    This is a great resource for bloom filters: en.wikipedia.org/wiki/Bloom_filter. There's a formula there. Sorry, I don't have time to craft a good answer, but if you find on in the link, you can answer your own question and get some credit. – Thomas Jay Rush Aug 14 '18 at 21:27
  • I wanted some clarification on Ethereum's case because it seems to work out to about 50% false positive rate at ~1000 messages and I couldn't find anything written about it. – Scott Aug 14 '18 at 22:00
1

As Thomas already suggested, https://en.wikipedia.org/wiki/Bloom_filter is a good resource for this.

As far as I understand, it works like this (correct please if wrong):

The estimate formula for false positive is (1-e^(-k*n/m))^k

Ethereum yellow paper says:

M3:2048 is a specialised Bloom filter that sets three bits out of 2048, given an arbitrary byte sequence.

Hence k=3, m=2048

For this we get the following false positive estimates (n = number of contract addresses and log topics contained in the bloom filter):

n =  100 ->  ~0,25%
n =  200 ->  ~1,64%
n =  430 -> ~10,20%
n = 1080 -> ~50,14%
n = 4000 -> ~99,15%

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.