This EIP introduces a new Merkle tree shape for Simple Serialize (SSZ) types that results in fewer hashes when only a small number of leaves is used. The new tree shape grows progressively with increased leaf count and no longer has a bounded capacity. It also offers forward compatibility: a given chunk index is always assigned the same stable generalized index (gindex) regardless of leaf count.
New types are defined to use the progressive Merkle tree shape: ProgressiveList[type] and ProgressiveBitlist. These new types represent lists of arbitrary length with stable merkleization, reducing hashing overhead for small lists and avoiding arbitrary capacity limits.
Motivation
Current SSZ List[type, N] types require a predefined capacity N, which leads to several issues:
Inefficient hashing: Lists often contain far fewer elements than their maximum capacity (e.g., Transaction), resulting in unnecessary zero-padding and dozens of extra hash computations. This is exacerbated when nesting List[type, N], e.g., in a design where each of up to X transactions has up to Y access lists, each with up to Z storage slots.
Arbitrary Limits: The capacity N is often chosen arbitrarily (e.g., MAX_BYTES_PER_TRANSACTION, MAX_TRANSACTIONS_PER_PAYLOAD) and set to an artificially large value to anticipate future design space which are not always correct.
The progressive Merkle tree shape addresses these by:
Using a recursive tree structure that progressively grows to the actual leaf count with minimal overhead
Dropping the notion of a maximum capacity, relying instead on practical limits, e.g., SSZ’s 4 GB variable offset cap, network payload limits, gas limits, bounds on number of signatures.
Maintaining stable gindices for each element, ensuring provers remain valid as the leaf count changes.
Specification
The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “NOT RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in RFC 2119 and RFC 8174.
b: Merkleize the first up to num_leaves chunks as a binary tree using merkleize(chunks[:num_leaves], num_leaves).
This results in a 0-terminated sequence of binary subtrees with increasing leaf count. The deepest subtree is padded with zeroed chunks (virtually for memory efficiency).
Requires two-step queries (length then gindex), increasing latency and reorg risks.
Complicates proofs with semantic lookups.
Mixing in successor subtrees ensures predictable gindices and proof sizes.
Why not fixed-capacity lists?
List[type, N]:
Imposes arbitrary limits, hindering scalability.
Breaks stability when redefined.
Wastes hashes with padding (e.g., 1024-element capacity for a 1-item list). (only log(N) wasted hashes)
ProgressiveList[type] offers a scalable, efficient alternative.
Why are initial leaf count and scaling factors not exposed parameters?
Simplicity: Fixed values (initial leaf count 1, scaling factor 4) provide a sensible default that balances efficiency and usability, aligning with SSZ’s goal of simplicity.
Future Extensibility: If specific use cases demand different values, a future EIP could introduce parameterization. For now, fixed values reduce adoption barriers and align with the principle of “good enough” defaults.
Backwards Compatibility
The new SSZ types coexist with existing types without conflict and share their serialization logic.
See EIP assets, based on protolambda/remerkleable.
Security Considerations
Resource limits: The uint32 limit for variable-length offsets essentially introduces a ~4GB cap when including a ProgressiveList[type] or ProgressiveBitlist within another complex type, but practical limits (e.g., 10MB libp2p messages) apply. Implementations SHOULD enforce context-specific bounds.
Variable proof size: Recursive traversal may increase proof sizes for large indices, though logarithmic in list size due to the scaling factor.