Sharding-Enabled Merkle Trie Design Choices about prysm HOT 14 CLOSED

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.

from prysm.

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.

from prysm.

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.

from prysm.

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.

from prysm.

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

from prysm.

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

from prysm.

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

from prysm.

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.

from prysm.

awesome! thank for the update @elihanover

from prysm.

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

from prysm.

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.

from prysm.

@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

from prysm.

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

from prysm.

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.

from prysm.