EIP-7495: SSZ ProgressiveContainer

SSZ type for forward-compatible containers

Abstract

This EIP introduces a new Simple Serialize (SSZ) type to represent containers with forward-compatible Merkleization: A given field is always assigned the same stable generalized index (gindex) even when different container versions append new fields or drop existing fields.

Motivation

SSZ containers are frequently versioned, for example across fork boundaries. When the number of fields reaches a new power of two, or a field is removed or replaced with one of a different type, the shape of the underlying Merkle tree changes, breaking verifiers of Merkle proofs for these containers. Deploying a new verifier may involve security councils to upgrade smart contract logic, or require firmware updates for embedded devices. This effort is needed even when no semantic changes apply to the fields that the verifier is interested in.

Further, if multiple versions of an SSZ container coexist at the same time, for example to represent transaction profiles, the same field may be assigned to a different gindex in each version. This unnecessarily complicates verifiers and introduces a maintenance burden, as the verifier has to be kept up to date with version specific field to gindex map.

Progressive containers address these shortcomings by:

• Using the progressive Merkle tree structure to progressively grow to the actual field count with minimal overhead, ensuring provers remain valid as the field count changes.
• Assigning stable gindices for each field across all versions by allowing gaps in the Merkle tree where a field is absent.
• Serializing in a compact form where absent fields do not consume space.

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.

ProgressiveContainer(active_fields)

Two new SSZ composite types) are defined:

• progressive container: ordered heterogeneous collection of values with stable Merkleization
  • python dataclass notation with key-type pairs, e.g.

  class Square(ProgressiveContainer(active_fields=[1, 0, 1])):
      side: uint16  # Merkleized at field index #0 (location of first 1 in `active_fields`)
      color: uint8  # Merkleized at field index #2 (location of second 1 in `active_fields`)
  
  class Circle(ProgressiveContainer(active_fields=[0, 1, 1])):
      radius: uint16  # Merkleized at field index #1 (location of first 1 in `active_fields`)
      color: uint8  # Merkleized at field index #2 (location of second 1 in `active_fields`)
  

• compatible union: union type containing one of the given subtypes with compatible Merkleization
  • notation CompatibleUnion({selector: type}), e.g. CompatibleUnion({1: Square, 2: Circle})

Compatible unions are always considered “variable-size”, even when all type options share the same fixed length.

The default value is defined as:

The following types are considered illegal:

• ProgressiveContainer with no fields are illegal.
• ProgressiveContainer with an active_fields configuration of more than 256 entries are illegal.
• ProgressiveContainer with an active_fields configuration ending in 0 are illegal.
• ProgressiveContainer with an active_fields configuration with a different count of 1 than fields are illegal.
• CompatibleUnion({}) without any type options are illegal.
• CompatibleUnion({selector: type}) with a selector outside uint8(1) through uint8(127) are illegal.
• CompatibleUnion({selector: type}) with a type option that has incompatible Merkleization with another type option are illegal.

Compatible Merkleization

• Types are compatible with themselves.
• byte is compatible with uint8 and vice versa.
• Bitlist[N] are compatible if they share the same capacity N.
• Bitvector[N] are compatible if they share the same capacity N.
• List[type, N] are compatible if type is compatible and they share the same capacity N.
• Vector[type, N] are compatible if type is compatible and they share the same capacity N.
• ProgressiveList[type] are compatible if type is compatible.
• Container are compatible if they share the same field names in the same order, and all field types are compatible.
• ProgressiveContainer(active_fields) are compatible if all 1 entries in both type’s active_fields correspond to fields with shared names and compatible types, and no other field name is shared across both types.
• CompatibleUnion are compatible with each other if all type options across both CompatibleUnion are compatible, and if shared selector values refer to the same type.
• All other types are incompatible.

Serialization

Serialization of ProgressiveContainer(active_fields) are identical to Container.

A value as CompatibleUnion({selector: type}) has properties value.data with the contained value, and value.selector which indexes the selected type option.

return value.selector.to_bytes(1, "little") + serialize(value.data)

Deserialization

Deserialization of ProgressiveContainer(active_fields) is identical to Container.

For CompatibleUnion, the deserialization logic is updated:

• In the case of compatible unions, the first byte of the deserialization scope is deserialized as type selector, the remainder of the scope is deserialized as the selected type.

The following invalid input needs to be hardened against:

• An out-of-bounds type selector in a CompatibleUnion

JSON mapping

The canonical JSON mapping is updated:

