Proposal: a multi-buffer (multi-message) hashing trait for parallel independent digests

[npmccallum]

The core primitive

We'd like to add a first-class abstraction for hashing N independent messages at once, so an implementation can place one message per SIMD lane and run the compression function across all lanes simultaneously:

Given N independent byte messages, produce their N digests in a single call.

This is the classic "multi-buffer" SHA construction (Gueron–Krasnov, Intel isa-l sha512_mb/sha256_mb). It exploits the fact that the round function has no cross-message dependency, even though it's fully serial within one message — so it's a different axis of parallelism from everything RustCrypto has today.

Why it's missing today (prior art)

As far as we can tell this capability doesn't exist anywhere in RustCrypto, and the existing parallelism is all a different axis:

• ParBlocksSizeUser / ParBlocks (crypto-common, used by cipher) is the closest structural match — "process LANES units at once + scalar tail," via encrypt_par_blocks/encrypt_tail_blocks over inout::InOutBuf. But it means multiple blocks of one stream, not independent messages.
• BLAKE2bp/sp, BLAKE3 tree mode, the sha2 AVX2 backend (elliptic-curve v0.6.4 #327) are all single-message internal SIMD.
• The hashing core API (digest/src/block_api.rs) has no par-blocks concept; update_blocks is serial over one message.

So this would be a genuinely new capability on the hashing side, ideally borrowing the cipher-side conventions.

Motivating use case

Parallel Merkle-tree leaf hashing: the leaves are independent, equal-length messages — the ideal multi-buffer workload. (Our concrete driver is a parallel, order-independent launch-measurement for AMD SEV-SNP confidential VMs, but the primitive is general: tree/dedup/storage/packet hashing all want it.) On AMD in particular, SHA-384/512 has no hardware engine, so multi-buffer is the only way to use the SIMD datapath — and it's substantial on the Zen 5 / Turin native 512-bit path.

Design options

A — High-level one-shot trait on top of Digest, runtime dispatch internal (sha2-style):

pub trait MultiDigest: Digest {
    fn digest_many(msgs: &[&[u8]], out: &mut [Output<Self>]); // impl detects avx2/avx512, chunks internally
}

B — Backend + driver split mirroring cipher's ParBlocks (compile-time width):

pub trait MultiDigestBackend: OutputSizeUser {
    type Lanes: ArraySize;                       // typenum, like ParBlocksSize
    fn digest_lanes(msgs: &Array<&[u8], Lanes>, out: &mut Array<Output<Self>, Lanes>);
    fn digest_tail(..); // len < Lanes
}
// + a driver that splits into Lanes-chunks then a scalar tail

C — Streaming multi-lane context (isa-l manager-style): N independent incremental states with submit/flush, handling unequal-length messages that finish at different times. Most general, closest to isa-l, most complex.

	A: one-shot driver	B: backend + driver	C: streaming manager
Width representation	internal (runtime)	type Lanes: ArraySize	internal
ISA selection	runtime cpufeatures (like sha2)	compile-time / backend types (like cipher)	runtime
Unequal lengths	precondition: equal (scalar tail)	equal per chunk	fully general
Streaming/incremental	no (one-shot)	no	yes
Complexity to land	low	medium	high
Fidelity to existing precedent	sha2 dispatch	cipher ParBlocks	isa-l only

Open questions for @tarcieri

1. Does a multi-message hashing trait belong in digest (or crypto-common, or a new crate), or would you prefer inherent batch methods on individual hashes rather than a shared trait?
2. Width as a typenum associated type (type Lanes: ArraySize, matching ParBlocksSize) vs kept internal with runtime cpufeatures dispatch (matching how sha2 selects backends)? These two precedents point in different directions here.
3. Is a one-shot, equal-length primitive an acceptable MVP, or do you want the general (unequal-length / streaming) shape from the start?
4. I/O convention: caller-provided output slice (à la inout/InOutBuf), and should inputs reuse InOutBuf or just &[&[u8]]?
5. Naming: MultiDigest + Lanes (deliberately avoiding Par*, which already means intra-message)?

Happy to prototype whichever direction you prefer — we have a multi-buffer SHA-512/384 (AVX2 4-lane, AVX-512 8-lane) ready to shape to your guidance, with all SHA-2 variants to follow.

[tarcieri]

The general idea makes sense to me. We just went through something similar with APIs for parallel multi-state keccak, and I'm sure @newpavlov has opinions there.

To answer your questions:

1. I think the traits can go in digest though it already has perhaps too many traits.
2. We've generally gone static dispatch in the past but it would be more flexible if it were dynamic and could potentially take advantage of more families SIMD instructions (e.g. SVE). Perhaps we could look at examples for both alternatives before choosing.
3. One shot equal length sounds not too far off from multi-state Keccak, though perhaps the trait itself could be futureproof.
4. A caller-provided output sounds good to me so as to simplify allocations. Not sure inout is necessary versus a mut slice.
5. Sounds fine to me. I think even a strawman PR would be helpful for discussion.

[newpavlov]

I am fine with the suggested addition as well. I think we could expose hasher backends similarly to what we have in cipher and expose the parallel processing capability as part of it. It also could be useful for cases where we want to hash a lot of different small messages and do not want to have the feature detection branch on each hashing.

1. I think it should be part of digest.
2. Explicit backend API should probably mirror cipher.
3. One-shot API would be simpler and we could start with it. A more general API would have to deal with a separate state type and associated traits.
4. I don't think we need inout here, plain slices and (hybrid) arrays should be sufficient.
5. We can leave name bikeshedding for after we got a rough draft of new APIs.

As a simpler alternative we could start with inherent methods like fn multi_digest(messages: &[&[u8]], hashes_dst: &mut [Output<Self>]) in relevant implementation crates (starting with sha2). The method would panic if messages do not have equal length and if messages.len() != hashes_dst.len().