2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Can you clarify what you want a prover to prove to a verifier in your scheme? For example, should the prover be able to convince a verifier that there exists a file at some path with some hash? Do you want to prevent the prover from equivocating about that file's hash? Do you need the prover to prove absence of some file at some path? What model are you in: Does the prover commit to the hierarchy and send the verifier the root hash, after which the verifier starts submitting queries? Or does the verifier compute the tree and root hash but later outsources the storage to the prover? $\endgroup$ – Alin Tomescu Feb 3 '18 at 20:30
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.