Prysm: Sharding-Enabled Merkle Trie Design Choices

[rauljordan]

Hi all,

This issue will explore all of the latest talk around what Merkle tree scheme we will follow as part of our sharding implementation. As #100 is being worked on, it is important to discuss the state trie design as it is beyond the scope of that PR. Sharding gives us a unique opportunity to optimize Ethereum's state tries in ways that were not possible before.

In its current form, Ethereum's trie has two layers. That is, there is a global accounts trie where each account has a corresponding storage trie. In a system with a sharded state, the inefficiencies behind this current scheme become immediately apparent as cross-shard transactions would have too many dependencies.

In addition, the data availability problem becomes a major concern when exploring stateless client mechanisms in a sharded environment. We want our trees to have built-in mechanisms for fraud proofs and data validity checks that are efficient.

Finally, we want to be storage-efficient with our trie implementation. We maintain that storing the trie representation should have as little footprint on sharding clients.

Storage Efficiency

To increase storage efficiency and create a single-layer trie instead of the current two-layers (accounts trie and storage trie for each account), a solid approach would be to use a Binary Tree as proposed by Dfinity, as it creates much smaller proofs.

The context of this approach was first explored in this: A Two Layer Account Trie Inside a Single Layer Trie on ETHResearch.

Vitalik's implementation in Python

Data Availability

See: Data-Availability Friendly Tries and Detailed Analysis of Stateless Client Witness Size.

Another possible approach to a modified Merkle tree that is friendly towards data availability proofs is a Sparse Merkle Tree construction. This approach would save what we call "intermediate state roots". This means that "a full node can now easily generate efficient fraud proofs for invalid state roots, because they only have to prove that one intermediate root is invalid for the whole block to be invalid." (ETHResearch Post) and would give the system massive efficiency gains.

Another approach is to use Reed-Solomon reparation schemes as our tree implementation, but this is a bit fuzzier and not talked about as much. It was proposed in the following ETHResearch post

Potential Pull Request

A potential PR could be to just start with a binary tree similar to what Vitalik was creating in the Python implementation and test out some basic benchmarks in Go. As this issue is fleshed out more, we can discuss what other scheme we can follow next, including sparse Merkle trees.

Please let me know your thoughts, team.

[Magicking]

Data availability

The Reed-Solomon approach seems more complex in term of algorithm and structure that having something close to a flat layout (nonce, balance, code, storage) in a simple tree (where hash can then easily be used for adressing).

Proof footprint

I also liked the idea of having smaller proof/receipt/simple-walk-along-one-tree in a environment where we are highly restricted by gas cost and gas usage, that may allow some extra functionalities in account abstraction possibilities.

Implementation issues

On the implementation sides of things, I think we should be more litterate on what kind of mecanism there is already in Geth and what that would that imply in term of how would be handled account in Geth (for example for hardware wallets, caching, storage, etc) with that new mindset.

[elihanover]

Working on binary state trie version of geth, should be done by the end of the week.

[terencechain]

@elihanover Thanks a lot for working on this! Before getting too deep into coding. Can you elaborate more on your design choice? In particular why a binary trie versus other options like Radix trie, Read-Solomon trie or Sparse Merkle trie?

[rauljordan]

Hey @terenc3t, the binary trie choice was originally mentioned on ETHResearch as proofs for light cilents would be much, much smaller. This would work well for a system such as sharding where we assume very little computational requirements or storage capacity of nodes.

[elihanover]

No problem. All I'm doing at first is changing the radix of the state trie to 2, which mostly involves changes to the encoding and nodes. Having that should allow us to test whether the smaller Merkle proofs are worth the increased size of the tree. It's mostly an experiment for me to get more familiar with the trie package, and give us a place to start testing things out as @rauljordan suggested in the potential PR.

[rauljordan]

Moving this to Sapphire release as not critical for minimal sharding protocol.

[elihanover]

Just to give an update, I implemented the binary trie and just need to run some tests on it, so will hopefully have that by the end of the week.

[terencechain]

awesome! thank for the update @elihanover

[rauljordan]

Thanks for this @elihanover can you share links to some code when you get a chance?

[musalbas]

Just wanted to note that the Reed-Solomon encoded tree and the sparse merkle tree serve two different purposes, so they are not mutually exclusive.

The Reed-Solomon encoded tree is for representing the transaction data in each block (the "transactions merkle root"), in such a way that allows for data availability guarantees (i.e. that the transaction data is actually available), as opposed to using a standard merkle tree.

Sparse merkle trees are for representing the state of the entire blockchain (the "state merkle root"); having intermediate state roots reduces the cost of generating fraud proofs for incorrectly generated state roots. This still requires a data availability scheme to store these intermediate roots (unless light clients actually download them), such as the Reed-Solomon scheme, thus they are not mutually exclusive. I call this "data availability proof friendly" because you don't need to ensure availability of the entire state tree anymore, which would be insanely expensive to do per block (i.e. you don't want to apply Reed-Solomon encoding on the entire state!).

tl;dr: you don't want to be using the Reed-Solomon scheme for the state merkle root; just probably for the transaction merkle root.

[elihanover]

Forgot to get back to this for a while, but I've got an implementation of a binary trie with some results here that might be of interest. While proofs ended up being about half the size of radix 16 proofs, this is still far from optimal as mentioned here. I'm interested in optimizing this further and would appreciate feedback.

[nisdas]

@elihanover That looks pretty interesting so instead of 4 bits of the hp - encoding you have 6 bits of encoding+padding from switching over to the binary trie ? Currently we will most likely be using the Sparse Merkle tree for representing the state of the whole chain

[elihanover]

@nisdas HP has 4 bit prefix and 0 or 4 bits of padding, while the binary encoding is 4 bits prefix and 0-7 bits of padding. I saw this particular encoding as a simple way to take advantage of the preexisting HP encoding code (and luckily the 2 unused bits which just happened to be the exact amount of information needed for the change); however, I imagine there are significantly better encoding schemes for a binary tree. Let me know if/how I can be of use in regards to this.

[rauljordan]

This will change significantly and will not be touched until perhaps phase 2 of the spec. We will close for now until it is brought up in later research.