This document gives a quick description of the _current_ (2024/12) zkL2 state-tree designs.

## ZKSync Era
- Tree: based on [Jellyfish Merkle Tree](https://developers.diem.com/papers/jellyfish-merkle-tree/2021-01-14.pdf) (Diem)
- Arity: 16
- Hash: [Blake2s256](https://github.com/matter-labs/zksync-era/blob/f27b4f3550cb105380d4a215f333317b66f7a096/core/lib/merkle_tree/src/hasher/mod.rs#L114-L136) for merkelization, field is Goldilocks ([more info about field, proving system, etc](https://l2beat.com/zk-catalog/zksync-era)).
- The proving system they use is [Boojum](https://github.com/matter-labs/zksync-crypto/tree/main/crates/boojum#boojum) (based on RedShift)
- [Code of circuits](https://github.com/matter-labs/zksync-protocol)
- They proving strategy relies on using [L4](https://www.nvidia.com/en-us/data-center/l4/), so that explains why Blake2 is an option. [More prover docs here](https://matter-labs.github.io/zksync-era/prover/latest/00_intro.html).
- [Tree implementation](https://github.com/matter-labs/zksync-era/blob/f27b4f3550cb105380d4a215f333317b66f7a096/core/lib/merkle_tree)

## Linea
- Tree: “Merkle sorted linked-list” inspired in [Veredict paper](https://eprint.iacr.org/2021/1263).
- I prefer calling it “sorted hashed-key Indexed Sparse Merkle Tree”.
- The SMT part is a normal bounded (e.g: 2^40 leaves) [implementation](https://github.com/Consensys/linea-monorepo/blob/7f83ea94cfebb354da4f744c6506b7a34c59f71f/prover/crypto/state-management/smt/tree.go).
- Leaves are a hash-key ordered doubly-linked list of `key:value`.
- Insertion is done by “appending” in the leaves, and leaf fields `prev` and `next` reflect the ordering of hashed keys. [Implementation reference](https://github.com/Consensys/linea-monorepo/blob/7f83ea94cfebb354da4f744c6506b7a34c59f71f/prover/crypto/state-management/accumulator/proverstate.go#L17).
- You can also see the [insertion trace](https://github.com/Consensys/linea-monorepo/blob/7f83ea94cfebb354da4f744c6506b7a34c59f71f/prover/crypto/state-management/accumulator/insertion.go#L15-L36) implementation. An *insertion trace* is what you’d expect: inserting a new leaf at the end and modifying the (potentially) existing `left` and `right` (reg hashed-key ordering) neighbors—a similar idea with *deletion trace* and *updating trace*.
- The main benefit is having a shallower tree since the number of leaves is bound by design (e.g: 2^40). As in, the path to a leaf is not “bits of key”.
- Arity: 2
- Tree [high-level spec](https://docs.linea.build/get-started/concepts/state-manager).
- Merkelization hash: [MIMC and the tree fixed-depth is 40](https://github.com/Consensys/linea-monorepo/blob/7f83ea94cfebb354da4f744c6506b7a34c59f71f/prover/backend/execution/statemanager/worldstate.go#L16-L19). Field is from BLS12_377.
- Prover: Arcane+Vortex, which, quoting Lev Soukhanov (h/t!), uses a lattice-based hash in the implementation of a Merkle tree of a commitment scheme (which resembles Brakedown and is code-based by itself). [More general info](https://linea.mirror.xyz/B3b1lUK8--UKZ_Qehk7SfOyvdcGbcuoyvNsSukHgOY8) and [prover code](https://github.com/Consensys/linea-monorepo/tree/main/prover/zkevm/prover/statemanager).

## Starknet
- Tree: Merkle Patricia Trie
- Very similar to MPT — has extension nodes in internal nodes as MPT, and not only in leaf nodes as EIP draft.
- Arity: 2.
- Hash: Poseidon. Uses STARK field of [252-bits](https://docs.starknet.io/architecture-and-concepts/cryptography/p-value/).
- [Spec](https://docs.starknet.io/architecture-and-concepts/network-architecture/starknet-state/#merkle_patricia_trie)

## Scroll
- Tree: Binary Tree
- Arity: 2
- Hash: Poseidon, with a field of 254-bits (EC bn128).
- Very similar to current draft EIP!, but:
- For key traverse LSB→MSB instead of MSB→LSB.
- No key grouping (i.e: 256-grouping) done in EIP draft.
- [Spec](https://github.com/scroll-tech/zktrie/blob/main/docs/zktrie.md):
- Similar construction to current EIP draft.
- Key construction:
1. `hash([address, storage key])`
2. Take lowest 248 bits of Poseidon since field is 254-bits.
3. Path is from LSB to MSB.
- Example of encoding of account and account data in finite-fields for proper Poseidon hashing, [see leaf value example](https://github.com/scroll-tech/zktrie/blob/main/docs/zktrie.md#ethereum-account-leaf-node).

## PolygonZKEVM
- Tree: Sparse Merkle Tree
- [Tree implementation in C++ prover](https://github.com/0xPolygonHermez/zkevm-prover/blob/d23715e37e1ceb048babd5a258147bb8f66ccc5e/src/hashdb/smt.cpp)
- Tree [key → [Goldilocks] encoding](https://github.com/0xPolygonHermez/zkevm-node/blob/8335850137041b2eebf5503387b704a4aa833cf6/merkletree/key.go#L20-L42) with [Poseidon config (cap: 4, rate: 8)→4](https://github.com/iden3/go-iden3-crypto/blob/625bf563ffc57f02e666d6979c4432e32f0b8059/goldenposeidon/poseidon.go#L56-L107) & [constants](https://github.com/iden3/go-iden3-crypto/blob/625bf563ffc57f02e666d6979c4432e32f0b8059/goldenposeidon/constants.go#L5-L14).
- Arity: 2
- Hash: Poseidon with Goldilocks field