Bloom Filter: wrong number of hash functions used

[bennetyee]

• Parity Ethereum version: HEAD
• Operating system: all
• Installation: built from source
• Fully synchronized: NA
• Network: NA
• Restarted: NA

The number of bloom filter hash functions used is actually one less than intended.

Both https://github.com/paritytech/parity-ethereum/blob/master/util/bloom/src/lib.rs#L133 and https://github.com/paritytech/parity-ethereum/blob/master/util/bloom/src/lib.rs#L145 iterate k_i starting at 0 up to (and including) self.k_num - 1, for a total of self.k_num iterations. The intent is to get self.k_num statistically independent hash values to set bits or check for bits in self.bitmap, as is normal for bloom filter implementations. However, the code for bloom_hash at https://github.com/paritytech/parity-ethereum/blob/master/util/bloom/src/lib.rs#L180 returns the same hash value for k_i equal to either 0 or 1. This means that, in effect, we are getting self.k_num - 1 independent hashes, instead of the expected self.k_num hashes. Since the value of self.k_num is computed in new at https://github.com/paritytech/parity-ethereum/blob/master/util/bloom/src/lib.rs#L88 with optimum_k_num https://github.com/paritytech/parity-ethereum/blob/master/util/bloom/src/lib.rs#L164 the value is correct, but the actual number of independent hash function used is incorrect; it is actually one fewer.

However, hash_backward_compatibility_for_new https://github.com/paritytech/parity-ethereum/blob/master/util/bloom/src/lib.rs#L246 seem to indicate that there is a strong desire to retain backward compatibility. Either a fix -- including changing the backwards compatibility tests -- or comments explaining why we want the first and second hash functions to be identical would be nice, because future readers of this code will want to know.

[jam10o-new]

I'm really unsure how to describe this, what (difference in) effect would this have in practice?

[niklasad1]

/cc @debris

[tomusdrw]

@bennetyee some background: #6404 (comment)

I think we should definitely fix this properly, I'd be in favour of using new way of hashing for fresh syncs, but keeping the old behaviour for old DBs to avoid the need of migration.

[adria0]

Closing issue due to its stale state.

[adria0]

Closing issue due to its stale state.