EIP-7916 SSZ Progressive List (SSZ ProgressiveList)
No call decision · Scaling & data · EIP status Review · created 2025-03-24
Adds new SSZ types, ProgressiveList[type] and ProgressiveBitlist, which grow to match the actual number of elements without a capacity cap. This reduces hash computation for short lists and keeps each element's proof position unchanged as the list grows longer.
Why it is needed
The current SSZ list type, List[type, N], requires a maximum capacity N to be fixed in advance. In practice, however, actual data is usually far shorter than the cap, so empty slots are padded with zeros and hashed anyway, which is wasteful. When lists are nested inside lists, as with transaction lists, the waste grows even larger. Also, N values such as MAX_BYTES_PER_TRANSACTION are arbitrarily large numbers chosen with future design headroom in mind, so their justification is weak. If N is changed at a fork, the position each element occupies in the tree (gindex, the generalized index) changes, breaking external verification code that validated proofs using that position. This EIP discards the notion of a capacity cap and introduces a Merkle tree shape that grows progressively to match the actual number of elements, addressing all three problems together.
What changes
Today
- Each list fixes a maximum capacity N in advance and hashes even the mostly unused empty space, padded with zeros
- N is set arbitrarily large, giving it weak design justification, and the cap may turn out to be wrong
- Changing N at a fork changes an element's tree position (gindex), breaking existing proof verifiers
After EIP-7916
- The tree grows only to match the actual number of elements by concatenating subtrees of 1, 4, and 16 leaves
- Relies only on practical constraints such as network payload limits and gas limits, instead of a maximum capacity
- Even if the list length changes, the same chunk always has the same gindex, so proofs remain stable
Who is affected
- Client teams: The SSZ library needs to implement merkleize_progressive and two new types. The serialization logic is the same as the existing List and Bitlist, so it can be reused.
- Proof-based app and light client developers: Since the gindex is fixed regardless of list length or fork, the problem of merkle proof verification code breaking at every fork disappears.
- Spec designers and researchers: When designing new data structures, there is no longer a need to pick an arbitrary maximum capacity constant.
- Ordinary users: There is no directly noticeable change, but it becomes a foundation for reducing the hashing burden on nodes.
In depth
The merkleize_progressive helper function
Adds merkleize_progressive(chunks, num_leaves=1) to the SSZ merkleization spec. The definition is recursive. If len(chunks) == 0, the root is the zero value Bytes32(). Otherwise, the root is computed as hash(a, b), where a is the leading up to num_leaves chunks binary-tree merkleized via merkleize(chunks[:num_leaves], num_leaves), and b is the remaining chunks merkleized recursively via merkleize_progressive(chunks[num_leaves:], num_leaves * 4). The result takes the shape of a chain of binary subtrees whose leaf counts grow 4x at a time, 1, 4, 16, 64, terminating in 0. Only the deepest subtree is padded with zero chunks, and this padding is handled virtually for memory efficiency.
Capacity by depth
Capacity grows to 1 chunk (32 bytes) at depth 1, a cumulative 5 (160 bytes) at depth 2, 21 (672 bytes) at depth 3, and reaches a cumulative 357,913,941 chunks, 11,453,246,112 bytes, at depth 15. Since the number of subtree leaves added at each step grows 4x, depth increases only logarithmically with respect to list size. Because the tree shape is fixed regardless of length, a given chunk index always stays at the same gindex as the list grows.
New type definitions and serialization
Two new composite types are defined. ProgressiveList[type] is a variable-length homogeneous collection with no upper bound (e.g. ProgressiveList[uint64]), and ProgressiveBitlist is a boolean collection with no upper bound. Both are classified as variable-size, with a default value of an empty list []. For convenience, ProgressiveByteList is defined as an alias for ProgressiveList[byte]. Serialization, deserialization, and JSON mapping are each identical to the existing List[type, N] and Bitlist[N], so the implementations can be reused as is. They coexist without conflicting with the existing types.
Merkleization rules
The merkleization definition is extended to three cases. For a progressive list of basic objects, it is mix_in_length(merkleize_progressive(pack(value)), len(value)); for a progressive bitlist, mix_in_length(merkleize_progressive(pack_bits(value)), len(value)); and for a progressive list of composite objects, the hash_tree_root of each element is collected and computed as mix_in_length(merkleize_progressive([hash_tree_root(element) for element in value]), len(value)). As with the existing List, the structure of mixing the length into the root is preserved, with only the inner merkleization function changed to the progressive approach.
Why this design
The recursive structure lets small lists use fewer hashes (a list of 3 elements wastes less than a List with a capacity of 1024), subtree size is fixed so the gindex stays stable, and it can grow without an upper bound. The alternative, dynamic-depth merkleization, was excluded because it requires a two-step query, first looking up the length and then looking up the gindex, which increases latency and reorg risk and complicates proofs. The initial leaf count of 1 and the growth factor of 4 are fixed rather than exposed as parameters, a choice made to preserve simplicity and lower the barrier to adoption; it is noted that they could be parameterized in a later EIP if needed.
Security considerations
Even though the type itself has no upper bound, it cannot grow infinitely. When placed inside another composite type, the uint32 limit on variable-length offsets effectively imposes a cap of about 4GB, and in practice more realistic limits such as 10MB libp2p messages apply first. Implementations SHOULD enforce size limits appropriate to context. Also, elements at larger indices require descending further through the recursion, which can increase proof size, but thanks to the growth factor of 4 this stays logarithmic with respect to list size.
Current status
This EIP is in Review status. The specification is not yet finalized and details may change. Tests include static tests in ethereum/remerkleable's test_impl.py and test_typing.py, and randomized tests in tests/general/phase0/ssz_generic of the ethereum/consensus-specs release. A reference implementation is also available in ethereum/remerkleable. There is no record of a call decision on including it in a specific fork.