EIP-7916: SSZ ProgressiveList
New SSZ type to improve efficiency for short lists
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 byhash_tree_root
of its elements, depending on whether the element type is basic or composite. (This matches packing behavior ofList
) - 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))
ifvalue
is anProgressiveList[T]
of basic objectsmix_in_length(merkleize_progressive_list([hash_tree_root(element) for element in value]), len(value))
ifvalue
is aProgressiveList[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 aProgressiveList[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.