EIP-7495 - SSZ StableContainer

Created 2023-08-18
Status Review
Category Core
Type Standards Track
Authors

New SSZ type to represent a flexible container with stable serialization and merkleization

Abstract

This EIP introduces two new Simple Serialize (SSZ) types to enable forward-compatible containers.

A StableContainer[N] extends an SSZ Container with stable merkleization and forward-compatible serialization even when individual fields are deprecated or new fields are introduced in the future.

Furthermore, Profile[B] is introduced to support specialized sub-types of StableContainer[N] while retaining the merkleization of the base type. This is useful, e.g., for fork-specific data structures that only use a subset of the base fields and/or when required base fields are known. Verifiers of Merkle proofs for these data structures will not break on new forks.

Motivation

Stable containers and profiles are currently not representable in SSZ. Adding support provides these benefits:

  1. Stable signatures: Signing roots derived from a StableContainer[N] never change. In the context of Ethereum, this is useful for transaction signatures that are expected to remain valid even when future updates introduce additional transaction fields. Likewise, the overall transaction root remains stable and can be used as a perpetual transaction ID.

  2. Stable merkle proofs: Merkle proof verifiers that check specific fields of a StableContainer[N] or Profile[B] do not need continuous updating when future updates introduce additional fields. Common fields always merkleize at the same generalized indices.

  3. Optional fields: Current SSZ formats do not support optional fields, prompting designs to use zero values instead. With StableContainer[N] and Profile[B], the SSZ serialization is compact; inactive 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.

Note: In this document, Optional[T] exclusively refers to Python's typing.Optional. Specifically, Optional[T] is NOT an SSZ type itself!

StableContainer[N]

Similar to the regular SSZ Container, StableContainer[N] defines an ordered heterogeneous collection of fields. N indicates the potential maximum number of fields to which it can ever grow in the future. N MUST be > 0.

All fields of a StableContainer[N] MUST be of of type Optional[T]. Such fields can either represent a present value of SSZ type T, or indicate absence of a value (indicated by None). The default value of an Optional[T] is None.

class Example(StableContainer[32]):
    a: Optional[uint64]
    b: Optional[uint32]
    c: Optional[uint16]

For the purpose of serialization, StableContainer[N] is always considered "variable-size" regardless of the individual field types.

Stability guarantees

The serialization and merkleization of a StableContainer[N] remains stable as long as:

JSON serialization

JSON serialization follows the canonical JSON mapping of SSZ Container.

Fields of type Optional[T] with a None value SHALL be omitted when serializing to JSON.

Binary serialization

Serialization of StableContainer[N] is defined similarly to the existing logic for Container. Notable changes are:

# Determine active fields
active_fields = Bitvector[N](([element is not None for element in value] + [False] * N)[:N])
active_values = [element for element in value if element is not None]

# Recursively serialize
fixed_parts = [serialize(element) if not is_variable_size(element) else None for element in active_values]
variable_parts = [serialize(element) if is_variable_size(element) else b"" for element in active_values]

# Compute and check lengths
fixed_lengths = [len(part) if part != None else BYTES_PER_LENGTH_OFFSET for part in fixed_parts]
variable_lengths = [len(part) for part in variable_parts]
assert sum(fixed_lengths + variable_lengths) < 2**(BYTES_PER_LENGTH_OFFSET * BITS_PER_BYTE)

# Interleave offsets of variable-size parts with fixed-size parts
variable_offsets = [serialize(uint32(sum(fixed_lengths + variable_lengths[:i]))) for i in range(len(active_values))]
fixed_parts = [part if part != None else variable_offsets[i] for i, part in enumerate(fixed_parts)]

# Return the concatenation of the active fields `Bitvector` with the active
# fixed-size parts (offsets interleaved) and the active variable-size parts
return serialize(active_fields) + b"".join(fixed_parts + variable_parts)

Deserialization

Deserialization of a StableContainer[N] starts by deserializing a Bitvector[N]. That value MUST be validated:

The rest of the data is deserialized same as a regular SSZ Container, consulting the Bitvector[N] to determine which fields are present in the data. Absent fields are skipped during deserialization and assigned None values.

Merkleization

The merkleization specification is extended with the following helper functions:

To merkleize a StableContainer[N], a Bitvector[N] is constructed, indicating active fields within the StableContainer[N], using the same process as during serialization.

Merkleization hash_tree_root(value) of an object value is extended with:

Profile[B]

Profile[B] also defines an ordered heterogeneous collection of fields, a subset of fields of a base StableContainer type B with the following constraints:

Serialization

