A two-layer account trie inside a single-layer trie

Data Structure
1

Currently, the ethereum state data structure is a two-layer trie. At the top there is the account tree, and each account is a 4-part data structure consisting of the nonce, balance, code and storage, where the storage is itself a key/value trie. This model has benefits, but it also has led to considerable implementation complexity. It turns out that we can get most of the benefits of the two-layer model by embedding it inside a single trie, with objects relating to the same account simply residing beside each other in the main tree, having the address of the account as a common prefix. That is, now we have:

main_tree[sha3(ADDRESS)] = acct = (nonce, balance, code, storage tree root)  
storage_tree[sha3(KEY)] = VALUE

But we can instead have:

main_tree[sha3(ADDRESS) + \x00] = nonce
main_tree[sha3(ADDRESS) + \x01] = balance
main_tree[sha3(ADDRESS) + \x02] = code
main_tree[sha3(ADDRESS) + \x03 + sha3(KEY)] = VALUE

The main benefits of this would be a simple implementation.

10 Likes
2

Key-value stores might perform better on this layout (access patterns are more local; caching is easier).

2 Likes
3

yes i think this a great idea! But also if you are considering making changes to the trie it might be worth considering moving to a binary trie also, since the light client proofs will be considerable smaller (at the cost of more lookups for full nodes)

1 Like
4

We already are!

https://github.com/ethereum/research/blob/master/trie_research/new_bintrie.py

3 Likes
5

I strongly believe this is worth testing and seeing if it actually performs better. It should.

1 Like