# Lodestar SSZ Design Doc

### Types

SSZ defines a set of types that can be composed to build application-level datatypes.

##### Uint
- uints have a fixed bytelength of 1, 2, 4, 8, 16, or 32
##### Boolean
- true / false
##### List
- elements must be of a single type
- lists have a limit, a max number of elements
##### Vector
- elements must be of a single type
- vectors have a fixed length
##### Container
- collection of key-value pairs
- fixed list of keys (their order is specified)
- each value has a specific type
##### BitList
- list of bits, can be treated as a list of booleans
##### BitVector
- vector of bits, can be treated as a vector of booleans

type SSZType =
  Uint | Boolean |
  List<SSZType> | Vector<SSZType> | RecordLike<string, SSZType> | BitList | BitVector;

We can imagine a `Type` interface/class that gives us a nice place to store type specifics and methods.

interface Type {...}
class UintType implements Type {...}

const Uint32 = new UintType({byteLength: 4});

### Operations

SSZ-typed datastructures can be operated on in several different ways.
##### Serialization / Deserialization
- data can be unambiguously serialized into a bytestring
##### Hash Tree Root / Root Expansion
- heirarchical data can be mapped into a merkle tree with stable indices for each data field
- data fields corresponding to merkle tree roots can be 'expanded' into their full or partial typed data
##### Get / Set field/index values
- heirarchical data can be fetched by field or index
##### Clone / Equals
- data can be relied on to be well-typed
- data can be copied, new values can be created from defaults, equality between values of the same type can be established

A type can provide methods for these operations.

interface Type<T> {
    hashTreeRoot(value: T): Uint8Array;
    serialize(value: T): Uint8Array;
    deserialize(data: Uint8Array, options: BackingOptions): T;
    defaultValue(options: BackingOptions): T;
    createValue(value: any, options: BackingOptions): T;
    clone(value: T, options: BackingOptions): T;
    equals(a: T, b: T): boolean;
}

Note the type must be given "backing options" for operations that create a new value.

In some cases, these operations may be methods on the value itself.

interface SSZValue<T> {
    hashTreeRoot(): Uint8Array;
    serialize(): Uint8Array;
    clone(): SSZValue<T>;
    equals(other: SSZValue<T>): boolean;
    // get and set
    [fieldOrIndex: string | number]: SSZValue<T[keyof T]>;
}

### Backings

The ssz value's "backing" is the data structure that is to be interpreted as a certain type via type information.

In Eth2, ssz data is used in many different places, for many different purposes. The form/backing the data takes depends on the usecase at hand.
Some examples:
- the _structural_ form is currently used for application-level logic
- eg: the beacon state transition requires lookups for eg: `block.body.deposits[i]`
- the _merkle tree_ form is used to generate/consume proofs
- eg: server X uses a merkle tree to generate a multiproof for client X
- eg: client Y receives a proof, corresponding to a partial merkle tree form of a BeaconBlock and must interpret the proof as an ssz object
- the _serialized_ form is sent/received off the wire
- eg: client Z received a byte array, a serialized Attestation that must be validated

These three representations of ssz data have differing tradeoffs for the known ssz operations: (this is very simplified and there are more intricacies in practice)

| operation | structural | merkle tree | serialized
|---|---|---|---
|hashTreeRoot | N log N | 1 | N log N
|serialize | N | N | 1
|deserialize | N | N | 1
|size | N | N | 1
|clone | N | 1 | N
|equals | N | 1 | N
|create | N | 1 | 1
|get | 1 | log N | 1
|set | 1 | log N | 1

Edit from Proto:
- structural/merkle tree:
- size: O(1) for static, and commonly less than log(N) for simple non-nested dynamic structures, although O(N) for lists of dynamic elements (avoided in eth2 spec).
- merkle tree:
- (de)serialize: O(N), but with significant overhead over structural. I.e. no range copies. (but may matter more for Go/Rust).

Note that certain backings and certain datatypes may allow for an extended set of operations and that these are simply the shared operations core to all ssz objects.

**If we can provide the same interface for these different formats, this will be a huge usability and code-reuse win.**

#### Structural Backing

In this form, data is backed by native language types corresponding best to ssz data types of the type definition. Practically speaking, this means using `Object`s, `Array`s, `boolean`s, `number`s, etc. to compose the data.

eg:
- A uint is a `number` or `BigInt` object
- A boolean is a `boolean`
- A list or vector is an `Array`
- A list of vector of bytes is a `Uint8Array`
- A bit list is a `BitList` object
- A bit vector is a `BitVector` object
- An container is an `Object`

This backing is _convenient_ to create and manipulate because of the close relationship between the backing and interpretation. It is also trivial to get/set properties, since this corresponds to simple object property lookup.

const block: BeaconBlock = {...};

const slot = block.slot;
const root = BeaconBlock.hashTreeRoot(block);

#### Merkle Tree Backing

In this form, data is backed by a linked datastructure that corresponds to nodes in a merkle tree. The tree may be fully formed or stubbed out partially. Any interpretation of tree nodes is external to the tree backing itself.

This backing is great for generating and consuming proofs. It can additionally be used to share data between objects if 'immutable, persistent' tree node management is used.

An ES6 `Proxy` handler is used to provide methods and getter/setter capabilities that handle type conversion to/from the relevant types.

import { Tree } from "@chainsafe/persistent-merkle-tree"

const backing: Tree = ...;
const block: TreeBacked<BeaconBlock> =
    BeaconBlock.tree.asTreeBacked(backing);

const slot = block.slot;
const root = block.hashTreeRoot();

#### Serialized Backing

In this form, data is backed by a byte array that is the serialized form of the data. Lookups and operations are done from this serialized form, rather than fully deserializing the data first.

If data is received in a serialized format, or space is a concern, it may be appropriate to use the serialized backing to operate on the data.

An ES6 `Proxy` handler is used to provide methods and getter/setter capabilities that handle type conversion to/from the relevant types.

const backing: Uint8Array = ...;
const block: SSZValue<BeaconBlock> =
    BeaconBlock.serialized.asByteArrayBacked(backing);

const slot = block.slot;
const root = block.hashTreeRoot();