# Improve BeaconState hashTreeRoot()

## 1. Description
As of Jun 2024, holesky validator size is 1.73M and mainnet validator size is 1.45M. We see the BeaconState's hashTreeRoot() was up to 1.5s to prepare for next epoch and it will increase in the upcoming months. Improving this function is critical for lodestar, especially after Electra where we'll likely see longer epoch transition there
With the new SIMD implementation of sha256, we hope that we can improve this time more, see below for more details

* ### 1.1 Current implementation
Majority of the hashTreeRoot() time is for validators so we need to care about it the most.
Right now each validator is typed as a ContainerNodeStruct which cache validator value without a tree. When a validator is modified, we need to recreate th wholee tree and compute root for it. Note that the tree is not stored anywhere, we just create when we need it and evicted by gc after all
- Pros:
- It's super fast to get a value of validator
- It's much lighter to store validator as value compared to nodes because an epoch field is tracked as 1 number in value instead of 8 as in a Node
- Cons:
- Tree creation time is a lot
- Cannot cache hashed nodes
- Cannot batch hash
* ### 1.2 Benchmark
This is the benchmark result with a 200k validator beacon state and half of that is modified

    ✓ BeaconState ViewDU recursive hash vc=200000                         1.045194 ops/s    956.7598 ms/op        -         13 runs   16.5 s
    ✓ BeaconState ViewDU recursive hash - commit step vc=200000           30.49162 ops/s    32.79589 ms/op        -         12 runs   2.96 s
    ✓ BeaconState ViewDU validator tree creation vc=100000                4.024561 ops/s    248.4743 ms/op        -         15 runs   6.76 s

This shows something we need to improve:
- Find a way for batch hash
- validator creation tree

