[CFRG] Re: BLAKE3 I-D

[Jack O'Connor <[e-mail]>]

Update: Those SIMD optimizations (AVX-512-only, Unix-only) have now been
published as v1.5.4 of the `blake3` crate. Here's the before and after on
my laptop.

Master but with the new optimizations commented out
<https://gist.github.com/oconnor663/4183a403cc09974aa03046ead42dffe3>:
$ cargo +nightly bench xof
...
test bench_xof_01_block                ... bench:          40.68 ns/iter
(+/- 1.74) = 1600 MB/s
test bench_xof_02_blocks               ... bench:          77.85 ns/iter
(+/- 3.37) = 1662 MB/s
test bench_xof_04_blocks               ... bench:         152.42 ns/iter
(+/- 3.35) = 1684 MB/s
test bench_xof_08_blocks               ... bench:         300.24 ns/iter
(+/- 3.17) = 1706 MB/s
test bench_xof_16_blocks               ... bench:         598.23 ns/iter
(+/- 5.45) = 1712 MB/s
test bench_xof_32_blocks               ... bench:       1,194.53 ns/iter
(+/- 119.65) = 1715 MB/s
test bench_xof_64_blocks               ... bench:       2,379.19 ns/iter
(+/- 13.14) = 1721 MB/s

v1.5.4 <https://crates.io/crates/blake3/1.5.4>:
$ cargo +nightly bench xof
...
test bench_xof_01_block                ... bench:          40.95 ns/iter
(+/- 4.41) = 1600 MB/s
test bench_xof_02_blocks               ... bench:          47.62 ns/iter
(+/- 1.04) = 2723 MB/s
test bench_xof_04_blocks               ... bench:          49.32 ns/iter
(+/- 1.78) = 5224 MB/s
test bench_xof_08_blocks               ... bench:          93.44 ns/iter
(+/- 3.44) = 5505 MB/s
test bench_xof_16_blocks               ... bench:         119.09 ns/iter
(+/- 8.88) = 8605 MB/s
test bench_xof_32_blocks               ... bench:         235.22 ns/iter
(+/- 3.97) = 8714 MB/s
test bench_xof_64_blocks               ... bench:         468.84 ns/iter
(+/- 26.65) = 8752 MB/s

If you happen to have an AVX-512-supporting machine, I'd be curious to see
if your benchmarks improve.

On Thu, Aug 15, 2024 at 4:33 PM Jack O'Connor <[e-mail]> wrote:

> I'm slightly embarrassed to report that our XOF implementation is slower
> than it should be. It should benefit from all the same SIMD optimizations
> as the input side, but our current assembly implementations only
> parallelize input, and the XOF uses a slower codepath with less
> parallelism. Concretely on a CPU with AVX-512 support, for outputs longer
> than 1 KiB or so, it should be ~5x faster than it is. (Not as fast as
> hardware-accelerated AES-CTR though.)
>
> If you do have an AVX-512 Linux machine, and you want to benchmark the
> properly optimized XOF, it's currently on this branch:
> https://github.com/BLAKE3-team/BLAKE3/tree/xof_integration_rebase. I've
> been dragging my feet on shipping that, but I should go ahead and push it
> out, even though it doesn't cover all our target platforms.
>
> On Thu, Aug 15, 2024 at 2:06 PM Christopher Patton <[e-mail]>
> wrote:
>
>> Hi all,
>>
>> Before adopting BLAKE3, I think it would be useful to see how much of a
>> difference it would make in our applications. I would suggest looking
>> through RFCs published by CFRG and assess how performance would change if
>> they could have used BLAKE3. Off the top of my head:
>> - RFC 9180 - HPKE (replace HKDF?)
>> - draft-irtf-cfrg-opaque - OPAQUE
>> - RFC 9380 - hashing to elliptic curves
>>
>> I'll add my own data point: draft-irtf-cfrg-vdaf. This draft specifies an
>> incremental distributed point function (IDPF), a type of function secret
>> sharing used in some MPC protocols. Most of the computation is spent on XOF
>> evaluation. For performance reasons, we try to use AES wherever we can in
>> order to get hardware support. We end up with a mix of TurboSHAKE128 and
>> AES, which is not ideal. It would be much nicer if we could afford to use a
>> dedicated XOF, but TurboSHAKE128 is not fast enough in software. I threw
>> together some benchmarks for B3:
>>
>> https://github.com/cjpatton/libprio-rs/compare/main...cjpatton:libprio-rs:exp/blake3-for-idpf?expand=1
>>
>> The results were interesting. Compared to Turbo, B3 is 30% faster, as
>> expected. Compared to the baseline (mix of Turbo and AES), B3 is 2-3x
>> slower for the client operation, as expected; but the server was slightly
>> faster, which frankly is a bit of a mystery. We'll need to dig into the
>> code more to be certain, as there may be some obvious inefficiencies on the
>> client side. But preliminarily, I would say B3 is probably too slow in
>> software for this application.
>>
>> Chris P.
>>
>>
>>
>>
>>