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.
Asked
Active
Viewed 432 times
7
-
1This is a great resource for bloom filters: https://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 Answers
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%
ivicaa
- 7,519
- 1
- 20
- 50