5 ms·

Compact Sparse Merkle Trees (CSMT) [1] is an already existing scheme for shorter proofs, which introduces the new CSMT data structure and was also posted on HN

Compact Sparse Merkle Trees (CSMT) [1] is an already existing scheme for shorter proofs, which introduces the new CSMT data structure and was also posted on HN a while ago.[2] This[3] is the implementation(in Elixir) of the above paper by the author for those interested. Also, here [4] is an interesting discussion between the author of Compact Sparse Merkle Trees and Vitalik Buterin, the creator of Ethereum on their research forum. I have posted these links because it seems disingenuous at best and malicious at worst, to not cite this original work which has been extensively discussed and documented before, anywhere in the current paper. [1] https://eprint.iacr.org/2018/955.pdf https://eprint.iacr.org/2018/955.pdf [2] https://news.ycombinator.com/item?id=18166298 https://news.ycombinator.com/item?id=18166298 [3] https://github.com/ZanjeerPlatform/csmt https://github.com/ZanjeerPlatform/csmt [4] https://ethresear.ch/t/compact-sparse-merkle-trees/3741 https://ethresear.ch/t/compact-sparse-merkle-trees/3741

irwt 7y ago
One of the authors of the paper here. We did not cite this work, because it has nothing to do with what we're proposing. One should not confuse Merkle multiproofs with sparse Merkle trees. We mentioned that in the paper as well. I do know that Vitalik once proposed the idea of sparse Merkle multiproofs somewhere informally, and we would love to cite that if someone could provide a link to that. But regarding the compact sparse Merkle tree, just because this paper shares some words in the title, does not make it the same thing.
- decentralised 7y ago
  I vaguely remember Vitalik mentioning multiproofs in the context of stateless clients for Ethereum 2.0, but this is what I could find: https://ethresear.ch/t/open-research-questions-for-phases-0-to-2/5871/2 https://ethresear.ch/t/open-research-questions-for-phases-0-... and the code: https://github.com/ethereum/research/tree/master/merkle_tree https://github.com/ethereum/research/tree/master/merkle_tree I also found a good article introducing multiproofs from Jim McDonald here: https://www.wealdtech.com/articles/understanding-sparse-merkle-multiproofs/ https://www.wealdtech.com/articles/understanding-sparse-merk...
  - irwt 7y ago
    Thank you for the links, I will try and edit the paper in the upcoming days to include Vitalik's mentioning. Jim McDonald's article is also wonderful, we referenced it multiple times and experimented quite a lot with his Merkle tree repo: https://github.com/wealdtech/go-merkletree https://github.com/wealdtech/go-merkletree
- remcob 7y ago
  I heard about about a similar (same?) method before and wrote about it here: https://ethresear.ch/t/optimizing-merkle-tree-multi-queries/4912 https://ethresear.ch/t/optimizing-merkle-tree-multi-queries/... In the comments Vitalik links to his implementation.

irwt 7y ago

One of the authors of the paper here. We did not cite this work, because it has nothing to do with what we're proposing. One should not confuse Merkle multiproofs with sparse Merkle trees. We mentioned that in the paper as well. I do know that Vitalik once proposed the idea of sparse Merkle multiproofs somewhere informally, and we would love to cite that if someone could provide a link to that. But regarding the compact sparse Merkle tree, just because this paper shares some words in the title, does not make it the same thing.

decentralised 7y ago
I vaguely remember Vitalik mentioning multiproofs in the context of stateless clients for Ethereum 2.0, but this is what I could find: https://ethresear.ch/t/open-research-questions-for-phases-0-to-2/5871/2 https://ethresear.ch/t/open-research-questions-for-phases-0-... and the code: https://github.com/ethereum/research/tree/master/merkle_tree https://github.com/ethereum/research/tree/master/merkle_tree I also found a good article introducing multiproofs from Jim McDonald here: https://www.wealdtech.com/articles/understanding-sparse-merkle-multiproofs/ https://www.wealdtech.com/articles/understanding-sparse-merk...
- irwt 7y ago
  Thank you for the links, I will try and edit the paper in the upcoming days to include Vitalik's mentioning. Jim McDonald's article is also wonderful, we referenced it multiple times and experimented quite a lot with his Merkle tree repo: https://github.com/wealdtech/go-merkletree https://github.com/wealdtech/go-merkletree
remcob 7y ago
I heard about about a similar (same?) method before and wrote about it here: https://ethresear.ch/t/optimizing-merkle-tree-multi-queries/4912 https://ethresear.ch/t/optimizing-merkle-tree-multi-queries/... In the comments Vitalik links to his implementation.