eth2.0-ssz icon indicating copy to clipboard operation
eth2.0-ssz copied to clipboard

Make backing binary tree structure 100% static

Open Nashatyrev opened this issue 5 years ago • 1 comments

Creating this issue just to discuss the following idea:

currently the backing tree structure is not static due to List and Union types. E.g. when an element is appended to a non-basic type List the tree structure changes: the Zero leaf is replaced by a new element's subtree. The similar applies to the Union type.

What if make the default List[T, N] backing tree the same way as with Vector[T, N]? I.e. tree nodes for non-existing list elements would be the default tree of type T instead of Zero leaf. With this approach the List backing tree would have the same structure independently of content it's representing.

With the above approach the List[T, N] could be represented exactly as Container(data: Vector[T, N], length: UInt64) and would have corresponding merkleization

Following the similar idea the Union[T1, ..., Tn] could be represented as Container(t1: T1, ..., tn: Tn, typeIndex: UInt64)

I believe making the backing binary tree structure static could make the whole SSZ concept a bit clearer and solid, enable more clear implementations and better optimizations.

This idea is non backward compatible with merkleization so could be potentially considered for say SSZ v2

Nashatyrev avatar Dec 09 '20 09:12 Nashatyrev