I want to use parallel hash for a large file. I want final result equal to single hash from this file. What techniques would be best suitable to solving this problem?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Define "single hash", and ranking of criteria for "Best". Would you be satisfied with a simple variant of SHA-512, based on the same round function, that uses marginally more code, memory, and CPU time than SHA-512 for a sequential implementation, but allows parallel hashing? $\endgroup$– fgrieu ♦Commented Feb 28, 2017 at 11:27
-
$\begingroup$ @Msd I've changed the question somewhat, hopefully keeping it mostly in line to your question. Reason: asking for "the best" is considered opinionated and that's a valid reason to put the question on hold. Still, please answer fgrieu to indicate if you would be satisfied with such an answer. $\endgroup$– Maarten Bodewes ♦Commented Feb 28, 2017 at 12:05
-
$\begingroup$ @fgrieu Now you've gotten me curious if you've got an answer that is different from a M.T. ... $\endgroup$– Maarten Bodewes ♦Commented Feb 28, 2017 at 12:10
-
$\begingroup$ @Maarten Bodewes: I have no answer to the reworded question, and I doubt there is one for stringent-enough definition of sequential/single hash. I was considering the "blocked" construction in this question, which is even more basic and easily re-turned sequential than the "interleaved" method in CodesInChaos's answer. $\endgroup$– fgrieu ♦Commented Feb 28, 2017 at 12:49
-
1$\begingroup$ @md That depends on how you define the "simple hash". If the simple hash is basic SHA-2/3 you are out of luck. But unless you need compatibility with an existing system, you can simply choose a parallelizable hash construction, like those I outline in my answer. $\endgroup$– CodesInChaosCommented Mar 1, 2017 at 9:42
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
If you want to produce a hash compatible with an existing sequential hash, like SHA-2, you're out of luck. But when you choose a parallel mode, you can always compute the same output using a single thread.
The two most important parallel constructions are:
Interleaved
You initialize a fixed number of sequential hashes. Then you feed them one block in turn. At the end of the file you take the outputs of the individual hashes and hash it down into a single hash.
The biggest downside of this approach is that you need to choose the maximal parallelism at design time and changing it breaks compatibility. It still needs to process the file start to finish, it can only take advantage of multi-core CPUs but can't parallelize IO by hashing different parts of the file at the same time.
A (deep) Merkle-Tree.
For example the Tiger-Tree-Hash splits the file into 1 KiB and computes an unlimited depth binary hash tree over it. (Don't forget tagging leaves and inner nodes differently, or an equivalent mechanism to avoid ambiguities)
This has slightly higher CPU (a few percent) and memory (a few KB) overhead. It can only parallelize hashing files larger than the leaf size.
In exchange you can hash pieces independently in any order and the maximal parallelism grows with the file size.
Personally I prefer the tree approach due to its flexibility.
If you can use a key, you can use a PRF/MAC instead of a collision resistant hash. For example GHash (the MAC part of GCM) is very flexible in how it allows you to partition and parallelize the computation. It's also much cheaper to compute than collision resistant hashes.
answered Feb 28, 2017 at 12:19