Parallel Tree Hashing and the BLAKE3 Design

Both SHA-2 and SHA-3 are sequential. Block i+1 of the compression function or the permutation needs the state left by block i, so a single core processing a message must walk it front to back, and adding cores buys nothing. A tree hash gives that up. It hashes independent chunks in parallel and combines the results with a binary tree, which turns a strictly serial dependency chain into a reduction that scales with available hardware. The cost is a more complicated digest, a loss of some provable security properties, and a set of new framing decisions that have to be made correctly.

Independent subtrees and a fixed arity

The tree is defined by a chunk length and a parent-node rule. BLAKE3 uses 1024-byte chunks, each hashed by a compression function over 64-byte blocks, and combines chaining values pairwise. A message shorter than one chunk is just a chunk. A message of exactly the chunk length and a message of one chunk plus one byte produce different roots, because the tree shape differs and the root’s finalisation flag differs.

The chaining value of a subtree depends only on the bytes in that subtree. That is the property that makes parallelism legal: an implementation splits the input into chunks, dispatches them across cores or SIMD lanes, and reduces the resulting chaining values. No message ordering has to be communicated between workers beyond which subtree each handles.

The reduction is not associative in the sense an attacker might wish. A left-heavy and a right-heavy arrangement of the same eight chunks give different roots, because parent nodes include position in their input and because the root applies a different finalisation than an interior node. Some hashes explicitly add a tree position counter to each parent’s input for exactly this reason; without it, a permutation of subtrees could produce the same root.

Compressing a digest is not the same as hashing it

The core security question is whether a tree hash built over a secure compression function is itself collision resistant. It is, under a condition: the leaf and node roles must be separated, and the reduction has to be to a collision in the compression function rather than in the tree.

The condition is the same one that governs Merkle tree encodings, which is worked out in domain separation in Merkle trees. A leaf that hashes to a value which can also be an internal node’s output reintroduces the structural collision. BLAKE3’s compression function carries a flag field that distinguishes chunk, parent, root, and keyed modes, so the four roles are disjoint by construction rather than by convention.

What the tree does give up is the tight collision-resistance reduction of the iterated case. For a single chain, a collision in the hash implies a collision in the compression function by a simple induction. For a tree with a variable shape, the induction has to handle the case where the two messages have different shapes and diverge at some node rather than at the root. The reduction still goes through, but the bound on the number of compression calls an attacker must make is a function of the tree depth and the chunk length, and it is looser than for a fixed chain. The practical consequence is that a tree hash with an n-bit chaining value should be treated as having slightly less than the full n/2 collision resistance of an ideal iterated hash, though by a small margin.

Streaming without knowing the length

A parallel hash has a problem the sequential one does not: the tree shape depends on the total message length, and the length may not be known when hashing starts. A network stream, a file being written, or a pipe delivers bytes until it stops.

There are two strategies. The first is to buffer and compute the tree lazily, which the specification for a tree-of-chunks construction typically prescribes: the finalisation step renders subtrees that are still queued. The second is the one BLAKE3’s implementation uses for streaming, maintaining a stack of subtree chaining values.

// Sketch of the streaming state: one pending chunk buffer plus a stack of
// completed subtree chaining values, ordered by subtree size.
struct Hasher {
    chunk_buf: [u8; 1024],
    chunk_len: usize,
    cv_stack: Vec<[u8; 32]>,
    total_len: u64,
}

fn push_cv(&mut self, cv: [u8; 32]) {
    let mut new_cv = cv;
    let mut level = 0u32;
    // Merge with any completed subtree of the same level, bottom-up.
    while self.total_len >> (level + 10) & 1 == 1 {
        new_cv = parent_cv(&self.cv_stack.pop().unwrap(), &new_cv);
        level += 1;
    }
    self.cv_stack.push(new_cv);
}

The stack holds at most one subtree per level, and the levels present are exactly the set bits of the count of completed chunks. That is the same invariant as a binary counter, and it bounds stack depth to log2(message_chunks), which is 54 entries for a 2^64-byte message at 1024-byte chunks. A streaming implementation therefore needs a few kilobytes of state regardless of message size, and it never has to re-read earlier bytes.

The level + 10 term is the chunk-size shift: with 1024-byte chunks, level k covers 2^(k+10) bytes. Hardcoding that constant is a normal source of bugs when the chunk size changes.

Verification cost and the multi-block trade

Tree hashing changes the shape of the workload. For a 1 MiB input at 1024-byte chunks, there are 1024 leaf compressions and 1023 parent compressions of a single compression function each, so the parent work is nearly as large as the leaf work and cannot be neglected. Larger chunks reduce the parent fraction but reduce the number of independent tasks, which limits parallelism on small inputs. There is no single correct chunk size; the choice trades reduction overhead against the granularity of available parallelism.

The same structure helps SIMD without any threads at all. A compression function over 64-byte blocks operating on a 256-bit or 512-bit vector unit can run the four-lane or eight-lane message schedule in parallel across lanes, and a tree structure gives it independent inputs to fill those lanes. This is why implementations report the tree hash scaling with vector width even on a single core: the parallelism is inside the compression function as well as across it.

Verification is where the structure costs more than it saves. A single digest cannot be checked incrementally; the verifier needs the whole message or a full tree of intermediate values. Protocols that distribute hashing across a network, as Certificate Transparency does, therefore commit to a tree structure as part of the protocol rather than relying on a hash that happens to be tree-based internally. RFC 9162 defines its own Merkle tree over leaf hashes, with an explicit inclusion proof format, so that a client can verify a leaf’s membership without hashing the log. The hash used for leaves is a sequential function there; the tree is at the protocol layer. That separation of concerns is the more general pattern: use a fast sequential or parallel hash for the bytes, and put the tree where the verifier actually needs it.

Where the design does not match the requirement

Tree hashing is the wrong choice when the requirement is unkeyed collision resistance at a fixed small size and nothing else. The extra machinery buys throughput, not strength, and a sequential hash has a longer track record and a simpler reduction.

It is also the wrong choice when the digest will be embedded in a signature scheme whose own design assumes a particular hash. Many signature standards fix the hash by identifier, and substituting a different function changes the security argument in ways the standard does not cover.

It is the right choice when the input is large and the hardware is wide, which describes most bulk data: file integrity manifests, content-addressed storage, package repositories, and any log whose entries are big enough that the tree overhead amortises. The related problem of arranging those trees so a client can verify a subset of the leaves efficiently is the subject of sparse Merkle trees, and the padding and length-encoding rules that any tree hash must still get right are covered in the Merkle-Damgård article.