[Research] Sparse Merkle Trie

[mratsim]

Someone asked during today's eth2.0 implementer call if sparse Merkle Trie if sparse merkle trie were implemented.

Relevant:

• Vitalik's spec: https://ethresear.ch/t/data-availability-proof-friendly-state-tree-transitions/1453/6
• Python: Sparse merkle tree part1 ethereum/py-trie#58
• Go: https://github.com/musalbas/smt

[zah]

@jangko expressed interest to work on this. We need 3 upvotes as usual.

[mratsim]

Please see also this video from @AlexeyAkhunov at ECDC Berlin, time 14:57

And also the following paper: Efficient Sparse Merkle Trees

[jangko]

time to delve into research materials.

[zah]

This has been implemented here:
#20

[zah]

@pablanopete, this bounty has been delivered by @jangko who has also recently submitted a pull request for another bounty that we are going to accept.

Can you please send a combined reward of 1200 USD for both bounties (preferably in ETH)? @jangko's ETH address is 0x6134d7fEeBC0386c2f6Bb5F0072FB2184B4D4Fc7

[zah]

The bounty has been paid out:
https://etherscan.io/tx/0xe9b0650a6a9d2f40c3e434827353328c045afe4498abf9d6f77e5d54a2594b94

[jangko]

thank you very much. and I'm sorry this week been very busy so I'm really slow finishing ad2 benchmark. I will resume on it soon.

[mratsim]

Just to keep track, a new optimizing scheme for Sparse Merkle Trees by Vitalik: https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751