SparseMerkleTree does not implement a sparse merkle tree

[prestwich]

Describe the bug
This is not a sparse merkle tree.

Sparse merkle trees definitionally have 2**n nodes at each level of the tree (where n is the 0-indexed depth). If you intend to build a sparse merkle, you ought not pad.

If you intend to build a regular merkle that allows incremental storage of nodes, you ought not use the default hash mechanism (bytes32(height) would be sufficient padding).

Also, please consider tagging your interior nodes

Expected behavior
Name should reflect common definition of sparse merkles

[ben-chain]

Hey James, thanks for the issue! Always great to see when the community has our back. 😃

I'm actually not sure what you mean by padding. Were you referring to this line? If so, that function does indeed return the root of a tree with 2**n nodes at each level. Here is a unit test comparing to our off chain SMT.

That said--it's definitely an unusual (ab)use of an SMT! This code is 8 months old and was built for the Unipig demo with knowledge that it would be deprecated. It was just easier to reuse our off-chain SMT even though a regular Merkle tree would suffice. We also didn't implement the standard SMT proof compression, though that seems unrelated to the points you're bringing up.

In any case--I'll throw up a ticket to remove this deprecated code so others aren't confused in the future. If you or anyone else wanted to utilize it, I'd point to this repo where it's been picked up by another community member!