Bloom simplifications / optimizations

[justindotpub]

Notes captured from dialog with @expede and @matheus23.

The current approach to Bloom Filters in go-car-mirror is quite flexible and makes it possible to deal with bloom capacity overflow, but it adds extra complexity for implementors. Brooke's recommendation is to start with something simpler.

Only support XXH3 per the spec.

Take the XXH3 hash, and then save bits of certain sizes around such that you can JIT convert to bitfield indices based on the size of the bitfield chosen.

• If you have a 256-bit bloom filter, you can use the first 8 bits of your hash as the index.
• If you have a 1024-bit bloom filter, you can use the first 10 bits,
• Up to, let’s say 2MiB bloom filter, where you can use the first 24 bits as index. So if you keep around the first 24 bits of each hash of the elements you want to add, you can generate any power-of-two size bloom filter under 2^24 bits (2MiB).

Also, if you keep around an array of precomputed indices without flattening them to a bitfield (i.e. [99, 42, 5014, 139, ...]), you can take however many of them you need for your size of bloom. There’s a bit more detail, but TL;DR you can do very performant things like query subgraphs of blooms from an in-memory cache and merge a bunch of them together (often in the query directly) and then flatten to a Bloom.

...

More details need to be spelled out here, but this issue is for getting the code back to spec compliance with regard to bloom usage / encoding, for the initial version of batch support.

ETA: 2023-10-31

[justindotpub]

As I've started testing with different sizes for MaxBlocksPerRound (and MaxBlocksPerColdCall) I've discovered that the current code will nest blooms more than 32 deep, leading to a CBOR error.

cbor: exceeded max nested level 32

Looks like this may need to be addressed sooner.