EIP-7916: SSZ ProgressiveList

Abstract

---

This EIP introduces a new Simple Serialize (SSZ) type, ProgressiveList[T], to represent lists of arbitrary length with stable merkleization. Unlike the existing List[T, N] type, which imposes a fixed capacity N, ProgressiveList[T] supports unbounded growth using a recursive tree structure during merkleization to efficiently handle lists of any size while maintaining stable generalized indices (gindices) for individual elements. This enables reduced hash overhead for small lists and avoids arbitrary predefined limits.

Motivation

---

Current SSZ List[T, 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.
• Arbitrary Limits: Fixed limits such as N are often chosen arbitrarily (e.g., MAX_BYTES_PER_TRANSACTION, MAX_TRANSACTIONS_PER_PAYLOAD), introducing unnecessary bound checks and restricting design flexibility for future state transitions.
• Unstable proofs: Modifying N across forks (e.g., MAX_ATTESTER_SLASHINGS_ELECTRA, MAX_ATTESTATIONS_ELECTRA) alters gindices, breaking downstream verifiers.

ProgressiveList[T] addresses these by:

• Using a recursive structure where each subtree has a fixed size, with larger lists extending into additional subtrees, reducing hash overhead for small lists.
• Eliminating the need for an explicit upper bound, 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 elements, ensuring provers remain valid as the list grows.

This is particularly valuable for execution-layer (EL) data like receipt logs and calldata, where list sizes vary widely, and for consensus-layer (CL) structures where unbounded growth avoids artificial caps.

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.

ProgressiveList[T]

ProgressiveList[T] defines an ordered, homogeneous collection of elements of type T, where T is any valid SSZ type (e.g., uint64, Container, etc.).

Serialization

Serialization of ProgressiveList[T] is identical to List[T, N].

Merkleization

ProgressiveList[T] is represented as a recursive Merkle tree following this process:

• Pack the list into chunks, either by pack or by hash_tree_root of its elements, depending on whether the element type is basic or composite. (This matches packing behavior of List)
• Merkleize the chunks into subtrees. This process repeats as needed, with each subsequent subtree’s size being the previous size multiplied by the scaling factor. E.g., the first subtree has 1 chunk, next has 4, then 16, 64, etc.
• Each subtree is a fixed-size Vector of chunks, with the next subtree’s root mixed in if present. The last subtree is padded to size with zeros, with a zero mixed in.
• The final root has the total length of the list mixed in.

• mix_in_length(merkleize_progressive_list(pack(value)), len(value)) if value is an ProgressiveList[T] of basic objects
• mix_in_length(merkleize_progressive_list([hash_tree_root(element) for element in value]), len(value)) if value is a ProgressiveList[T] of composite objects

#	Layer size (chunks)	Total capacity (chunks)
1	1	1
2	4	5
3	16	21
4	64	85
5	256	341
6	1'024	1'365
7	4'096	5'461
8	16'384	21'845
9	65'536	87'381
10	262'144	349'525
11	1'048'576	1'398'101
12	4'194'304	5'592'405
13	16'777'216	22'369'621
14	67'108'864	89'478'485
15	268'435'456	357'913'941

ProgressiveByteList

For convenience ProgressiveByteList is defined as an alias to ProgressiveList[byte].

#	Layer size (bytes)	Total capacity (bytes)
1	32	32
2	128	160
3	512	672
4	2'048	2'720
5	8'192	10'912
6	32'768	43'680
7	131'072	174'752
8	524'288	699'040
9	2'097'152	2'796'192
10	8'388'608	11'184'800
11	33'554'432	44'739'232
12	134'217'728	178'956'960
13	536'870'912	715'827'872
14	2'147'483'648	2'863'311'520
15	8'589'934'592	11'453'246'112

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[T, 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[T, 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[T] offers a scalable, efficient alternative.

Why Are Base Size and Scaling Factors Not Exposed Parameters?

• Simplicity: Fixed values (base size 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

---

ProgressiveList[T] is a new SSZ type, coexisting with List[T, N] and other types without conflict. Its List-equivalent serialization ensures compatibility with existing serializers.

Test Cases

---

See EIP assets.

Reference Implementation

---

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[T] 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 scaling.

Copyright

---

Copyright and related rights waived via CC0.