EIP-7495: SSZ ProgressiveContainer

SSZ type for forward-compatible containers

Metadata

Status: DraftStandards Track: CoreCreated: 2023-08-18

Authors

Etan Kissling (@etan-status), Cayman (@wemeetagain)

Requires

EIP-7916

Links

GitHub page Discussion on Ethereum Magicians

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.

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)`

A new SSZ composite types) is defined:

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

The default value is defined as:

Type	Default Value
`ProgressiveContainer(active_fields)`	`[default(type) for type in progressive_container]`

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.

Serialization

Serialization of ProgressiveContainer(active_fields) is identical to Container.

Deserialization

Deserialization of ProgressiveContainer(active_fields) is identical to Container.

JSON mapping

The canonical JSON mapping is updated:

SSZ	JSON	Example
`ProgressiveContainer(active_fields)`	object	`{ "field": ... }`

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.

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.

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.

`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.

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.