17
$\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$
8
  • 1
    $\begingroup$ blake2b is probably along the lines of what you're looking for. $\endgroup$ 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$ 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$ 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
7
$\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$
5
  • $\begingroup$ Thanks, doesn't seem finalized yet, but accepting anyway. Somewhat sad that block size is an unstandarized parameter. $\endgroup$ 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$ Mar 4 '17 at 17:51
  • $\begingroup$ @GeoffreyIrving, true enough. $\endgroup$
    – otus
    Mar 5 '17 at 7:56
  • $\begingroup$ KangarooTwelve is an improved version of ParallelHash with a fixed chunk sized, a reduced round count, and less overhead for short messages. $\endgroup$ Jul 12 '20 at 22:53
5
$\begingroup$

The BLAKE3 hash function was just announced today. Internally, it's a Merkle tree.

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

Edit: With the release of BLAKE3, the latest version of Bao is no longer its own hash function. Instead, it's based on BLAKE3, implementing the verified streaming part of the spec.

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