[CFRG] Re: BLAKE3 I-D

[Christopher Patton <[e-mail]>]

> The main difference between B3 and K12 in this case is that, while both
> make extensive use of SIMD parallelism, only b3sum is multithreaded.
> k12sum could use multithreading in theory, but in practice I'm not aware
> of any multithreaded implementations of K12. The difference in tree
> structures is important: B3 is a binary tree with the usual recursive
> structure, which lets us use "divide-and-conquer" / "fork-join" parallelism
> of the sort provided by OpenMP in C/C++ or Rayon in Rust. K12 has a
> shallow/one-parent structure, which would need some sort of job queue with
> more synchronization and tuning, and the root note itself can be a
> bottleneck. (TurboSHAKE has a serial structure and can't take much
> advantage of SIMD or threads, which is a major performance disadvantage on
> modern machines.)
>

For my own edification, what applications benefit from the tree structure?
Does this create overhead if you are only hashing with a single thread?


> The B3 XOF is counter-based, similar to ChaCha or AES-CTR, which makes it
> parallelizable and suitable as a stream cipher or a high-performance
> CSPRNG. K12 and TurboSHAKE use a sponge-style XOF that isn't parallelizable.
>

This seems valuable, but I wonder if it limits how one might use BLAKE3.
Would you recommend BLAKE3 for instantiating random oracles?

Chris P.