EIP-7495: SSZ ProgressiveContainer

EIPs
21
22

Overall this is a nice addition to SSZ and accomplishes its objectives.

As far as formatting of the EIP, it looks like care was given to ensure that large sections can be copy/pasted directly into the ssz document in the consensus specs. Good job there.

I do wish that the Variant type was mentioned earlier in the document, given its importance. And that it had a format that was similarly able to be copied to the ssz document.

Also feels like some sort of motivation for Variant is missing. eg:

While StableContainer provides a flexible structure for forward and backward compatibility of ssz containers, in practice, having known versions of containers, with known subsets of fields are useful, eg: a datastructure where a field is available after a fork boundary but not before. To provide this type safety as well as more efficient serialization, Variant[S] is defined.

1 Like
23

Have added a Variant mention in the abstract as well: Update EIP-7495: Add `Variant[S]` to abstract by etan-status · Pull Request #8511 · ethereum/EIPs · GitHub

The Variant used to share serialization as well, because for EIP-6493 it is never serialized. Only EIP-7688 prompted the more compact serialization. Agree that with its increased relevance, it deserves an earlier mention.

1 Like
24
25

Updated to rename Variant to MerkleizeAs to better describe what it does. Furthermore, improved explanations and rationale for more clarity, and extended on tests.

Thanks @wemeetagain for the crazy amount of help. Feel free to also link the TypeScript implementation here :slight_smile:

26

Typescript implementation here:
https://github.com/ChainSafe/ssz/pull/373

1 Like
27

Looks like Update EIP-7495: Rename `Variant` -> `MerkleizeAs` and improve rationale by etan-status · Pull Request #8558 · ethereum/EIPs · GitHub got closed after I commented, pasting here for discussion:

IMO we should consider removing MerkleizeAs[“a container”] if the only benefit here is to support field reordering.

Also I’m just if reordering of fields is helpful in general, or if its just asking too much from ssz. Is there a case where reordering of fields during serialization is required, and not just a nice-to-have?

Removing the bitvector for serialization by creating a “subtype” is helpful and has tangible benefit. It follows logically from motivation to StableContainer definition. It makes MerkleizeAs serialization more efficient and on-par with Containers.

But reordering of fields feels more handwavey and wrt spec, looks more like a feature ‘because we can’, something that ‘falls from the implementation’. My recommendation would be keeping this EIP more restricted (removing all field reordering). And adding an additional EIP that extends functionality of MerkleizeAs, or defines a new thing with that functionality – where the functionality is matched by the motivation.

28

I love the idea for StableContainer!!! I have to admit thought naming convention for MerkleizeAs feels… less than ideal. How do you feel about StableContainer for the abstract over-arching container and InvariantContainer for the specific, unchanging, version of instead of MerkleizeAs. Code could look like InvariantContainer<BeaconState, Electra> or similar. What do you think @etan-status ?

1 Like
29

Thanks for the feedback; adjusted the name to Profile[B].

Furthermore, the spec was simplified:

  • Reordering of fields in Profile[B] no longer allowed
  • StableContainer[N] now requires everything to be Optional[T] to avoid duplicating logic from Profile[B]
  • Profile[B] now require B to be a StableContainer[N], for the cases that used Container the semantics are the same when not linking the types.

https://github.com/ethereum/EIPs/pull/8562/files

30

ssz_generic test vectors for this EIP added here:
https://github.com/ethereum/consensus-specs/pull/3777

1 Like
31

Added checks to remerkleable that ensure compatibility that only valid types can be created (no re-ordering, compatible field types, no extra fields, and so on).

https://github.com/ethereum/EIPs/pull/8619/files

Tests can be found here:

32

The serialization spec defines:

def is_active_field(element):
    return not is_optional(element) or element is not None

In the specification of StableContainer[N] it’s stated that:
" All fields of a StableContainer[N] MUST be of of type Optional[T]. Such fields can either represent a present value of SSZ type T, or indicate absence of a value (indicated by None). The default valueof an Optional[T] is None."

This makes the first part of is_active_field seem ambiguous - what does is_optional mean? If it means “of type Optional[T]”, this is true for all fields by definition, so do we actually want this?

def is_active_field(element):
    return element is not None
1 Like
33

That’s indeed correct! Have integrated the simplification:

1 Like
34

EIP-7916 defines a way how to get rid of capacities for List to avoid excessive hashing when the capacity is set to some arbitrary large value exceeding theoretical maximum (essentially ‘unlimited’ / application defined limit). I have updated StableContainer specs to support ProgressiveList as well.

