Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support packed Vectors #33

Open
michaelsproul opened this issue Jan 23, 2024 · 2 comments
Open

Support packed Vectors #33

michaelsproul opened this issue Jan 23, 2024 · 2 comments

Comments

@michaelsproul
Copy link
Member

@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:

milhouse/src/vector.rs

Lines 249 to 255 in 6c82029

fn tree_hash_type() -> tree_hash::TreeHashType {
tree_hash::TreeHashType::Vector
}
fn tree_hash_packed_encoding(&self) -> PackedEncoding {
unreachable!("Vector should never be packed.")
}

In Milhouse the packing logic is relevant here:

milhouse/src/utils.rs

Lines 33 to 38 in 6c82029

pub fn opt_packing_factor<T: TreeHash>() -> Option<usize> {
match T::tree_hash_type() {
TreeHashType::Basic => Some(T::tree_hash_packing_factor()),
TreeHashType::Container | TreeHashType::List | TreeHashType::Vector => None,
}
}

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
Copy link

dapplion commented Jan 23, 2024

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
Copy link
Member Author

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>

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants