Bab

Bab leaves open some paramters, they need to be given as “input” to the Bab specification.

The chunk_size value must be a natural number greater than zero. Given an input bytestring in of at most $2^{64}-1$ bytes, Bab splits it into a non-empty sequence chunks of chunks: the first chunk_size bytes become the first chunk, the next chunk_size bytes become the second chunk, and so on. Only the final chunk may be shorter than chunk_size. For example, splitting the ASCII string hello_world with a chunk_size of 2 yields the chunks he, ll, o_, wo, rl, and d. If in is the empty string, then chunks consists of a single, empty chunk.

The width value must be a natural number greater than zero. Bab maps input bytestrings (of at most $2^{64}-1$ bytes) to digests of width many bytes.

The hash_chunk function determines the labels of the leaf nodes of Bab’s Merkle-tree. It must be a function that maps a chunk and a boolean flag (whether the node is the root node or not) to a bytestring of width bytes.

The hash_inner function determines the labels of the inner nodes of Bab’s Merkle-tree. It must be a function that maps a quadruplet of two bytestrings of width bytes (the labels of the two child nodes), an unsigned 64-bit integer (the length of the input substring covered by the node), and a boolean flag (whether the node is the root node or not) to bytestrings of width bytes.

To hash a bytestring in that was split into a chunk sequence chunks, Bab constructs the unique binary tree with one leaf per chunk such that all left subtrees are complete trees, and the size of the left subtrees is strictly decreasing from left to right11This characerization is taken from the BLAKE3 paper (O’Connor et al., 2020). The construction is identical to that of the certificate transparency logs of RFC 9162 (Laurie et al., 2021).. we number the vertices in depth-first order, prioritizing left children over right children, starting at $1$ in the root. Figure 1 shows an example.

Bab assigns to each vertex v a label lbl(v); the root label serves as the digest of in.

If v is a leaf vertex corresponding to some chunk c, then lbl(v) is hash_chunk(c, $\top$) if c is the only chunk in chunks, and hash_chunk(c, $\perp$), otherwise.

If v is an inner vertex, let left denote its left child, let right denote its right child, let len denote the total length of the chunks corresponding to all leaf descendents of v, and let is_root be $\top$ if v is the root of the tree and $\perp$ otherwise. Then lbl(v) is hash_inner(left, right, len, is_root).

Figure 2 demonstrates the label computation in the example Merkle-tree:

The choice of parameters for using Bab is flexible, but some care needs to be taken to create a secure (i.e., collision-resistant and preimage-resistant) hash function. hash_chunk and hash_inner must be secure hash functions themselves, and it must further be impossible to find an input to hash_chunk and one to hash_inner such that both yield the same digest.

We supply two useful instantiations: one based on arbitrary secure hash functions, and a more efficient one that closely mimics BLAKE3.

2.3.1 Via Conventional Hash Functions

2.3.2 WILLIAM3

Using the root label of a Merkle-tree as the digest allows verifying that some string is a prefix of a string of a known digest. To do so, each chunk is preceded by the labels of the left and right children of all inner vertices on the path from the root of the tree to that chunk. As an optimization, each label is transmitted at most once; it is the receiver’s responsibility to cache labels until they are not needed for verification any longer. This data stream is preceded by the length of the string to yield the baseline verifiable stream. Figure 3 gives an example:

1122The length of the original string in bytes., lbl(2), lbl(9), lbl(3), lbl(6), lbl(4), lbl(5), he, ll, lbl(7), lbl(8), o_, wo, lbl(10), lbl(11), rl, d.

The client can verifies stream by eargerly reconstructing the labels of tree nodes, and asserting that the computed labels match the received data and the lengths of the data match the length values used in the computation of inner labels33Particular care must be taken at the end of the data stream: the end of input implicitly defines the length of the final chunk, and that implicit length must be validated to match the length(s) explicitly used in the digest.. You can go through the verification process for the example stream step by step below. Each step consists of reading either a full label or a full chunk from the stream. The graphic shows the Merkle tree and indicates for each node the knowledge that the client has about it: dim if the client has not yet received any data concerning it, diagonally striped orange if the client has received data that it will need later but cannot verify yet, green if it could verify the data and needs to keep it for verification of subsequent data, and gray if it has verified the data and will not need it for any future verification steps.

The Merkle-tree design allows for verifiable streaming of any slice (of chunks) within a string of known digest. Assume a client wants to receive some number of chunks, starting at some chunk offset. The response data is defined with the same technique as for the baseline verifiable stream: the transmission of each chunk in the slice is preceded by the labels of the left and right children of all inner vertices on the path from the root of the tree to that chunk. Chunks outside the slice do not contribute any data. Again, each label is transmitted at most once. Since the length of the slice is known to the client, the response need not be prefixed by the length. We call this transmission the baseline verifiable slice stream. Figure 4 shows an example of which data needs to be transmitted when the client requests three chunks, starting at offset two (zero-indexed).

