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

ZKSync Era

• Tree: based on Jellyfish Merkle Tree (Diem)
• Arity: 16
• Hash: Blake2s256 for merkelization, field is Goldilocks (more info about field, proving system, etc).
  • The proving system they use is Boojum (based on RedShift)
  • Code of circuits
  • They proving strategy relies on using L4, so that explains why Blake2 is an option. More prover docs here.
• Tree implementation

Linea

• Tree: “Merkle sorted linked-list” inspired in Veredict paper.
  • I prefer calling it “sorted hashed-key Indexed Sparse Merkle Tree”.
  • The SMT part is a normal bounded (e.g: 2^40 leaves) implementation.
  • 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.
  • You can also see the insertion trace 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.
• Merkelization hash: MIMC and the tree fixed-depth is 40. 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 and prover code.

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.
• Spec

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:
  • 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.

PolygonZKEVM

• Tree: Sparse Merkle Tree
  • Tree implementation in C++ prover
  • Tree key → [Goldilocks] encoding with Poseidon config (cap: 4, rate: 8)→4 & constants.
• Arity: 2
• Hash: Poseidon with Goldilocks field