>Let's say you have a bunch of files in your ~/Documents folder, some public, some private. Run merkdir on the directory, and you get a root hash which anonymously represents all your documents. Now you can publish that, sign it, timestamp it, whatever you like.
Maybe I'm the wrong audience for this, but I don't know what this means.
I feel like the Github README stops one or two steps short of explaining how this tool is useful for a real-world task.
(author here) That's fair. The real world applications are slim, but interesting. Maybe I'm a whistleblower with thousands of files, but I don't want to release them all right now. This tool allows you to easily prove that a file you release later was part of the original collection.
Another use case might be an organization that has a large archive of important files. This tool allows them to efficiently sign all of these files by signing the root hash.
>Maybe I'm a whistleblower with thousands of files, but I don't want to release them all right now. This tool allows you to easily prove that a file you release later was part of the original collection.
That makes it more concrete. Thanks!
>Another use case might be an organization that has a large archive of important files. This tool allows them to efficiently sign all of these files by signing the root hash.
This one, I'm still a bit confused. Sign them for what purpose?
If they're signing a bunch of documents to vouch for their authenticity, don't they have to cryptographically hash all the documents anyway? Or is the idea that instead of hash+sign N documents, they hash N documents, but they only have to sign one thing?
Yes, it means you have to sign only once. Maybe for signing this doesn't matter, but sometimes these authenticity operations you are doing can be more expensive. Maybe you're adding hashes to a blockchain or something.
Plus the size of signatures can really add up depending on the number of files and algo.
It's a bit jarring that, when you run the command twice in the same directory, you get a different root hash. IIUC, this nondeterminism comes from two sources: 1) each file is hashed with a random nonce, so as to distinguish files with identical contents; and 2) the work is distributed among goroutines on a first-come-first-serve basis, so the position of each file in the tree varies from run to run.
The latter shouldn't be too difficult to solve; just match each file's hash to its index from when the directory was walked. You can then use that index as a nonce, resolving the other source of nondeterminism.
I understand that you can still build and validate proofs despite the nondeterminism, but there's a good reason to eliminate it: doing so also eliminates the need to store the tree nodes! That is, storing the nodes becomes a performance optimization, rather than a necessity. (Oh yeah, another bit of UX feedback: I made the mistake of outputting the tree file to the same directory I was hashing, inadvertently introducing another source of nondeterminism! Maybe print a warning or something if the user does that.)
Lastly, I suggest representing your Merkle tree as a BNT stack (https://eprint.iacr.org/2021/038), as this will allow you to compute Merkle roots and build/verify proofs in streaming fashion, rather than allocating a big slice to hold all of the leaf hashes. The blake3 package you import uses this approach ;)
> each file is hashed with a random nonce, so as to distinguish files with identical contents
Actually, the purpose of the nonce is for privacy. The inclusion proof necessarily contains a leaf node hash, but I didn't want the proof to expose the hash of files it wasn't proving. That's because it could be private information, such as "bob has sensitive file X downloaded".
Since this approach makes determinism impossible, I chose to ignore the goroutine determinism part you mention.
Storing the tree nodes would likely still be required however, since otherwise the system would be brittle against things like file content and name changes, deletion, etc.
Ah, that makes sense. Still, you could use a single nonce per directory, plus an index per file.
As for brittleness -- some degree is unavoidable, since if you want to provide an inclusion proof for a file, you need to provide the (unchanged) file itself. I kinda assumed that the directory would be treated as immutable, but maybe that was premature since no one seems to have landed on the exact use case for this tool yet. :P
Oh, also -- since a BLAKE3 hash is itself a Merkle root, you could technically extend your proofs down into the files themselves; that is, you could prove that some 1024-byte slice of data was part of a file which was part of the directory. The blake3 package doesn't (currently) provide an API for that, though.
The BLAKE3 tree structure is designed to give exactly one tree layout for a given file length, so there's not really any flexibility to represent application data directly in the tree structure. You'd need to somehow transform your tree into a flat array of bytes and hash that.
It would be useful to allow the option for determinism (with its security downside) e.g. for people who want to assert that a directory contents hasn't changed? Or is there a simpler/standard way to get a hash of all content under a given directory? Something like fd | sort | xargs cat | md5sum, but including file names.
Listen to the "reproducible hashes" feedback. Think of it as a "super-md5" of a directory instead of a single file.
However it is done, the output should be deterministic by default, with "controllably underterministic" as an advanced choice.
Use case, especially with the suggestion of sub-file BLAKE3 inclusion validation:
Continual random file validation for backups.
Assume you "sign" your hard drive, or your home directory or something as part of your backup process.
Ship bits willy-nilly to anywhere, and be able to request an arbitrary subset / sub-block of any file to compare to the local disk.
Instead of making me download a 1GB file from you to compare SHA's and ensure it isn't corrupted... I challenge you to return to me the SHA of an arbitrary byte range from within that file.
Assuming we both have the original bits on a disk somewhere, it's an easy task. Basically you're trying to prevent replay attacks where the upload-receiver accepts the file, "cheats" by just saving the SHA, and responding (replay) with the SHA from when it was uploaded.
Forcing "proof" that they "could" return an arbitrary range of the file is "proof" that they still hold the "whole" file.
The unique "game playing" that you're doing here is "proving" that you can reproduce a portion of a directory on demand. The value is then being able to validly demand (as the original file-holder) a subset of your data from a third party.
"I prove that I have all this... I gave something from within there to you... now please prove to me that you can give it back (prove that you in fact received it)"
Take a look at Software Hash ID (swhid.org), which aims to be a standardized way of specifying such content. Copying from the specification:
> As an example, swh:1:dir:d198bc9d7a6bcf6db04f476d29314f157507d505 is the SWHID computed from a directory containing the source code of the darktable photography application at a given point in time of its development on May 4th 2017.
Would it make sense to integrate this into software packaging? For example, could this be used to quickly validate that a given file hasn't been altered from the version included in the package it came from?
I would mention blinding in passing in the use case section, not just in security. I wrote the tool off with my concern about revealing short files, but comment here
but I think it's incompatible with other aspect of this use case. My first impulse is using a prefix nonce, but the file system secrecy just conflicts with it too much
I think of the rolling-hash-split block store, tarsnap-style, as a different variant, tough indirection through tar (concatenation), compression, or rolling hash would cancel out benefits of the simple correspondence to structure matching file system layout.
14 comments
[ 3.3 ms ] story [ 35.9 ms ] thread>Let's say you have a bunch of files in your ~/Documents folder, some public, some private. Run merkdir on the directory, and you get a root hash which anonymously represents all your documents. Now you can publish that, sign it, timestamp it, whatever you like.
Maybe I'm the wrong audience for this, but I don't know what this means.
I feel like the Github README stops one or two steps short of explaining how this tool is useful for a real-world task.
Another use case might be an organization that has a large archive of important files. This tool allows them to efficiently sign all of these files by signing the root hash.
Edit: added this to the README
That makes it more concrete. Thanks!
>Another use case might be an organization that has a large archive of important files. This tool allows them to efficiently sign all of these files by signing the root hash.
This one, I'm still a bit confused. Sign them for what purpose?
If they're signing a bunch of documents to vouch for their authenticity, don't they have to cryptographically hash all the documents anyway? Or is the idea that instead of hash+sign N documents, they hash N documents, but they only have to sign one thing?
Plus the size of signatures can really add up depending on the number of files and algo.
It's a bit jarring that, when you run the command twice in the same directory, you get a different root hash. IIUC, this nondeterminism comes from two sources: 1) each file is hashed with a random nonce, so as to distinguish files with identical contents; and 2) the work is distributed among goroutines on a first-come-first-serve basis, so the position of each file in the tree varies from run to run.
The latter shouldn't be too difficult to solve; just match each file's hash to its index from when the directory was walked. You can then use that index as a nonce, resolving the other source of nondeterminism.
I understand that you can still build and validate proofs despite the nondeterminism, but there's a good reason to eliminate it: doing so also eliminates the need to store the tree nodes! That is, storing the nodes becomes a performance optimization, rather than a necessity. (Oh yeah, another bit of UX feedback: I made the mistake of outputting the tree file to the same directory I was hashing, inadvertently introducing another source of nondeterminism! Maybe print a warning or something if the user does that.)
Lastly, I suggest representing your Merkle tree as a BNT stack (https://eprint.iacr.org/2021/038), as this will allow you to compute Merkle roots and build/verify proofs in streaming fashion, rather than allocating a big slice to hold all of the leaf hashes. The blake3 package you import uses this approach ;)
> each file is hashed with a random nonce, so as to distinguish files with identical contents
Actually, the purpose of the nonce is for privacy. The inclusion proof necessarily contains a leaf node hash, but I didn't want the proof to expose the hash of files it wasn't proving. That's because it could be private information, such as "bob has sensitive file X downloaded".
Since this approach makes determinism impossible, I chose to ignore the goroutine determinism part you mention.
Storing the tree nodes would likely still be required however, since otherwise the system would be brittle against things like file content and name changes, deletion, etc.
As for brittleness -- some degree is unavoidable, since if you want to provide an inclusion proof for a file, you need to provide the (unchanged) file itself. I kinda assumed that the directory would be treated as immutable, but maybe that was premature since no one seems to have landed on the exact use case for this tool yet. :P
Oh, also -- since a BLAKE3 hash is itself a Merkle root, you could technically extend your proofs down into the files themselves; that is, you could prove that some 1024-byte slice of data was part of a file which was part of the directory. The blake3 package doesn't (currently) provide an API for that, though.
However it is done, the output should be deterministic by default, with "controllably underterministic" as an advanced choice.
Use case, especially with the suggestion of sub-file BLAKE3 inclusion validation:
Continual random file validation for backups.
Assume you "sign" your hard drive, or your home directory or something as part of your backup process.
Ship bits willy-nilly to anywhere, and be able to request an arbitrary subset / sub-block of any file to compare to the local disk.
Instead of making me download a 1GB file from you to compare SHA's and ensure it isn't corrupted... I challenge you to return to me the SHA of an arbitrary byte range from within that file.
Assuming we both have the original bits on a disk somewhere, it's an easy task. Basically you're trying to prevent replay attacks where the upload-receiver accepts the file, "cheats" by just saving the SHA, and responding (replay) with the SHA from when it was uploaded.
Forcing "proof" that they "could" return an arbitrary range of the file is "proof" that they still hold the "whole" file.
The unique "game playing" that you're doing here is "proving" that you can reproduce a portion of a directory on demand. The value is then being able to validly demand (as the original file-holder) a subset of your data from a third party.
"I prove that I have all this... I gave something from within there to you... now please prove to me that you can give it back (prove that you in fact received it)"
Take a look at Software Hash ID (swhid.org), which aims to be a standardized way of specifying such content. Copying from the specification:
> As an example, swh:1:dir:d198bc9d7a6bcf6db04f476d29314f157507d505 is the SWHID computed from a directory containing the source code of the darktable photography application at a given point in time of its development on May 4th 2017.
Shorter proofs can be done with Verkle trees, https://web.archive.org/web/20231115115627/https://vitalik.c...
but I think it's incompatible with other aspect of this use case. My first impulse is using a prefix nonce, but the file system secrecy just conflicts with it too much
I think of the rolling-hash-split block store, tarsnap-style, as a different variant, tough indirection through tar (concatenation), compression, or rolling hash would cancel out benefits of the simple correspondence to structure matching file system layout.