Low-level tree manipulations and other sharp tools

The target audience for this module is projects like Bao, which work directly with the interior hashes ("chaining values") of BLAKE3 chunks and subtrees. For example, you could use these functions to implement a BitTorrent-like protocol using the BLAKE3 tree structure, or to hash an input that's distributed across different machines. These use cases are advanced, and most applications don't need this module. Also:

On the other hand:

The main entrypoint for this module is the HasherExt trait, particularly the set_input_offset and finalize_non_root methods. These let you compute the chaining values of individual chunks or subtrees. You then combine these chaining values into larger subtrees using merge_subtrees_non_root and finally (once at the very top) merge_subtrees_root or merge_subtrees_root_xof.

Examples

Here's an example of computing all the interior hashes in a 3-chunk tree:

           root
         /      \
     parent      \
   /       \      \
chunk0  chunk1  chunk2

# fn main() {
use blake3::{Hasher, CHUNK_LEN};
use blake3::hazmat::{merge_subtrees_non_root, merge_subtrees_root, Mode};
use blake3::hazmat::HasherExt; // an extension trait for Hasher

let chunk0 = [b'a'; CHUNK_LEN];
let chunk1 = [b'b'; CHUNK_LEN];
let chunk2 = [b'c'; 42]; // The final chunk can be short.

// Compute the non-root hashes ("chaining values") of all three chunks. Chunks or subtrees
// that don't begin at the start of the input use `set_input_offset` to say where they begin.
let chunk0_cv = Hasher::new()
    // .set_input_offset(0) is the default.
    .update(&chunk0)
    .finalize_non_root();
let chunk1_cv = Hasher::new()
    .set_input_offset(CHUNK_LEN as u64)
    .update(&chunk1)
    .finalize_non_root();
let chunk2_cv = Hasher::new()
    .set_input_offset(2 * CHUNK_LEN as u64)
    .update(&chunk2)
    .finalize_non_root();

// Join the first two chunks with a non-root parent node and compute its chaining value.
let parent_cv = merge_subtrees_non_root(&chunk0_cv, &chunk1_cv, Mode::Hash);

// Join that parent node and the third chunk with a root parent node and compute the hash.
let root_hash = merge_subtrees_root(&parent_cv, &chunk2_cv, Mode::Hash);

// Double check that we got the right answer.
let mut combined_input = Vec::new();
combined_input.extend_from_slice(&chunk0);
combined_input.extend_from_slice(&chunk1);
combined_input.extend_from_slice(&chunk2);
assert_eq!(root_hash, blake3::hash(&combined_input));
# }

Hashing many chunks together is important for performance, because it allows the implementation to use SIMD parallelism internally. (AVX-512 for example needs 16 chunks to really get going.) We can reproduce parent_cv by hashing chunk0 and chunk1 at the same time:

# fn main() {
# use blake3::{Hasher, CHUNK_LEN};
# use blake3::hazmat::{Mode, HasherExt, merge_subtrees_non_root, merge_subtrees_root};
# let chunk0 = [b'a'; CHUNK_LEN];
# let chunk1 = [b'b'; CHUNK_LEN];
# let chunk0_cv = Hasher::new().update(&chunk0).finalize_non_root();
# let chunk1_cv = Hasher::new().set_input_offset(CHUNK_LEN as u64).update(&chunk1).finalize_non_root();
# let parent_cv = merge_subtrees_non_root(&chunk0_cv, &chunk1_cv, Mode::Hash);
# let mut combined_input = Vec::new();
# combined_input.extend_from_slice(&chunk0);
# combined_input.extend_from_slice(&chunk1);
let left_subtree_cv = Hasher::new()
    // .set_input_offset(0) is the default.
    .update(&combined_input[..2 * CHUNK_LEN])
    .finalize_non_root();
assert_eq!(left_subtree_cv, parent_cv);

// Using multiple updates gives the same answer, though it's not as efficient.
let mut subtree_hasher = Hasher::new();
// Again, .set_input_offset(0) is the default.
subtree_hasher.update(&chunk0);
subtree_hasher.update(&chunk1);
assert_eq!(left_subtree_cv, subtree_hasher.finalize_non_root());
# }

However, hashing multiple chunks together must respect the overall tree structure. Hashing chunk0 and chunk1 together is valid, but hashing chunk1 and chunk2 together is incorrect and gives a garbage result that will never match a standard BLAKE3 hash. The implementation includes a few best-effort asserts to catch some of these mistakes, but these checks aren't guaranteed. For example, this second call to update currently panics:

# fn main() {
# use blake3::{Hasher, CHUNK_LEN};
# use blake3::hazmat::HasherExt;
# let chunk0 = [b'a'; CHUNK_LEN];
# let chunk1 = [b'b'; CHUNK_LEN];
# let chunk2 = [b'c'; 42];
let oops = Hasher::new()
    .set_input_offset(CHUNK_LEN as u64)
    .update(&chunk1)
    // PANIC: "the subtree starting at 1024 contains at most 1024 bytes"
    .update(&chunk2)
    .finalize_non_root();
# }

For more on valid tree structures, see the docs for and left_subtree_len and max_subtree_len, and see section 2.1 of the BLAKE3 paper. Note that the merging functions (merge_subtrees_root and friends) don't know the shape of the left and right subtrees you're giving them, and they can't help you catch mistakes. The best way to catch mistakes with these is to compare your root output to the blake3::hash of the same input.