Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Introduce domain separation for all Merkle Tree implementations #110

Open
DanieleDiBenedetto opened this issue Jun 29, 2021 · 0 comments
Open
Labels
security issue A (possible) attack vector

Comments

@DanieleDiBenedetto
Copy link
Collaborator

The current Merkle tree implementations don't differentiate between internal nodes and leaf nodes when hashing them. Such Merkle trees lack second preimage resistance: given a root R and tree T, it is possible to compute a tree T′ that also produces R: given a tree:

           R
     /           \
    N1           N2
 /     \      /     \
L1     L2    L3      L4

If domain separation is missing, then the following tree will produce the same root:

           R
     /           \
    N1           N2

Concrete attacks can be carried out if second preimage property is missing (e.g. https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/).

As it can be seen, this problem affects only trees with variable height and/or unfixed leaves and node values, so for some use cases (in SNARK one always use constant height trees and phantom node/leaves) these implementations are fine; nevertheless we should envision also the usage of this library for other use cases for which we need to introduce domain separation when hashing Merkle Tree nodes/leaves.

@DanieleDiBenedetto DanieleDiBenedetto added the security issue A (possible) attack vector label Jun 29, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
security issue A (possible) attack vector
Projects
None yet
Development

No branches or pull requests

1 participant