lbl(2), lbl(9), lbl(3), lbl(6), lbl(7), lbl(8), o_, wo, lbl(10), lbl(11), rl.

You can step through the verification process for this example below:

A server can provide a short proof for the length of any string to a client who already has the digest of that string. If the string fits into a single chunk, the proof simply is that chunk itself (the client can reconstruct the digest and assert that it matches). If the string is longer than a single chunk, then the root of the Merkle tree is an inner node. The server can then supply the length of the string together with the labels of the left and right children of the root. The client feeds these into hash_inner and asserts that the result matches the digest.

BLAKE3 does not incorporate lengths into the computation of inner vertex labels. BLAKE3 still supports length proofs, these consist of the length followed by the same data as a reply to a slice request for only the final chunk. Such a proof always contains at least a full chunk, plus twice the height of the tree in labels; its size is logarithmic in the length of the string. For a moderately short string (say, 4096 bytes), the length proof via BLAKE3 has a size of $8+2\cdot 2\cdot 32+1024=1160$ bytes. The corresponding WILLIAM3 lenght proof, in comparison, requires $2\cdot 32+8=72$ bytes.

Even when short length proofs are not needed, a Bab instantiation must not ignore the length argument in hash_inner. Doing so opens up certain attacks where an attacker can create invalid trees whose baseline verifiable slice stream would pass verification for certain slices.

Both hash_chunk and hash_inner take a boolean is_root flag as an argument. This flag must influence the output to guard against length extension attacks. The flag ensures subtree-freeness (Daemen et al., 2018) (also called final-node separability (Bertoni et al., 2014)), which prevents length extension attacks. Ignoring the flag does not make the resulting hash function insecure, but it does open up length-extension attacks.

BLAKE3 includes the index of each chunk when computing leaf labels in the Merkle-tree. Bab does not. The authors of BLAKE3 give a clear justification for why they added chunk indices:See the BLAKE3 paper, section 7.5.

We [...] use the t parameter during the input phase, to indicate the chunk number. This means that each chunk has a distinct CV44“Chaining Value”, their terminology for Merkle-tree labels. with high probability, even if two chunks have the same input bytes. This is not strictly necessary for security, but it discourages a class of dangerous optimizations.

Consider an application that hashes sparse files, which are mostly filled with zeros. The majority of this application’s input chunks could be the all-zero chunk. This application might try to compute the CV of the zero chunk only once, and then check each chunk before compressing it to see whether it can use that precomputed CV. This check is cheap, and for this application it could be a big speedup. But this optimization is dangerous, because it is not constant-time. The runtime of the hash function would leak information about its input.

If tricks like this were possible, an unsafe implementation would inevitably find its way into some privacy-sensitive use case. By distinguishing each chunk, BLAKE3 deliberately sabotages these tricks, in the hopes of keeping every implementation constant-time.

Bab is decidedly not a general-purpose hash function. It has no ambition to be used as a building block in, say, a digital signature scheme. Hence, we see little value in adding complexity just to deter a certain class of implementation techniques.

Binary trees are not the only candidate digraphs as the merkelization backbone. Other candidate constructions include ternary trees (which are more efficient than binary trees in some applications), and efficient binary linking schemes. However, for verified streaming, binary trees turn out to be more efficient.

Interestingly enough, the humble linked list, aka hash chain, has some intriguing properties. If the Merkle-DAG was a linked list where the label of the second chunk incorporates the label of the first chunk, the label of the third chunk that of the second, and so on, verified streaming could be done without sending any internal labels — by sending chunks in reverse order. Unfortunately, the worst-case size of slice verification proofs would be linear in the size of the tree. This dilemma is similar to that encountered in secure timestamping and related problems.

Also note that the Merkle tree structure allows for easy parallelization of hash computation, whereas a linked list (or any linking scheme) completely precludes parallelization.

Bab leaves the chunk_size as a freely choosable parameter, because different values incur different tradeoffs. At the most basic, a larger chunk_size shrinks the Merkle tree and thus reduces the metadata overhead in verified streaming, but it also increases the amount of data that needs to be read in sequence without being able to verify it immediately. The chunk_size also serves as an upper bound to the size of proofs of string length in Bab. Finally, the chunk size also affects the performance of computing digests, see the discussion in Section 7.1 of the BLAKE3 paper (O’Connor et al., 2020).

When receiving a string interleaved with verification metadata, we call a transmitted label verified if it is the root label66We assume that the client trusts the digest it uses for a request., or if it and its sibling label have been fed into hash_inner, yielded the label of the parent vertex, and the parent label has also been verified. We call a chunk verified if it has been fed into hash_chunk, yielded the label of the vertex corresponding to the chunk, and that label has also been verified.

An unverifiable sequence is a sequence of consecutive bytes in a response stream whose corresponding labels and chunks cannot yet be verified. We call the length of a maximal unverifiable sequence of a stream its verification delay.

What are the unverifiable sequences in the baseline verifiable stream? Any partially transmitted label is unverifiable. Further, a label of a left child is unverifiable without the label of its sibling. Since these are always transmitted in succession, the longest unverifiable sequences contributed by labels have length $2\cdot width-1\text{.}$ Chunks can only be verified when their final byte gets received, so they contribute unverifiable sequences of length $chunk\_size-1\text{.}$

This puts the verification delay of the baseline verifiable stream at the maximum of $2\cdot width-1$ and $chunk\_size-1\text{.}$ In most practical instantiations, the chunk_size should dominate77BLAKE3 and WILLIAM3, for example, have a width of 32 bytes and a chunk_size of 1024 bytes.. For the remainder of this document, we will assume that $chunk\_size\ge 2\cdot width\text{,}$ yielding a verification delay of the baseline verifiable stream of $chunk\_size-1\text{.}$

The verification delay gives an upper bound of how much progress is lost if a connection failure occurs in the worst possible moment. It also gives the greatest amount of untrusted data that a client has to buffer in memory simultaneously88This number is one greater than the verification delay, because the final byte also needs to be loaded into memory for verification. Verification of chunks might not require holding the full chunk in memory, but we assume that the client requested the chunk data for a reason, and thus has to hold on to it even if not strictly necessary for verification alone..

Note that this required buffer capacity is mostly independent from the memory that the client needs for buffering verified labels for reuse in later assertions. Every label of a right child needs to be kept in memory after verification, in order to verify the labels of its two children. Hence, verification always requires the capacity to buffer one label per layer of the Merkle-tree (see this example).

When a response stream omits a left label, the client cannot verify the corresponding right label when it arrives. But it can, at a later point, reconstruct the left label, and then use the reconstructed data to verify both the right label and the reconstructed one. We now describe this process more precisely, and then we investigate how to improve upon the baseline verifiable stream with this technique.

Let p be an inner Merkle-tree vertex with left child l and right child r. What precisely happens when we omit lbl(l) from the baseline verifiable stream?

After the omitted label, the stream continues with lbl(r). Unlike in the unmodified baseline verifiable stream, the client cannot verify lbl(l) immediately; the client needs to buffer it as unverified data instead. Next, the stream continues with the data corresponding to l. There are two cases, depending on whether l is a leaf vertex or an inner vertex.

If l is a leaf vertex, then the stream continues with a chunk. This chunk can be fed into hash_chunk to recover a (still unverified) candidate label of l. Feeding this candidate label and the (still unverified) lbl(r) into hash_inner yields a candidate label for p. The client can now compare the candidate label for p against the actual lbl(p) that it received and verified earlier in the stream. If they are equal, then both the received chunk and the received lbl(r) are successfully verified.

If l is an inner vertex, then the stream continues with the labels of the left and right children of l. These can be fed into hash_inner to recover a (still unverified) candidate label of l. The client can then perform the same verification steps as in the first case, leading to verification of both the labels of the children of l, and of lbl(r).

When omitting the label of a leaf vertex l, the verification delay increases99Remember our assumption that $chunk\_size\ge 2\cdot width\text{.}$ by width. But when l is an inner vertex, an unverifiable sequence of length $2\cdot width$ is turned into an unverifiable sequence of length $3\cdot width\text{.}$ If $chunk\_size\ge 3\cdot width\text{,}$ then the verification delay remains unchanged — despite omitting width many bytes from the verification stream!

Moreover, we can omit successive left labels from the baseline verifiable stream by iterating the reconstruction of the labels. For each successively omitted left label, the corresponding right label needs to be buffered in an unverified state. Figure 5 shows the stream when omitting all left labels except those that are labels of leaf vertices for the hello_world example (that is, omitting the labels of vertices $2$ and $3\text{):}$

111010The length of the original string in bytes., lbl(9), lbl(6), lbl(4), lbl(5), he, ll, lbl(7), lbl(8), o_, wo, lbl(10), lbl(11), rl, d.

Below, you can step through the verification process. Step 4 demonstrates the cascading verification of several buffered, unverified right labels.