15
$\begingroup$

SHA-1, SHA-2, and the standardized version of SHA-3 are all sequential. This is impractical for hashing very large files distributed across machines. Any sequential hash can be straightforwardly converted into an efficiently parallelized hash using Merkle trees, but then I lose the standardization, and this is undesirable if the hash is to be used for long term authenticated storage.

Question: Is there an officially standardized tree-based (parallelizable) hash?

The most important property of the tree-based hash for my purposes is that for any partition of the input string, each portion can be reduced down to $O(\log n)$ intermediate space in parallel such that the intermediate values can be combined into the final hash, with at most a constant factor overhead over a sequential hash.

$\endgroup$
  • 1
    $\begingroup$ blake2b is probably along the lines of what you're looking for. $\endgroup$ – Stephen Touset Nov 9 '15 at 5:47
  • 3
    $\begingroup$ I think NIST is working on something as part of the SHA-3 process, but they do not have a draft yet $\endgroup$ – Richie Frame Nov 9 '15 at 6:02
  • 2
    $\begingroup$ csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/… $\endgroup$ – otus Nov 9 '15 at 9:05
  • 2
    $\begingroup$ Tiger Tree Hash is probably the closest thing to a standard tree hash. $\endgroup$ – CodesInChaos Nov 9 '15 at 12:39
  • 1
    $\begingroup$ @GeoffreyIrving I think tree hashing was included in some (/many?) of candidate designs for SHA-3 because there is no standard for tree hashing. It would not be required to include the tree hashing into the algorithm if there was. $\endgroup$ – Maarten Bodewes Nov 9 '15 at 22:51
6
$\begingroup$

With SHA-3 Derived Functions (SP 800-185, pdf) there is now a standardized parallel hash based on SHA-3, called ParallelHash, appropriately.

However, it is not a tree hash, but more of a hash-list-based mode. The string to be hashed is divided into equal-sized blocks, which are hashed, concatenated and then hashed again.

While it is not a tree hash it should cover the use case of hashing very large files across many machines. The arbitrarily small blocking size allows you to get to your $O(\log n)$ requirement if you base it on an appropriate function of the input size.

$\endgroup$
  • $\begingroup$ Thanks, doesn't seem finalized yet, but accepting anyway. Somewhat sad that block size is an unstandarized parameter. $\endgroup$ – Geoffrey Irving Mar 4 '17 at 14:57
  • 1
    $\begingroup$ @GeoffreyIrving, it was finalized a few months ago. I don't think it would be nearly as useful if the block size was constant. $\endgroup$ – otus Mar 4 '17 at 15:42
  • 3
    $\begingroup$ That's only true because it isn't a tree hash. $\endgroup$ – Geoffrey Irving Mar 4 '17 at 17:51
  • $\begingroup$ @GeoffreyIrving, true enough. $\endgroup$ – otus Mar 5 '17 at 7:56
3
$\begingroup$

I'm working on a tree hash based on BLAKE2 that's absolutely not in any way official, but it's exactly the sort of design you described. Maybe this would be useful once it's been properly reviewed and stabilized: https://github.com/oconnor663/bao

One of the features of Bao that might be nice for authenticated storage, is that it can verify any part of a file against the root hash, without needing to retrieve the entire file first. So for example, if the authenticated file is a big video, and you want to stream it and seek around it on a mobile phone, you can do that.

$\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.