It's impossible to parallelize crypto hash operations, if the hash covers the whole file.
You can hash chunks, or maybe use different kind of hashes though.
You can hash chunks, or maybe use different kind of hashes though.
The leaves and then all nodes can be computed in parallel.
With a typical node size of say 4 KB any file that is at least 4 MB in size can utilise 1,024 cores.
Same for objects stores like S3 or Google Drive, they only give you a single hash, you can't parallelize that, you need to add your own merkle tree on top.
Also, the tree can be based on any underlying hash function, so the root hash can be literally "just" a SHA256 hash, but instead of hashing the whole file, it hashes a list of hashes.
You don't even need to store those intermediate nodes! They must be recomputed on-the-fly to verify the root hash anyway.
Last, but not least, the temporary space required is logarithmic in the size of the data, typically with a large exponent, so in practice this all fits on the stack. No heap memory allocations required, compatible with embedded devices, and can re-use cryptographic acceleration primitives like the AES-NI instruction set.
Conversely, tree-based hash constructions allow:
- Parallel generation and verification.
- Incremental repair of partially corrupted data.
- Extension of an existing hash (efficient append & prepend).
- Patricia hashes also allow efficient mutation in the middle of the data.
- Various deduplication and efficient incremental sync scenarios.