Which type of Merkle Tree design and implementation should be used?

[Olshansk]

This discussion will aim to capture the research, discussion and decision of which Merkle Tree design and implementation to use for the core implementation of the Pocket Network V1 Protocol.

At the time of writing, the Pocket Network V1 Protocol specification lines several different alternatives as seen in the following screenshot:

There is already ongoing work & research in the core pocket repo found at the following links:

• [Persistence] Evaluate Celestia's Sparse Map Tree implementation #199
• [STALE - DO NOT REVIEW][Persistence] State Commitment - State Hash #152
• [Persistence] State Hash Computation Implementation #147

The one thing that we know for sure is that we will 100% be moving away from IAVL in the original Cosmos implementation. There is a long and very interesting discussion found here: cosmos/cosmos-sdk#7100

I will continue posting related ideas, research and updates here as the topic evolves

[Olshansk]

I have summarized Etherum's Merkle Patricia Trees and Diem's Jellyfish Merkle Tree below:

• https://olshansky.substack.com/p/5p1r-ethereums-modified-merkle-patricia
• https://olshansky.substack.com/p/5p1r-jellyfish-merkle-tree

Will post an update once the work on Verkle Trees is done as well.

[Olshansk]

Though it is still an early WIP, the culmination of all the research will be summarized and presented in this deck: https://docs.google.com/presentation/d/1dgXVKLf_uqnviCMC-VfVsmy64j8ihY3AkySZDMr3tyU/edit?usp=sharing