[Research] Sparse Merkle Trie

status-im / nim-eth-trie

Merkle Patricia Tries as specified by Ethereum

Apache License 2.0

7 stars 4 forks source link

[Research] Sparse Merkle Trie #19

Closed mratsim closed 6 years ago

mratsim commented 6 years ago

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: https://github.com/ethereum/py-trie/pull/58
Go: https://github.com/musalbas/smt

zah commented 6 years ago

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

mratsim commented 6 years ago

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

And also the following paper: Efficient Sparse Merkle Trees

jangko commented 6 years ago

time to delve into research materials.

zah commented 6 years ago

This has been implemented here: https://github.com/status-im/nim-eth-trie/pull/20

zah commented 6 years ago

@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 commented 6 years ago

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

jangko commented 6 years ago

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 commented 6 years ago

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