Introduce domain separation for all Merkle Tree implementations
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.