Link preview
Aljoscha Meyer
BabIntroductionThe Bab Hash FunctionParametersThe Merkle TreeInstantiationsVia Conventional Hash FunctionsWILLIAM3Design RationaleStreaming VerificationSlice VerificationLength VerificationThe is_root FlagNo Chunk IndicesThe Binary TreeParameterized Chunk SizeOptimized Streaming VerificationUnverifiable SequencesOmitting Left LabelsOmitting Lower LayersSlice StreamingConclusionAcknowledgementsReferencesAljoscha Meyerhttps://github.com/worm-blossom/babBab is a family of secure hash functions, heavily inspired by BLAKE3. Bab hashes allow for streaming verification of strings, similar to the BLAKE3-based Bao algorithm. We discuss several optimization techniques that go beyond the Bao specification. Further, unlike BLAKE3 and Bao, Bab digests allow for constant-sized length proofs of their strings.1 IntroductionContent-addressable storage lets users refer to strings (files) by a secure hash. Bab is a specification for a hash function specifically designed for usage in peer-to-peer content-addressable storage systems.The key feature of Bab is streaming verification of a string: as a program reads a string, it can verify at regular intervals that the prefix read so far is indeed part of a string hashing to some target digest. Content-addressed storage systems without this feature face a problem in byzantine environments. Suppose a client requests the string corresponding to some digest. The server replies with some data, but the connection is interrupted before the full string was transfered. What should the client do?It could store the data it received, and could later issue a request for the same string, resuming at the correct offset. But that request will fail if the orginal server fed it garbage, and the client will be unable to tell which of its two communication partners acted maliciously. Further, the server might have sent it data that is illegal to store. Hence, a careful client should not persist incomplete data. But this makes it unlikely to successfully receive large strings over an unreliable network.When strings are hashed with Bab, servers can embed into the data stream small proofs that the data they sent so far is indeed prefixing the requested string. More specifically, Bab enables the following features (all explained in detail in Section 3):secure content-addressing,incremental verification of streaming string data,efficient verification of arbitrary subslices within a string, andconstant-size length proofs for strings.While we explore Bab in the context of hashing, you can also think of it as an authenticated data structure (Tamassia, 2003) for arrays.Bab employs many of the same techniques as the BLAKE3-based (O’Connor et al., 2020) Bao specification. Key differences are short proofs of string length, more efficient slice requests, and a hash-function-agnostic specification. Bao is a byproduct of a well-designed general-purpose hash function, whereas Bab is a family of special-purpose hash functions that gets to add features beyond Bao’s capabilities.We define Bab in Section 2, before explaining and justifying the design in Section 3, both from a high-level view and in its details. We examine optimizations for verified streaming in Section 4.2 The Bab Hash FunctionLike BLAKE3, Bab hashes an input string by splitting it into chunks, and arranging the chunks as the roots of a deterministically constructed, binary Merkle-tree; the label of the root becomes the digest of the input.2.1 ParametersBab 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 264−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 264−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.2.2 The Merkle TreeTo 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.Figure 1: Unlabeled Example TreeThe (unlabeled) binary tree for the input string hello_world with a chunk_size of 2.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, ⊤) if c is the only chunk in chunks, and hash_chunk(c, ⊥), 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 ⊤ if v is the root of the tree and ⊥ otherwise. Then lbl(v) is hash_inner(left, right, len, is_root).Figure 2 demonstrates the label computation in the example Merkle-tree:Figure 2: Labeled Example TreeThe label computations for the example tree from Figure 1.2.3 InstantiationsThe 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 FunctionsGiven a conventional, secure hash function h of digest size w, we can instantiate Bab for a width of w and an arbitrary chunk_size.Define hash_chunk(chunk, is_root) as applying h to the concatenation ofchunk, andthe byte 0x00 if is_root is false, or the byte 0x01 otherwise.Define hash_inner(left, right, len, is_root) as applying h to the concatenation ofleft,right.len encoded as an unsigned big-endian 64-bit integer, andthe byte 0x02 if is_root is false, or the byte 0x03 otherwise.2.3.2 WILLIAM3WILLIAM3 is a Bab instantiation that is almost identical to BLAKE3. There are three differences: first, WILLIAM3 does not supply chunk indices into the label computation for chunks. Second, WILLIAM3 incorporates a length value into the label computation of inner tree vertices. And third, WILLIAM3 uses different constants IV0,…,IV7 than BLAKE3. WILLIAM3 has a normal hash mode and a keyed hash mode (based on a 256 bit key, by setting the key words k0 to k7 to the key just like BLAKE3); unlike BLAKE3 it does not support a key derivation mode, and it does not allow for extendable output.WILLIAM3 uses a chunk_size of 1024 bytes (just like BLAKE3). Its width is 32 bytes (just like BLAKE3).Where BLAKE3 uses its constants IV0,…,IV7, WILLIAM3 uses the following constants instead:The constants form the BLAKE3 digest of the ASCII-encoded string WILLIAM3.Using diferent constants than BLAKE3 ensures that BLAKE3 and WILLIAM3 produce non-equal digests for equal inputs, even if the inputs fit into a single chunk.IV0: 0xc88f633bIV1: 0x4168fbf2IV2: 0x6ba32583IV3: 0xb0ff1847IV4: 0xac57e47dIV5: 0xa8931330IV6: 0x796a4645IV7: 0x6b28a3eeThe hash_chunk function is almost identical to the BLAKE3 computation of chunk chaining values, with a single exceptionExplained in Section 3.5. (beyond the changed IV0,…,IV7 constants): where BLAKE3 sets the t parameter of its compression function to the chunk index, WILLIAM3 sets it to 0.The hash_inner function is almost identical to the BLAKE3 computation of parent node chaining values, with a single exceptionExplained in Section 3.3. (beyond the changed IV0,…,IV7 constants): whereas BLAKE3 sets the t parameter of its compression function to 0, WILLIAM3 sets t to the third argument (the length value) of hash_chunk (as an unsigned little-endian 64-bit integer).3 Design RationaleWe now explain the decisions that went into the definition of Bab.Bab is heavily based off BLAKE3 and Bao, so many of these rationales are restating the design work that went into BLAKE3 and Bao. Compared to those two, only little creativity went into the design of Bab.3.1 Streaming VerificationUsing 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… bab-hash.org · aljoscha-meyer.de
BabIntroductionThe Bab Hash FunctionParametersThe Merkle TreeInstantiationsVia Conventional Hash FunctionsWILLIAM3Design RationaleStreaming VerificationSlice VerificationLength VerificationThe is_root FlagNo Chunk IndicesThe Binary TreeParameterized Chunk SizeOptimized Streaming VerificationUnverifiable SequencesOmitting Left LabelsOmitting Lower LayersSlice StreamingConclusionAcknowledgementsReferencesAljoscha Meyerhttps://github.com/worm-blossom/babBab is a family of secure hash functions, heavily inspired by BLAKE3. Bab hashes allow for streaming verification of strings, similar to the BLAKE3-based Bao algorithm. We discuss several optimization techniques that go beyond the Bao specification. Further, unlike BLAKE3 and Bao, Bab digests allow for constant-sized length proofs of their strings.1 IntroductionContent-addressable storage lets users refer to strings (files) by a secure hash. Bab is a specification for a hash function specifically designed for usage in peer-to-peer content-addressable storage systems.The key feature of Bab is streaming verification of a string: as a program reads a string, it can verify at regular intervals that the prefix read so far is indeed part of a string hashing to some target digest. Content-addressed storage systems without this feature face a problem in byzantine environments. Suppose a client requests the string corresponding to some digest. The server replies with some data, but the connection is interrupted before the full string was transfered. What should the client do?It could store the data it received, and could later issue a request for the same string, resuming at the correct offset. But that request will fail if the orginal server fed it garbage, and the client will be unable to tell which of its two communication partners acted maliciously. Further, the server might have sent it data that is illegal to store. Hence, a careful client should not persist incomplete data. But this makes it unlikely to successfully receive large strings over an unreliable network.When strings are hashed with Bab, servers can embed into the data stream small proofs that the data they sent so far is indeed prefixing the requested string. More specifically, Bab enables the following features (all explained in detail in Section 3):secure content-addressing,incremental verification of streaming string data,efficient verification of arbitrary subslices within a string, andconstant-size length proofs for strings.While we explore Bab in the context of hashing, you can also think of it as an authenticated data structure (Tamassia, 2003) for arrays.Bab employs many of the same techniques as the BLAKE3-based (O’Connor et al., 2020) Bao specification. Key differences are short proofs of string length, more efficient slice requests, and a hash-function-agnostic specification. Bao is a byproduct of a well-designed general-purpose hash function, whereas Bab is a family of special-purpose hash functions that gets to add features beyond Bao’s capabilities.We define Bab in Section 2, before explaining and justifying the design in Section 3, both from a high-level view and in its details. We examine optimizations for verified streaming in Section 4.2 The Bab Hash FunctionLike BLAKE3, Bab hashes an input string by splitting it into chunks, and arranging the chunks as the roots of a deterministically constructed, binary Merkle-tree; the label of the root becomes the digest of the input.2.1 ParametersBab 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 264−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 264−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.2.2 The Merkle TreeTo 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.Figure 1: Unlabeled Example TreeThe (unlabeled) binary tree for the input string hello_world with a chunk_size of 2.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, ⊤) if c is the only chunk in chunks, and hash_chunk(c, ⊥), 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 ⊤ if v is the root of the tree and ⊥ otherwise. Then lbl(v) is hash_inner(left, right, len, is_root).Figure 2 demonstrates the label computation in the example Merkle-tree:Figure 2: Labeled Example TreeThe label computations for the example tree from Figure 1.2.3 InstantiationsThe 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 FunctionsGiven a conventional, secure hash function h of digest size w, we can instantiate Bab for a width of w and an arbitrary chunk_size.Define hash_chunk(chunk, is_root) as applying h to the concatenation ofchunk, andthe byte 0x00 if is_root is false, or the byte 0x01 otherwise.Define hash_inner(left, right, len, is_root) as applying h to the concatenation ofleft,right.len encoded as an unsigned big-endian 64-bit integer, andthe byte 0x02 if is_root is false, or the byte 0x03 otherwise.2.3.2 WILLIAM3WILLIAM3 is a Bab instantiation that is almost identical to BLAKE3. There are three differences: first, WILLIAM3 does not supply chunk indices into the label computation for chunks. Second, WILLIAM3 incorporates a length value into the label computation of inner tree vertices. And third, WILLIAM3 uses different constants IV0,…,IV7 than BLAKE3. WILLIAM3 has a normal hash mode and a keyed hash mode (based on a 256 bit key, by setting the key words k0 to k7 to the key just like BLAKE3); unlike BLAKE3 it does not support a key derivation mode, and it does not allow for extendable output.WILLIAM3 uses a chunk_size of 1024 bytes (just like BLAKE3). Its width is 32 bytes (just like BLAKE3).Where BLAKE3 uses its constants IV0,…,IV7, WILLIAM3 uses the following constants instead:The constants form the BLAKE3 digest of the ASCII-encoded string WILLIAM3.Using diferent constants than BLAKE3 ensures that BLAKE3 and WILLIAM3 produce non-equal digests for equal inputs, even if the inputs fit into a single chunk.IV0: 0xc88f633bIV1: 0x4168fbf2IV2: 0x6ba32583IV3: 0xb0ff1847IV4: 0xac57e47dIV5: 0xa8931330IV6: 0x796a4645IV7: 0x6b28a3eeThe hash_chunk function is almost identical to the BLAKE3 computation of chunk chaining values, with a single exceptionExplained in Section 3.5. (beyond the changed IV0,…,IV7 constants): where BLAKE3 sets the t parameter of its compression function to the chunk index, WILLIAM3 sets it to 0.The hash_inner function is almost identical to the BLAKE3 computation of parent node chaining values, with a single exceptionExplained in Section 3.3. (beyond the changed IV0,…,IV7 constants): whereas BLAKE3 sets the t parameter of its compression function to 0, WILLIAM3 sets t to the third argument (the length value) of hash_chunk (as an unsigned little-endian 64-bit integer).3 Design RationaleWe now explain the decisions that went into the definition of Bab.Bab is heavily based off BLAKE3 and Bao, so many of these rationales are restating the design work that went into BLAKE3 and Bao. Compared to those two, only little creativity went into the design of Bab.3.1 Streaming VerificationUsing 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.Figure 3: Verifiable Streaming ExampleThe vertices of our recurring example tree, each showing the data that they contribute to the baseline verifiable stream that lets a client incrementally verify the digest of the string hello_world.Listing the vertices in the order in which they contribute their child labels or chunks is quite instructive: 1,2,3,4,5,6,7,8,9,10,11. Can you spot the pattern?The client can verify a stream by eagerly 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.Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(4)lbl(5)helllbl(7)lbl(8)o_wolbl(10)lbl(11)rld1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(3) = hash_chunk(lbl(4), lbl(5), 4, false)lbl(4) = hash_chunk(he, false)lbl(5) = hash_chunk(ll, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)lbl(11) = hash_chunk(d, false)3.2 Slice VerificationThe 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.Figure 4: Verifiable Slice Streaming ExampleThe vertices of our recurring example tree, each showing the data that they contribute to let a client incrementally verify the slice o_worl in the string hello_world.The list of vertices in the order in which they contribute their child labels or chunks has some gaps, but is still strictly ascending: 1,2,6,7,8,9,10.You can step through the verification process for this example below:Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)Previous StepNext Steplbl(2)lbl(9)lbl(3)lbl(6)lbl(7)lbl(8)o_wolbl(10)lbl(11)rl1293645hell78o_wo1011rldlbl(1) is trustedlbl(1) = hash_chunk(lbl(2), lbl(9), 11, true)lbl(2) = hash_chunk(lbl(3), lbl(6), 8, false)lbl(6) = hash_chunk(lbl(7), lbl(8), 4, false)lbl(7) = hash_chunk(o_, false)lbl(8) = hash_chunk(wo, false)lbl(9) = hash_chunk(lbl(10), lbl(11), 3, false)lbl(10) = hash_chunk(rl, false)3.3 Length VerificationA 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⋅2⋅32+1024=1160 bytes. The corresponding WILLIAM3 lenght proof, in comparison, requires 2⋅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.3.4 The is_root FlagBoth 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.3.5 No Chunk IndicesBLAKE3 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.3.6 The Binary TreeBinary 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,
Comments