# EPF6 - Week 14 Updates

## tl;dr

- Merged one PR([#15704](https://github.com/OffchainLabs/prysm/pull/15704)) for handling `Bitlist` and `Bitvector`.
- Opened one PR([#15725](https://github.com/OffchainLabs/prysm/pull/15725)) for handling `List` over `List`.
- Now SSZ-QL engine parses any random `BeaconState`/`BeaconBlock`! 🙌

## Details

### `Bitlist` and `Bitvector`

{%preview https://github.com/OffchainLabs/prysm/pull/15704 %}

`Bitlist` and `Bitvector` are different with `List` and `Vector` in terms of the encoding/decoding methodology. `List[bool, N]` isn't same as `Bitlist[N]`, as we can encode much better with bits. You might refer to the `consensus-specs` [here](https://github.com/ethereum/consensus-specs/blob/master/ssz/simple-serialize.md#bitvectorn).

Fortunately, Prysm relies on [`go-bitfield`](https://github.com/OffchainLabs/go-bitfield/tree/master) library for **all** `Bitlist`/`Bitvector` SSZ types in Go. I can determine whether `[]byte` is a `Bitlist`/`Bitvector` or not by checking the Go struct tag like:

if castType := tag.Get(castTypeTag); strings.Contains(castType, "go-bitfield") {
    isBitfield = true
}

Also, I can safely leverage on one useful method from `go-bitfield` to get the bit length of raw bytes:

// SetLengthFromBytes determines the actual bitlist length from SSZ-encoded bytes.
func (l *bitlistInfo) SetLengthFromBytes(rawBytes []byte) error {
	// Wrap rawBytes in a Bitlist to use existing methods.
	bl := bitfield.Bitlist(rawBytes)
	return l.SetLength(bl.Len())
}

### `List[List[...], ...]`

{%preview https://github.com/OffchainLabs/prysm/pull/15725 %}

When I tried to parse `BeaconBlock`, the test failed because of this path: `.body.execution_payload`. `ExecutionPayload` has a field named `transactions` which contains `Transaction` as a `List`. Since `Transaction` is also a `List` of byte, the size for each transaction can be vary. My current design for `listInfo` only holds the general information of the element:

// listInfo holds information about a SSZ List type.
//
// length is initialized with zero,
// and can be set using SetLength while populating the actual SSZ List.
type listInfo struct {
	// limit is the maximum number of elements in the list.
	limit uint64
	// element is the SSZ info of the list's element type.
	element *sszInfo
	// length is the actual number of elements at runtime (0 if not set).
	length uint64
}

So the best way to calculate the size (in byte) is just multiplying `element.Size()` with the `length`. This works well for trivial cases like `List[uint64, 5]` but it becomes much complex if the element is a variable-sized type as well.

So I added one field under `listInfo`:

// elementSize caches the each element's byte size for variable-sized type elements
elementSize []uint64

and `elementSize` is appended **after** recursively populating the `sszInfo` of each element.

if listInfo.element.isVariable {
	listInfo.elementSize = make([]uint64, 0, length)

	// Populate nested variable-sized type element lengths recursively.
	for i := range length {
		if err := PopulateVariableLengthInfo(listInfo.element, val.Index(i).Interface()); err != nil {
			return fmt.Errorf("could not populate nested list element at index %d: %w", i, err)
		}
		listInfo.elementSize = append(listInfo.elementSize, listInfo.element.Size())
	}
}

One other thing to consider is about offset bytes. As you might know, `List` type is a variable-sized type which means it always results 4-byte of offset for indicating where the actual data was encoded. Thus, if `transations` contains three transactions, we should consider 12 (4*3) bytes more as well as the actual size of each transaction. This led me to add one more method under `listInfo`:

// OffsetBytes returns the total number of offset bytes used for the list elements.
// Each variable-sized element uses 4 bytes to store its offset.
func (l *listInfo) OffsetBytes() uint64 {
	if l == nil {
		return 0
	}

	if !l.element.isVariable {
		return 0
	}

	return offsetBytes * l.length
}

`OffsetBytes()` is used for 1) calculating the size of `Container` (which has `List` field) and 2) populating the length with an actual value.

### Test Results!

{%preview https://hackmd.io/@junsong/Bkl7aa2oxl %}

You might check this out, which includes the result of parsing `BeaconState` and `BeaconBlock`. For this EPF project, I planned to support two APIs:

- `/prysm/v1/beacon/states/{state_id}/query`
- `/prysm/v1/beacon/blocks/{block_id}/query`

So it is enough to test with those two objects. I yet have one remaining task for getting one element using index(e.g., `validators[3]`), but this doesn't look that hard.