ginger-lib icon indicating copy to clipboard operation
ginger-lib copied to clipboard

Introduce domain separation for all Merkle Tree implementations

Open 95DDB opened this issue 4 years ago • 0 comments

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.

95DDB avatar Jun 29 '21 10:06 95DDB