Does the Blake3 hash have identities, due to its merkle tree structure?

Question

I've read that the Blake3 hash uses a Merkle Tree.

Does it follow that there are identities such as:

b3sum("This is ") xor b3sum("a test.") == b3sum("This is a test.")

The example above does not work, perhaps because the block size is not eight bytes.

Are there any real Blake3 identities of a similar form?

Answer 1

No, any simple identity like that would violate the cryptographic properties that BLAKE3 aims to have. Finding these cases is supposed to require a brute force search.

BLAKE3 is a Merkle tree, but it isn't constructed by XORing things together. Instead, parent nodes in the tree are constructed by concatenating the hashes ("chaining values") of each child, and then calling the compression function again with that concatenation as the input. Other important details are that the compression function domain-separates chunk/leaf outputs from parent node outputs, and that it domain-separates the root node from non-root nodes. (As an aside, it also domain-separates each chunk/leaf based on its index. That's not necessary for the security property we're talking about here, but it accomplishes other things. See section 7.5 of the BLAKE3 paper.) Putting all that together, it should be difficult to find any relationship between the BLAKE3 hashes of any two distinct inputs.

Answer 2

Blake3 and all Blake series are based on the HAIFA construction which is proposed to improve the MD construction. Blake3 is using a binary tree^* structure to achieve an unbounded degree of parallelization. It has a built-in extendable output function (XOF) mode.

On the security side, the Blake3 targets 128-bit security for pre-image, secondary pre-image, collision, and differentiability attacks. The target 128-bit rationality is given by Atighehchi and Rolland in Optimization of tree modes for parallel hash functions: A case study.

---

• So if the question is; can we find pairs of string $(x,y)$ such that

  $$\operatorname{Blake3}(x) \oplus \operatorname{Blake3}(y) = \operatorname{Blake3}(x||y) \label{eq}\tag{1}$$

  The security of the Blake3, like any hash function, is limited by the output size. If the output size is small, one can easily find $(x,y)$ pairs satisfy the equation \ref{eq}.

  Now, consider that we have full 128-bit security, can we use the binary (Merkle) tree structure of Blake3 to construct such a pair?

  The short answer is no! We don't expect such weakness in the Blake3 design. The design of the Blake series combined the tools from the HAIFA and the countermeasure of the problem of the Merkle trees. The compression function deviates for each location by

  • The input chaining value, $h_0, \ldots h_7$ (256 bits)
  • The message block, $m_0 \ldots m_{15}$ (512 bits)
  • A 64-bit counter, $t = t_0, t_1$, with $t_0$ the lower order word and $t_1$ the higher order word.
  • The number of input bytes in the block, $b$ (32 bits).
  • A set of domain separation bit flags, $d$ (32 bits).

  The domain separation of the compression function is necessary for security; the flags are

  • Necessary flags
    • ROOT
    • CHUNK_START
  • Not strictly necessary but put for conversation design
    • PARENT
    • CHUNK_END

---

• If the question is; Can we use the Blake3 for file transfer ( streaming files)?

  The answer is yes. Squeamish Ossifrage wrote an extensive answer for using the Merkle Tree and the bao library already implement this with Blake3.

---

_{^*Although the question says Merkle-Tree, the paper just says a binary tree, so I've kept that}