CompatibleUnion is encoded as an object with a selector and data field, where the contents of data change according to the selector.

Merkleization

The SSZ Merkleization specification is extended with two helper functions:

• get_active_fields(value), where value is of type ProgressiveContainer(active_fields): return active_fields.
• mix_in_active_fields: Given a Merkle root root and an active_fields configuration return hash(root, pack_bits(active_fields)). Note that active_fields is restricted to ≤ 256 bits.
• mix_in_selector: Given a Merkle root root and a type selector selector ("uint8" serialization) return hash(root, selector).

The Merkleization definitions are extended.

• mix_in_active_fields(merkleize_progressive([hash_tree_root(element) for element in value]), get_active_fields(value)) if value is a progressive container.
• mix_in_selector(hash_tree_root(value.data), value.selector) if value is of compatible union type.

Rationale

Why is active_fields limited to 256 bits?

256 bits (1 word) allows the mix-in to be simple, consistent with the length mix-in for lists, and is practically sufficient. An alternate design with a ProgressiveBitlist mix-in was explored, however deemed too over-engineered as it it would effectively require introducing caches to pre-compute the mix-in’s hash_tree_root to avoid repeated computations, and also makes verifier logic more complex than necessary.

Even though the 256 field limit includes all fields (including deprecated ones), it is unlikely that many progressive containers come close to reach 256 fields (BeaconState currently reaches around 40 fields). If that happens, one can add a more field with a nested ProgressiveContainer.

Why is empty ProgressiveContainer an illegal type?

It would result in 0-length serialization, meaning that the length of a list of such a container cannot be determined from the serialization.

Why CompatibleUnion?

Certain types, e.g., transactions, allow multiple variants carving out slightly different feature sets. Merkleization equivalence is still desirable, as it allows verifiers to check common fields across variants. These types should still efficiently deserialize into one of their possible variants corresponding to its known tree shape. In programming languages, this is typically achieved by tagged unions.

An alternative design was explored where the active_fields bitvector was emitted. While that works in principle, it becomes very inefficient to parse when ProgressiveContainer are nested, as the parser cannot immediately determine the overall tree shape. Further, the bitvector makes every single nesting layer variable-length, adding a lot of overhead to the serialized format.

With CompatibleUnion, a tag is emitted that tells the parser early on what to expect, including for nested fields.

Note that wrapping a field in a CompatibleUnion is not a backward compatible operation. However, new options can be introduced, and existing options dropped, without breaking verifiers. Therefore, CompatibleUnion has to be introduced earlyon wherever future design extensions are anticipated, even when only a single type option is used.

Why are CompatibleUnion selectors limited to 1 ... 127?

Reserving 0 prevents issues with incomplete initialization, and can possibly be used in a future EIP to denote optionality.

Reserving selectors above 127 (i.e., highest bit is set) enables future backwards compatible extensions.

The range 1 ... 127 is sufficient to satisfy current demand.

Optional[type]?

Introducing Optional is not required by any current functionality and is deferred to a future EIP.

The active_fields bitvector can be updated to also indicate optionality. Further, serialization for sparse lists should be explored.

Backwards Compatibility

ProgressiveContainer(active_fields) is a new SSZ type and does not conflict with existing types.

CompatibleUnion({selector: type}) is an alternative to an earlier union proposal. However, it has only been used in deprecated specifications. Portal network also uses a union concept for network types, but does not use hash_tree_root on them, and could transition to the new compatible union proposal with a new networking version.

Test Cases

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

Reference Implementation

See ethereum/remerkleable.

Security Considerations

Light client based verifiers and smart contracts (e.g., based on EIP-4788) do not update at the same cadence as Ethereum. If a future fork removes a field from a ProgressiveContainer(active_fields), the active_fields mix-in enables such verifiers to distinguish absent fields from 0 values. Without active_fields, the hash_tree_root for these cases would collide.

For CompatibleUnion({selector: type}), the selector mix-in guarantees a unique hash_tree_root if multiple type options refer to the same Merkle tree shape, or also if multiple type options solely differ in the element type of a List[type, N] or ProgressiveList[type] field (as the hash_tree_root of any empty list does not depend on the type). Without the selector, such cases would either have to be defined as illegal types, or handled by the application logic (e.g., by mixing it into the signing root, or by encoding the element type into a different field).

Copyright

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Etan Kissling (@etan-status), Cayman (@wemeetagain), "EIP-7495: SSZ ProgressiveContainer [DRAFT]," Ethereum Improvement Proposals, no. 7495, August 2023. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7495.