This is a work in progress describing typing, serialization and Merkleization of Ethereum 2.0 objects.
| Name | Value | Description |
|---|---|---|
BYTES_PER_CHUNK |
32 |
Number of bytes per chunk. |
BYTES_PER_LENGTH_OFFSET |
4 |
Number of bytes per serialized length offset. |
BITS_PER_BYTE |
8 |
Number of bits per byte. |
"uintN":N-bit unsigned integer (whereN in [8, 16, 32, 64, 128, 256])"bool":TrueorFalse
- container: ordered heterogeneous collection of values
- key-pair curly bracket notation
{}, e.g.{"foo": "uint64", "bar": "bool"}
- key-pair curly bracket notation
- vector: ordered fixed-length homogeneous collection of values
- angle bracket notation
[type, N], e.g.["uint64", N]
- angle bracket notation
- list: ordered variable-length homogeneous collection of values
- angle bracket notation
[type], e.g.["uint64"]
- angle bracket notation
We recursively define "variable-size" types to be lists and all types that contains a variable-size type. All other types are said to be "fixed-size".
For convenience we alias:
"byte"to"uint8"(this is a basic type)"bytes"to["byte"](this is not a basic type)"bytesN"to["byte", N](this is not a basic type)
The default value of a type upon initialization is recursively defined using 0 for "uintN", False for "bool", and [] for lists.
We recursively define the serialize function which consumes an object value (of the type specified) and returns a bytestring of type "bytes".
Note: In the function definitions below (
serialize,hash_tree_root,signing_root,is_variable_size, etc.) objects implicitly carry their type.
assert N in [8, 16, 32, 64, 128, 256]
return value.to_bytes(N // 8, "little")assert value in (True, False)
return b"\x01" if value is True else b"\x00"# Reccursively serialize
fixed_parts = [serialize(element) if not is_variable_size(element) else None for element in value]
variable_parts = [serialize(element) if is_variable_size(element) else b"" for element in value]
# 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(sum(fixed_lengths + variable_lengths[:i])) for i in range(len(value))]
fixed_parts = [part if part != None else variable_offsets[i] for i, part in enumerate(fixed_parts)]
# Return the concatenation of the fixed-size parts (offsets interleaved) with the variable-size parts
return b"".join(fixed_parts + variable_parts)Because serialization is an injective function (i.e. two distinct objects of the same type will serialize to different values) any bytestring has at most one object it could deserialize to. Efficient algorithms for computing this object can be found in the implementations.
We first define helper functions:
pack: Given ordered objects of the same basic type, serialize them, pack them intoBYTES_PER_CHUNK-byte chunks, right-pad the last chunk with zero bytes, and return the chunks.merkleize: Given orderedBYTES_PER_CHUNK-byte chunks, if necessary append zero chunks so that the number of chunks is a power of two, Merkleize the chunks, and return the root.mix_in_length: Given a Merkle rootrootand a lengthlength("uint256"little-endian serialization) returnhash(root + length).
We now define Merkleization hash_tree_root(value) of an object value recursively:
merkleize(pack(value))ifvalueis a basic object or a vector of basic objectsmix_in_length(merkleize(pack(value)), len(value))ifvalueis a list of basic objectsmerkleize([hash_tree_root(element) for element in value])ifvalueis a vector of composite objects or a containermix_in_length(merkleize([hash_tree_root(element) for element in value]), len(value))ifvalueis a list of composite objects
Let value be a self-signed container object. The convention is that the signature (e.g. a "bytes96" BLS12-381 signature) be the last field of value. Further, the signed message for value is signing_root(value) = hash_tree_root(truncate_last(value)) where truncate_last truncates the last element of value.