Serialization of Profile[B] is similar to the one of its base StableContainer[N], except that the leading Bitvector is replaced by a sparse representation that only includes information about fields that are optional in Profile[B]. Bits for required fields of Profile[B] as well as the zero-padding to capacity N are not included. If there are no optional fields in Profile[B], the Bitvector is omitted.

Profile[B] is considered "variable-size" iff it contains any Optional[T] or any "variable-size" fields.

Merkleization

Merkleization of Profile[B] follows the merkleization of base type B.

# Defines the common merkleization format and a portable serialization format
class Shape(StableContainer[4]):
    side: Optional[uint16]
    color: Optional[uint8]
    radius: Optional[uint16]

# Inherits merkleization format from `Shape`, but is serialized more compactly
class Square(Profile[Shape]):
    side: uint16
    color: uint8

# Inherits merkleization format from `Shape`, but is serialized more compactly
class Circle(Profile[Shape]):
    color: uint8
    radius: uint16

Serialization examples:

Shape(side=0x42, color=1, radius=None)

Square(side=0x42, color=1)

Shape(side=None, color=1, radius=0x42)

Circle(radius=0x42, color=1)

While this serialization of Profile[B] is more compact, note that it is not forward-compatible and that context information that determines the underlying data type has to be indicated out of bands. If forward-compatibility is required, Profile[B] SHALL be converted to its base type B and subsequently serialized according to B.

Rationale

What are the problems solved by StableContainer[N]?

Current SSZ types are only stable within one version of a specification, i.e., one fork of Ethereum. This is alright for messages pertaining to a specific fork, such as attestations or beacon blocks. However, it is a limitation for messages that are expected to remain valid across forks, such as transactions or receipts. In order to support evolving the features of such perpetually valid message types, a new SSZ scheme needs to be defined. Furthermore, consumers of Merkle proofs may have a different software update cadence as Ethereum; an implementation should not break just because a new fork introduces unrelated new features.

To avoid restricting design space, the scheme has to support extension with new fields, obsolescence of old fields, and new combinations of existing fields. When such adjustments occur, old messages must still deserialize correctly and must retain their original Merkle root.

What are the problems solved by Profile[B]?

The forward-compatible merkleization of StableContainer may be desirable even in situations where only a single sub-type is valid at any given time, e.g., as determined by the fork schedule. In such situations, message size can be reduced and type safety increased by exchanging Profile[B] instead of the underlying base type. This can be useful, e.g., for consensus data structures such as BeaconState, to ensure that Merkle proofs for its fields remain compatible across forks.

Why not Union[T, U, V]?

There is combinatorial complexity when new optional features are introduced. For example, if there are three transaction types, and then priority fees are introduced as an optional feature, one has to define three additional transaction types to allow inclusion of a priority fee, raising the total to six transaction types. If, subsequently, optional access lists are introduced, that doubles again, to twelve transaction types.

Union also requires each participant of the network to know about all existing Union cases. For example, if the execution layer provides transactions via engine API as a Union, the consensus layer would also have to know about all concrete Union cases, even though it only wishes to package them and forward them. Using StableContainer[N] provides a more similar situation as JSON where the underlying type is determined based on the presence / absence of fields and their values.

Typically, the individual Union cases share some form of thematic overlap, sharing certain fields with each other. In a Union, shared fields are not necessarily merkleized at the same generalized indices. Therefore, Merkle proof systems would have to be updated each time that a new flavor is introduced, even when the actual changes are not of interest to the particular system.

Why not model Optional[T] as an SSZ type?

If Optional[T] is modeled as an SSZ type, each individual field introduces serialization and merkleization overhead. As an Optional[T] would be required to be "variable-size", lots of additional offset bytes would have to be used in the serialization. For merkleization, each individual Optional[T] would require mixing in a bit to indicate presence or absence of the value.

Additionally, every time that the number of fields reaches a new power of 2, the Merkle roots break, as the number of chunks doubles. The StableContainer[N] solves this by artificially extending the Merkle tree to N chunks regardless of the actual number of fields currently specified. Because N is constant across specification versions, the Merkle tree shape remains stable. The overhead of the additional empty placeholder leaves only affects serialization of the Bitvector[N] (1 byte per 8 leaves); the number of required hashes during merkleization only grows logarithmically with N.

Backwards Compatibility

StableContainer[N] and Profile[B] are new SSZ types and, therefore, do not conflict with other SSZ types currently in use.

Test Cases

See EIP assets.

Reference Implementation

See EIP assets, based on protolambda/remerkleable.

Security Considerations

None

Copyright

Copyright and related rights waived via CC0.