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.

ProgressiveList[T]

       V4   0 (terminator)
        \  /
     V3  \/
      \  /
   V2  \/
    \  /
 V1  \/
  \  /
   \/  LEN
    \  /
     \/
    ROOT

V1: Vector[T, 1]
V2: Vector[T, 4]
V3: Vector[T, 16]
V4: Vector[T, 64]

• 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

def merkleize_progressive_list(chunks, base_size=1, scaling_factor=4):
    if len(chunks) <= base_size:
        return mix_in_aux(merkleize(chunks + [Bytes32()] * (base_size - len(chunks))), Bytes32())
    else:
        next_size = base_size * scaling_factor
        subtree = chunks[:base_size]
        successor = chunks[base_size:]
        subtree_root = merkleize(subtree)
        successor_root = merkleize_progressive_list(successor, next_size, scaling_factor)
        return mix_in_aux(subtree_root, successor_root)

ProgressiveByteList

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

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.

Security Considerations

• Resource limits: The uint32 length-prefix caps serialization of variable-length subsections at 4GB, 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.