[MerkleTree] Other implementations

[nrryuya]

• loom Plasma Cash SMT

• OpenZeppelin

  • Assumes that each pair of leaves and each pair of pre-images are sorted.

[nrryuya]

Bryant's suggestion.

vyperlang/vyper#806 (comment)

[fubuloubu]

I think both of those implementations have different optimizations that they make... Hard to say what the core algorithm should be, but not sure how we capture optimizations.

[fubuloubu]

Note that OpenZeppelin example assumes a sorted tree, which is a non-standard optimization that makes an assumption for how the keypath should be processed. A more general algorithm should not make this assumption. I believe it is a general, non-sparse merkle tree not commonly used for Plasma proofs.

[fubuloubu]

Note that Loom's implementation has an optimization including an additional data structure that declares whether a given sibling corresponds to a null subtree (allowing the compression of the branch to exclude pre-defined null nodes)