We were looking at the latest spec and it didn't have much background information or explanation on what SSZ is trying to achieve. What are the key goals of SSZ?
Examples of its serialization and Merkleization advantages would be very helpful as this may be a canonical question.
SimpleSerialize (SSZ) is the canonical serialization format used in Eth2. The SSZ specification instructs the reader on how to perform two distinct tasks:
BeaconBlock or a BeaconState) as strings of bytes that can be sent over the network or stored in a database.For each I will state the goals (or my understanding of them) and also an example for each of these tasks.
As far as I know, there was never a canonical statement of the goals of SSZ. However, I think it's fair to say that these are some of the goals:
BeaconBlock. With this property, the SSZ encoding forms an "identity" for that instance.I will provide a simple example and also recommend the reader to @protolambda's SSZ encoding diagram.
Lets assume this imaginary data structure since none of the structures in the Eth2 spec are great for this example:
class Example
id: uint64,
bytes: List[uint8, 64]
next: uint64
The Example has two 64-bit integer fields (id and next) and a bytes field that can hold 0-64 bytes. Lets instantiate it:
my_example = Example(id=42, bytes=List[0, 1, 2], next=43)
Now, lets look at the output of serialize(my_example):
# serialize(my_example)
#
# Note: this is a single byte-array split over four lines for readability.
[
42, 0, 0, 0, # The little-endian encoding of `id`, 42.
12, 0, 0, 0, # The "offset" that indicates where the variable-length value of `bytes` starts (little-endian 12).
43, 0, 0, 0, # The little-endian encoding of `next`, 43.
0, 1, 2 # The value of the `bytes` field.
]
As we can see, fields are encoded in the order that they are defined. "Fixed-size" items are simply serialized right into the buffer, whilst "variable-sized" items are first serialized as an "offset" that points to the start of the actual value of the the item. The actual values (not offsets) of variable-size items are appended after all the fixed-size items and offsets have been appended.
Eth2 does not just use a simple SHA256 hash of encoding of a block to identify it (e.g., sha256(serialize(block)). Instead, all hashes in Eth2 are Merkle-roots.
The decision to use Merkle-roots for all hashes was made so that light clients and execution environments can use Merkle-proofs to learn about parts of the Eth2 state. For example, if a light client has a trusted 32-byte hash of some block root, I can make a succinct, cryptographic proof to that light client that validator n has a balance of x.
However, the decision to use Merkle-roots as the canonical hash has a significant computational overhead. The syncing bottle-neck in Lighthouse (the client I work on) is performing these Merkle-hashes. Some of these routines take tens of milliseconds when a simple sha256(serialize(block)) would take microseconds (that's millions of times slower).
So, I would say the goal of the Merkleization scheme is to ensure that constrained environments (light clients, execution environments, eth1, etc.) can have access to light-weight proofs which they can use to make important decisions.
Let's use the previous Example type and also the my_example instantiation. Again, I suggest a diagram by @protolambda: SSZ hash-tree-root and merklization.
To aid in the example, we define hash_concat(a, b) which returns the SHA256 hash of the concatenation of a and b. E.g., hash_concat([1], [2]) == hash([1, 2]).
First, we determine the leaves of the Example Merkle tree:
# id: little-endian 42, right-0-padded to 32 bytes.
leaf_0 = [42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# bytes: when a list is hashed, you first hash the list values (right-0-padded to the next multiple of 32) along with the little-endian encoding of the list length (aka., "mixing in the length").
leaf_1 = hash_concat(
[0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[3, 0, 0, 0]
)
# id: little-endian 43, right-0-padded to 32 bytes.
leaf_2 = [43, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Now, we hash the leaves into the middle-layer of the Merkle tree:
# Hash the concatenation of `id` and `bytes`.
node_1 = hash_concat(leaf_0, leaf_1);
# Hash the concatentation of `next` and a "zero leaf" (32 zero-bytes), since there is no fourth element.
node_2 = hash_concat(leaf_2, [0; 32])
Finally, we can find the root of this Merkle tree with root = hash_concat(node_1, node_2).
Ultimately, we have produced a nested Merkle tree that looks like this:
root
|
-----------------
/ \
node_1 node_2
| |
------ -----------
/ \ / \
id bytes_root next ZERO_LEAF
|
-------
/ \
bytes len(bytes)
