search

kaxxa123 / zkyes-smt

Sparse Merkle Tree Implementations
3 stars 0 forks source link

Tree corruption when leaves have identical hashes #3

Open kaxxa123 opened 3 weeks ago

kaxxa123 commented 3 weeks ago

In SMTHashZero, SMTNaive and SMTSingleLeaf the leaf hash is simply computed as Hash(value), where value is directly provided on calling addLeaf. This can easily lead to leaves and subtrees to have identical hashes.

In these cases different trees branches will end up sharing common nodes.

Editing one such "repeated" leaf can corrupt the SMT as the shared nodes are deleted on replacing.

The same problem is not present in SMTSingleLeafEx whose hashes leaves as Hash(index | value | 1).

kaxxa123 commented 3 weeks ago

Can be fixed in one of the following ways:

  1. Remove node deletion code. Node deletion is only done to cleanup resources.
  2. Ensure all leaves have a unique hash as in SMTSingleLeafEx