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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ blake2b is probably along the lines of what you're looking for. $\endgroup$
    – Stephen Touset
    Commented Nov 9, 2015 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
    Commented Nov 9, 2015 at 6:02
  • 2
    $\begingroup$ csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/… $\endgroup$
    – otus
    Commented Nov 9, 2015 at 9:05
  • 2
    $\begingroup$ Tiger Tree Hash is probably the closest thing to a standard tree hash. $\endgroup$
    – CodesInChaos
    Commented Nov 9, 2015 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 ♦
    Commented Nov 9, 2015 at 22:51

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, doesn't seem finalized yet, but accepting anyway. Somewhat sad that block size is an unstandarized parameter. $\endgroup$
    – Geoffrey Irving
    Commented Mar 4, 2017 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
    Commented Mar 4, 2017 at 15:42
  • 3
    $\begingroup$ That's only true because it isn't a tree hash. $\endgroup$
    – Geoffrey Irving
    Commented Mar 4, 2017 at 17:51
  • $\begingroup$ @GeoffreyIrving, true enough. $\endgroup$
    – otus
    Commented Mar 5, 2017 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$
    – Jack O'Connor
    Commented Jul 12, 2020 at 22:53
6
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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