# EPF6 - Week 7 Updates
## Summary
1. More review about SSZ, Prysm code review and no-gopher catch up with Go.
2. Review Merkle Tree and SSZ libraries
3. Workaround with recursive computation on HashTreeRoot based on Jun's recursive SSZ PoC

## Details
### 1. SSZ, Prysm and Go catch up
#### SSZ
In this iteration of SSZ review, I would highlight Dafny. A Consensys formal specification of the Eth2.0 spec. Although [SSZ notes](https://github.com/Consensys/eth2.0-dafny/blob/4e41de2866c8d017ccf4aaf2154471ffa722b308/wiki/ssz-notes.md) are not fully covered, it is a good resource to consider while digging to SSZ and Merkleization. This formal specification provides a better understanding of what is going under the hood.
#### Prysm
Walk through Prysm code base and minor review of Bazel.
Prysm's [implementation](https://github.com/OffchainLabs/prysm/blob/develop/beacon-chain/state/state-native/proofs.go).
This is a deterministic implementation of Merkle Proofs of certain fields: `CurrentSyncCommitteeGeneralized`, `NextSyncCommitteeGeneralized`and `FinalizedRoot`. To generate Merkle Proofs, Prysm computes hashes field-by-field as it can be seen in [`ComputeFieldRootsWithHasher`](https://github.com/OffchainLabs/prysm/blob/cd6cc76d5826f4a4ff880a1b8a9fa3d58772928a/beacon-chain/state/state-native/hasher.go#L20) function.
Unrelated yet inspirational, Prysm computes other Merkle proofs:
- [BuildBlobSidecars](https://github.com/OffchainLabs/prysm/pull/15473/files#diff-ae56a23d899634e55e82e948571c29337ba5018c0c45b7a233cf1d64b27f9dc9). In here, the pre-computation of shared Merkle tree components once instead of recalculating for each blob, eliminates O(n) redundant computations.
- [Block's Payload Proofs for Light Clients](https://github.com/OffchainLabs/prysm/blob/develop/consensus-types/blocks/proofs.go).

#### Go
Go is a statically typed langauge, but sometimes we need to discover or manipulate values whose concrete types are only known at runtime. In this case, we use the reflect package:
- To inspect the value's type and some metadata
- Read or set field and elements dynamically
- Call methods when you don't have the static type in scope.

import "reflect"

v := reflect.ValueOf(anyValue)   // runtime representation of the value
t := v.Type()                    // runtime representation of its type

[Reflect package](https://pkg.go.dev/reflect) and [Laws of reflection](https://go.dev/blog/laws-of-reflection)
In a later iteration I will check [Generics](https://go.dev/doc/tutorial/generics).
In relation to the project, Jun already did a great job implementing the SSZ core logic using this reflect package.

### 2. SSZ implementations
Ethereum provides a list of [SSZ implementations](https://github.com/ethereum/consensus-specs/issues/2138)
#### a. Ferranbt's [fastssz](https://github.com/ferranbt/fastssz/blob/main/tree.go)
This library (used in Prysm) provides a

// TreeFromChunks constructs a tree from leaf values.
// The number of leaves should be a power of 2.
func TreeFromChunks(chunks [][]byte) (*Node, error) {
	numLeaves := len(chunks)
	if !isPowerOfTwo(numLeaves) {
		return nil, errors.New("number of leaves should be a power of 2")
	}


	leaves := make([]*Node, numLeaves)
	for i, c := range chunks {
		leaves[i] = NewNodeWithValue(c)
	}
	return TreeFromNodes(leaves, numLeaves)
}

---
SSZ-QL opt for [marshaling everything and treat as string of bytes](https://hackmd.io/@junsong/Byr3_lfPxl#Option-2-Marshal-everything-and-treat-as-string-of-bytes--Byte-Parsing-Engine).

#### b. pk910's [dynssz]()
This library is very promising benchmark. It uses both in-library methods and fastssz, depending on which is most efficient.

### 3. Recursive HashTreeRoot workaround
This has been my first week of real Go coding since the beginning of the project. I felt a bit rusty and I had to overcome some knowledge gap as for example, I've never used reflections. Very thankful to Jun's because his SSZ-QL prototype is a great inspiration. I suffered from Dunning Kruger effect, so I might have underestimated this beast. It is great to realized this early so as to take actions.

My goals were stupidly high thinking of doing a whole prototype of efficient Merkle Proofs computation, so as the week went by, I had to reduce them. I finally end-up working on recursively compute the Hash Tree Root based on:
- `sszInfo` already computed
- `marshalledData`

This is already working except from variable size elements:

In this regard, I mainly coded a funtion that is called recursively and reads the `sszType` field from `sszInfo` var and redirect the computation to the correct HashTreeRoot function:

### Next steps
- Fix HashTreeRoot computation
- Define the struct for MerkleProofs
- Research for an efficient approach