sigp / milhouse

Persistent binary merkle tree
Apache License 2.0
18 stars 7 forks source link

Support packed `Vector`s #33

Open michaelsproul opened 7 months ago

michaelsproul commented 7 months ago

@dapplion Notes that SSZ Vectors that fit inside 32-bytes, e.g. Vector<u8, U16> should be packed when tree-hashing, but we do not pack them:

https://github.com/sigp/milhouse/blob/6c82029bcbc656a3cd423d403d7551974818d45d/src/vector.rs#L249-L255

In Milhouse the packing logic is relevant here:

https://github.com/sigp/milhouse/blob/6c82029bcbc656a3cd423d403d7551974818d45d/src/utils.rs#L33-L38

This design decision was inherited from ssz_types which has a similar issue:

https://github.com/sigp/ssz_types/blob/e22576e3760ece4cb633748c4f68c6d9b1d92eb3/src/fixed_vector.rs#L180-L199

This issue needs further investigation to determine whether it's actually a problem or somehow everything just works out. It's not a blocker for Ethereum mainnet because such small vectors are not used presently.

dapplion commented 7 months ago

Checking the spec, we should not do that. Packing should only be done for "basic objects". A basic object is one of these three types uintN, byte, or boolean.

  • merkleize(pack(value)) if value is a basic object or a vector of basic objects.
  • mix_in_length(merkleize(pack(value), limit=chunk_count(type)), len(value)) if value is a list of basic objects.

https://github.com/ethereum/consensus-specs/blob/dev/ssz/simple-serialize.md#merkleization

michaelsproul commented 7 months ago

I interpreted the "or a vector of basic objects" in that sentence to mean that we should!

Funnily I think it means we should not pack Vector<Vector<u8, 2>, 4>, because the outer vector is not a vector of basic objects. But we should pack Vector<u8, 8>