Another simple method to optimize SMT without security loss.
The hash merge function:
- if L == 0, return R
- if R == 0, return L
- otherwise sha256(L, R)
This function has one problem, merge(L, 0) == merge(0, L), which can easily construct a conflicted merkle root from a different set of leaves.
To fix this, instead of use hash(value), we compute a leaf_hash = hash(key, value) as leaf’s value to merge with its sibling.
(we can store leaf_hash -> value in a map to indexed to the original value).
Proof:
Since the key is hashing into the leaf_hash, no matter what the value is, the leaves’ hashes are unique. Since all leaves have unique hash, nodes at each height will either merged by two different hashes or merged by a hash with a zero(for a non-zero parent, since the child hash is unique, the parent is surely unique at the height), until the root, if the tree is empty we got zero, or if the tree is not empty, the root must merge from two hashes or a hash with a zero, it’s still unique.
more details: https://github.com/jjyr/sparse-merkle-tree