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

Inizia leggendo digest/src/block_api.rs e confrontando le convenzioni di crypto-common per ParBlocks con l’implementazione di cipher e il dispatch del backend sha2 a cui si fa riferimento nell’issue. Esamina le tre forme di API proposte e le questioni aperte prima di proporre una direzione. Il lavoro è concluso quando i maintainer concordano sul crate, sull’API, sulla rappresentazione delle lane e sull’ambito dell’MVP; non è ancora stato selezionato alcun design.

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 (#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.

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.