Merkle roots do not bind computationally

[AaronFeickert]

The codebase uses Merkle mountain ranges to enable compact representations and proofs for different data structures.

However, the implementation is vulnerable to second-preimage attacks since it does not bind node status (leaf or inner) to hashes. It relies on the caller to provide pre-hashed leaf node data, and uses a caller-provided hash function for inner node hashing. If these two hashers cannot admit collisions, or if the caller otherwise relies on application-specific data context, the attack is mitigated, but the library cannot assert this is the case.

There are a few options for what to do:

• Update the documentation to indicate that the caller is responsible for second-preimage attack mitigation.
• Have the caller provide serializable data structures and a single hasher, and have the library hash leaf nodes with node position prefixing.
• Have the caller provide pre-serialized byte string data and a single hasher, and have the library hash leaf nodes again with node position prefixing.

The first option is the easiest, but requires the caller to be careful about any relationships between its hashers. The second option requires each relevant data structure to support serialization of the appropriate fields in a way that the library can use. The third option requires the caller to serialize its data in a way that avoids collisions.