SSZ CompatibleUnion

Abstract

This EIP introduces a new Simple Serialize (SSZ) type to represent unions with forward-compatible Merkleization: A given field is always assigned the same stable generalized index (gindex) across all type options.

Motivation

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.

If multiple versions of an SSZ container coexist at the same time, for example to represent transaction types, 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.

Compatible unions allow only type options to be used that provide stable gindex assignment across all of them.

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.

CompatibleUnion({selector: type})

A new SSZ composite type is defined:

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

Type	Default Value
CompatibleUnion({selector: type})	n/a (error)

The following types are considered 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.
• All other types are incompatible.

Serialization

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

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
• Incomplete data (less than 1 byte for selector)
• Corrupted or malformed serialized data
• Invalid serialization of inner types (delegated to inner type deserialization)

JSON mapping

The canonical JSON mapping is updated:

SSZ	JSON	Example
CompatibleUnion({selector: type})	selector-object	{ "selector": string, "data": type }

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 a helper function:

• 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_selector(hash_tree_root(value.data), value.selector) if value is of compatible union type.

Rationale

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.

Why not field collections?

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 backwards compatible operation. However, new options can be introduced, and existing options dropped, without breaking verifiers. Therefore, CompatibleUnion has to be introduced early on wherever future design extensions are anticipated, even when only a single type option is used.

Backwards Compatibility

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-specs releases contain random tests in tests/general/phase0/ssz_generic, generated according to a format defined in tests/format/ssz_generic.

Reference Implementation

See ethereum/remerkleable.

Security Considerations

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.