Merkle-like hash tree that mirrors existing tree structure

Question

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)

Answer 1

Yes: this allows the root hash to authenticate the entire content of the directory tree so that, e.g., a malicious storage server cannot fool you into accepting a forgery replacing a file you previously asked it to store. This is how Tahoe-LAFS is structured, or at least the immutable parts, and how ZFS block pointers are stored when authentication is enabled. More broadly, there is a modest literature on authenticated data structures that are all built out of essentially this idea.