anoma-archive icon indicating copy to clipboard operation
anoma-archive copied to clipboard

Published 20 hours ago • verified publisher icon anoma

[ledger] sparse merkle tree

Open tzemanovic opened this issue 3 years ago • 2 comments

We're currently using this library https://github.com/heliaxdev/sparse-merkle-tree/tree/tomas/encoding. We only store the hashes (H256) of the key and values in the tree (more details in https://github.com/heliaxdev/rd-pm/blob/master/tech-specs/src/explore/design/db.md). The fork has added a borsh encoding.

TODOs:

  • [ ] review the code and tests
  • [ ] review the benchmarks
  • [ ] review the memory requirements as the tree grows (quick and dirty first version at https://github.com/heliaxdev/sparse-merkle-tree/commit/623cedbdd7810660d9c2f0254b9eeb3fab1cfe98 - we should check the serialized version and proofs sizes too)
  • [ ] can the encoding for persistent storage be made more efficient?

┆Issue is synchronized with this Asana task by Unito

tzemanovic avatar Feb 24 '21 10:02 tzemanovic

it would be nice to also compare this with https://github.com/lazyledger/smt (as suggested in collab-cosmos-crypto channel https://heliax.slack.com/archives/C01CLNU56D7/p1615904669004400)

tzemanovic avatar Mar 16 '21 15:03 tzemanovic

also Diem is using sparse merkle tree https://github.com/diem/diem/blob/be4811ee515407175be79cbfcc333fa43ae548d9/storage/scratchpad/src/sparse_merkle/mod.rs

tzemanovic avatar Mar 16 '21 16:03 tzemanovic