* ### 1.3 SIMD sha256
There's hashtree-js binding work [here](https://github.com/ChainSafe/hashtree-js) which call the great native hashtree implementation of Prysm which promise to be 20x faster than the current version of Lodestar. I'm waiting for Mathew to try its performance on different cpus but if it's 5x faster than the current version, it's already amazing to me
Besides that, we also have wasm implementation [here](https://github.com/ChainSafe/ssz/pull/367), the best it can do is 2x faster on Macbook 2017 Intel cpu

It shows that hashtree is almost 5x faster than as-sha256 on Mac M1 cpu

 hasher
    as-sha256
      ✓ hash 2 Uint8Array 500000 times - as-sha256                          2.717292 ops/s    368.0135 ms/op        -         12 runs   47.8 s
      ✓ hashTwoObjects 500000 times - as-sha256                             2.864475 ops/s    349.1041 ms/op        -         12 runs   45.4 s
      - batchHashObjects - as-sha256
      ✓ executeHashComputations - as-sha256                                 31.25938 ops/s    31.99039 ms/op        -         37 runs   3.19 s
    hashtree
      ✓ hash 2 Uint8Array 500000 times - hashtree                           5.551561 ops/s    180.1295 ms/op        -         12 runs   23.4 s
      ✓ hashTwoObjects 500000 times - hashtree                              6.362881 ops/s    157.1615 ms/op        -         12 runs   20.4 s
      - batchHashObjects - hashtree
      ✓ executeHashComputations - hashtree                                  149.3710 ops/s    6.694742 ms/op        -        136 runs   8.26 s

## 2. Get HashComputations and execute it
### 2.1 persistent-merkle-tree

I created this data structure for batch hash work, the field name is not really nice but good enough for a POC

export type HashComputation = {
  src0: Node;
  src1: Node;
  dest: Node;
};

it shows batch hash is less than 2x faster than regular hash although `hashtree.executeHashComputations()` is 5x faster than as-sha256, I think HashComputation above caused gc to run more?

Node batchHash
    ✓ getHashComputations 250000 nodes                                    86.79037 ops/s    11.52202 ms/op        -         32 runs   28.0 s
    ✓ batchHash 250000 nodes                                              19.13791 ops/s    52.25231 ms/op        -         29 runs   22.2 s
    ✓ get root 250000 nodes                                               10.25390 ops/s    97.52391 ms/op        -         18 runs   14.1 s
    ✓ getHashComputations 500000 nodes                                    38.27039 ops/s    26.12986 ms/op        -         34 runs   57.2 s
    ✓ batchHash 500000 nodes                                              8.678133 ops/s    115.2322 ms/op        -         27 runs   38.3 s
    ✓ get root 500000 nodes                                               5.180939 ops/s    193.0152 ms/op        -         12 runs   18.8 s

`getHashComputation()` takes 11% - 13% time, it basically do one traversal from root to group HashComputations by level and execute from the bottom. There's an idea to improve `getHashComputation()` as below

### 2.2 Get HashComputations during ViewDU.commit() in ssz

ViewDU in ssz() has a great design to track changed nodes and views. Based on this we can compute HashComputations to save one tree traversal (see above). The saved time is very small as I benchmarked, however it's reasonable to do so.

It's 10ms saved as in my benchmark result

BeaconState ViewDU partially modified tree vc=200000 numModified=100000
    ✓ BeaconState ViewDU batchHash - commit & getHashComputation vc=20    1.802902 ops/s    554.6614 ms/op        -         79 runs   52.9 s
    ✓ BeaconState ViewDU hashTreeRoot - commit step vc=200000             1.835587 ops/s    544.7849 ms/op        -         59 runs   39.5 s

## 3. Lazily create and persist validator trees

TLDR: This is only good enough to start with, persisting the tree in order to batch hash is not a great idea after I run a node on holesky (see below)

The current implementation only create validator tree on the fly without tracking it so we cannot do batch hash.
First approach is to lazily compute it when needed and persist the tree in BranchNodeStruct

 BeaconState ViewDU partially modified tree vc=200000 numModified=100000
    ✓ BeaconState ViewDU recursive hash vc=200000                         1.128123 ops/s    886.4279 ms/op        -         27 runs   29.1 s
    ✓ BeaconState ViewDU recursive hash - commit step vc=200000           13.13220 ops/s    76.14873 ms/op        -         45 runs   8.58 s
    ✓ BeaconState ViewDU validator tree creation vc=100000                2.462462 ops/s    406.0976 ms/op        -         67 runs   39.7 s
    ✓ BeaconState ViewDU batchHash vc=200000                              1.292733 ops/s    773.5550 ms/op        -         43 runs   37.7 s
    ✓ BeaconState ViewDU batchHash - commit & getHashComputation vc=20    1.802902 ops/s    554.6614 ms/op        -         79 runs   52.9 s
    ✓ BeaconState ViewDU batchHash - hash step vc=200000                  3.886184 ops/s    257.3218 ms/op        -         57 runs   57.0 s
    ✓ BeaconState ViewDU hashTreeRoot vc=200000                           1.322128 ops/s    756.3564 ms/op        -         63 runs   53.6 s
    ✓ BeaconState ViewDU hashTreeRoot - commit step vc=200000             1.835587 ops/s    544.7849 ms/op        -         59 runs   39.5 s
    ✓ BeaconState ViewDU hashTreeRoot - hash step vc=200000               3.717275 ops/s    269.0142 ms/op        -         57 runs   60.2 s

Above benchmark shows that tree creation takes even 1.5x hash time while we cannot do much to improve hash time, I decided to improve this. Note that tree creation time increased 1.6x (406ms vs 248ms) because of the persistence of it, which shows it's not a great approach

But batch hash helped a bit (total time is 756ms vs 886ms as the old way)

## 4. Avoid validator tree creation time
TLDR: great for the benchmark, paid 9GB more RAM to save 1s epoch transition, not sustainable in the long run
## 4.1. Maintain both validator tree and value
I enhanced ContainerNodeStruct ViewDU to track both the value, nodes and views changed.
- The read operations are as great as earlier
- The write (commit/hashTreeRoot) operations are as great as Container, no tree creation involved
- Benchmark results are great:
- no tree creation time, default recursive hash is 2x faster
- number of HashComputations are reduced, hash time is 2x faster
- in total, it shows 3x faster than the original result (328ms vs 956ms)

  BeaconState ViewDU partially modified tree vc=200000 numModified=100000
    ✓ BeaconState ViewDU recursive hash vc=200000                         2.383132 ops/s    419.6159 ms/op        -         18 runs   12.6 s
    ✓ BeaconState ViewDU recursive hash - commit step vc=200000           5.037264 ops/s    198.5205 ms/op        -         16 runs   6.25 s
    ✓ BeaconState ViewDU validator tree creation vc=100000                35.76944 ops/s    27.95682 ms/op        -         38 runs   20.7 s
    ✓ BeaconState ViewDU batchHash vc=200000                              2.855090 ops/s    350.2516 ms/op        -         13 runs   7.67 s
    ✓ BeaconState ViewDU batchHash - commit & getHashComputation vc=20    4.192557 ops/s    238.5179 ms/op        -         14 runs   6.50 s
    ✓ BeaconState ViewDU batchHash - hash step vc=200000                  7.569542 ops/s    132.1084 ms/op        -         51 runs   29.1 s
    ✓ BeaconState ViewDU hashTreeRoot vc=200000                           3.039540 ops/s    328.9972 ms/op        -         12 runs   6.44 s
    ✓ BeaconState ViewDU hashTreeRoot - commit step vc=200000             4.499143 ops/s    222.2646 ms/op        -         21 runs   8.92 s
    ✓ BeaconState ViewDU hashTreeRoot - hash step vc=200000               7.361959 ops/s    135.8334 ms/op        -         36 runs   21.0 s

### 4.2 Testing
I continued with spec tests, they all passed
Then I integrated to lodestar and got this surprise: OOM
My investigation showed that I can only load validators until 1.2M, both mainnet and holesky surpassed that
Its not possible to store a full BeaconState tree with the current implementation

### 4.3 Troubleshooting

Each node object could takes up to 2 bytes x8 for property names and 8 bytes x8 for property values, plus the overhead for Object itself, so it takes at least (2x8 + 8x8) = 80 bytes
A validator value is represented by:

- pubkey: 96 bytes = 3 nodes
- withdrawalCredentials: 32 bytes = 1 node
- effectiveBalance: 8 bytes = 1 node
- slashed: boolean = 1 node
- activationEligibilityEpoch: 8 bytes = 1 node
- activationEpoch: 8 bytes = 1 node
- exitEpoch: 8 bytes = 1 node
- withdrawableEpoch: 8 bytes = 1 node

validator tree:

level
 0                                            validator root
                               /                                         \
 1                        10                                                11
                   /                 \                                 /             \
 2            20                          21                     22                    23
           /       \                  /       \             /       \             /         \
 3      pub         with         eff         sla        act         act         exit        with
      /     \
 4 pub0      pub1

level 0: 1 node
level 1: 2 nodes
level 2: 4 nodes
level 3: 8 nodes (8 properties in total)
level 4: 2 nodes (only for pubkey)
total: 17 nodes

so it has 16 nodes in addition to the current implementation (which is 1 node). Consider each node is 80 bytes, a validator tree could take at least 16 x 80 = 1280 bytes, so with more than 1.7M of holesky validators it takes at least 1.28x1.7 = 2.178 GB, this explains the OOM

### 4.4 More testing
I was only able to run a node with this branch with max-old-heap-size being set to 16GB

PrepareNextEpoch duration is 1s less than stable

So we pay around 9GB to save 1s epoch transition which may not be worth it, `gc` increased through and it does not seem sustainable in the long term

## 5. Batch commit
Right now we commit validators individually so we have to put everything inside HashComputations in order to batch, but that requries persisting trees as we see.
We need to find a way to commit validators and compute its root in batch

### 5.1 Prepopulate validator trees

- Extend state.validators type to specify its own ViewDU called ValidatorsViewDU
- ValidatorsViewDU extends ListCompositeViewDU
- Create 16 validator tree once
- Each item of it is ValidatorViewDU
- For every 16 validators, populate trees from ValidatorViewDU value, compute root in batch
- ValidatorViewDU create new node =root + value from there
- ValidatorViewDU extends ContainerStructViewDU
- new method to populate tree from value: valueToTree(node: Node) void
- new method commitHashObject(ho: HashObject): this create new root from there + value, apply ho (HahsObject) to root
- BranchNodeStruct
- no change
- In ValidatorViewDU.commitHashObject(), new an instance and applyHash() directly
- Pros:
- able to batch hash but no need to create tree every time
- trees are created once and reuse, should be less gc
- Cons:
- no generic, has to create specific type for state.validators
- 2-step commits, one for validators and one for remaining. state.validators.commit() actually do the hash as well

Result (with hashtree) is great:
- recursive hash is 3.24x faster
- batchhash is 2.89x faster
- hashTreeRoot is 3x faster

BeaconState ViewDU partially modified tree vc=200000 numModified=100000
    ✓ BeaconState ViewDU recursive hash vc=200000                         3.653621 ops/s    273.7010 ms/op        -         28 runs   12.8 s
    ✓ BeaconState ViewDU recursive hash - validators commit step vc=20    4.545098 ops/s    220.0172 ms/op        -         18 runs   6.41 s
    ✓ BeaconState ViewDU validator tree creation vc=100000                128.2135 ops/s    7.799492 ms/op        -         28 runs   22.1 s
    ✓ BeaconState ViewDU batchHash vc=200000                              3.733401 ops/s    267.8523 ms/op        -         18 runs   6.93 s
    ✓ BeaconState ViewDU batchHash - commit & getHashComputation vc=20    4.310165 ops/s    232.0097 ms/op        -         15 runs   5.80 s
    ✓ BeaconState ViewDU batchHash - hash step vc=200000                  31.72988 ops/s    31.51603 ms/op        -         14 runs   10.9 s
    ✓ BeaconState ViewDU hashTreeRoot vc=200000                           3.954695 ops/s    252.8640 ms/op        -         16 runs   6.07 s
    ✓ BeaconState ViewDU hashTreeRoot - commit step vc=200000             4.277347 ops/s    233.7898 ms/op        -         18 runs   6.67 s
    ✓ BeaconState ViewDU hashTreeRoot - hash step vc=200000               30.73572 ops/s    32.53543 ms/op        -         26 runs   15.0 s

### 5.2 Prepopulate Uint8Array
Start from same idea to 5.1, the idea is that we don't need to populate middle nodes in order to have validator root. We only need to have Uint8Array at different levels of validator,and we let the hasher to compute root

Result is even 30% faster than 5.1

BeaconState ViewDU partially modified tree vc=200000 numModified=100000
    ✓ BeaconState ViewDU recursive hash vc=200000                         4.706004 ops/s    212.4945 ms/op        -         23 runs   9.20 s
    ✓ BeaconState ViewDU recursive hash - validators commit step vc=20    6.520329 ops/s    153.3665 ms/op        -         12 runs   3.77 s
    ✓ BeaconState ViewDU validator tree creation vc=100000                7.992198 ops/s    125.1220 ms/op        -         14 runs   6.58 s
    ✓ BeaconState ViewDU batchHash vc=200000                              4.850986 ops/s    206.1437 ms/op        -         14 runs   4.79 s
    ✓ BeaconState ViewDU batchHash - commit & getHashComputation vc=20    5.573049 ops/s    179.4350 ms/op        -         14 runs   4.28 s
    ✓ BeaconState ViewDU batchHash - hash step vc=200000                  40.95685 ops/s    24.41594 ms/op        -         16 runs   10.0 s
    ✓ BeaconState ViewDU hashTreeRoot vc=200000                           5.156880 ops/s    193.9157 ms/op        -         23 runs   6.88 s
    ✓ BeaconState ViewDU hashTreeRoot - commit step vc=200000             5.963063 ops/s    167.6991 ms/op        -         14 runs   4.41 s
    ✓ BeaconState ViewDU hashTreeRoot - hash step vc=200000               35.06000 ops/s    28.52253 ms/op        -         30 runs   13.2 s
    - BeaconState ViewDU hashTreeRoot - commit step each validator vc=200000

#### 5.2.1 Improve hashtree digestNLevelUnsafe
The key function to compute validator root from a single Uint8Array is digestNLevelUnsafe(). We used 2 Uint8Arrays to hash at each level, turned out we can use one only, it avoid a `Uint8Array.set()`. Also, we should not allocate temporary HashObject and call "applyHash()", each hash method should support result as a output parameter.

This gives 30% faster than the above

 BeaconState ViewDU partially modified tree vc=200000 numModified=100000
    ✓ BeaconState ViewDU recursive hash vc=200000                         6.950837 ops/s    143.8676 ms/op        -         14 runs   5.26 s
    ✓ BeaconState ViewDU recursive hash - commit step vc=200000           9.200534 ops/s    108.6893 ms/op        -         13 runs   3.20 s
    ✓ BeaconState ViewDU validator tree creation vc=100000                8.308017 ops/s    120.3657 ms/op        -         12 runs   4.73 s
    ✓ BeaconState ViewDU batchHash vc=200000                              7.139702 ops/s    140.0619 ms/op        -         15 runs   3.88 s
    ✓ BeaconState ViewDU batchHash - commit & getHashComputation vc=20    8.223193 ops/s    121.6073 ms/op        -         18 runs   4.35 s
    ✓ BeaconState ViewDU batchHash - hash step vc=200000                  35.87954 ops/s    27.87103 ms/op        -         20 runs   8.51 s
    ✓ BeaconState ViewDU hashTreeRoot vc=200000                           7.531041 ops/s    132.7838 ms/op        -         19 runs   4.53 s
    ✓ BeaconState ViewDU hashTreeRoot - commit step vc=200000             9.199858 ops/s    108.6973 ms/op        -         13 runs   3.24 s
    ✓ BeaconState ViewDU hashTreeRoot - hash step vc=200000               38.55383 ops/s    25.93776 ms/op        -         22 runs   8.32 s

Compare to 1.2, this is 956/132 ~= 7.24x faster than unstable in my environment.

## Lesson learn from this work
hashtree performance is great, but an important improvement from this work is to use reusable memory to hash validators in batch. We may not use batch technique in other places, but having reusable memory to hash is a great technique, we can use it to compute root for:
- Attestation
- Signing Root

hashtree also has a nice "hashInto" api which saved a lot of memory for consumer, should apply the samething to as-sha256