EIP-7916: SSZ ProgressiveByteList

EIPs EIPs core
1

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.

1 Like
2
  • Added ProgressiveBitlist
  • Tree now grows to left instead of right
  • Fixed incorrect Bitvector notion in graphic: Unused chunks are padded with 0 chunks instead of default(T) chunks.
  • Simplified Merkleization code
3

Started an implementation tracker: https://pureth.guide/implementations-ssz/

4

image
image1280×607 108 KB

Received EIP-7916 feedback where some people slightly prefer changing to the Merkle tree layout in the right picture (while others slightly prefer staying on the left).

Arguments for left:

  • Easier implementation, as standard left-to-right DFS iteration visits deeper branches first. O(1) memory instead of O(log(N)), or simpler algo. Also easier formulas for handling gindices.

Arguments for right:

  • Later list indices are assigned a gindex further right in the tree than earlier list indices. Maybe makes incremental building (e.g., deposit contract snapshot style) a bit easier.

Same for both:

  • Hash count is the same. Proof size is the same.

Personally fine with either, but will lock it down by end of week so that implementation effort doesn’t get derailed.

5

Draft for Merkleizing to right: