← Back to Blog Cryptography

ParallelHash: Multi-Core SHA-3 Hashing

10 min read
ParallelHash: Multi-Core SHA-3 Hashing - QNSQY post-quantum encryption guide

Modern computers have many cores. A laptop has 8. A desktop workstation has 16 or more. A server has 32, 64, or 128. But most cryptographic hash functions are inherently sequential. SHA-256, SHA-512, SHA3-256: each processes its input one block at a time, with each block's computation depending on the previous one. You cannot speed them up by adding cores.

For small inputs this does not matter. Hashing a 1 KB message is done in microseconds regardless. But for large inputs, the sequential bottleneck shows up. Hashing a 10 GB file with SHA-256 takes seconds, even with hardware acceleration. Backup tools, file integrity systems, blockchain validators, deduplication services, and virtual machine fingerprinting all run into this wall.

NIST Special Publication 800-185, published in December 2016, introduced ParallelHash specifically to solve this. ParallelHash splits a long input into chunks, hashes each chunk in parallel, and then combines the chunk hashes into a final result. Multi-core CPUs can then hash large data at a rate that scales with cores.

This article explains how ParallelHash works, when to use it, and how it compares to other parallel hash designs like BLAKE3.

The Problem with Sequential Hashes

The Merkle-Damgard hash construction (used in SHA-2) and the Sponge construction (used in SHA-3) are both inherently sequential. Each compression step takes the previous internal state and the next message block and produces a new internal state. You cannot start step N until step N-1 is finished.

For a 10 GB input with SHA-256:

10 * 10^9 bytes / 64 bytes per block = ~150 million blocks Each block takes ~10 nanoseconds with SHA-NI hardware Total: ~1.5 seconds, single-threaded

You cannot reduce this by adding cores because the chain is sequential. The only way to use multiple cores is to break the sequence somehow.

ParallelHash's Solution

ParallelHash divides the input into fixed-size chunks (typically a few kilobytes each), hashes each chunk independently, then hashes the concatenation of chunk hashes to produce the final output.

The function is:

ParallelHash128(X, B, L, S) ParallelHash256(X, B, L, S)

X is the input, B is the chunk size in bytes, L is the desired output length in bits, and S is a customization string.

Internally:

  1. Split X into n chunks of B bytes each (the last chunk may be shorter).
  2. For each chunk i, compute z_i = cSHAKE(chunk_i, output_size = 256 bits, N = "ParallelHash", S = "")
  3. Concatenate: Z = encode(B) || z_1 || z_2 || ... || z_n || encode(n) || encode(L)
  4. Output: ParallelHash(X, B, L, S) = cSHAKE(Z, L, N = "ParallelHash", S = S)

Step 2 is the parallelizable part. Each z_i can be computed on a different core. Step 4 combines them sequentially, but its input is small (just n hash values), so this final step is fast.

The chunk size B is a tuning parameter. Smaller B gives more parallelism but more overhead per chunk. Larger B gives less parallelism but lower overhead. Typical choices are 1024, 4096, or 8192 bytes.

The customization string S provides domain separation, just as in cSHAKE, KMAC, and TupleHash.

A Worked Example

Suppose you want to hash a 1 GB file using 8 cores.

With sequential SHA3-256, the hash takes about 5 seconds (SHA-3 is slower than SHA-2 in software).

With ParallelHash256 and B = 8 KB, the file is split into 131,072 chunks. Each core processes ~16,384 chunks. Per-chunk hashing on each core dominates. Wall-clock time: roughly 5 seconds / 8 cores = ~0.625 seconds. Plus a small overhead for the final combining step.

In practice you usually get 4-6x speedup, not perfect 8x, due to memory bandwidth, cache effects, and chunk processing variance. But the speedup is substantial and it scales with hardware.

Where ParallelHash Is Used

ParallelHash is well-suited to:

File integrity checks for very large files (multi-gigabyte VM images, multi-terabyte backup archives).

Block-level deduplication systems that need to fingerprint large blocks.

Code signing of large binaries (game installers, OS images).

Blockchain block hashing where blocks are large and validators have spare cores.

Long content-addressed-storage hashes (CAS, content hashes) in IPFS-like systems.

Forensic disk image fingerprinting.

It is less useful for small inputs (less than a megabyte). The chunk overhead and final combining step add latency that is not amortized over enough work.

ParallelHash vs BLAKE3

BLAKE3 is another parallel hash, designed by Jean-Philippe Aumasson and others in 2020. It uses a tree structure (called Bao) where leaves are processed in parallel and merged up the tree. We covered it in BLAKE3 Hashing.

The differences:

BLAKE3 is faster than ParallelHash on commodity CPUs because it does not require SHA-3 acceleration (which is rare). BLAKE3 uses a custom mixing function similar to BLAKE2 and ChaCha, which is fast in pure software.

ParallelHash is FIPS-approved as part of NIST SP 800-185. BLAKE3 is not in the NIST family.

BLAKE3 supports streaming with rewindable seeking; ParallelHash is more rigid because chunk size B must be set up front and the input split before processing starts.

BLAKE3 has built-in keyed and key-derivation modes. ParallelHash is unkeyed by default; you can prepend a key as part of the customization string for similar effect.

For FIPS environments, ParallelHash. For maximum performance and modern API, BLAKE3.

Performance Considerations

The bottleneck for parallel hashes is often memory bandwidth, not CPU. If your input lives in slow storage (HDD, network), the disk read or network transfer dominates and parallelism in hashing barely helps.

For RAM-resident inputs on a modern server with high memory bandwidth, ParallelHash can saturate cores effectively. Benchmarks show 4-6x speedup on 8-core CPUs for inputs larger than 100 MB.

Cache effects matter too. If chunk size B is much larger than L1 cache (~32 KB on modern x86), each chunk's processing involves many memory loads. Picking B around 4-8 KB tends to fit in L1 and minimize cache traffic.

Thread overhead matters for small inputs. The cost of spawning and joining threads is microseconds; if the total hash work is microseconds, threading is a net loss. ParallelHash should fall back to sequential hashing for small inputs, which most implementations do automatically.

Implementation Pitfalls

Wrong chunk size. If B is too small, the per-chunk overhead dominates. If B is too large, you do not get enough parallelism. Pick B based on profiling, but 4096 to 8192 bytes is a reasonable default.

Using the wrong customization string. The chunk-level cSHAKE call uses S = "" internally; the final combining call uses the user's S. Mixing this up breaks domain separation.

Not handling the last chunk. The last chunk may be shorter than B. The spec handles this correctly; implementations must encode the actual chunk length.

Counting chunks wrong. The encoding of n (number of chunks) and L (output length) must use NIST's left_encode/right_encode. Custom encodings break interoperability.

Treating it as a streaming hash. ParallelHash needs to know the input length up front to split into chunks. It is not natively streaming the way SHA-256 is. There are extensions for streaming, but they require buffering.

ParallelHash and Post-Quantum Use Cases

The post-quantum primitives standardized in NIST FIPS 203/204/205 do not directly use ParallelHash. They use cSHAKE-based derivations internally, but the inputs are small (key material, signatures, ciphertexts), so parallelism would not help.

Where ParallelHash is useful in post-quantum contexts:

File-level encryption and signing. When QNSQY signs a large file, the file is hashed first, and the signature is computed over the hash. For large files, ParallelHash could speed up the hashing step. (QNSQY currently uses BLAKE3 for this role due to better performance on consumer hardware; see BLAKE3 Hashing.)

Long-term archival signatures. Stateful signature schemes like LMS (covered in LMS Stateful Signatures) hash the message before signing. For multi-terabyte archives, ParallelHash speeds this up.

Cryptographic accumulators and Merkle trees. When building a Merkle tree over many large data blocks, hashing the leaves in parallel with ParallelHash is faster than sequential SHA-3.

ParallelHash Variants and Truncation

ParallelHash128 provides 128-bit security; ParallelHash256 provides 256-bit security. The "128" or "256" refers to the underlying cSHAKE security level, not the output length. You can ask for any output length L from either variant.

For output lengths longer than 256 bits, both variants provide the same effective collision resistance up to their security parameter (128 or 256 bits). Asking for 1024 bits of output gives you a long random-looking string but does not increase collision resistance beyond the variant's nominal level.

For most use, ParallelHash256 with L = 256 or L = 512 is the right choice.

Frequently Asked Questions

Should I use ParallelHash or just hash chunks myself?

ParallelHash gives you the standard. If you implement chunk-and-combine yourself, you have to decide chunk size, encoding, customization, and combining function. Each decision can be a bug. ParallelHash makes those decisions consistently. Use it.

What if my hardware does not have many cores?

ParallelHash still works on a single core; it just runs sequentially with extra overhead. For single-core deployments, plain SHA-3 or BLAKE3 is faster.

Is ParallelHash secure?

Yes, under the assumption that cSHAKE is a secure XOF. NIST SP 800-185 includes the security analysis. The chunk-and-combine structure preserves cSHAKE's collision and preimage resistance.

Can ParallelHash be GPU-accelerated?

In principle yes, since each chunk is independent. In practice, GPU implementations of SHA-3 are slow because the Keccak permutation does not vectorize well. BLAKE3 GPU implementations exist and are fast; ParallelHash GPU is mostly a research curiosity.

How does ParallelHash compare to a Merkle tree?

A Merkle tree hashes leaves in parallel and combines them in a binary tree. ParallelHash hashes chunks in parallel and combines them with a single final hash. Merkle trees enable proofs of inclusion (you can prove a single leaf is in the tree without revealing the others); ParallelHash does not provide this. For applications that need inclusion proofs (e.g., transparency logs), use a Merkle tree. For pure speed, ParallelHash or BLAKE3.

Can the chunk size be changed mid-stream?

No. The chunk size B is part of the function definition and is encoded into the input. Changing B mid-computation would produce a different ParallelHash result. If you need to change B, recompute from scratch.

Why are there two security levels (128 and 256)?

The 128 and 256 refer to the underlying cSHAKE security strength. ParallelHash128 internally uses cSHAKE128 with rate 1344 bits and capacity 256 bits, giving 128-bit security against generic attacks. ParallelHash256 uses cSHAKE256 with rate 1088 bits and capacity 512 bits, giving 256-bit security. The capacity is half the security parameter doubled, which is how SHA-3 sponges are tuned.

For post-quantum applications and high-value data integrity, ParallelHash256 is the right choice. Quantum brute-force search (Grover's algorithm) gives at most square-root speedup, so 256-bit security translates to 128 bits of effective quantum security, matching the NIST high-strength target.

A Note on Streaming and Online Hashing

Strictly speaking, ParallelHash is not streaming-friendly. The function definition assumes the input is available as a contiguous byte string that can be split into chunks of size B. Real applications often want to hash data as it arrives, without buffering the entire input.

There are two common workarounds.

The first is to buffer chunks. As data arrives, accumulate it in a buffer of size B. When the buffer fills, dispatch the chunk to a worker thread for cSHAKE computation. When the input ends, dispatch any remaining partial chunk. This requires memory equal to one full chunk per worker, plus the queue of pending chunk hashes. For B = 8 KB and 8 workers, that is 64 KB of buffering, which is negligible.

The second is to abandon ParallelHash for streaming use cases and use BLAKE3 instead. BLAKE3's tree structure is naturally streaming-friendly because each leaf can be hashed as soon as a chunk's worth of input is available, and the tree is merged incrementally. We discuss BLAKE3's tree design in BLAKE3 Hashing.

For most server-side use cases (large files in storage, full RAM-resident data), buffering is fine. For streaming use cases (network transfers, sensor data feeds), BLAKE3 is more natural.

Sources

  1. NIST Special Publication 800-185. "SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash." December 2016. https://csrc.nist.gov/pubs/sp/800/185/final
  2. NIST FIPS 202. "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions." August 2015. https://csrc.nist.gov/pubs/fips/202/final
  3. O'Connor, J., Aumasson, J.-P., Neves, S., and Wilcox-O'Hearn, Z. "BLAKE3: One Function, Fast Everywhere." 2020. https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf
  4. Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. "Sufficient conditions for sound tree and sequential hashing modes." International Journal of Information Security, 2014. https://link.springer.com/article/10.1007/s10207-013-0220-y
  5. NIST FIPS 203. "Module-Lattice-Based Key-Encapsulation Mechanism Standard." August 2024. https://csrc.nist.gov/pubs/fips/203/final
  6. Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. "KECCAK Sponge Function Family Main Document." Submission to the SHA-3 competition, 2010. https://keccak.team/files/Keccak-main-2.1.pdf

Related Articles

Protect Your Data Before Q-Day Arrives

QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.

Try QNSQY