twoeths
commented
2 months ago an interesting talk about sha256 for merkle tree regarding batch hash https://www.youtube.com/watch?v=NfK4np15E64
there are 2 implementations for now:
- SIMD which is 2x the current as-sha256 https://github.com/ChainSafe/ssz/issues/356
- hashtree 20x the current as-sha256 as shown above
There are 2 ways we can do the batch hash
- we can go from root to group same level hash computation and do it in batch from bottom to top
type HashComputation = { src0: Node; src1: Node; dest: Node; };
getHashComputation(level: number, hashCompsByLevel: Map<number, HashComputation[]>): void { if (this.h0 === null) { let hashComputations = hashCompsByLevel.get(level); if (hashComputations === undefined) { hashComputations = []; hashCompsByLevel.set(level, hashComputations); } hashComputations.push({src0: this.left, src1: this.right, dest: this}); if (!this.left.isLeaf()) { (this.left as BranchNode).getHashComputation(level + 1, hashCompsByLevel); } if (!this.right.isLeaf()) { (this.right as BranchNode).getHashComputation(level + 1, hashCompsByLevel); }
return;
}
// else stop the recursion, LeafNode should have h0}
this traversal takes <10% of our current hash time
- or we can do it during the `ViewDU.commit()` which has the rebind inside. Need to take a closer look at this but this approach is more potential because we don't waste another traversal there
Current Hashing Approach
Lodestar's architecture relies heavily on maintaining a full merkle tree of the beacon state. We represent the tree as a linked data structure, where each node is 1. immutable, 2. lazily computing but caching the hash of its children.
This allows us to minimize the number of hashes we need to perform during state transition. Since all hashes of a prestate are maintained, only the paths thru the tree to the "diff" need to be re-hashed. This reduces the computational cost of hashing.
Also, it allows us perform structural sharing, sharing the memory for beacon states with shared subtrees. For example, between epochs in a sync period, where sync committees remain constant, if we maintain a reference to two beacon states, both states will share the same underlying subtrees for the sync committees. This reduces the memory cost of maintaining several related states.
Hashing Function
We use as-sha256 with several optimizations
we rely on hash inputs always being 64 bytes - this allows us to precompute part of the sha256 internals for a decent gain
we avoid allocations inside library, only using fixed input/output buffers
Related hashing perf analysis https://github.com/ChainSafe/lodestar/issues/2206
Hash Cache Representation
The memory usage for each type of object in Javascript is not very efficient coming from a systems language intuition. We store hash objects NOT as 32-byte Uint8Array. A 32-byte Uint8Array takes 223 total bytes! There's a bunch of pointers and additional bookkeeping that's being stored behind the scenes. We store hash objects as objects with 8 uint32 numbers. eg:
{h0: 0, h1: 0, ..., h7: 0}. This takes somewhere between 88 bytes and 216 bytes, depending on the sizes of the indiviudal component numbers. Smaller numbers are represented as Smi (small integer) as an immediate value, while larger numbers are stored on the heap. In practice, this happens TODO.How to improve?
The hashing speed in lodestar is quite low compared to other implementations.
The memory of our hashes in a lodestar node constitute a lot of a running beacon node. And our memory usage, measured per-hash, is still very large compared to systems languages.
Results
Some experiments were made, results below
cayman/hash-objecthashtreedoes exceptionally well operating on largeUint8Arrays, not as well on rustHashObjects. (seehashtree uint8arrayrow) (hashtreecode has since been pulled into a repo here:@chainsafe/hashtree-js)rustrow), also using a rust port of as-sha256 was slower (seerust object rs-sha256)node -r ts-node/register node_modules/.bin/benchmark packages/ssz/test/perf/hash.test.tsUnfortunately, a rust
HashObjectis more expensive, memory-wise, than the status quo.node -r ts-node/register --expose-gc packages/ssz/test/memory/hash.test.tscayman/hash-cachenode -r ts-node/register node_modules/.bin/benchmark packages/ssz/test/perf/eth2/hashTreeRoot.test.tshash cache
master
node -r ts-node/register --expose-gc packages/ssz/test/memory/eth2Objects.test.tshash cache
master
cayman/napi-merkle-nodeNodeto javascript. This design allows most of the tree to exist in rust, with napi pointers into the tree as navigation demands.