[CFRG] Re: BLAKE3 I-D

[Jean-Philippe Aumasson <[e-mail]>]

Hey Chris, all

Thanks for following up, please see my answers below:

On Wed 14 Aug 2024 at 13:35 Christopher Patton <[e-mail]>
wrote:

>
>
>> 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?
>

Essentially all apps where you hash more than a handful KBs, be it bare
metal or via vCPUs. With a single-thread B3 still parallelizes at the
instruction level via SIMD instructions. Single-threading incurs minimal
overhead, and in this case B3's performance remains superior to standard
crypto hash functions.


>
>> 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?
>


Yes B3's construction is indifferentiable from an RO, making it suitable to
instantiate ROs as much as SHA3.

>
We (B3 team) will be happy to answer any questions regarding B3's design
and performance, and how they compare to K12. However, we should try to
avoid a prolonged  "K12 vs B3" debate that would be unproductive for
everyone involved. Regardless of K12's (and other Keccak family members')
undeniable merits, our goal with this submission is to meet the needs of
the organizations and projects that wish to use B3 but require some formal
validation (typically for compliance reasons or other red tape situations).
For example, we're regularly asked when B3 will make it into OpenSSL but it
seems that it will be challenging without some formal standardization of
the specs.

As Jack pointed out, a number of prominent projects already integrated B3,
to benefit from its performance and production-ready software. A tremendous
amount of work was done by Jack and Samuel to create and maintain reliable
and efficient code in https://github.com/BLAKE3-team/BLAKE3, a repo now
with 5k+ stars. We believe that, more than our technical arguments in favor
of B3, its popularity among users speaks for itself.

(re-adding Samuel to the thread)


>