3
$\begingroup$

In the BLAKE2 paper, the authors define

  • Maximal depth (1 byte): an integer in [1, 255] (set to 255 if unlimited, and to 1 only in sequential mode)
  • Node depth (1 byte): an integer in [0, 255] (set to 0 for the leaves, or in sequential mode)

Node depth is incremented as you approach the root node of the tree.

I was considering using BLAKE2b in tree mode with a fanout of 1 (e.g., a "unary" tree) for an iterated hashing scheme. The spec above says to set maximal depth to 255 for "unlimited" depth, but the node depth is only one byte so can only uniquely denote nodes in trees smaller than this depth.

First, is there a reasonable way to achieve arbitrarily-deep trees (e.g., on the order of 2^48 nodes deep) with BLAKE2b? And second, is this way preferable to some other approach?

Edit: One idea that comes to mind is to swap the interpretation of the node offset and node depth fields for the purpose of this scheme, since node offset would otherwise go unused (all trees in this scheme have an offset of 0), and it's a 64-bit value.

$\endgroup$
  • $\begingroup$ @CodesInChaos Any thoughts? I know you had a hand in BLAKE2. $\endgroup$ – Stephen Touset Oct 9 '13 at 22:26
  • $\begingroup$ We did not consider unary trees when designing the tree mode and I still don't get their point. Where is the difference between a sequential hash and a unary tree? $\endgroup$ – CodesInChaos Oct 10 '13 at 7:55
  • $\begingroup$ A unary tree mode allows me to use the node depth field to store the iteration counter (guaranteeing that all iterated calls to the hash function are unique). Otherwise I have to use bytes of the personalization field for this internal record keeping, which reduces the amount available for end-users of my scheme. $\endgroup$ – Stephen Touset Oct 10 '13 at 17:43
  • $\begingroup$ In this case, I'm trying to implement the Catena password hash with BLAKE2. BLAKE2 doesn't, AFACT, have a native way of giving me access to the intermediate hashes in sequential mode (calling blake2b_final to get the intermediate hash affects the internal state), which are necessary for implementing the memory-hardness of Catena. $\endgroup$ – Stephen Touset Oct 10 '13 at 18:22
  • $\begingroup$ I wanted to point out that you can memcpy an intermediate state and finalize one and put data into the other. This will give you a series of hashes from serial hashing $\endgroup$ – Kyle Butt Jun 26 '18 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.