[ledger] sparse merkle tree

[tzemanovic]

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]

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]

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