Description

One strategy for improving block processing times during re-org (#2805) that I've been thinking about for a while would be to make it extremely cheap to clone and duplicate BeaconStates. Currently a lot of our caches and optimisations dance around the fact that BeaconStates are huge 30-50MB objects that take 200ms+ to clone. Building a tree hash cache from scratch also takes ~1s.

Using persistent data structures that are copy-on-write, we could exploit the large amount of data shared between states at nearby slots. If each BeaconState were represented as a tree with Arc nodes, then we could keep a large number of them in memory, and use these to accelerate block processing. In smooth network conditions we could probably keep every state since finalization in memory: with and without blocks applied.

On the implementation side, we could revive my old implementation of the "validator tree" from EthDenver 2020, which lives in this defunct branch: https://github.com/michaelsproul/lighthouse/tree/validator-tree-ethdenver. It was inspired by talks with Proto about Remerkleable.

This issue is pretty vague currently, but I'll add to it as my thinking on it develops (it also links in to using some sort of diff-based representation to store states on disk).