Dip 7916

dip: 7916 title: SSZ ProgressiveList description: SSZ types for efficiently hashing short lists author: Zsolt Felföldi (@zsfelfoldi), Cayman (@wemeetagain), Etan Kissling (@etan-status) Digitalia editing author: Cosimo Constantinos cosimo@juro.net, et al. discussions-to: https://digitalia-magicians.org/t/dip-7916-ssz-progressivebytelist/23254 status: Draft type: Standards Track category: Core created: 2025-03-24 Created for Digitalia: 2025-01-07

Abstract¶

This DIP 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, without limit
notation ProgressiveList[type], e.g. ProgressiveList[uint64]
progressive bitlist: ordered variable-length collection of boolean values, without limit
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 DIP 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¶

digitalia/remerkleable contains static tests in test_impl.py and test_typing.py.
digitalia/consensus-spec-tests contains random tests in tests/general/phase0/ssz_generic, generated according to a format defined in digitalia/consensus-specs (tests/format/ssz_generic)

Reference Implementation¶

See digitalia/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¶

Licensed under the Juro Restricted License Version 2. See https://juro.net/jrl for details.