search

LayerXcom / verified-vyper-contracts

FVyper: A collection of useful Vyper contracts developed with formal methods
Apache License 2.0
55 stars 15 forks source link

[MerkleTree] Other implementations #66

Open nrryuya opened 5 years ago

nrryuya commented 5 years ago
nrryuya commented 5 years ago

Bryant's suggestion.

https://github.com/ethereum/vyper/issues/806#issuecomment-451665063

fubuloubu commented 5 years ago

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

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

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)