⚠️ Review Standards Track: Core

EIP-7495: SSZ StableContainer

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

Authors	Etan Kissling (@etan-status)
Created	2023-08-18

This EIP is in the process of being peer-reviewed. If you are interested in this EIP, please participate using this discussion link.

Abstract
Motivation
Specification
Rationale
Backwards Compatibility
Test Cases
Reference Implementation
Security Considerations
Copyright

Abstract

This EIP introduces a new Simple Serialize (SSZ) type to represent StableContainer[N] values.

A StableContainer[N] is an SSZ Container with stable serialization and merkleization even when individual fields become optional or new fields are introduced in the future.

Motivation

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

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.
Stable merkle proofs: Merkle proof verifiers that check specific fields of a StableContainer[N] do not need continuous updating when future updates introduce additional fields. Common fields always merkleize at the same generalized indices.
Compact serialization: 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.

Type definition

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.

As part of a StableContainer[N], fields of type Optional[T] MAY be defined. 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: uint64
    b: Optional[uint32]
    c: 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:

The maximum capacity N does not change
The order of fields does not change
New fields are always added to the end
Required fields remain required T, or become an Optional[T]
Optional fields remain Optional[T], or become a required T

When an optional field becomes required, existing messages still have stable serialization and merkleization, but will be rejected on deserialization if not present.

Serialization

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

A Bitvector[N] is constructed, indicating active fields within the StableContainer[N]. For required fields T and optional fields Optional[T] with a present value (not None), a True bit is included. For optional fields Optional[T] with a None value, a False bit is included. The Bitvector[N] is padded with False bits up through length N
Only active fields are serialized, i.e., fields with a corresponding True bit in the Bitvector[N]
The serialization of the Bitvector[N] is prepended to the serialized active fields
If variable-length fields are serialized, their offsets are relative to the start of serialized active fields, after the Bitvector[N]

def is_active_field(element):
    return not is_optional(element) or element is not None

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

# 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:

For each required field, the corresponding bit in the Bitvector[N] MUST be True
For each optional field, the corresponding bit in the Bitvector[N] is not restricted
All extra bits in the Bitvector[N] that exceed the number of fields MUST be False

The rest of the data is deserialized same as a regular SSZ Container, consulting the Bitvector[N] to determine what optional 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:

chunk_count(type): calculate the amount of leafs for merkleization of the type.
- StableContainer[N]: always N, regardless of the actual number of fields in the type definition
mix_in_aux: Given a Merkle root root and an auxiliary SSZ object root aux return hash(root + aux).

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:

mix_in_aux(merkleize(([hash_tree_root(element) if is_active_field(element) else Bytes32() for element in value.data] + [Bytes32()] * N)[:N]), hash_tree_root(value.active_fields)) if value is a StableContainer[N].

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.

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.

Why not `Union[T, U, V]`?

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.

Furthermore, SSZ Union types are currently not used in any final Ethereum specification and do not have a finalized design themselves. The StableContainer[N] serializes very similar to current Union[T, U, V] proposals, with the difference being a Bitvector[N] as a prefix instead of a selector byte. This means that the serialized byte lengths are comparable.

Why not a `Container` full of `Optional[T]`?

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] is a new SSZ type and does 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

Citation

Please cite this document as:

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