EIP-7916: SSZ ProgressiveByteList

New SSZ type to improve efficiency for short lists

Abstract

This EIP introduces a new Simple Serialize (SSZ) type to make List[T, N] with large capacities N more efficient in cases where the list is much shorter than the capacity.

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.

ProgressiveByteList container

ProgressiveByteList[CAPACITY, COMMON_RATIO] is defined as a byte list container type that consists of multiple byte vectors of different size. The size of the first vector is 32 bytes (a single chunk) while the size of further vectors is growing according to a geometric sequence with the specified common ratio (a power of 2), with a potential exception for the last vector which might be smaller (but still a power of 2) according to the total number of chunks required for realizing the specified capacity. As shown on the figure below, in the Merkle hashing scheme the smaller vectors are close to the root, allowing less hashing and shorter proofs if the actual list is significantly smaller than the maximum capacity or only the first part of the list needs to be proven.

ProgressiveByteList[3000, 4]

       V4  V5
        \  /
     V3  \/
      \  /
   V2  \/
    \  /
 V1  \/
  \  /
   \/  LEN
    \  /
     \/
    ROOT

V1: ByteVector[32]
V2: ByteVector[128]
V3: ByteVector[512]
V4: ByteVector[2048]
V5: ByteVector[512]

Fig 1. Merkle hashing scheme of the ProgressiveByteList container

In this example a list with a capacity limit of 3000 is realized using 5 vectors. Note that the last vector is smaller than what would follow in the geometric sequence because the total size of 32+128+512+2048+512 is already enough to store 3000 bytes.

Rationale

ByteList definitions sometimes are defined with capacities that exceed their typical practical usage, to avoid limiting design space. For example, the Transaction type has a maximum capacity of 1 GB MAX_BYTES_PER_TRANSACTION, despite actual transactions often being below 1 KB. This difference results in at least 20 extra hashes for common cases, to offer a design space that is not practically viable.

With this EIP, common cases can be hashed more efficiently while not restricting the design space, and while also retaining stable generalized Merkle indices for each individual chunk of the ByteList.

Backwards Compatibility

The new SSZ type does not interfere with any existing types.

Security Considerations

None

Copyright

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Zsolt Felföldi (@zsfelfoldi), "EIP-7916: SSZ ProgressiveByteList [DRAFT]," Ethereum Improvement Proposals, no. 7916, March 2025. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7916.