We should consider whether a similar approach can also be used to get rid of the StableContainer[N] capacity – it is very difficult to reason about the N value, and chances are that devs using StableContainer may just pick a value that’s either too optimized (and later breaks when it is extended), or that’s too large (and, therefore, inefficient to hash).

The open question on adopting progressive approach for StableContainer would be in serialization / merkleization of the BitVector[N] mix-in (if N is unknown). A simple solution could be to just limit the number of fields to 254 and add another 1-byte prefix indicating N of the highest used bit plus 1. That would keep the merkleization mix-in simple (a single 256-bit node).

Alternatively we could define a ProgressiveBitlist and use that (at higher hashing cost, though!). Or we add a Bitvector to each recursive tree. First stablecontainer field gets paired with a Bitvector[1], the next 4 fields get paired with a Bitvector[4], the next 16 get paired with a Bitvector[16] and so on. Some middleground that would not introduce a 254 field limit.

35
  • StableContainer becomes pure mental model for assigning field indices
  • Profile becomes ProgressiveContainer
  • Drop optionals support from ProgressiveContainer
  • Compact encoding as union, as deserialization needs type info anyway
  • Leave partial data encoding up to applications
36

Idea based on reviewer feedback to drop 256 field limit:

Concern is that the 256 limit is across all iterations of the container, including any deprecated fields. While practically unlikely, it’s weird to make this nice type that’s unbounded in nature and then limit it artificially. The counterargument is that mixing in a Bitvector[256] is a single chunk, much simpler than mixing in an entire ProgressiveBitlist. Performance characteristics remain comparable, though, as the mixed in bitlist roots can be cached.

37

After further discussion, reinstated the 256 field limit to keep the protocol simple. Instead, recommend to add a more field if the limit is close to being reached with a nested ProgressiveContainer.

38

There were more discussions about CompatibleUnion’s security properties.

The current CompatibleUnion design is very flexible, because it can be retroactively introduced without breaking light client verifiers and smart contracts (e.g., based on EIP-4788).

However, as the selector is not mixed in to the hash_tree_root, certain restrictions apply:

  • All type options MUST have unique Merkle tree shapes. Otherwise, two values that solely differ in their selector would share the same hash_tree_root.
  • Type options MUST NOT only differ in the element type of a List[type, N] or ProgressiveList[type]. This is because the empty list [] has the same hash_tree_root irrespective of the element type.

A static type checker was prototyped in Python to enforce these restrictions. It works, but especially the restriction on lists, effectively banning homogenous lists Union[ProgressiveList[A], ProgressiveList[B]], and instead requiring ProgessiveList[Union[A, B]] (where each element has to be separately checked), is quite unintuitive.

If it is considered important to be able to retroactively introduce unions, the restrictions may be avoided through hackery, e.g., requiring the lowest selector tag to be used where multiple selector tags are valid. However, that would cut in quite a bit into the “Simple” part of “SSZ”.

Therefore, I propose that we drop the ability to retroactively introduce unions, encouraging to use CompatibleUnion earlyon, wherever future design space extensions are expected. This is not ideal, as it means we introduce CompatibleUnion with solely a single type option that might never be extended, and it also implies forward-looking design which is often neglected when artificial time constraints become part of the equation. However, at least it is a clear, simple design, without arbitrary feeling restrictions.

Mixing in the selector in a compatible way is a bit tricky, because different contexts given by outer CompatibleUnion may only support certain subsets of inner CompatibleUnion. For example, an EIP-7702 SetCode transaction only supports type 5 authorizations, i.e., the authorizations list would be a CompatibleUnion[Type5Authorization], while a future transaction may extend this to a CompatibleUnion[Type5Authorization, TypeXAuthorization], or even later drop original authorizations as a CompatibleUnion[TypeXAuthorization, TypeYAuthorization, TypeZAuthorization].

This means that if an inner object is extracted, and moved elsewhere, that a TypeXAuthorization either has selector value 2 or 1 depending on the surrounding scope, which is not ideal. Therefore, I’m also proposing to define the type with an associative dict CompatibleUnion({selector: type}), where the same selector can be reused regardless of surrounding context, e.g., in CompatibleUnion({5: A, 20: B}), selector 20 would always point to B, even if other contexts may drop A or may support additional type options.

39

Have further split CompatibleUnion into its own EIP:

1 Like