2 ms·

Some quick feedback: 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 co

Some quick feedback: 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 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 ;)

makeworld 3y ago
Thanks for the feedback! I will look into BNTs. > 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.
- nemo1618 3y ago
  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.
  - oconnor663 3y ago
    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.
- da39a3ee 3y ago
  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.

makeworld 3y ago

Thanks for the feedback! I will look into BNTs. > 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.

nemo1618 3y ago
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.
- oconnor663 3y ago
  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.
da39a3ee 3y ago
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.