Repository navigation
Proposal: a multi-buffer (multi-message) hashing trait for parallel independent digests #2478
Description
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 bycipher) is the closest structural match — "process LANES units at once + scalar tail," viaencrypt_par_blocks/encrypt_tail_blocksoverinout::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_blocksis 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 tailC — 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
- Does a multi-message hashing trait belong in
digest(orcrypto-common, or a new crate), or would you prefer inherent batch methods on individual hashes rather than a shared trait? - Width as a
typenumassociated type (type Lanes: ArraySize, matchingParBlocksSize) vs kept internal with runtimecpufeaturesdispatch (matching howsha2selects backends)? These two precedents point in different directions here. - Is a one-shot, equal-length primitive an acceptable MVP, or do you want the general (unequal-length / streaming) shape from the start?
- I/O convention: caller-provided output slice (à la
inout/InOutBuf), and should inputs reuseInOutBufor just&[&[u8]]? - Naming:
MultiDigest+Lanes(deliberately avoidingPar*, 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.
Activity
tarcieri commentedon Jul 31, 2026
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:
digestthough it already has perhaps too many traits.inoutis necessary versus a mut slice.newpavlov commentedon Jul 31, 2026
I am fine with the suggested addition as well. I think we could expose hasher backends similarly to what we have in
cipherand 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.digest.cipher.inouthere, plain slices and (hybrid) arrays should be sufficient.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 withsha2). The method would panic if messages do not have equal length and ifmessages.len() != hashes_dst.len().npmccallum commentedon Aug 3, 2026
Opened #2479 with a strawman for these traits (traits only; no algorithm implementation).
It lands as design B from above — a backend plus a lane-count-hiding core, mirroring
cipher'sParBlocks— with two adjustments that came out of building a full SHA-2 implementation against it:updatetakes whole blocks so the bulk of a message is absorbed with no copy (important fortag ‖ payloadinputs like Merkle leaves); onlyfinalizetakes the sub-block tail.[&[u8; N]; MSGS]), so unequal lengths fail to compile and the API stays infallible, matchingDigest.Static-dispatch backends per your and @newpavlov's guidance, with the core selecting one at run time so a new instruction set is a new backend rather than a trait change. Output is caller-provided; no
inout.Open questions (trait count, update/finalize split, naming, and whether a byte-buffering convenience belongs here or in an impl crate) are listed in the PR description. Details and numbers there.
newpavlov commentedon Aug 3, 2026
Do you need incremental multi-buffer hashing or could we start with one-shot multi-message hashing using an inherent method as I suggested above? I think we could postpone addition of traits for this functionality until it will be implemented in at least 2-3 crates.
Using
tails: &[&[u8; TAIL]; MSGS]for finalization seems to be unnecessarily restrictive and block-oriented API is likely to be somewhat inconvenient to use. Your LLM-generated PR also did not use the backend trick implemented incipherwhich is important when we perform backend selection at runtime.npmccallum commentedon Aug 8, 2026
@newpavlov I replied to this comment on the PR. Could we move discussion there?