SSZ ProgressiveList

Abstract

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.
• Unstable proofs: Modifying N across forks (e.g., MAX_ATTESTER_SLASHINGS_ELECTRA, MAX_ATTESTATIONS_ELECTRA) alters gindices, breaking downstream verifiers.

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.

Progressive Merkle tree

The SSZ Merkleization specification) is extended with a helper function:

• merkleize_progressive(chunks, num_leaves=1): Given ordered BYTES_PER_CHUNK-byte chunks:
  • The merkleization depends on the number of input chunks and is defined recursively:
    • If len(chunks) == 0: the root is a zero value, Bytes32().
    • Otherwise: compute the root using hash(a, b)
      • a: Recursively merkleize chunks beyond num_leaves using merkleize_progressive(chunks[num_leaves:], num_leaves * 4).
      • 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).

        root
         /\
        /  \
       /\   1: chunks[0 ..< 1]
      /  \
     /\   4: chunks[1 ..< 5]
    /  \
   /\  16: chunks[5 ..< 21]
  /  \
 0   64: chunks[21 ..< 85]

Depth	Added chunks	Total chunks	Total capacity (bytes)
0	0	0	0
1	1	1	32
2	4	5	160
3	16	21	672
4	64	85	2'720
5	256	341	10'912
6	1'024	1'365	43'680
7	4'096	5'461	174'752
8	16'384	21'845	699'040
9	65'536	87'381	2'796'192
10	262'144	349'525	11'184'800
11	1'048'576	1'398'101	44'739'232
12	4'194'304	5'592'405	178'956'960
13	16'777'216	22'369'621	715'827'872
14	67'108'864	89'478'485	2'863'311'520
15	268'435'456	357'913'941	11'453'246'112

ProgressiveList[type] and ProgressiveBitlist

Two new SSZ composite types) are defined:

• progressive list: ordered variable-length homogeneous collection
  • notation ProgressiveList[type], e.g. ProgressiveList[uint64]
• progressive bitlist: ordered variable-length collection of boolean values
  • notation ProgressiveBitlist

The new types are considered "variable-size".

For convenience we alias:

• ProgressiveByteList to ProgressiveList[byte]

The default value is defined as:

Type	Default Value
ProgressiveList[type]	[]
ProgressiveBitlist	[]

Serialization

Serialization, deserialization, and JSON mapping of ProgressiveBitlist are identical to Bitlist[N].

Serialization, deserialization, and JSON mapping of ProgressiveList[type] are identical to List[type, N].

Merkleization

The Merkleization definitions are extended.

• mix_in_length(merkleize_progressive(pack(value)), len(value)) if value is a progressive list of basic objects.
• mix_in_length(merkleize_progressive(pack_bits(value)), len(value)) if value is a progressive bitlist.
• mix_in_length(merkleize_progressive([hash_tree_root(element) for element in value]), len(value)) if value is a progressive list of composite objects.

Rationale

Why a recursive structure?

• Efficiency: Small lists use fewer hashes (e.g., a 3-item list in a 16-element subtree wastes fewer hashes than a 1024-element List[type, N]).
• Stability: Fixed subtree sizes ensure stable gindices, avoiding the need for dynamic depth adjustments or multiple queries.
• Scalability: Recursive subtrees allow arbitrary growth without a hardcoded limit, constrained only by practical limits (e.g., network payload limit, validation rules).

Why not dynamic depth?

Dynamic-depth Merkleization destabilizes gindices:

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

Test Cases

See ethereum/remerkleable.

Reference Implementation

See ethereum/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.

Copyright

Copyright and related rights waived via CC0.