SSZ ProgressiveList
相关视频
正文
Abstract
This EIP 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 nestingList[type, N]
, e.g., in a design where each of up toX
transactions has up toY
access lists, each with up toZ
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 orderedBYTES_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 beyondnum_leaves
usingmerkleize_progressive(chunks[num_leaves:], num_leaves * 4)
.b
: Merkleize the first up tonum_leaves
chunks as a binary tree usingmerkleize(chunks[:num_leaves], num_leaves)
.
- If
- The merkleization depends on the number of input chunks and is defined recursively:
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
- notation
ProgressiveList[type]
, e.g.ProgressiveList[uint64]
- notation
- progressive bitlist: ordered variable-length collection of
boolean
values- notation
ProgressiveBitlist
- notation
The new types are considered "variable-size".
For convenience we alias:
ProgressiveByteList
toProgressiveList[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))
ifvalue
is a progressive list of basic objects.mix_in_length(merkleize_progressive(pack_bits(value)), len(value))
ifvalue
is a progressive bitlist.mix_in_length(merkleize_progressive([hash_tree_root(element) for element in value]), len(value))
ifvalue
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 EIP 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
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[type]
orProgressiveBitlist
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
Copyright and related rights waived via CC0.