Don't store full pubkey in pubkey2index map

[dapplion]

Describe the feature

We don't need to store the full pubkey since the collision probability is low enough with just a few bytes. Note that ethereum addresses use 20 bytes only.

Check a safe minimum byte count and create a map that can extend the size of the key if it detects a collision. Keep an array of key bytes, starting at [10] for example, and if there's a collision extend to [11] and write new keys with 11 bytes. Then to check slice to 11 check, slice to 10 check.

[dapplion]

pubkey2index map is retaining 320MB in Prater (220_000 validators) which averages 1454 bytes per pubkey 🤯

[dapplion]

Proposal:

• Use only the first N bytes of the pubkey (i.e. 4) and encoded as base64url to have a very short key. Use base64url since it has no padding and saves 2 characters
• The Map value will be an array of indices that start with that pubkey prefix.

Since the goal of this Map is to speed up lookup by pubkeys narrowing down from 250_000 to ~10 instead of 1 is good enough.

Analysis of probabilities should pick an appropriate byte length. Also must check that BLS pubkeys have a sufficient random distribution of the first N bytes.

[dapplion]

After doing some research today:

• The bulk of the memory usage is cause by this awful concatenated strings. With Use memory efficient toHex in pubkey2index map #3561 the memory usage of the map is reduced by 10x from 350MB to 35MB.

• With non-concatenated strings, using less bytes has marginal benefits being able to reduce 2.5x extra. However that's an absolute reduction of ~19MB for the entire application so not a lot. Also, using shorter keys adds non-trivial complexity to ensure keys are not known. To do that indexed sync committees MUST not rely of the pubkey2index map but for the first indexation.

• Using hex, base64 or base64url has not effect of the total memory usage of the Map

WIP branch: https://github.com/ChainSafe/lodestar/tree/dapplion/pubkey2index-short-key

[dapplion]

The real cause of the memory inefficiency is the concatenated strings as shown here #3446

The current size of the Pubkey2Index map is 45.5MB for 275496 validators. We could consider reducing the pubkey length but now it's not that prioritary

[philknows]

Is this a worthy optimisation for memory? Need to investigate further.

[wemeetagain]

• closing in favor of feat: use napi-rs pubkey-index-map #7091