I'm wondering about the security of a hash-tree structure that mirrors the structure of another tree. In an ordinary Merkle tree the block hashes form the leaves of the tree, and all internal nodes are computed by hashing their children, but what if the data being hashed already conforms to a natural tree structure T? Could you securely create a hash-tree from T by replacing the leaf nodes of T by their hashes and the internal nodes of T by the hashes of their children?
My motivating example for this data-structure is a hierarchical filesystem. I've written some code that realises this idea but I'd like to know if this method is actually secure.
Proof-of-concept code here: https://github.com/michaelsproul/antifa/tree/master/src
I've attempted to make it second-preimage resistant by adopting the framing bytes from Certificate Transparency. The hash of a file is
h(00 || contents) and the hash of a directory is
h(01 || child1 || child2 || ...). Children are sorted by name before hashing, but their names aren't included in the hash (although perhaps they should be to avoid an order-preserving renaming attack).
Here's an example run on the
src directory of the PoC:
$ tree . ├── bin │ └── shasum.rs ├── hash.rs ├── lib.rs └── main.rs 1 directory, 4 files $ cd .. && target/release/antifa src : SHA-256:9c9489d389f253820a7b7b04a00f38cc04e7d9381e6e6792a69cade7982c6ab1 ["lib.rs"]: SHA-256:e070004ebdeca318c5451f5f4e716d5322c286e7a347b3bef987402efc362454 ["main.rs"]: SHA-256:83e39d33c072b917ac299bb761442f51e473ccb69b0b40cbf87a80e892fb68b6 ["bin"]: SHA-256:22065eed254ac789dddc348d1f429f0e27a09f4e7f0a432d7c4f70e26d5b0e4a ["bin", "shasum.rs"]: SHA-256:c91146c4ac71b8b336cdd8d70475ea8fed3186b16e189ba9d3e003fc80da9113 ["hash.rs"]: SHA-256:984b35e7bb55608982bcf1e76d461e0bacd6e75b54f0f0fca5dfac12b23e6135
(the file paths are shown as a list of their components for now)