search

SpinResearch / merkle.rs

:christmas_tree: Merkle tree in Rust
BSD 3-Clause "New" or "Revised" License
129 stars 23 forks source link

No domain separation between leaf and internal node hashes #20

Closed AGWA closed 7 years ago

AGWA commented 7 years ago

It appears from https://github.com/SpinResearch/merkle.rs/blob/90d804e3ce9f313003014175184d393cde7737f1/src/hashutils.rs#L19-L28 that leaf hashes are calculated as H(bytes) and internal node hashes are calculated as H(left || right). Consequentially, it's possible for a leaf to have the same hash as an internal node, and therefore for two different trees to have the same root hash. To avoid this, I suggest calculating leaf and internal node hashes as H(0x00 || bytes) and H(0x01 || left || right), respectively, Certificate Transparency-style.

zmanian commented 7 years ago

I think you should domain separate the the internal nodes and the serialization proof should explicitly state the domain separation tag to be as explicit as possible.